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

Сегодня большинство алгоритмических интервью проходит онлайн — через Zoom или Google Meet вместе с разделяемым редактором кода.

Раньше значительно чаще встречались onsite-интервью с белой маркерной доской в офисе компании, на которой приходилось писать код. Такой формат все еще можно встретить, но он стал заметно реже.

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

На этом шаге полезно взять какой-нибудь пример входных данных и разобрать его. Разбор примера позволит:

После разбора простого примера стоит подумать о граничных случаях. Что должен выводить алгоритм в случае пустых данных или состоящих из одного элемента? Может ли у нас случиться переполнение типа данных? Есть ли циклы в графе? Более конкретные случаи зависят от специфики задачи.

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

К этому моменту мы собрали требования, погрузились в условие задачи и выяснили граничные случаи. И пора переходить к обсуждению алгоритма. Обычно в голову приходит первая идея «наивного» подхода. Например, полного перебора. И это отличная точка старта для обсуждения. Стоит вкратце рассказать эту идею интервьюеру.

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

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

Не стоит долго задерживаться на первой идее, которая пришла в голову. Можно взять паузу и минутку подумать о том, как можно улучшить это решение, потому что часто у задач их несколько.

Главное — не уходить надолго в себя и через пару минут вернуться к обсуждению. Отдельный плюс можно получить за рассуждения о компромиссах при выборе алгоритма.

Например: у нас есть один подход, он будет работать за O (n*log (n)) по времени и O (1) по памяти. Также есть другой, который работает за O (n) по времени и O (n) по памяти. И дальше в зависимости от того, какой вычислительный ресурс (CPU или RAM) у нас более приоритетен, можно делать выбор в пользу конкретного алгоритма.

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

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

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

Полезно также вспомнить про возвращение ошибок. Может показаться странным: «зачем стоит уделять этому время?». В лучшем случае — если пропустить эту часть, интервьюер не обратит на это внимание. В худшем — может сделать пометку, что кандидат не уделяет внимание проектированию API.

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

К настоящему моменту у нас есть все, чтобы приступить к написанию кода. И можно уже переходить к нему. Но лучше сделать паузу — сказать интервьюеру, что вам нужно подумать еще чуть-чуть о деталях реализации, и взять еще 20-30 секунд.

В этот момент стоит представить, как вы декомпозируете код, какие будут блоки и что вы планируете выделить в отдельные функции.

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

Вся подготовительная работа проделана, алгоритм выбран, что писать — ясно. Пора приступить к самому интересному.

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

Во время реализации используйте «скелет функции»: сначала сигнатура + пустая реализация, затем ее содержимое. Это снижает шанс забыть что-то реализовать.

Интервьюер со 100% вероятностью отметит ваш стиль написания и отразит это в своем отчете об интервью, если ему что-то покажется не соответствующим общепринятым практикам.

Какие аспекты в написании кода повысят ваши шансы на положительное ревью:

Я бы рекомендовал писать свой код с мыслью, что вы его отправите на ревью коллеге. Поставит ли он approve или напишет комментарии и попросит доработать? Если второе, то стоит сразу это учесть.

Если же написать код «как в production» не получается (все же мы на интервью, время ограничено и задача достаточно искусственная), то полезно голосом проговорить, как бы вы сделали в рабочей ситуации.

Одна из частых ошибок — это сказать «готово» сразу после ввода последнего символа вашей программы.

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

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

Также удобно выписать переменные прямо в редакторе и обновлять их значения во время трассировки. Это помогает не запутаться самому и делает процесс проверки более наглядным для интервьюера.

Правильного ответа каким подходом пользоваться нет. Многое зависит от конкретной задачи и ваших предпочтений.

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

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

В конце интервью, если остается время, можно дополнительно блеснуть знаниями. Например: указать, как еще лучше можно решить задачу или распараллелить, если задача это позволяет.

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

Чтобы не держать всю структуру в голове, можете следовать простому чек-листу прохождения алгоритмического собеседования:

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

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

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

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

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

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

Важно выбирать задачи, которые либо встречаются чаще всего, либо являются основополагающими для решения других. Я сам решил более 400 задач на LeetCode и хочу сказать, что большого смысла в этом нет — решив 100 задач, вы будете готовы к 80% алгоритмических собеседований на российском рынке.

Лучше выбрать 10−15 шаблонов задач и для каждого решить 5−10 представителей, чтобы научиться узнавать паттерн использования алгоритма по формулировке задачи.

Важно начинать решение задач с простых, постепенно увеличивая их сложность, и расписать процесс решения на LeetCode. Не просто бездумно прорешивайте задачи, а старайтесь видеть паттерны применения того или иного алгоритма, чтобы потом быстро подобрать для решения похожей задачи.

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

В них есть разбор ключевых паттернов и практика на задачах уровня реальных алгосекций

Пробуйте писать код без IDE — тренировки нужно вести в условиях, приближенных к интервью, где может не быть подсветки синтаксиса и автокомплита.

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

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

Чтобы извлечь из этого максимум пользы, я бы рекомендовал обращать внимание на несколько вещей:

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

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

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

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

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

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

В конце статьи хочется поделиться небольшим исследованием, которое мы провели. Мы опросили более 600 разработчиков, которые проходили алгоритмические собеседования в различных Российских компаниях. На основе их ответов получилось следующее распределение тем:

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

Успешных вам алгоритмических собеседований!