Уильям Линь, школьник и международный гроссмейстер на Codeforces, прошел имитацию технического интервью Google с Клеманом Михайлеску. За 45 минут кандидат решил задачу Airport Connections, которую Клеман называет сложнейшей на платформе AlgoExpert .
🛫 Постановка задачи об авиалиниях 2:48
Кандидат выступает в роли владельца авиакомпании, которая должна обеспечить доступ ко всем аэропортам из единого центра . Входные данные включают три параметра:
- Список аэропортов (трехбуквенные коды, например, LGA, CDG).
- Список существующих односторонних маршрутов между ними.
- Начальный аэропорт (starting airport), который является штаб-квартирой .
Задача заключается в поиске минимального количества новых односторонних рейсов, которые нужно добавить. После их добавления пассажир должен иметь возможность долететь из начальной точки в любой аэропорт из списка . Прямые рейсы необязательны, допускается любое количество пересадок . В тестовом примере для обеспечения связности потребовалось добавить 3 новых маршрута .
📊 Графовая модель и сильно связанные компоненты 8:16
Уильям Линь сразу предложил рассматривать структуру аэропортов как ориентированный граф . Ключевой концепцией решения стали сильно связанные компоненты (SCC). Это группы узлов, внутри которых каждый аэропорт достижим из любого другого .
Логика оптимизации графа:
- Все узлы внутри одной SCC можно объединить в один супер-узел (конденсация графа) .
- Результирующий сконденсированный граф всегда является направленным ациклическим графом (DAG) .
- Если мы можем добраться до любого узла внутри компоненты, мы автоматически получаем доступ ко всем остальным узлам этой группы .
🧭 Стратегия поиска недостающих маршрутов 14:31
В сконденсированном графе Уильям Линь выделил узлы с нулевой степенью захода (in-degree 0) . Это компоненты, в которые не ведет ни один внешний маршрут. Чтобы сделать такие аэропорты достижимыми из штаб-квартиры, необходимо добавить хотя бы одно входящее ребро к каждому такому узлу .
Алгоритм решения сводится к четырем шагам:
- Преобразование строковых названий аэропортов в числовые идентификаторы (ID) .
- Поиск сильно связанных компонентов в исходном графе .
- Конденсация графа путем замены компонентов их представителями .
- Подсчет количества компонент с нулевой степенью захода, которые не содержат начальный аэропорт .
💻 Реализация через алгоритм Косарайю 32:36
Для поиска сильно связанных компонентов Уильям Линь использовал алгоритм Косарайю . Реализация потребовала создания двух представлений графа: обычного списка смежности и реверсированного .
Процесс кодирования включал:
- Использование
std::unordered_mapдля быстрого сопоставления кодов аэропортов с ID . - Первый проход поиском в глубину (DFS) для заполнения стека в порядке времени выхода .
- Второй проход DFS по реверсированному графу в порядке, извлеченном из стека .
- Массив
who, в котором для каждого исходного узла хранится ID представителя его компоненты .
В финальной части кода кандидат итерирует по всем ребрам исходного графа. Если ребро соединяет узлы из разных компонент, он увеличивает степень захода для принимающей компоненты . Ответ — количество компонент, чья степень захода осталась равной нулю (исключая компоненту со стартовым аэропортом) .
📈 Анализ сложности и вердикт 46:16
Временная сложность итогового решения составляет O(N + M), где N — количество аэропортов, а M — число существующих маршрутов . Это оптимальный показатель, так как алгоритму необходимо как минимум прочитать все входные данные.
Клеман Михайлеску оценил выступление кандидата как «Strong Hire» (уверенный найм) . Интервьюер отметил высочайший уровень коммуникации Уильяма, который комментировал каждый шаг под давлением времени. Единственным замечанием стало использование кратких имен переменных (например, who), характерных для спортивного программирования, но менее желательных в промышленной разработке .
