«Не треба складнощів, щоб ухвалити рішення»: питання, яке я ставив кандидатам на співбесіді в 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 та відповідав на підступні питання