Мой вопрос с кодинг интервью в Google

Я провел более 200 собеседований в Google и оценил более 50 пакетов с интервью. Ясно одно: проводить интервью тяжело. Сигналов слишком много. И у интервьюера, и у интервьюируемого есть меньше часа, чтобы сделать все возможное. Иногда по разным причинам мы получаем ложные или неточные сигналы. Такова природа человека.

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

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

Предварительный сценарий

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

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

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

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

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

Задача

Дан положительно отсортированный массив a = [ 3, 4, 6, 9, 10, 12, 14, 15, 17, 19, 21 ]

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

Например:

f(а, 12) = 12
f(а, 13) = 12

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

Данный отсортированный массив представлен специально. Отрицательные числа и ноль не добавляют ценности вопросу и игнорируются. Элементов ровно одиннадцать, поэтому индексы от 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, где второкурсники буквально берут свои первые уроки в программировании. Хорошо написанное решение с циклом for и отладкой тестовых случаев будет для них наймом.

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

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

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

Омлет-тест

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

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

В «Пряности и страсти» главного героя Хасана Кадама попросили приготовить омлет. По одному кусочку мадам Мэллори (которую играет Хелен Миррен) смогла решить, стоит ли ему работать на ее кухне.

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

Решение

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

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, написал в своей книге Programming Pearls, что только 10% профессиональных программистов способны правильно его реализовать.

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

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

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

Но подождите, в решении выше все еще есть ошибка. Вы можете найти ее?

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

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

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

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

(Обратите внимание, что в комитете по найму Google у вас есть 24 часа, чтобы просмотреть 4 пакета по 5 интервью в каждом. Таким образом, вы должны оценить 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])? Один вариант читается намного легче, чем другой.
• Использование вспомогательной функции и оператора возврата при выборе рекурсии, но я отвожу людей от этого.

Другие сигналы, которые я ищу:

• Полнота определения тестовых случаев.
• Общее понимание и переход от тестовых случаев к коду и отладке.
• Возможность использовать доску для отладки и объяснения бинарного поиска.
• Общие коммуникативные навыки и реакция на мои подсказки.
• Умение замечать и исправлять ошибки, уверенно двигаться вперед.
• Делать вещи простыми вместо спагетти-кода из операторов if/else.

Выравнивание ожиданий

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

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

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

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

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

Постскриптум

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

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

Источник