Войти Регистрация
Алгоритмы

170. Маршрут из перемешанных билетов

Лёгкая

Дан список билетов tickets, каждый — [откуда, куда], и город start. Из каждого города отправляется не больше одного билета.

Начните в start и садитесь на билет из текущего города, пока такой есть и он ещё не использован. Верните использованные билеты по порядку.

Билеты, на которые с маршрута не попасть, в ответ не входят. Если из start билета нет — ответ пустой.

В работе: Яндекс Путешествия: заказ из нескольких перелётов приходит списком, а в приложении его показывают по порядку пересадок.

Пример 1

Ввод
tickets = [["Москва", "Бишкек"], ["Белгород", "Москва"], ["Бишкек", "Санкт-Петербург"]]
start = "Белгород"
Вывод
[["Белгород", "Москва"], ["Москва", "Бишкек"], ["Бишкек", "Санкт-Петербург"]]

Пример из задачи на собеседовании.

Пример 2

Ввод
tickets = [["Казань", "Сочи"], ["Сочи", "Казань"]]
start = "Сочи"
Вывод
[["Сочи", "Казань"], ["Казань", "Сочи"]]

Кольцо: второй раз билет из Сочи не используем.

Ограничения

  • 0 ≤ длина tickets ≤ 2·10⁵
  • Города — непустые строки, из каждого города не больше одного билета
  • Лимит — 2 с на тест (1500 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def build_route(tickets, start):
Хеш-таблицаСтрокицельO(n)

Источник: Яндекс, фронтенд, репозиторий кандидата на GitHub, 2024. Условие пересказано своими словами.