07.05.2019 10:15
ashagraev 53 22300 Источник

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


Так что мы подготовили для вас следующие материалы:


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



Как мы собеседуем разработчиков


Собеседование любого разработчика состоит из нескольких этапов:


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

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


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


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


Зачем писать код на доске или бумаге


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


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


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


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


Алгоритмические секции и спортивное программирование


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


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


Контест для подготовки к собеседованию


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


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


Разбор задач контеста

Задача A. Камни и украшения


Даны две строки строчных латинских символов: строка J и строка S. Символы, входящие в строку J, — «драгоценности», входящие в строку S — «камни». Нужно определить, какое количество символов из S одновременно являются «драгоценностями». Проще говоря, нужно проверить, какое количество символов из S входит в J.

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


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


Задача B. Последовательно идущие единицы


Требуется найти в бинарном векторе самую длинную последовательность единиц и вывести её длину.

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


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


Постарайтесь использовать лишь константный объём дополнительной памяти.


Задача C. Удаление дубликатов


Дан упорядоченный по неубыванию массив целых 32-разрядных чисел. Требуется удалить из него все повторения.

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


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


Задача D. Генерация скобочных последовательностей


Дано целое число $n$. Требуется вывести все правильные скобочные последовательности длины $2\cdot n$, упорядоченные лексикографически (см. https://ru.wikipedia.org/wiki/Лексикографический_порядок). В задаче используются только круглые скобки.

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


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


Задача E. Анаграммы


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


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


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


Задача F. Слияние $k$ сортированных списков


Даны $k$ отсортированных в порядке неубывания массивов неотрицательных целых чисел, каждое из которых не превосходит 100. Требуется построить результат их слияния: отсортированный в порядке неубывания массив, содержащий все элементы исходных $k$ массивов. Длина каждого массива не превосходит $10\cdot k$.

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


В этой задаче многие испытывают сложности с форматом ввода. Обратите внимание на то, что первые элементы строк не описывают элементы массивов, они описывают длины массивов!


FAQ по контесту


A: Я точно написал правильный код, но тесты не проходят; наверное, в них ошибка?
Q: Нет, все тесты правильные. Подумайте: вероятно, вы не предусмотрели какую-нибудь необычную ситуацию.


A: Я пишу на языке X, ему точно требуется больше памяти в задаче Y. Поднимите лимиты!
Q: Все лимиты выставлены таким образом, что решение возможно с использованием любого из доступных языков. Попробуйте проверить, не зачитываете ли вы случайно входной файл целиком в задачах со строгими лимитами по используемой памяти.


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


A: Не хочу проходить контест. Можно я не буду?
Q: Конечно! Контест не является обязательным к решению всеми кандидатами. Впрочем, я всё равно рекомендую его порешать: это в любом случае будет полезно.


A: Что ещё посоветуете для подготовки?
Q: Прочитайте наши советы на официальной странице про собеседования в Яндекс: https://yandex.ru/jobs/ya-interview. От себя добавлю, что решение задачек на leetcode.com является крайне полезным для любого практикующего разработчика, независимо от того, планирует ли он в ближайшее время проходить интервью или участвовать в соревнованиях по программированию. Даже небольшое количество практики позволяет почувствовать себя увереннее при решении рабочих задач.


Заключение


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


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


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


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


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


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

Комментарии (53)


  1. geisha
    07.05.2019 16:08
    #20124360

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

    Выесть мозг на собеседовании и продемонстрировать на хабре пустой череп уже стало почти традицией. Как вы оцениваете сроки (минимальное и среднее значения), за который можно получить оффер от яндекса?


    1. IvanVakhrushev
      07.05.2019 16:54
      #20124648

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


    1. Antervis
      07.05.2019 17:06
      #20124730

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


      1. geisha
        07.05.2019 22:27
        #20126090

        Ну это норм если все очные собеседования за два дня в одну неделю.


  1. jehy
    07.05.2019 17:21
    #20124828
    +11

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

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

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


    1. ashagraev Автор
      07.05.2019 18:08
      #20125098
      -4

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

      Я совершенно не согласен с тем, что наши задачи — синтетические. Такой же код постоянно приходится писать для продакшена, каждый день. Нужно уметь использовать циклы, if'ы, иногда рекурсию, ассоциативные массивы; нужно использовать их своевременно и не допускать при этом ошибок. Что из этого не относится к работе разработчика? :)

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


      1. geisha
        07.05.2019 18:31
        #20125214
        +6

        Наверное, "не так" то, что задачки (под спойлером в статье) с районной олимпиады 9 класса. И закидоны в духе "не пользуясь дебаггером", "без подстветки синтаксиса в блокноте" — тоже напоминают эти школьные соревнования. Замечательные были времена, да.


    1. Antervis
      08.05.2019 15:43
      #20129334

      И зачем там специалисты по алгоритмам — непонятно

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


  1. Kane
    07.05.2019 17:27
    #20124866
    +9

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

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


    Или у вы как-то по-другому в Яндексе код пишете?


    1. ashagraev Автор
      07.05.2019 18:05
      #20125084
      -1

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

      Когда я пишу о проверке с трассировкой, я имею в виду, например, такие ситуации, как off-by-one error в количестве итераций цикла. Да, такую ошибку очень легко установить трассировкой, но намного лучше уметь заметить её просто взглянув на код. Ещё лучше вообще не допустить :)


      1. Kane
        07.05.2019 18:22
        #20125180
        -1

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


  1. 1anisim
    07.05.2019 17:38
    #20124942
    +3

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

    Можно ли получить hire, если секция алгоритмов не пройдена, но пройдены все остальные?


    1. F0iL
      08.05.2019 09:43
      #20127204

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


  1. Whiteha
    07.05.2019 18:05
    #20125080
    +19

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


    1. ptyrss
      07.05.2019 19:18
      #20125430

      не холивара ради, а интереса. А куда посоветуете?


      1. bak
        07.05.2019 19:40
        #20125518
        +1

        в гугл / фейсбук / амазон / etc, с переездом в европу / штаты?


    1. iskhomutov
      08.05.2019 08:19
      #20126888
      +2

      вариант для тех кто не умеет в разговорный английский


  1. thekvs
    07.05.2019 18:23
    #20125182
    +9

    А в Яндекс по-прежнему очередь из соискателей?


    1. balexa
      08.05.2019 12:03
      #20128126

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


      1. thekvs
        08.05.2019 12:10
        #20128170
        +1

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


  1. ptyrss
    07.05.2019 19:05
    #20125360
    +1

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

    И всё же, на что ориентирован данный подбор задач. Мне лично они показались тривиальными. Самое сложное было заметить что в задаче C числа 32-разрядные а не битные :)


  1. ViceCily
    07.05.2019 19:08
    #20125376
    -1

    Господа, ваши тесты и критерии оценки их решений зажаты строго в ваши рамки. Иначе как объяснить, что условие задачи из статьи про "скобки" абсолютно не говорит что требуется сделать и что имеем на входе. Эту информацию нужно выяснять где-то отдельно или быть автором задачи из Яндекс?


    1. ptyrss
      07.05.2019 19:10
      #20125392

      странно. Вроде бы всё написано было. «Дано целое число n. Требуется вывести все правильные скобочные последовательности длины 2 ? n, упорядоченные лексикографически». Самая первая строка. Формат ввода/вывода тоже есть.


      1. ViceCily
        08.05.2019 03:56
        #20126666

        Что из двух вариантов больше?
        ((()))
        (()())
        Как вы это определили из условия? По кодам ASCII? Но это не обозначено в условиях.


  1. Jigglypuff
    07.05.2019 19:32
    #20125482
    +6

    Disclaimer: Никакого хейта по отношению к Яндексу, их подходу к собеседованиям, конкретным собеседующим у меня нет. Все ниженаписанное — опыт одного человека, который не должен быть обобщен. Мнение сугубо субъективно.

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


    Это не совсем так. Расскажу про мой опыт собеседования в яндекс.

    Собеседование по скайпу:
    * Начали с ревью «плохого» кода на плюсах. Обсудили отсутствие виртуального деструктора, отсутствие проверки на самого себя в операторе присваивания, deep/shallow copy, сырые/умные указатели.
    * Теория алгоритмов и структур данных. Как внутри устроен квиксорт, что в нем и как. Красно-черное дерево, его нутрянка, гарантия балансируемости.
    * Три не особо сложных алгоритмических задачки. Про hashmap, про рекурсию что-то, ну и про бинарный поиск.

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

    Итог прохождения скайп-интервью: 1 час, 100% ответов, покрытые темы — знание специфики языка, его темные углы, теория алгоритмов и структур данных, практика алгоритмов и структур данных, глубокие технические моменты.

    Приглашение на очную встречу. 3 интервью по часу.

    1. Один удаленный собеседующий. Две задачи. Первая — на линал (которого в требованиях к вакансии не было, и который не повторялся). Вторая — на знание стандартного алгоритма (который я знал, но из-за предположения о том, что задача на динамическое программирование, отмёл). Интервьювер почти не задавал наводящих вопросов, на вопросы отвечал сжато.
    2. Два собеседующих. Три задачи. Первая — простая, на сортировку подсчетом. Вторую не особо помню, что-то про hashmap. Третья — на циклический буфер, но хитро поданная. Наводящие вопросы задавали, живо обсуждали решение, даже коснулись специфики языка.
    3. Два собеседующих. Две задачи. К сожалению, их я забыл, но тоже на алгоритмику.

    Итого, 7 задач на алгоритмику. Из них я решил 3.5 (в одной я озвучил решение, но не успел записать), в письме с результатом сообщили, что зачтены были 3.

    Итог прохождения очного интервью: 3.5 часа, 50% ответов, покрытие тем — знание линала, знание стандартных алгоритмов и умение их вспомнить в нужный момент, практика алгоритмов и структур данных, совсем чуть-чуть языковой специфики.

    Оффера не поступило.

    С моей точки зрения, не прошел собеседование я абсолютно справедливо.

    Однако, мне осталась непонятной некоторая однобокость: если бы те же 3 секции распределили как «знание языка программирования», «проектирование», «алгоритмы и структуры данных», то вполне возможно, что результаты были бы 80%/80%/50%. А может и нет. В любом случае, не было бы ощущения, что для работы важен только один навык, набиваемый, при желании, за 3 месяца на hackerrank (полноценно выучить плюсы сложнее, чем натренироваться решать задачки).

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

    Ну и, собственно, почему я пишу этот комментарий. Как мне кажется, процитированный в начале фрагмент, не совсем корректен. Алгоритмическая секция, по крайней мере в моем случае, была если не единственной (если учитывать скайп), то явно стояла во главе угла.
    Это не хорошо и не плохо, но на этом, как мне кажется, стоит всё-таки акцентировать внимание.

    Disclaimer again: Я не зол и не обижен на Яндекс за то, что я не прошел собеседование. Помимо Яндекса я в то время получил 2 весьма приятных оффера и в Яндекс, если честно, собеседовался из интереса. Это просто опыт одного собеседования, о котором мне захотелось рассказать, не более.


    1. GarfieldX
      07.05.2019 20:40
      #20125732
      +2

      На мой взгляд вообще хороший инженер, коим является разработчик, не тот кто все знает, а тот кто знает что нужно использовать, где посмотреть как и правильно применить. Ну не вспомню я сейчас на вскидку точно как работает квиксорт. Не нужно это сейчас. Есть туча готовых библиотек чтобы не изобретать велосипед. Раньше, в молодости, любил сам все реализовать, но сейчас это просто не нужно. Так же как и многое другое что любят спрашивать на собеседованиях тратя кучу времени и думая что получают какие то ответы.
      Так же когда-то, на собеседовании, не смог написать простейший запрос. Хотя дома у меня на эту фигню с созданием реальной БД и заполнением данными ушло не более 5 минут. Выгляде, наверное, идиотом. Забавно что следом устроился в материнскую компанию этой конторы и успешно проработал там 4 года.


      Самое классное собеседование в моей жизни было сразу с руководителем и следующим диалогом:


      • Хорошо знаешь %среда_разработки%?
      • Ммм… хорошо
      • Вот и чудненько

      Претензий потом не было.


    1. F0iL
      08.05.2019 09:40
      #20127188

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


  1. ExModE
    07.05.2019 19:36
    #20125506
    -2

    Спасибо за контест!

    Пришлось поломать голову над задачей F.
    Так вышло, что моя имплементация не проходила последний тест — time-limit-exceeded.

    Оказалось, что дело в количестве flush'ей.

    Стало неожиданностью, что тесты остальных задач не проверяют производительность IO.


    1. ptyrss
      07.05.2019 19:55
      #20125576

      С другой стороны IO вообще дурной тон на мой взгляд. В олимпиадах школьников в последние годы надо реализовать функцию в которую все данные уже прочитаны и переданы. Или наоборот, для чтения использовать функцию жюри. Почему это хорошо. На условном С++ слишком много манёвра для оптимизаций именно ввода/вывода. Банальная замена потоков на старые добрый scanf/printf может дать эффект. Про магию ускорений на уровне codeforces.com/blog/entry/5217?locale=ru и говорить не приходится. А иногда можно и ещё больше ускорить используя чтения по символу и преобразование в число…

      Я так иногда пропихивал (именно это слово) неоптимальный алгоритм именно таким методом.


      1. myxo
        07.05.2019 21:45
        #20125942

        Кстати, а в варианте, когда данные подаются через stdin или файл, меряется полное время выполнение программы? Ну то есть время разворачивания всяких питоновских интерпретаторов, jvm сюда входит?


  1. myxo
    07.05.2019 21:41
    #20125918

    У вас в задаче F постановочная бага (ну или тест на внимательность, не знаю). В общем она легко решается за n*k, причем решение гораздо легче приведенного тут.

    Там достаточно сохранять в массив сколько раз встречается число со входа. А потом вывести в stdout в отсортированном порядке.

    Псевдокодом примерно так
    int array[100] = {0};
read k
for i=1..k
  read n
  for j = 1..n
    read number
    array[number]++

for i = 1..100
  for j = 1..array[i]
    print(i)


    1. ptyrss
      07.05.2019 22:40
      #20126140

      скорее вынужденная мера. Сделали бы числа до 10^9 — размер файла раза в 3 увеличивать пришлось с данными. И тогда по времени прочитать не успевали бы.


      1. ashagraev Автор
        08.05.2019 02:14
        #20126560

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


  1. BalinTomsk
    07.05.2019 23:11
    #20126238

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

    Особенно если контрактник.

    Пришли к выводу что происходит вымывание специализаций.
    И большинство решает свои задачи гуглением по stackoverflow.


    1. BugM
      07.05.2019 23:31
      #20126300

      А меньшинство туда пишет.


  1. kyrylo
    08.05.2019 00:02
    #20126376

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

    На заре информатики такие финты ушами имели смысл: компьютерное время стоило дорого; подумай четырежды прежде чем компилировать и запускать программу. Инструментов для разработки было немного (или вообще не было). Однако мы живем в 2019 году. Умение пользоваться дебаггером должно приветствоваться. Это упрощает разработку и экономит время.

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


  1. moncruist
    08.05.2019 00:26
    #20126442

    Внесу свои пять копеек про собеседования в Яндексе на позицию С++ разработчика. Дело было в далеком 2016 году и, после интервью по скайпу, я был приглашен в офис для очного собеседования.
    Из того, что помню, спрашивали:

    • Написать свой unique_ptr на листе бумаги (да, я каждый день пишу кастомный умный указатель с его двумя специализациями, в каждом из которых по 6-7 конструкторов)
    • Написать что-то типа своего LRU кэша на доске. Эта задачка понравилась больше всего, так как интервьюер был живенький и охотно отвечал на уточняющие вопросы.
    • Нарисовать и разработать архитектуру распределенного хранилища (самое то для embedded developer'а)
    • Какая-то геометрическая задачка про нахождение центра множества точек (точное условие не помню)


    Офера не получил, но было интересно попробовать.

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

    В принципе, на эти алгоритмические задачки можно просто натренироваться по книжке типа Cracking The Coding Interview, но стоит ли оно того? Ну и видно, что задачки у них типовые и они не подстраиваются под бэкграунд кандидата.


  1. atoro
    08.05.2019 02:15
    #20126562

    А можно тупой вопрос от человека, который слишком долго стул грел в тихом омуте и от жизни порядком отстал, ко всем присутствующим — я по тексту так и не понял, задания контекста (за исключением первого) предполагают, что кандидат на какую позицию претендует — джуниор, миддл? Или там, что для Яндекса джуниор, для средней компании на миддла тянет…
    P.S. Вообще на мой дилетантский взгляд хабру немного не хватает «тэга-уровня» для материалов по программированию. Может и боян конечно, но часто читаешь что-то типа «С++ страдание» и по прочтении теряешь в догадках — то-ли радоваться, что не имея особого опыта в последние 5 лет в плюсах процентов на 90% автора понял, то-ли рвать волосы от стыда, что человек тебе разжевал всё, а ты проглотить не смог…


    1. ashagraev Автор
      08.05.2019 02:21
      #20126572

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


  1. kashey
    08.05.2019 02:45
    #20126598

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

    По своему опыту могу сказать, что умение писать "по плану" является признаком плохого программиста. Это называется Остапа понесло.


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


    Разница тут как между нарисовать сову методом scan line, и "итеративным" классическим образом. Можно даже сказать — по agile.


    1. GarfieldX
      08.05.2019 13:17
      #20128526
      +1

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


  1. kalombo
    08.05.2019 08:29
    #20126908
    +3

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


  1. theWaR_13
    08.05.2019 09:44
    #20127222

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

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


  1. QtRoS
    08.05.2019 09:57
    #20127300
    +1

    По поводу написания кода на бумаге или доске хотелось бы кое-что сказать.

    Однако, этот способ позволяет позволяет проверить два очень важных для каждого разработчика свойства.
    Свойства эти имеют опосредованное отношение к упражнению:
    Первое из них — умение быстро разбираться с работоспособностью кода «на глаз».
    А может лучше проверять умение разбираться с работоспособностью кода на глаз с помощью просмотра кода? Да ну, бред какой-то
    Второе важное свойство — способность заранее продумывать план решения и затем следовать ему.
    Интервью как раз про диалог, уточняющие вопросы, создание простого решения, его анализ, затем совершенствование. А тут про какой-то план речь…
    В реальной жизни всё это сильно замедляет разработку, но отчасти маскируется скоростью работы в редакторе кода
    Взять тот же кодинг-стрим geohot'a: он с практически молниеносной скоростью печати в основном гуглит документацию, возникающие ошибки или примеры кода библиотек. И конечно же код по ходу исправляется и рефачится. Интересно, на анонимном интервью отсеяли бы его? Чувствуется, запросто.


    1. Static_electro
      08.05.2019 11:52
      #20128034

      А вы бы лично наняли geohot'а «к себе», причём не как единственную и неповторимую звезду, а в команду?


      1. Whuthering
        08.05.2019 12:49
        #20128382

        Это вопрос уже больше из области soft skills, характеристик личности и командной работы. А топик-то именно о технических скиллах и их проверке.


      1. QtRoS
        08.05.2019 15:49
        #20129370

        Очень абстрактный вопрос, ответ зависит от команды и рода ее деятельности. Скорее команда не подойдёт ему (или другому абстрактному известному разработчику), чем он команде :) В моей текущей он почти наверняка бы заскучал — народ в финсекторе чаще из-за денег, а не призвания.


  1. sergeyns
    08.05.2019 10:35
    #20127568

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


  1. andrsam
    08.05.2019 10:52
    #20127690

    Когда я пишу о проверке с трассировкой, я имею в виду, например, такие ситуации, как off-by-one error в количестве итераций цикла. Да, такую ошибку очень легко установить трассировкой, но намного лучше уметь заметить её просто взглянув на код. Ещё лучше вообще не допустить :)

    ashagraev, существуют ли методики (литература на тему) предварительной оценки работоспособности кода до этапа компиляции(например, распознать упомянутую Вами off-by-one error)? Полагаю, что в спортивном программировании подобные практики должны существовать.


  1. KirillGerasimov
    08.05.2019 20:46
    #20130822

    Поделюсь своим опытом. Тоже заваливал алгоритмическую секцию в Яндексе, но задачки были посложнее. Вторая требовала выдумать алгоритм Алгоритм Рабина — Карпа. Алгоритм хоть и придумался (даже без наводящих вопросов), но реализовать его не успел.

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


  1. johnl
    08.05.2019 20:46
    #20130824

    К задаче F специально такое неэффективное решение за O(k*log(k)) написали? :) Ее же можно легко решить за O(k)


    1. ashagraev Автор
      08.05.2019 20:47
      #20130826

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


  1. bkh
    08.05.2019 22:17
    #20131118
    +3

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

    В целом, как мне кажется, большие IT компании стоят перед задачей найма программистов «потоком», для этого нужен какой-то более-менее стандартизированный метод оценки. Причем этот метод должен по-хорошему основываться на каких-то численных показателях для сравнения кандидатов друг с другом. В то же время, метод оценки программистов по количеству решенных алгоритмических задач не является идеальным. У него большой процент false negative ошибок, когда в целом хорошие программисты сталкиваются с проблемами при реализации чисто алгоритмических задач, а люди с олимпиадным прошлым получают бонус.
    Но, при всех своих недостатках этот метод работает. Тот кто решил все задачи с большой долей вероятности является неплохим разработчиком, даже с учетом того что в 95% случаев в работе умение решать такие задачи не требуется.

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