«Не нужно сложностей, чтобы принять решение»: вопрос, который я задавал кандидатам на собеседовании в Google

Software Engineering Manager Уильям Вен, который уже 13 лет работает в Google, провел более 200 собеседований для компании и оценил более 50 пакетов наймаФормы, которые новенький сотрудник должен заполнить перед официальным наймом. Также может содержать информацию о компании, должности и любую другую, связанную с работой. В своем блоге на Medium он поделился вопросом, который задавал кандидатам разного уровня — от стажеров до сеньоров. Передаем ему слово.

---

Понятно, что собеседование — стрессовое событие и для интервьюера, и для кандидата. Чтобы оценить друг друга, у нас есть меньше часа. И неудивительно, что иногда мы ошибаемся. 

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

В решении не более 30 строк кода, но они дают мне возможность правильно оценить кандидата на любую должность — от стажера до сеньора. 

Как именно? Это я и объясню ниже.

Предисловие

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

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

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

У Google есть шутка. Во время собеседования кандидату предлагается создать компилятор. Когда он выполнит задание, просят изменить цвет кнопки и переместить ее на два пикселя влево.

По моему опыту работы над фронтенд-программами, значительная часть работы FE/BE заключается в чтении/записи из хранилища данных или gRPC, преобразовании данных из одного Protocol Buffer в другой и отправке их клиенту для воспроизведения.

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

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

Вопросы по кодингу

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

Define a function f(a, x) that returns x, the next smallest number, or -1 for errors.

i.e.
f(a, 12) = 12
f(a, 13) = 12

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

Этот отсортированный массив выбран не случайно:

• отрицательные числа и ноль не придают ценности вопросу и игнорируются;
• есть ровно одиннадцать элементов, поэтому индексы от 0 до 10, и разделить на два — легко;
• 12 — это середина, которая и есть первый тестовый случай;
• второй тестовый случай — 13, поскольку он требует изменения направления средней точки бинарного поиска вправо, а затем влево. 

Я начинаю с того, что спрашиваю кандидата о тестовых случаях, как те, которые я предоставил для x = 12 и x = 13.

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

Как правило, после некоторых подсказок, мы получаем следующий список:

f(a, 12) = 12    // number found
f(a, 13) = 12    // smaller number found
f(a, 2) = -1     // out of bounds too small
f(a, 22) = 21    // out of bounds too large
f(a, 3) = 3      // exact left boundary
f(a, 21) = 21    // exact right boundary
f([], x) = -1    // empty array
f(null, x) = -1  // invalid input

Вы можете не поверить, но большинство разработчиков не может составить полный список. Некоторые забывают точные предельные случаи 3 и 21 или слишком большие/малые случаи. Некоторые — недопустимые входные данные. Некоторые используют метод перебора f(a, x), где x = Int.MIN до Int.MAX.

А кто-то даже не понимает, о чем я прошу. Каждая ошибка рассказывает мне, какой у вас опыт кодинга.

Далее поговорим об алгоритме. Да, мы можем использовать метод перебора и задать цикл for на O(n).

Такой ответ приемлем для самых младших интернов. Я проводил собеседования в HBCU Общее название для учреждений высшего образования в США, которые были основаны в Акте о гражданских правах 1964 года с намерением в первую очередь обслуживать афроамериканцев, где молодежь только начинает знакомиться с программированием. Хорошо написанное решение для цикла for и умение дебажить тестовые примеры означало для них найм.

Для всех остальных — переходим к решению двоичного поиска O(log n). Я разрешу кандидату обсудить алгоритм, смогу убедиться, что он на правильном пути, а потом попрошу код.

Попытайтесь и вы сейчас выполнить эту задачу. 

С возвращением!

• Итак, сколько времени вам понадобилось? Больше 30 минут? Больше часа?
• Сработал ли ваш алгоритм с первой попытки?
• Учитывает ли вычисление средней точки как движение влево, так и вправо?
• Вы выбрали итерационное решение?
• Вы попали в бесконечный цикл?
• Или вы выбрали рекурсивное решение?
• Тогда вы добавили вспомогательный метод?
• Как вернули меньшее число?
• Вы не забыли вернуть рекурсивное значение?
• Прошел ли ваш код восемь тестов, или вам пришлось добавить специальные предложения if/ else?

Не волнуйтесь, мне тоже было тяжело первый раз.

Тест на омлет

Много лет назад я прочитал книгу «Становление шеф-повара». Там рассказывалось о трех разных способах стать поваром:

1. Первый: вы можете сдать экзамен на сертифицированного мастера-повара.
2. Второй — сделать как Майкл Саймон, опытный шеф-повар: он владелец ресторанов и медийная личность, часто появляющаяся в телевизоре.
3. А яркий пример третьего способа — Томас Келлер, который начинал как посудомойщик, а затем учился у французских шеф-поваров, чтобы стать одним из лучших в мире.

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

В фильме «Пряности и страсти» главного героя Хасана Кадама попросили приготовить омлет. Так мадам Мэллори смогла решить, стоит ли ей нанимать его.

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

Решение

Есть много возможных решений, но самое простое итерационное решение должно выглядеть так:

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, и содержимое цикла while должно выполняться. Увеличение и уменьшение середины 1 также важно: это позволяет избежать бесконечных циклов.

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

Те, у кого больше опыта, могут добавить проверку предварительных условий, чтобы четко описать предельные случаи:

// Precondition checks
// f(null, x), f([], x)
if (a == null || a.length == 0) return -1; 
// f(a, 2)
if (x < a[0]) return -1;
// f(a, 3)
if (x == a[0]) return a[0];
// f(a, 21), f(a, 22)
if (x >= a[a.length - 1]) return a[a.length - 1];

Почему бинарный поиск?

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

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

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

«… в истории в главе 6.2.1 книги Sorting and Searching Кнут указывает, что первый двоичный поиск был опубликован в 1946 году, но первый опубликованный двоичный поиск без ошибок появился только в 1962 году»

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

Но погодите, в вышеприведенном решении все еще есть ошибка. Заметили?

В 2006 году Джошуа Блох, главный архитектор Google Java, автор Effective Java, обнаружил, что реализация Java содержала скрытую ошибку в течение девяти лет! Расчет средней точки вызвал ошибки целых чисел вне диапазона для современных наборов данных большого размера:

var mid = Math.floor(low + high) / 2); // bad
var mid = low + Math.floor((high - low) / 2); // good

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

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

Обратите внимание, что в комитете Google по найму на работу у вас есть 24 часа: вы должны просмотреть четыре пакета собеседований с пятью собеседованиями в каждом. Итак, всего 20 интервью. И в это же время вы выполняете и основные рабочие задачи, и должны успевать отдохнуть.

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

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

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

Я обращаю внимание на:  

• Разумные имена функций и переменных. Не очень хорошо, когда есть длинные имена, например, функция Find_X_Or_Next_Smallest_Impl_Factory_Builder_Singleton(…)
• Открытые фигурные скобки закрыты для функции, while, if, else и т.д., остается достаточно места для заполнения оставшегося кода.
• Знание, что индексы массива — от 0 до length-1.
• Переменные имеют область применения и инициируются правильными значениями.
• Использование == в операторах if, а не только =. Скобки открываются и закрываются.
• Надлежащее отступление кода и/или точка с запятой, если это уместно.
• Читаемость кода. Вы писали if (a[mid] < x) или if (x > a[mid])? 

А еще я буду принимать во внимание следующее:

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

Ожидание для кандидатов с разным опытом

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

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

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

Если это собеседование с PM или Engineering-менеджером, я бы несколько корректировал свои ожидания, в зависимости от их уровня. Эти люди должны понимать, как кодить, но не делать это идеально. 

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

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

P. S.

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

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

Текст адаптировала Евгения Козловская

Читайте также: «Он, наверное, считает меня идиотом»: как ChatGPT проходил собеседование в Google и отвечал на коварные вопросы