# Как пройти техническое интервью в Google: пошаговый разбор

Источник: https://www.youtube.com/watch?v=Ti5vfu9arXQ
Канал: Life at Google
Опубликовано: 10.02.2025

---

## Искусство решения задач: Разбор технического собеседования в Google
[[JUMP:0:00]]

Техническое собеседование в Google — это не просто проверка умения писать код, а демонстрация того, как кандидат мыслит, задает уточняющие вопросы и итеративно улучшает свое решение. В этом видео ведущая Джулиана, инженер-программист YouTube, проводит имитацию интервью с Сэмми, научным сотрудником Google Research, чтобы показать процесс работы над типичной алгоритмической задачей.

### 🔍 Этап 1: Уточнение условий задачи
[[JUMP:1:32]]

Интервьюер ставит перед кандидатом задачу: найти максимальную площадь квадрата, состоящего из «хорошей» земли (обозначенной единицами в матрице), среди «плохой» земли (обозначенной нулями).

Сэмми начинает с критически важного шага — прояснения требований:

* **Форма области:** Обязательно ли это квадрат, или может быть прямоугольник? Джулиана подтверждает: только квадрат.
* **Открытость вопросов:** Ведущая отмечает, что многие задачи формулируются намеренно расплывчато, чтобы увидеть, как кандидат вступает в диалог с проблемой.

### 🛠 Этап 2: От «грубой силы» к оптимальному решению
[[JUMP:2:15]]

Сэмми предлагает начать с «наивного» (brute force) подхода: перебор всех индексов и проверка каждой возможной границы квадрата.

* **Оценка сложности:** Сэмми сразу признает, что при размере матрицы $N \times N$ сложность такого решения составит $O(N^4)$, что является крайне неэффективным.
* **Визуализация:** По просьбе интервьюера Сэмми описывает логику: для каждой точки он проверяет возможность построения квадрата $1 \times 1$, затем $2 \times 2$, $3 \times 3$ и так далее, постоянно обновляя значение максимума.
* **Реакция интервьюера:** Джулиана одобряет этот подход, подчеркивая, что даже если решение неоптимально, важно показать ход мыслей и готовность оценить соседние значения.

### 🧠 Этап 3: Рекурсия и мемоизация
[[JUMP:5:07]]

После обсуждения базового варианта, Сэмми переходит к более совершенным методам, предлагая рекурсивный подход.

* **Логика рекурсии:** Идея заключается в том, чтобы, находясь в ячейке, спросить соседей (справа, снизу и по диагонали) о размере квадрата, который они могут сформировать.
* **Вывод:** Сэмми приходит к выводу, что нужно брать минимум из значений соседей и добавлять единицу.
* **Оптимизация:** Сэмми понимает, что простая рекурсия будет пересчитывать одни и те же значения, поэтому предлагает добавить мемоизацию, что снизит временную сложность до $O(N^2)$.

### 💻 Этап 4: Динамическое программирование (Bottom-Up)
[[JUMP:12:37]]

Джулиана направляет кандидата к наиболее эффективному решению — динамическому программированию снизу вверх.

* **Принцип:** Создается матрица того же размера, что и входная, заполненная нулями. Значение в каждой ячейке вычисляется на основе соседей: если в текущей ячейке единица, то значение равно `min(left, top, diagonal) + 1`.
* **Реализация:** Сэмми пишет код на Python, используя массив для хранения промежуточных результатов. 
* **Важные замечания:** * Интервьюер уточняет, что в массиве будет храниться сторона квадрата, а не его площадь, что является корректным подходом.
    * Сэмми оптимизирует процесс отслеживания максимума, обновляя переменную `max_num` непосредственно внутри цикла, чтобы избежать повторного прохода по матрице.