Алгоритмическая секция с написанием кода на доске или бумаге — один из важнейших этапов собеседования разработчиков для получения работы в Яндексе. Мы решили подробнее рассказать о том, как устроены эти секции, чтобы помочь будущим кандидатам в подготовке. Кроме того, надеюсь, многие из тех, кто не решается прийти в Яндекс на собеседование, опасаясь слишком сложных испытаний, после этого рассказа поймут, что в действительности всё не так уж и страшно!
Так что мы подготовили для вас следующие материалы:
- Специальный контест, содержащий задачи, похожие на те, что мы даём на интервью.
- Этот пост. В нём рассказывается, почему нужно проводить такие секции, а также разбираются все задачи контеста.
- Два видео, в которых разбираются задачи из контеста: в первом — задача попроще, во втором — две задачи посложнее. Из этих видео вы узнаете о типичных ошибках, допускаемых и при прохождении алгоритмических секций, и при написании продакшен-кода.
Как мы собеседуем разработчиков
Собеседование любого разработчика состоит из нескольких этапов:
- предварительная секция с рекрутером;
- техническое скайп-интервью;
- несколько очных секций;
- финальные интервью с нанимающими менеджерами.
На предварительной секции рекрутер знакомится с кандидатом, узнаёт его интересы и мотивы для того, чтобы понять, на какие позиции имеет смысл его рассматривать. Техническое скайп-интервью предназначено для предварительной оценки навыков кандидата и отсеивает тех, кто со всей определённостью не справится с очными секциями.
Очные секции — основной этап. Именно очные секции дают ответ на вопрос о том, что умеет кандидат. Алгоритмическая секция — одна из очных технических секций. Помимо алгоритмических, бывают и другие очные испытания: скажем, кандидаты в старшие разработчики обязательно проходят секцию по архитектуре, а будущие руководители ещё и отвечают на вопросы по управлению командами и проектами. Вообще, если у кандидата есть какая-то сильная сторона в специфической области (машинном обучении, низкоуровневой оптимизации, разработке высоконагруженных систем, мобильной разработке или любой другой) — мы обязательно организуем секцию с профильным специалистом.
Алгоритмическая секция проверяет, способен ли кандидат придумывать алгоритмы для решения несложных задач, оценивать сложность этих алгоритмов и реализации их без ошибок, в процессе соблюдая баланс между качеством тестирования и скоростью решения.
Зачем писать код на доске или бумаге
Естественное состояние для программиста — программирование в интегрированной среде разработки с подсветкой синтаксиса и возможностью трассировки. Поэтому идея на собеседовании писать код на доске или бумаге первоначально кажется не слишком естественной. Однако, этот способ позволяет проверить два очень важных для каждого разработчика свойства.
Первое из них — умение быстро разбираться с работоспособностью кода «на глаз». Представьте себе, что при написании каждого цикла, возникающего в программе, разработчику требуется потратить время на то, чтобы проверить его работоспособность трассировкой; или что при падении сервиса в продакшене ему всегда обязательно нужно запустить код под дебаггером. Ясно, что написание и отладка даже несложных программ будут занимать у него непозволительно много времени. Конечно, полезно уметь читать код и при код-ревью.
Второе важное свойство — способность заранее продумывать план решения и затем следовать ему. Если плана нет, это будет приводить к большому количеству исправлений, зачёркиваний (на бумаге) и переписыванию больших кусков кода. В реальной жизни всё это сильно замедляет разработку, но отчасти маскируется скоростью работы в редакторе кода. Доска и бумага в этом смысле являются беспощадными поверхностями.
Естественно, мы учитываем, что писать код от руки — не слишком быстрое дело. Поэтому наши задачи обычно предполагают решение не намного длиннее десятка строк, а количество задач, которые необходимо решить в течение одной секции, обычно равняется двум или трём.
Алгоритмические секции и спортивное программирование
Спортивное программирование развивает в будущем разработчике, помимо прочего, и способность быстро и без ошибок реализовывать простые алгоритмы согласно заранее назначенному плану. Поэтому кандидаты с опытом спортивного программирования, действительно, неплохо справляются с алгоритмическими секциями на собеседованиях. Часто можно наблюдать ситуацию, когда будущие стажёры легко справляются с алгоритмической секцией, решая все задачи за 15-20 минут, тогда как более опытные программисты на те же задачи тратят целый час.
В то же время, алгоритмическая секция с написанием кода — лишь одна из секций, проверяющая минимально необходимые для любого разработчика навыки. С этой секцией справятся не только олимпиадные программисты, но и опытные промышленные разработчики. Будущего старшего разработчика или руководителя группы обязательно ждёт архитектурная секция, на которой он сможет раскрыть свои самые сильные стороны; конечно, эта секция никогда не ставится стажёрам и младшим разработчикам.
Контест для подготовки к собеседованию
Специально для того, чтобы вы могли примерно представить себе содержание задач, которые мы даём на алгоритмических секциях, мы собрали контест, который можно использовать при подготовке к собеседованиям. Попробуйте решить все задачи, ни разу не запустив дебаггер; написать решение в Notepad'е без подсветки синтаксиса; придумать как можно более короткое решение, которые пройдёт все тесты; продумать все возможные проблемы заранее и сдать решение с первого раза.
Контест содержит пять задач. Вы можете попробовать решить их самостоятельно, а можете заранее прочитать разбор: это всё равно будет полезно, т.к. вы сможете потренировать свой навык безошибочного кодирования заранее известного алгоритма.
Даны две строки строчных латинских символов: строка J и строка S. Символы, входящие в строку J, — «драгоценности», входящие в строку S — «камни». Нужно определить, какое количество символов из S одновременно являются «драгоценностями». Проще говоря, нужно проверить, какое количество символов из S входит в J.
Это очень простая разминочная задача, к которой прилагаются решения на нескольких языках программирования, чтобы участники могли освоиться с проверяющей системой.
Алгоритм достаточно простой: из строки с «драгоценностями» необходимо построить множество, затем пройтись по строке с «камнями» и каждый символ проверить на вхождение в это множество. Используйте такую реализацию множества, чтобы гарантировать линейную сложность полученного решения, несмотря на то, что входные строки очень короткие и поэтому возможно сдать даже квадратичный по сложности алгоритм.
Задача B. Последовательно идущие единицы
Требуется найти в бинарном векторе самую длинную последовательность единиц и вывести её длину.
Алгоритм решения следующий: пройтись по всем элементам массива; встретив единицу, нужно увеличить счётчик длины текущей последовательности, а, встретив ноль, нужно обнулить этот счётчик. В конце нужно вывести максимальное из значений, которые принимал счётчик.
Проверьте, что правильно обрабатываете ситуацию, когда массив заканчивается на искомую последовательность единиц. При аккуратной реализации такая ситуация не потребует специальной обработки.
Постарайтесь использовать лишь константный объём дополнительной памяти.
Дан упорядоченный по неубыванию массив целых 32-разрядных чисел. Требуется удалить из него все повторения.
Правильный алгоритм последовательно обрабатывает элементы массива, сравнивая их с последним выведенным. Нужно не забыть обновлять переменную, содержащую последний выведенный элемент и, кроме того, не ошибиться при обработке последнего элемента.
При решении этой задачи также не нужно использовать дополнительную память.
Задача D. Генерация скобочных последовательностей
Дано целое число. Требуется вывести все правильные скобочные последовательности длины
, упорядоченные лексикографически (см. https://ru.wikipedia.org/wiki/Лексикографический_порядок). В задаче используются только круглые скобки.
Это пример относительно сложной алгоритмической задачи. Будем генерировать последовательность по одному символу; в каждый момент мы можем к текущей последовательности приписать либо открывающую скобку, либо закрывающую. Открывающую скобку можно дописать, если до этого было добавлено менее n открывающих скобок, а закрывающую — если в текущей последовательности количество открывающих скобок превосходит количество закрывающих. Такой алгоритм при аккуратной реализации автоматически гарантирует лексикографический порядок в ответе; работает за время, пропорциональное произведению количества элементов в ответе на n; при этом требует линейное количество дополнительной памяти.
Примером неэффективного алгоритма был бы следующий: сгенерируем все возможные скобочные последовательности, а затем выведем лишь те из них, что окажутся правильными. При этом объём ответа не позволит решить задачу быстрее, чем тот алгоритм, что приведёт выше.
Эта достаточно простая задача — типичный пример задачи, для решения которой необходимо использовать ассоциативные массивы. При решении нужно учитывать, что символы могут повторяться, поэтому необходимо использовать не множества, а словари. Поэтому решение будет следующим: составим из каждой строки по словарю, который для каждого символа будет хранить количество его повторений; затем сравним получившиеся словари. Если они совпадают, необходимо вывести единицу, в противном случае — ноль.
Альтернативное решение: отсортируем входные строки, а затем сравним их. Это решение хуже в том, что оно работает медленнее, а также меняет входные данные. Зато такое решение не использует дополнительной памяти.
Если в процессе собеседования у вас возникло несколько вариантов решения, отличающихся своими по своим характеристикам, расскажите об этом. Всегда здорово, когда разработчик знает несколько вариантов решения задачи и может рассказать об их сильных и слабых сторонах.
Задача F. Слияние 
сортированных списков
Даны.
Для каждого массива создадим по указателю; изначально каждый указатель расположен в начале соответствующего массива. Элементы, соответствующие позициям указателей, поместим в любую структуру данных, которая поддерживает извлечение минимума — это может быть мультимножество или, например, куча. Далее будем извлекать из этой структуры минимальный элемент, помещать его в ответ, сдвигать позицию указателя в соответствующем массиве и помещать в структуру данных очередной элемент из этого массива.
В этой задаче многие испытывают сложности с форматом ввода. Обратите внимание на то, что первые элементы строк не описывают элементы массивов, они описывают длины массивов!
FAQ по контесту
A: Я точно написал правильный код, но тесты не проходят; наверное, в них ошибка?
Q: Нет, все тесты правильные. Подумайте: вероятно, вы не предусмотрели какую-нибудь необычную ситуацию.
A: Я пишу на языке X, ему точно требуется больше памяти в задаче Y. Поднимите лимиты!
Q: Все лимиты выставлены таким образом, что решение возможно с использованием любого из доступных языков. Попробуйте проверить, не зачитываете ли вы случайно входной файл целиком в задачах со строгими лимитами по используемой памяти.
A: Некоторые задачи можно решить намного проще из-за указанных ограничений. Зачем вы так?
Q: Мы специально упростили ввод в некоторых задачах, чтобы участникам было проще сосредоточиться на реализации алгоритма и не думать, например, о скорости загрузки данных или каких-то других вещах, важных в спортивном программировании. Постарайтесь реализовать именно те алгоритмы, которые мы рекомендуем — только в такой ситуации вы получите от контеста максимальную пользу.
A: Не хочу проходить контест. Можно я не буду?
Q: Конечно! Контест не является обязательным к решению всеми кандидатами. Впрочем, я всё равно рекомендую его порешать: это в любом случае будет полезно.
A: Что ещё посоветуете для подготовки?
Q: Прочитайте наши советы на официальной странице про собеседования в Яндекс: https://yandex.ru/jobs/ya-interview. От себя добавлю, что решение задачек на leetcode.com является крайне полезным для любого практикующего разработчика, независимо от того, планирует ли он в ближайшее время проходить интервью или участвовать в соревнованиях по программированию. Даже небольшое количество практики позволяет почувствовать себя увереннее при решении рабочих задач.
Заключение
Я часто бываю на конференциях для разработчиков и руководителей разработки, состою во многих чатах, посвящённых разработке, провёл несколько сотен собеседований и нанял в Яндекс огромное количество разработчиков. Опыт подсказывает, что алгоритмические секции с написанием кода на доске или бумаге часто вызывают вопросы. В заключение статьи я отвечу на самые популярные из них.
Зачем проводить собеседование в условиях, столь сильно отличающихся от реальных условий работы разработчика?
Это позволяет понять, способен ли кандидат находить проблемы в программах, не запуская дебаггер; может ли он заранее придумать план алгоритма и затем безошибочно следовать ему; может ли он придумать небольшой, но достаточный, набор тестов и затем проверить свою реализацию на соответствие этому набору тестов.
Такие секции отдают несправедливое преимущество спортивным программистам?
Спортивное программирование развивает в разработчиках некоторые очень полезные навыки, поэтому участники олимпиад по программированию, действительно, хорошо справляются с алгоритмическими секциями. Так что преимущество имеется, но оно является справедливым. Алгоритмическая секция является лишь одной из многих, поэтому у каждого кандидата будет достаточно возможностей для того, чтобы показать свои самые сильные стороны!
Зачем проводить алгоритмические секции, если все алгоритмы уже давно реализованы, и нужно лишь уметь искать их реализации в готовых библиотеках?
На алгоритмических секциях, общих для всех разработчиков, мы проверяем лишь минимально необходимые навыки: умение придумать и без ошибок реализовать простой алгоритм, содержащий циклы, проверки условий и, возможно, требующий использования ассоциативных массивов. Код такого типа постоянно приходится писать для реализации пользовательских сервисов.
Какой смысл в секции, которая не проверяет огромное количество навыков разработчика?
Алгоритмическая секция, действительно, проверяет лишь минимально необходимый для любого разработчика набор навыков. Другие навыки мы проверяем при помощи других секций.
Вы проводите алгоритмические секции для разработчиков всех специальностей?
Да. Алгоритмические секции проводятся для бекенд-разработчиков, аналитиков, мобильных и фронтенд-разработчиков, разработчиков инфраструктуры и методов машинного обучения, и так далее.
