Как работает массив tickets в JavaScript
Что проверяют
Такой вопрос почти всегда вырастает из лайвкодинга, где дают массив tickets. Самая частая версия: билеты вида { from, to } перемешаны, и нужно восстановить маршрут. Проверяют знание методов массива, понимание, какие из них мутируют данные, и умение оценить сложность. Следом просят решение быстрее, чем за O(n²).
Как отвечать
Сначала база, её стоит коротко проговорить в любом варианте задачи:
- ссылочный тип: массив это объект.
const tickets = []запрещает переприсвоение, но неpush, а переданный в функцию массив меняется и у вызывающего кода; - мутирующие методы:
push,pop,shift,unshift,splice,sort,reverse.shiftиunshiftработают за O(n), потому что сдвигают все индексы; - немутирующие:
map,filter,reduce,slice,concat, а с ES2023 ещёtoSorted,toReversed,toSplicedиwith, копирующие аналоги мутирующих методов; sort()без компаратора сравнивает строки:[10, 9, 1].sort()даст[1, 10, 9], для чисел нужен(a, b) => a - b.
Для маршрута решение за линейное время строится на двух структурах. За один проход собираете Map, где ключ это город отправления, а значение билет, и Set всех пунктов назначения. Стартовая точка та, которой нет среди пунктов назначения. Дальше идёте по Map от старта, пока не наберёте tickets.length билетов. Выходит O(n) по времени и памяти вместо O(n²) у решения с find внутри цикла.
Проговорите пограничные случаи: пустой массив, разрыв в цепочке, повторный город. Уточните, гарантирован ли единственный маршрут, от этого зависит, нужна ли проверка.
Где спотыкаются
Пишут tickets.find(...) внутри цикла и не замечают квадратичную сложность. На десяти билетах разницы нет, на ста тысячах есть, и интервьюер спросит именно об этом.
Вызывают sort или splice прямо на входном массиве, не предупредив. Функция портит данные вызывающего кода, безопаснее toSorted или копия через spread.
Берут обычный объект вместо Map для ключей-городов и спотыкаются о ключ вроде constructor, унаследованный от прототипа. Map или Object.create(null) эту проблему снимают.