План алгоритмического собеседования: как впечатлить интервьюера и получить работу мечты28.01.2023 16:16

При поиске работы программистам часто приходится сталкиваться с алгоритмическим интервью. Вам предлагают лист бумаги или доску, ручку, фломастер и просят продемонстрировать свои навыки программирования без IDE, автодополнения, Google, StackOverflow, ChatGPT и даже возможности легко стереть написанное. К счастью, Covid-19 научил всех проводить собеседования удалённо и сейчас можно пользоваться компьютером и обычным текстовым редактором.

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

В начале расскажу немного о себе, чтобы заслужить ваше доверие и доказать, что у меня есть соответствующий опыт для рекомендаций по этой теме. За свою карьеру я имел возможность быть по обе стороны баррикад. С одной стороны я провёл сотни алгоритмических интервью в компаниях, в которых работал. У меня есть понимание изнутри, что ожидает интервьюер и на какие нюансы обращает внимание. С другой стороны я сам успешно проходил такие интервью и получал оффер в Google, Facebook, Amazon, Uber, Yandex и Mail.Ru.

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

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

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

Сбор требований

Первым шагом, как и в любом рабочем проекте или задаче, нужно собрать требования. Интервьюеры редко дают достаточное количество деталей. Обычно формулировки звучат дан массив, надо что-то посчитать или дан граф, в нём нужно что-то найти. В сборе требований можно выделить 3 направления, которые вам нужно прояснить:

размер входных данных. Если дан массив или строка, то какова их максимальная длина. Если граф, то сколько в нём вершин. Прояснить этот момент очень важно, потому что можно получить подсказку, какой алгоритм тут может подойти, а какой наверняка не подойдет.
природа данных. Стоит выяснить какого типа данные на входе, какой допустимый диапазон значений. Полезно задать вопрос про свойства входных данных, например, отсортированы ли они.
краевые случаи. Возможен ли пустой массив на входе, есть ли в нём null элементы? Если нужно посчитать количество подмножеств, нужно ли учитывать пустое подмножество в ответе.

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

Разбор простого примера

Следующим шагом полезно взять какой-нибудь пример входных данных и разобрать его.

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

Во-вторых, разбор примера позволит заметить некоторые закономерности и с высокой вероятностью натолкнёт на идею алгоритма. Правда стоит учесть, что пример входных данных не должен быть слишком маленьким. Например, массива из 1 элемента или графа с 2–3 вершинами скорее всего будет недостаточно. Слишком простой пример может не только не помочь с алгоритмом, но и хуже того, увести поток мыслей в сторону решения упрощённой версии задачи.

Граничные примеры

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

Предлагаемый алгоритм и оценка его сложности

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

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

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

API

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

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

Структура кода в голове

К настоящему моменту у нас есть всё, чтобы приступить к написанию кода. И можно уже переходить к нему. Но я рекомендую сделать глубокий вдох, сказать интервьюеру, что вам нужно подумать ещё чуть-чуть о деталях реализации, и взять ещё секунд 20–30. В этот момент стоит представить верхнеуровнено структуру кода: как вы декомпозируете его, какие будут блоки и что вы планируете выделить в отдельные функции. Я бы предложил разбить так:

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

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

Написание кода

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

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

Понятные названия функций и переменных. Однозначно стоит избегать однобуквенных (за исключением общепринятых вида i для счётчика цикла), непонятных или ничего не означающих названий. Худшее, что можно сделать, так это давать названия функциям или переменным, которые будут запутывать читателя кода. Из своего опыта помню историю, когда кандидат сделал 2 переменные. Одну назвал result, а вторую temp. Но на самом деле возвращал из функции то, что находилось в temp, а result использовал для хранения промежуточных значений. Подобное однозначно плохая практика, которую интервьюер наверняка запишет в минусы.
Декомпозиция. Код нужно структурировать и разбивать на вспомогательные блоки, которые выделять в отдельные функции. Понятно, что 5 строчек особо не разобъёшь и большого смысла в этом нет. Но если логически напрашивается выделение блока в отдельную функцию, то это стоит сделать. Любые повторы и копипасты обязательно надо выносить в переиспользуемую часть.
Обработка ошибок. Стоит уделить отдельное внимание обработкам ошибок. Может ли тут произойти исключение? Возвращает ли библиотечная функция ошибку? Обязательно стоит про это подумать и все подобные ситуации обработать. Как минимум их стоит проговорить во время написания кода.
Граничные случаи. Если алгоритм ведет себя иначе в граничных случаях (пустые входные данные, null-ы и т.д.), это стоит явно учесть и обработать. На этом этапе очень помогут те граничные примеры, которые мы выписали ранее.
Читаемость. Код должен быть понятным и легко читаемым. Представьте, что этот код не ваш и вы его видите впервые? Какие мысли приходят в голову: автор молодец, всё понятно написал или выкинуть и переписать? Если второе, то это плохой сигнал и стоит подумать как упросить код. Сюда входит всё перечисленное выше, но не только. Если у вас получается большая вложенность блоков, стоит этого избегать. Обилие условных операторов усложняет восприятие алгоритма. Если от них можно избавиться, то это стоит сделать. Плохая читаемость может привести к тому, что интервьюер не поймёт код, засомневается в корректности и решит, что вы не смогли написать то, что предложили. А это не в наших интересах.
Фокус на главном. Есть кандидаты, которые начинают писать с вспомогательных функций, описывают все конструкторы для классов или хуже того вообще начинают реализовывать то, что не относится к задаче. Во-первых, это отвлекает от основной логики решения задачи. Во-вторых, действуя таким образом, у вас может не остаться времени на то, чтобы завершить самые значимые и важные части. Я бы предложил начинать с того, что составляет основную часть вашего алгоритма. По ходу написания можно объявлять вспомогательные функции, объяснять, что они делают, какие данные принимают и что возвращают, и оставлять их реализацию на конец. Если у вас останется время, вы сможете их дописать. Но скорее всего вам даже не потребуется это делать. Интервьюеру чаще всего не очень интересно, что происходит в них и достаточно просто обсудить интерфейс.
Знание языка Для интервью стоит выбирать комфортный для вас язык программирования. Я бы рекомендовал выбирать ваш рабочий язык. Будет очень плохо смотреться, если вы поплывете в стандартном синтаксисе и будете на это тратить значимое время. Также важно уметь объяснить как работают языковые конструкции, которые вы применяете, и некоторые детали их реализаций. Например, за какое время они работают или используют ли дополнительную память. Интервьюер может про них спросить, и необязательно он пытается вас подловить. Скорее всего этот язык программирования для него не основной, и он хочет прояснить детали, чтобы лучше понять ваш код. Также полезно знать стандартную библиотеку выбранного вами языка, основные структуры данных и алгоритмы оттуда, а также уметь ими пользоваться: сортировки, двоичные поиски, хэш-таблицы, кучи, очереди, стеки и так далее.

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

Тестирование

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

Ранее мы уже проделали существенную часть мыслительной работы по подготовке тестовых сценариев. Вот их и нужно проверить.

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

Наверняка ваша программа содержит несколько функций и вам надо протестировать каждую из них. Тут есть 2 подхода:

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

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

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

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

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

Тайминг

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

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

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

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

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

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

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

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

Заключение

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

Мне кажется, что компании уже отошли от некогда популярных головоломок и сложных идейных задач для алгоритмической секции. Чаще всего для успешного прохождения этой секции должно хватить познаний базовых структур (например, хэш-таблиц), стандартной библиотеки (сортировки, двоичный поиск) и понимания некоторых не сложных основ. Но в любом случае алгоритмическая секция очень отличается от того, что мы привыкли делать каждый день: писать код в IDE, пользоваться умными подсказками и обращаться с вопросами к Google. Также на работе обычно никто не стоит за спиной и не наблюдает, как конкретно вы пишете код. При подготовке к алгоритмической секции я бы рекомендовал не только прочитать рекомендации в разных источниках, но и потратить несколько вечеров на то, чтобы попрактиковаться с задачами на практике. Можно включить таймер, взять задачу с одного из популярных ресурсов типа hackerrank или leetcode и попробовать порешать её в режиме интервью.

На этом я завершаю своё повествование. Всем желаю интересных несложных задач и удачных интервью!