Моя любимая задачка по программированию для кодинг-интервью

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

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

В этой статье будут вещи, с которыми вы можете не согласиться. Это нормально. Это просто моё мнение, а так как я уже вышел на пенсию, то больше не представляю опасности ни для интервьюеров, ни для инженеров Google при принятии решений о найме! ;-)

Пара слов обо мне

Когда я был начинающим инженером, я регулярно читал сайт joelonsoftware.com. Одной из статей, которая оставила у меня неизгладимое впечатление, был гайд по проведению собеседований. Самое важное решение, которое ты можешь принять менее чем за час, — нанимать или не нанимать, исходя из того, умён ли человек и может ли он довести дело до конца. Позволяет ли собеседование убедиться и в том, и в другом?

Лично я пришел в кодинг из электроники. Записался на курсы по структурам данных и даже написал программу решения лабиринта для нашего выпускного проекта Micromouse. У меня не было формального образования в компьютерной сфере, и хотя программа работала отлично (заставить электроаппаратуру работать было на порядок сложнее!), я не смог бы назвать алгоритм, который я использовал. Поэтому я предпочитаю держаться подальше от вопросов, которые проверяют, проходил ли кандидат конкретные курсы по CS. Это не моя самая сильная сторона.

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

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

Внимание, вопрос!

У нас есть массив, отсортированный по возрастанию:

a = [ 3, 4, 6, 9, 10, 12, 14, 15, 17, 19, 21 ];

Определите функцию f(a, x), которая возвращала бы x, ближайшее наименьшее число или -1 в случае ошибки.

То есть:

f(a, 12) = 12
f(a, 13) = 12

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

Массив, фигурирующий в задаче, составлен нарочно таким образом, чтобы не включать 0 и отрицательные числа – это не добавило бы к решению задачи ровным счетом ничего. Элементов в массиве 11, что дает нам пространство индексов от 0 до 10. 10 легко делится на 2, поэтому среднюю точку можно определить без проблем – это число 12. Оно находится ровно посередине списка – это наш первый тест-кейс. А следующий пример, число 13, требует провести поиск уже в другой половине элементов. Все эти маленькие тонкости будут направлять интервью в нужное русло.

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

f(a, 12) = 12       // Найдено заданное число
f(a, 13) = 12       // Найдено меньшее число
f(a, 2) = -1        // Число слишком мало и выходит за границы массива
f(a, 22) = 21       // Число слишком велико и выходит за границы массива
f(a, 3) = 3         // Левая граница массива
f(a, 21) = 21       // Правая граница массива
f([], x) = -1       // Массив пуст
f(null, x) = -1     // Неверные аргументы

Верьте или нет, большинство разработчиков не в состоянии составить этот список до конца. Кто-то забывает о границах массива. Кто-то игнорирует слишком большие или малые значения x. Некоторым кандидатам не приходит в голову проверить вводимые данные на правильность. Отдельные уникумы и вовсе занимаются брутфорсом: f(a, x), где x = Int.MIN до Int.MAX.

Еще кое-кто не понимает, чего я от них добиваюсь таким вопросом. 

А на деле из каждой реакции, каждого «сигнала» я получаю массу дополнительной информации о кандидате.

Затем мы переходим к обсуждению алгоритма. Да, можно написать что-то вроде цикла for для O(n). Если я собеседую молодого и зеленого стажера, это вполне приемлемый ответ.  Одно время я занимался собеседованием студентов колледжей, и могу вам сказать: хорошо составленный цикл и умение отладить его для всех тест-кейсов – это гарантированный оффер.

Что касается более опытных кандидатов – от них я хотел бы видеть реализацию двоичного поиска: O(log n). Сначала мы обсуждаем алгоритм, я убеждаюсь, что человек мыслит в правильном направлении, и лишь затем прошу написать код. Если всё идет по плану, можно запустить готовый вариант и произвести отладку для всех восьми тест-кейсов. Я в этот момент отхожу в сторонку и наблюдаю.

Добро пожаловать обратно

Итак, долго ли вы писали код? Процесс занял полчаса? Или даже целый час? А алгоритм заработал как надо с первого раза? Вычисление средней точки корректно работает для элементов из обеих половин? Вы прибегли к итеративному решению? А учли ли возможность попасть в бесконечный цикл? Или же вы выбрали рекурсивный подход? А вспомогательный метод создали? Как вы находите меньшее значение? Проходит ли ваш код все 8 тестов, или пришлось добавить специальные if/else для ряда случаев? Не переживайте. В первый раз, когда я решал эту задачу, я страдал не меньше вашего.

Омлетный тест

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

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

В фильме The Hundred-Foot Journey (примечание переводчика: в России известен под названием «Пряности и страсти») главного героя, Хасана Кадама, попросили приготовить омлет. С одного укуса мадам Мэллори (её играла Хелен Миррен) понять, стоит ли ему работать у нее на кухне.

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

Решение

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

function f(a, x) {
  if (a == null || a.length == 0) return -1;
  var answer = -1;
  var low = 0;
  var high = a.length — 1;
  while(low <= high) {
    var mid = Math.floor((low + high) / 2);
    if (a[mid] == x) {
      return x;
    } else if (a[mid] < x) {
      answer = a[mid];
      low = mid + 1;
    } else {
      high = mid — 1;
    }
  }
  return answer;
}

Что касается двоичного поиска – он выглядит примерно как while(low <= high), делим на две части, пока не найдем искомое число. 

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

Найти же следующее наименьшее число – чуть более сложная задача. Грамотным решением будет объединить линейный поиск с двоичным, инициализировать answer как -1, затем обновлять значение переменной всякий раз, когда a[mid] будет меньше, чем x. Если x не удастся найти, ответом всегда будет наименьшее обнаруженное значение.

Еще более опытные специалисты могут добавить дополнительные проверки для проверки граничных значений x.

// Например, вот так:
  if (a == null || a.length == 0) return -1;        // f(null, x), f([], x)
  if (x < a[0]) return -1;                          // f(a, 2)
  if (x == a[0]) return a[0];                       // f(a, 3)
  if (x >= a[a.length — 1]) return a[a.length — 1]; // f(a, 21), f(a, 22)

Зачем использовать двоичный поиск

Двоичный поиск относится к одной из самых сложных «простых» проблем программирования. Алгоритм выглядит тривиально, но реализовать его — сущий ад. Джон Бентли, бывший профессор CMU, в своей книге Programming Pearls написал, что только 10% профессиональных программистов способны правильно его реализовать, в том числе и аспиранты.

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

В своей книге он написал, что специалистам потребовалось 16 лет, чтобы написать алгоритм без ошибок!

« ... в разделе 6.2.1 книги «Сортировка и поиск», Кнут отмечает, что, хотя первая реализация двоичного поиска и была опубликована в 1946 г., первый опубликованный вариант без ошибок появился только в 1962 году».

Джон Бентли, «Жемчужины программирования» (издание первое)

Но погодите-ка, в приведенном выше решении все же есть одна небольшая ошибка. Сумеете её найти?

В 2006 году Джошуа Блох, главный Java-архитектор Google, автор книги «Эффективный Java» и бывший аспирант Бентли, раскрыл, что в течение девяти лет Java содержала скрытый баг! Вычисление средней точки приводило к выходу за границы массива при работе на больших объемах данных!

var mid = Math.floor(low + high) / 2);         // плохо
var mid = low + Math.floor((high — low) / 2);  // хорошо

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

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

Нанимать или не нанимать?

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

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

Вот список самых простых сигналов, которые я жду от кандидата:

• Адекватные имена переменных и функций. Find_X_Or_Next_Smallest_Impl_Factory_Builder_Singleton(...) однозначно не проходит.

• Скобки, обрамляющие функции, циклы и условия, закрыты, а весь нужный код помещен внутри.

• Кандидат в курсе, что индексы массива начинаются с 0, а заканчиваются на количестве элементов массива — 1.

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

• Кандидат использует  == в условиях, а не просто =. Скобки открываются и закрываются там, где надо.

• В коде правильно сделаны отступы и/или точки с запятой

• Код читаемый и ясный. Как бы вы написали:  if (a[mid] < x) или  if (x > a[mid])? Один из вариантов читается намного проще.

И еще парочка сигналов другого рода:

• Полнота в определении всех тест-кейсов.

• Общее понимание процесса: от постановки задачи до тестирования и реализации.

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

• Общие коммуникационные навыки.

• Умение не зацикливаться на ошибках и быстро двигаться вперед.

• Умение писать простой код без спагетти из тысячи if/else.

Мои ожидания для каждого уровня кандидата

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

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

Что касается старшего инженера L5, то он должен быть в состоянии провести собеседование до конца и закончить его с достаточным количеством оставшегося времени для вопроса о проектировании систем. Скорее всего, такие кандидаты напишут предварительные условия и будут знать об ошибке переполнения средней точки. Могут быть мелкие недочёты/ошибки, но прогресс должен быть быстрым.

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

Послесловие

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

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

Благодарности

Я сам узнал об этом вопросе от коллеги из Google. К сожалению, за давностью лет я уже не помню его имя. В любом случае – спасибо тебе!