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

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

Как проходит алгоритмическое собеседование

Процесс зависит от компании, но структура обычно примерно одинаковая. Алгоритмическое собеседование занимает 40–60 минут и включает 2–3 задачи. Работу над каждой из них можно разделить на 2 логических этапа.

1. Обсуждение решения задачи

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

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

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

2. Работа с кодом

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

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

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

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

Дополнительно могут задать вопрос о сложности алгоритма. В этом случае нужно как минимум понимать, чем отличается линейная сложность O(n) от квадратичной O(n2n^2), логарифмической O(log n) и т. д. А еще уметь правильно оценить сложность своего алгоритма по времени и по памяти. Будет лучше, если свою оценку вы подкрепите рассуждениями, почему получается именно такая сложность. Например, у нас вложенный цикл, внутри выполняются операции с линейной сложностью. Значит, общая сложность алгоритма по времени — квадратичная.

Если не знаете, как подготовиться к интервью, попробуйте курс «Алгоритмы и структуры данных». Во время обучения вы поднимете свой уровень знаний по алгоритмам.

Какие задачи дают на собеседовании

Как правило, задачи равнозначные по сложности, но разнонаправленные. Скажем, первую задачу можно решить с помощью сортировки или прохода по массиву. Ниже — пример.

В массиве из чисел найти непрерывный подмассив длиной k с максимальным средним значением. То есть такой подмассив, в котором среднее значение всех чисел будет больше, чем во всех остальных подмассивах.

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

Дан массив связанных списков, каждый список отсортирован в порядке возрастания. Нужно соединить все списки в один связный и отсортированный список.

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

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

Нужно не просто знать отдельные темы, а иметь навык решения задач. Поэтому первый совет — больше практикуйтесь. Неважно, новичок вы или уже несколько лет работаете в коммерческой разработке, начинайте готовиться за один-два месяца, чтобы прийти в форму.

Самый простой вариант — решать задачи на Leetcode и Codewars. Если вообще ничего не знаете, начинайте с легкого уровня, но не задерживайтесь на нем. Когда увидите, что дело пошло, переходите к среднему и тяжелому уровню. Если не получается придумать решение, подсмотрите в ответе — возможно, увидите новую структуру данных или алгоритм. Нормально, если из 100 задач среднего уровня получается решить 90–95.

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

Что еще пригодится на алгоритмическом собеседовании

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

• Бинарный поиск и связанные с ним задачи. Например, стоит посмотреть First bad version, Sqrt x, 2D matrix.

• Метод двух указателей и задачи со скользящим окном.

• Алгоритмы на строках: найти палиндром, обратную строку и другие.

Выше далеко не весь список того, что вам может понадобиться. Если есть время, изучите, например, динамическое программирование, жадные алгоритмы, алгоритмы Ли и Дейкстры.

А чтобы снизить волнение перед реальным интервью, можете попросить друга или знакомого устроить вам тестовое собеседование.

Почувствовать себя увереннее на алгоритмическом собеседовании и повысить шансы на трудоустройство поможет онлайн-курс «Алгоритмы и структуры данных». За 4 месяца вы узнаете про часто используемые способы решения алгоритмов, научитесь писать эффективный код и прорешаете более 100 задач. Первые шесть уроков можно пройти бесплатно — пробуйте и решайте, хотите ли переходить к полной программе.