# Как решать технические задачи на собеседовании в Google

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

---

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

Процесс найма в Google часто пугает кандидатов своей неизвестностью, однако ключевая цель компании — не просто получить правильный ответ, а увидеть ход ваших мыслей. В этом видео, подготовленном командой рекрутеров Google, демонстрируется пример того, как кандидат и интервьюер взаимодействуют при решении технической задачи. Главные советы для соискателей: всегда озвучивайте свои предположения, стремитесь к оптимизации решения и будьте готовы к «открытым» вопросам, где важно не только знание алгоритмов, но и коммуникативные навыки.

### 🧩 Условие задачи: Поиск максимальной площади
[[JUMP:1:05]]

Интервьюер Джулиана (инженер YouTube) предложила кандидату Сэмми (научный сотрудник Google Research) задачу:

* Дан двумерный массив («матрица») из 0 и 1.
* 1 означает «хорошую» землю, 0 — «плохую».
* Задача: найти максимальный квадрат, состоящий исключительно из 1, и вернуть его площадь.

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

### 🐢 Первый подход: «Наивное» решение
[[JUMP:2:15]]

Сэмми предложил «брутфорс»-алгоритм (метод грубой силы):

* Перебор каждой ячейки матрицы (индексы I и J).
* Для каждой «единицы» запуск дополнительного двойного цикла для проверки возможности расширения квадрата до размеров 2x2, 3x3 и так далее.
* Сложность такого алгоритма составляет $O(N^4)$, что, по мнению самого кандидата, не является оптимальным.

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

### 🔄 Оптимизация: Рекурсия и динамическое программирование
[[JUMP:5:07]]

Для поиска более эффективного решения Сэмми предложил рекурсивный подход:

* Если текущая ячейка равна 1, можно посмотреть на соседей (справа, снизу и по диагонали) и вычислить размер возможного квадрата.
* Идея заключалась в том, чтобы брать минимум из значений соседей и прибавлять 1.
* Для борьбы с избыточными вычислениями он предложил добавить мемоизацию, что снизило бы сложность до квадратичной.

Джулиана предложила перейти к еще более эффективному методу — «снизу вверх» (bottom-up) динамическому программированию. В этом сценарии создается вспомогательная матрица (DP-матрица) того же размера. Каждая ячейка в ней заполняется минимальным значением из трех соседей (слева, сверху, сверху-слева по диагонали) плюс единица, если в исходной матрице стоит 1.

### 💻 Написание кода на Python
[[JUMP:15:09]]

Сэмми реализовал решение с использованием Python. Важные аспекты написания кода в «полевых условиях»:

* Использование двумерного массива для хранения промежуточных результатов.
* Обработка граничных условий (края матрицы).
* Использование функции `max()` для фиксации итогового результата во время прохода цикла, что позволяет избежать лишнего прохода по массиву в конце.

Интервьюер Джулиана похвалила Сэмми за то, что он корректно пересмотрел свои ранние предположения и пришел к оптимальному решению.