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

Короткий ответ

Для построения маршрута из массива билетов в React нужно создать структуру данных, где каждый билет - объект с полями from и to. Используйте хеш-таблицу для быстрого поиска начальной точки маршрута (город, который не является пунктом назначения ни для одного билета). Затем последовательно проходите по билетам, начиная с найденного старта, и собирайте упорядоченный список. React-компонент отображает готовый маршрут после обработки данных.

Подробное объяснение

Задача сводится к восстановлению пути в ориентированном графе, где каждый билет - ребро. Массив билетов неупорядочен, поэтому нужно найти начальный город - тот, который встречается только как from, но не как to. Для этого строим два сета: всех городов отправления и всех городов назначения. Разность сетов даёт стартовую точку.

Далее используем хеш-таблицу (Map) для быстрого доступа к следующему билету по текущему городу. Проходим от старта до конца, пока не останется билетов. В React логику лучше вынести в хук useMemo, чтобы избежать повторных вычислений при ререндерах. Компонент получает массив билетов как пропс и отображает маршрут в виде списка или строки.

Важно учитывать edge cases: пустой массив, один билет, циклические маршруты (если они возможны по условию). Для production стоит добавить валидацию и обработку ошибок.

На практике

В реальном проекте данные о билетах часто приходят с сервера в виде JSON. Логику построения маршрута лучше изолировать в отдельный модуль или хук, чтобы её можно было переиспользовать и тестировать. Для оптимизации используйте useMemo с зависимостью от массива билетов.

Если билетов много (тысячи), алгоритм O(n) по времени и O(n) по памяти будет эффективен. Для отображения маршрута можно использовать компонент списка с key от индекса, так как порядок фиксирован после построения.

Пример кода

JSX
import { useMemo } from 'react';

function buildRoute(tickets) {
  if (!tickets.length) return [];

  const fromSet = new Set();
  const toSet = new Set();
  const ticketMap = new Map();

  tickets.forEach(({ from, to }) => {
    fromSet.add(from);
    toSet.add(to);
    ticketMap.set(from, to);
  });

  const start = [...fromSet].find(city => !toSet.has(city));
  if (!start) throw new Error('No valid start city found');

  const route = [];
  let current = start;
  while (current) {
    route.push(current);
    current = ticketMap.get(current);
  }
  return route;
}

function RouteDisplay({ tickets }) {
  const route = useMemo(() => buildRoute(tickets), [tickets]);

  if (!route.length) return <p>No tickets provided</p>;

  return (
    <ol>
      {route.map((city, index) => (
        <li key={index}>{city}</li>
      ))}
    </ol>
  );
}

Как отвечать на собеседовании

Начните с чёткого описания задачи: восстановление пути из неупорядоченных пар. Объясните выбор структуры данных (Map, Set) и алгоритм O(n). Упомяните, что в React логику выносите в useMemo для производительности. Покажите понимание edge cases: пустой массив, один билет, отсутствие старта. Если спросят про циклические маршруты, скажите, что по условию их быть не должно, но можно добавить проверку на бесконечный цикл.

Что проверяет интервьюер

• Умение работать с графами и хеш-таблицами
• Понимание React-оптимизаций (useMemo, мемоизация)
• Навыки обработки edge cases и валидации данных
• Способность писать чистый, переиспользуемый код
• Умение объяснять алгоритмические решения

Типичные ошибки

• Использование вложенных циклов (O(n²)) вместо хеш-таблицы
• Неправильное определение стартового города (проверка только по первому билету)
• Игнорирование пустого массива или одного билета
• Мутация исходного массива билетов
• Отсутствие обработки ошибок при отсутствии старта
• Создание новых массивов и объектов при каждом рендере без useMemo