Подготовка к техническому интервью по алгоритмам

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

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

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

Чем интервью отличается от работы

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

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

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

Решение вслух

Самый дешёвый по времени навык и самый редкий: думать вслух. Андрей, о котором шла речь выше, в тишине решал бы задачу нормально. Молчание на интервью читается как «не знает», хотя за ним может стоять хорошее решение.

Порядок, который хорошо ложится на любую задачу, проще объяснить на ней же. Дан список чисел и целевая сумма; нужно найти два числа, дающие сумму. Первым делом вы переспрашиваете условие: числа целые? могут повторяться? есть ли гарантия, что ответ существует? Эти вопросы нужны не для вежливости: по ним интервьюер видит, что вы замечаете края задачи, и порой сам даёт подсказку. Затем называете очевидное решение: перебрать все пары. Если чисел немного, оно подходит, и об этом стоит прямо сказать. Потом оцениваете его: пар в списке порядка квадрата длины, при ста тысячах чисел это уже слишком много. И только после этого ищете улучшение: пройти список один раз, запоминая встреченные числа в хеш-таблице, и для каждого нового проверять, лежит ли в ней недостающее до суммы. Проверка в хеш-таблице в среднем занимает постоянное время, поэтому весь проход пропорционален длине списка.

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

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

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

Приёмы вместо сотни задач

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

Вот те, с которых разумно начинать:

• хеш-таблица для поиска «был ли такой элемент раньше», как в задаче про сумму
• два указателя на отсортированных данных, когда нужно найти пару или сузить диапазон
• бинарный поиск, который работает только там, где данные упорядочены или есть монотонное условие
• обход в ширину и в глубину по графу или по сетке, например поиск пути в лабиринте
• рекурсия с запоминанием, которая в задачах про «сколькими способами» заменяет перебор
• сортировка как первый шаг: многие задачи становятся простыми, если данные упорядочены, а сама сортировка стоит порядка n log n

После каждой задачи записывайте приём и признак, по которому вы его заметили, а само решение хранить необязательно: «вижу слова „первый повторяющийся“, значит, нужна память о том, что уже было». Через несколько десятков задач такой список работает быстрее любого справочника, потому что вы собрали его сами.

Что даёт занятие с репетитором, а что нет

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

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

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

Математика и английский

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

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

Неделя, в которой нет времени

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

Начать поиск:

• репетиторы по информатике для взрослых
• репетиторы для взрослых
• репетиторы для взрослых с пробным занятием

Вопросы и ответы

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

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

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

Можно ли пройти интервью, не зная динамического программирования? Это зависит от компании и роли, и обещать здесь нечего.

Как репетитор может помочь, если он не видит мой экран? Он читает код, который вы отправляете в чат, вставкой в сообщение или файлом, слушает, как вы объясняете решение, и задаёт те вопросы, которые задал бы интервьюер: какая сложность, что будет на пустом входе, почему не сделать проще. Так отрабатывается речь и проверка решения. Чего он не сможет, так это наблюдать, как вы печатаете и где спотыкаетесь на синтаксисе, поэтому беглость с редактором тренируется у вас дома.