Software Engineering Manager Уильям Вен, который уже 13 лет работает в Google, провел более 200 собеседований для компании и оценил более 50 пакетов найма
Понятно, что собеседование — стрессовое событие и для интервьюера, и для кандидата. Чтобы оценить друг друга, у нас есть меньше часа. И неудивительно, что иногда мы ошибаемся.
Поэтому на протяжении многих лет я задаю один вопрос по кодингу, который мне очень нравится. Он выглядит просто, но на самом деле это не так.
В решении не более 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 и есть ли у вас докторская степень. Это важно, потому что мне не нужно тратить время на объяснение вопроса на собеседовании.
Этот отсортированный массив выбран не случайно:
Я начинаю с того, что спрашиваю кандидата о тестовых случаях, как те, которые я предоставил для 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). Я разрешу кандидату обсудить алгоритм, смогу убедиться, что он на правильном пути, а потом попрошу код.
Попытайтесь и вы сейчас выполнить эту задачу.
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, написал в своей книге «Жемчужины программирования», что только 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.
Моя цель — не похвастаться, какой замечательный вопрос я придумал для собеседований. Я хочу подчеркнуть, что вам не нужен сверхсложный вопрос, чтобы принять решение. Смотрите не только код, который пишет кандидат, но и то, как он его пишет, как ищет ошибки.
Насколько я знаю, один из моих старых товарищей по команде все еще использует этот вопрос. Так что успехов ему и вам также, если вы проходите собеседование в Google.
Текст адаптировала Евгения Козловская
Читайте также: «Он, наверное, считает меня идиотом»: как ChatGPT проходил собеседование в Google и отвечал на коварные вопросы
Прокси (proxy), или прокси-сервер — это программа-посредник, которая обеспечивает соединение между пользователем и интернет-ресурсом. Принцип…
Согласитесь, было бы неплохо соединить в одно сайт и приложение для смартфона. Если вы еще…
Повсеместное распространение смартфонов привело к огромному спросу на мобильные игры и приложения. Миллиарды пользователей гаджетов…
В перечне популярных чат-ботов с искусственным интеллектом Google Bard (Gemini) еще не пользуется такой популярностью…
Скрипт (англ. — сценарий), — это небольшая программа, как правило, для веб-интерфейса, выполняющая определенную задачу.…
Дедлайн (от англ. deadline — «крайний срок») — это конечная дата стачи проекта или задачи…