Как подготовиться к алгоритмическому собеседованию

Алгоритмическая секция есть на собеседованиях в большинстве крупных IT-компаний: в Яндексе, Т-Банке, Авито, Ozon, VK, Google. Её часто побаиваются и опытные разработчики. При этом набор типовых задач ограничен, а формат почти везде одинаковый, так что подготовка хорошо окупается.

Как проходит секция

Обычно 45-60 минут и одна-две задачи. Код пишут в общем онлайн-редакторе, часто без возможности запустить. Интервьюер ждёт, что вы будете рассуждать вслух: уточнять условие, предлагать решение, оценивать его сложность и проверять на примерах.

Что оценивают

• правильность решения, включая крайние случаи;
• сложность по времени и памяти и умение её объяснить;
• понятный код: имена переменных, отсутствие лишнего;
• как вы рассуждаете и как используете подсказки интервьюера.

Решение, к которому вы пришли сами и аккуратно объяснили, часто ценится выше, чем быстрый ответ без объяснений.

Какие задачи встречаются

Большинство задач сводится примерно к двадцати паттернам. Чаще всего встречаются:

• хеш-таблицы и подсчёт элементов;
• два указателя и скользящее окно;
• префиксные суммы;
• двоичный поиск;
• стек, в том числе монотонный, и скобочные последовательности;
• сортировка и задачи на отрезки;
• куча;
• обход графа и сетки в ширину и в глубину;
• связные списки и деревья;
• простое динамическое программирование.

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

1. Уточните условие: размер входа, могут ли быть повторы и отрицательные числа, что вернуть, если ответа нет.
2. Расскажите самое простое решение и его сложность, даже если оно медленное.
3. Улучшите его и объясните, за счёт чего стало быстрее.
4. Напишите код. Если что-то забыли, скажите об этом вслух.
5. Пройдите код руками на примере, потом на крайних случаях: пустой ввод, один элемент, все элементы одинаковые.

План на 4-6 недель

1. Каждую неделю берите две-три группы паттернов из списка и решайте по 2-3 задачи в день.
2. Решайте без запуска кода и с таймером на 30 минут. Запускайте только после того, как решили, что код готов.
3. Через неделю возвращайтесь к старым задачам и решайте их заново, не подглядывая.
4. С третьей недели проводите пробные собеседования: с другом, коллегой или ментором, вслух и на время.

Частые ошибки

• Сразу писать код, не обсудив решение.
• Молчать. Интервьюер не видит, о чём вы думаете, и не может подсказать.
• Не называть сложность или называть её неправильно.
• Не проверять код на примере перед тем, как сказать «готово».

Если вы занимались олимпиадами

Олимпиадный опыт сильно помогает: паттерны те же, а задачи на собеседовании обычно проще олимпиадных. Но на олимпиаде никто не спрашивает, почему решение работает, а на собеседовании это половина оценки. Привычку рассуждать вслух придётся тренировать отдельно.

В «Кружке 102» к алгоритмическим собеседованиям готовят преподаватели, которые сейчас стажируются в Яндексе и Т-Банке. Занятия один на один, есть пробные собесы с письменным разбором. Диагностика бесплатная, подробности на странице подготовки к собеседованиям.