Как реализовать построение полного маршрута из массива билетов в React

Что проверяют

Прежде всего алгоритм: сможете ли вы собрать цепочку за линейное время, а не перебором. React здесь вторичен, и интервьюер смотрит, не потащите ли вы чистое вычисление в useEffect и состояние. Следом спросят, что делать с разорванной цепочкой или повторяющимися городами.

Как отвечать

Проговорите условие: каждый билет это { from, to }, города не повторяются, маршрут один. Тогда решение в три шага:

• индекс: Map из пункта отправления в билет и Set всех пунктов назначения, один проход, O(n);
• старт: город, который есть среди from, но отсутствует в множестве назначений. Такой должен быть ровно один;
• обход: от старта идёте по Map, пока есть следующий билет.

В конце сверьте длину: в маршруте должно оказаться tickets.length + 1 городов. Если меньше, билеты не складываются в одну цепочку, и об этом надо сообщить явно, а не вернуть обрывок. Если старта нет, маршрут замкнут в кольцо, и нужен дополнительный вход, например известный город вылета.

В React функция живёт отдельно от компонента, она чистая, и её легко покрыть тестами на Vitest или Jest. Компонент вычисляет маршрут во время рендера, при большом наборе через useMemo от tickets. Хранить результат в useState и синхронизировать через useEffect не нужно: это лишний рендер и шанс рассинхрона. В списке ключом берите идентификатор билета, а не индекс.

Если города могут повторяться (A→B, B→A, A→C), задача превращается в поиск эйлерова пути, его решают алгоритмом Хирхольцера. Упомянуть это полезно даже без кода.

Где спотыкаются

Ищут старт через includes по массиву значений внутри find. Получается O(n²) и копирование массива на каждой итерации.

Не проверяют связность. Для билетов A→B и C→D наивный обход вернёт ['A', 'B'] и молча потеряет половину данных, а тест, который «ожидает пустой массив», при этом никто не запускал.

Кладут вычисление в эффект и получают два рендера, мелькание пустого состояния и повторный запуск эффекта в StrictMode при разработке.