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

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

Видите ли вы, что find или filter внутри цикла дают квадратичную сложность, и умеете ли заменить повторные проходы индексом. Классическая форма: «дан неупорядоченный массив билетов { from, to }, восстановите маршрут». Следом спрашивают про сложность и про некорректные данные.

Как отвечать

Наивное решение на каждом шаге ищет следующий билет через tickets.find(t => t.from === current). Это полный проход массива на каждом из n шагов, итого O(n²).

Оптимизация в том, чтобы один раз построить индекс:

• Map по пункту отправления: new Map(tickets.map(t => [t.from, t])), дальше следующий билет достаётся за O(1);
• начальная точка: собрать Set всех пунктов назначения, старт это единственный from, которого там нет. Ещё один проход, O(n);
• сборка: идти от старта по Map, пока есть продолжение. Итог O(n) по времени и O(n) по памяти.

Объект вместо Map тоже сработает, но Map не смешивает ключи с прототипом и принимает ключи любого типа.

Та же идея работает и для других «маршрутов», если интервьюер имел в виду их:

• роутинг в SPA: статические пути кладутся в Map, а пути с параметрами вроде /users/:id в префиксное дерево по сегментам, и совпадение ищется за длину пути, а не перебором всех маршрутов;
• кратчайший путь на графе: список смежности вместо массива рёбер, BFS для графа без весов, Дейкстра с бинарной кучей для весов, A* при хорошей эвристике.

Уточнить у интервьюера постановку задачи само по себе плюс.

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

Сразу отвечают A* или Дейкстрой, не уточнив условие. В задаче про билеты граф это одна цепочка, и тяжёлый алгоритм только запутывает решение.

Не проверяют данные: цикл в билетах даёт бесконечный обход, а два билета из одного города молча перезапишут друг друга в Map. Нужны счётчик шагов и проверка на дубликаты.

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