# Уильям Линь решил сложнейшую задачу интервью Google за 45 минут

Источник: https://www.youtube.com/watch?v=qz9tKlF431k
Канал: Clément Mihailescu
Опубликовано: 03.05.2020

---

Уильям Линь, школьник и международный гроссмейстер на Codeforces, прошел имитацию технического интервью Google с Клеманом Михайлеску. За 45 минут кандидат решил задачу Airport Connections, которую Клеман называет сложнейшей на платформе AlgoExpert [00:43].

## 🛫 Постановка задачи об авиалиниях
[[JUMP:02:48]]

Кандидат выступает в роли владельца авиакомпании, которая должна обеспечить доступ ко всем аэропортам из единого центра [02:50]. Входные данные включают три параметра:

*   Список аэропортов (трехбуквенные коды, например, LGA, CDG).
*   Список существующих односторонних маршрутов между ними.
*   Начальный аэропорт (starting airport), который является штаб-квартирой [04:35].

Задача заключается в поиске минимального количества новых односторонних рейсов, которые нужно добавить. После их добавления пассажир должен иметь возможность долететь из начальной точки в любой аэропорт из списка [05:40]. Прямые рейсы необязательны, допускается любое количество пересадок [06:24]. В тестовом примере для обеспечения связности потребовалось добавить **3** новых маршрута [07:18].

## 📊 Графовая модель и сильно связанные компоненты
[[JUMP:08:16]]

Уильям Линь сразу предложил рассматривать структуру аэропортов как ориентированный граф [08:46]. Ключевой концепцией решения стали сильно связанные компоненты (**SCC**). Это группы узлов, внутри которых каждый аэропорт достижим из любого другого [09:13].

Логика оптимизации графа:

*   Все узлы внутри одной **SCC** можно объединить в один супер-узел (конденсация графа) [11:49].
*   Результирующий сконденсированный граф всегда является направленным ациклическим графом (**DAG**) [12:37].
*   Если мы можем добраться до любого узла внутри компоненты, мы автоматически получаем доступ ко всем остальным узлам этой группы [13:19].

## 🧭 Стратегия поиска недостающих маршрутов
[[JUMP:14:31]]

В сконденсированном графе Уильям Линь выделил узлы с нулевой степенью захода (in-degree 0) [14:45]. Это компоненты, в которые не ведет ни один внешний маршрут. Чтобы сделать такие аэропорты достижимыми из штаб-квартиры, необходимо добавить хотя бы одно входящее ребро к каждому такому узлу [15:29].

Алгоритм решения сводится к четырем шагам:

1.  Преобразование строковых названий аэропортов в числовые идентификаторы (ID) [19:34].
2.  Поиск сильно связанных компонентов в исходном графе [21:57].
3.  Конденсация графа путем замены компонентов их представителями [25:44].
4.  Подсчет количества компонент с нулевой степенью захода, которые не содержат начальный аэропорт [31:00].

## 💻 Реализация через алгоритм Косарайю
[[JUMP:32:36]]

Для поиска сильно связанных компонентов Уильям Линь использовал алгоритм Косарайю [22:10]. Реализация потребовала создания двух представлений графа: обычного списка смежности и реверсированного [36:18].

Процесс кодирования включал:

*   Использование `std::unordered_map` для быстрого сопоставления кодов аэропортов с ID [34:27].
*   Первый проход поиском в глубину (**DFS**) для заполнения стека в порядке времени выхода [38:15].
*   Второй проход **DFS** по реверсированному графу в порядке, извлеченном из стека [40:43].
*   Массив `who`, в котором для каждого исходного узла хранится ID представителя его компоненты [42:07].

В финальной части кода кандидат итерирует по всем ребрам исходного графа. Если ребро соединяет узлы из разных компонент, он увеличивает степень захода для принимающей компоненты [43:05]. Ответ — количество компонент, чья степень захода осталась равной нулю (исключая компоненту со стартовым аэропортом) [45:21].

## 📈 Анализ сложности и вердикт
[[JUMP:46:16]]

Временная сложность итогового решения составляет **O(N + M)**, где N — количество аэропортов, а M — число существующих маршрутов [50:10]. Это оптимальный показатель, так как алгоритму необходимо как минимум прочитать все входные данные. 

Клеман Михайлеску оценил выступление кандидата как «Strong Hire» (уверенный найм) [55:36]. Интервьюер отметил высочайший уровень коммуникации Уильяма, который комментировал каждый шаг под давлением времени. Единственным замечанием стало использование кратких имен переменных (например, `who`), характерных для спортивного программирования, но менее желательных в промышленной разработке [55:21].