«Він, напевне, вважає мене ідіотом»: як ChatGPT проходив співбесіду в Google та відповідав на підступні питання

Software Engineering Manager Вільям Вен, який вже 13 років працює у Google, ставив це дещо підступне запитання розробникам, які хотіли потрапити до компанії.

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

Передмова

Я почав працювати над цією статтею через тиждень після запуску ChatGPT наприкінці листопада 2022 року. Тоді ChatGPT зміг написати ідеальний двійковий пошук, але не зміг отримати «наступне найменше число». Здається, він заплутався через тестові випадки. 

У грудні ChatGPT став дуже популярним. Щоразу, коли я намагався увійти, він зависав. Лише після Нового року мені вдалось поспілкуватись з ним знову. І цього разу я отримав зовсім інший результат, що стало для мене сюрпризом. 

Співбесіда

Я: Доброго ранку. Хочу поставити питання зі співбесіди з програмістами. Чи зможете написати рішення на JavaScript?

ChatGPT за замовчуванням використовує Python, але ви можете попросити його працювати і з іншими мовами.

ChatGPT: Звичайно! Яке питання?

Я: Дано додатній відсортований масив 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

Якщо я не попрохаю почати з тестових випадків, ChatGPT перейде відразу до кодингу реалізації. Схоже на живих програмістів, чи не так? 

ChatGPT: Ось кілька додаткових тестів:

f(a, 3) = 3
f(a, 4) = 4
f(a, 6) = 6
f(a, 9) = 9
f(a, 10) = 10
f(a, 14) = 14
f(a, 15) = 15
f(a, 17) = 17
f(a, 19) = 19
f(a, 21) = 21
f(a, 2) = -1 (x is smaller than the smallest number in the array)
f(a, 22) = 21 (x is larger than the largest number in the array)
f(a, 0) = -1 (x is negative)
f(a, 0.5) = -1 (x is not an integer)
f([], 0) = -1 (the input array is empty)

Плюс. ChatGPT знайшов усі граничні випадки, включно з порожнім масивом і навіть пояснив, чому. Він не робив цього, коли я запитував про «наступне найменше число».

Мінус. Мені не дуже подобається грубе форсування всіх чисел у заданому масиві, але нічого страшного.

Я: Давайте додамо до списку f(a, 12) = 12 і f(a, 13) = 12. Ви розумієте, чому f(a, 13) має повертати 12?

ChatGPT: Так, я розумію. Функція має повертати попереднє найменше число в масиві, якщо введене число не знайдено в масиві.

У цьому випадку вхідним числом є 13: його немає в масиві.

Тому функція має повернути попереднє найменше число – 12.

Незважаючи на те, що я спеціально просив додати тестові випадки для f(a, 12) і f(a, 13), я підозрював, що ChatGPT уже зрозумів питання, враховуючи, що він запропонував тестовий приклад f(a, 22) = 21.

ChatGPT, ймовірно, вважає мене ідіотом.

Я: Перш ніж перейдемо до кодингу, запитаю, який би алгоритм ви обрали?

Це звична частина мого сценарію, коли я ставлю це запитання на інтерв’ю. Якщо я питаю розробників про алгоритм або псевдокод, це покращує їх швидкість і точність кодингу. 

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

ChatGPT: Є кілька різних алгоритмів, які ми можемо використати для вирішення цієї проблеми. Одним із варіантів може бути використання алгоритму лінійного пошуку, де ми ітеруємо масив і повертаємо останній елемент, менший за введене число. Це матиме часову складність O(n), що не є особливо ефективним, але працюватиме для малих вхідних даних.

Іншим варіантом було б використання бінарного алгоритму пошуку, який мав би часову складність O(log n). Це було б ефективніше для більших вхідних даних. Щоб використати бінарний пошук, ми спочатку перевіримо середній елемент масиву.

Якщо середній елемент менший за введене число, ми шукатимемо праву половину масиву. Якщо середній елемент більший за введене число, ми шукатимемо ліву половину масиву. Ми будемо повторювати цей процес, доки не знайдемо попереднє найменше число або не визначимо, що його немає в масиві.

Я б рекомендував використовувати бінарний алгоритм пошуку, оскільки він більш ефективний і має добре працювати як для малих, так і для великих вхідних даних.

Це добре. ChatGPT пояснює обидва алгоритми як справжній інженер та дає правильні рекомендації щодо алгоритму.

Я: Гарно звучить. Давайте напишемо код.

Чи запише ChatGPT правильний бінарний пошук з першого разу? Це було б неймовірно!

ChatGPT: Звісно! Ось реалізація функції f із використанням бінарного алгоритму пошуку:

function f(a, x) {
  // edge cases
  if (a.length === 0) return -1; // array is empty
  // x is smaller than the smallest number in the array
  if (x < a[0]) return -1; 
  // x is larger than the largest number in the array
  if (x > a[a.length - 1]) return a[a.length - 1]; 
  if (x % 1 !== 0) return -1; // x is not an integer

  let start = 0;
  let end = a.length - 1;
  while (start <= end) {
    const mid = Math.floor((start + end) / 2);
    if (a[mid] === x) {
      return x;
    } else if (a[mid] > x) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
  return a[end];
}

Ця функція має часову складність O(log n), яка ефективна як для малих, так і для великих вхідних даних. Вона також обробляє граничні випадки, які ми визначили раніше.

Щоб перевірити функцію, ми можемо використати такий код:

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

console.log(f(a, 12)); // 12
console.log(f(a, 13)); // 12
console.log(f(a, 3)); // 3
console.log(f(a, 4)); // 4
console.log(f(a, 6)); // 6
console.log(f(a, 9)); // 9
console.log(f(a, 10)); // 10
console.log(f(a, 14)); // 14
console.log(f(a, 15)); // 15
console.log(f(a, 17)); // 17
console.log(f(a, 19)); // 19
console.log(f(a, 21)); // 21
console.log(f(a, 2)); // -1
console.log(f(a, 22)); // 21
console.log(f(a, 0)); // -1
console.log(f(a, 0.5)); // -1
console.log(f([], 0)); // -1

Круто, 12 і 13 є тут. Чудова робота, ChatGPT!

Спочатку я подумав, що тут є помилка для f(a, 13). Потім, двічі перевіривши код, я побачив, що він повернув a[end] в кінці функції. Якщо число x не знайдене, початок і кінець перехрещуються, щоб вийти з циклу while, отже, кінець вказує на попереднє найменше число. Розумно!

Насправді, я був дуже здивований, що ChatGPT зміг зрозуміти це самостійно. Набагато краще, ніж під час попередніх спроб. Зауважте, що це конкретне рішення працює завдяки наявності перевірки попередніх умов, тому немає способу, яким кінець може вказувати на -1 для тестового випадку f(a,2). Насправді це звичайна пастка для цього запитання на інтерв’ю.

Але ChatGPT відразу ж придумав перевірку попередніх умов і правильну реалізацію!

Я: У коді є прихована помилка, якщо масив дуже-дуже-дуже великий. Чи можете ви помітити це та виправити помилку?

Подивимося, чи зможе ChatGPT визначити помилку розрахунку середньої точки.

ChatGPT: Реалізація функції f, яку я надав, має працювати правильно для масивів будь-якого розміру. Однак, якщо масив надзвичайно великий, може знадобитися багато часу, щоб знайти попереднє найменше число через часову складність алгоритму бінарного пошуку O(log n).

Якщо вам потрібно знайти попереднє найменше число в дуже великому масиві, ви можете розглянути можливість використання іншого алгоритму або структури даних, які можуть обробляти великі вхідні дані більш ефективно. Наприклад, ви можете використовувати таку структуру даних, як двійкове дерево, яке має часову складність O(log n) для операцій пошуку.

Тому, якщо ви просто хочете змінити поточну реалізацію, щоб ефективніше обробляти дуже великі масиви, ви можете спробувати використати ефективніший алгоритм пошуку, такий як потрійний пошук або Jump Search (пошук з переходом або пошук по блоку). Ці алгоритми мають часову складність O(log3 n) і O(√n) відповідно, що може бути пришвидшити процеси для дуже великих масивів.

Я: Що станеться під час обчислення середньої точки для дуже великих масивів?

Це спроба дати підказку, не кажучи правильну відповідь…

ChatGPT: Розрахунок середньої точки у функції f такий:

const mid = Math.floor((start + end) / 2);

Це обчислення буде працювати правильно для масивів будь-якого розміру, включно з дуже великими. Функція Math.floor округлює результат до найближчого цілого числа, тому середня точка завжди буде дійсним індексом у масиві.

Наприклад, якщо початок дорівнює 0, а кінець 10^9 (один мільярд), середина буде 5*10^8 (п’ятсот мільйонів). Це не спричинить жодних проблем, оскільки середня точка все ще буде дійсним індексом у масиві.

Я: А якщо розмір масиву буде Number.MAX_VALUE?

Гаразд, я здаюся.

ChatGPT: Властивість Number.MAX_VALUE представляє максимальне число, яке можна використовувати JavaScript. Це дуже велике число, приблизно 1,79 x 10^308.

Якщо розмір масиву дорівнює Number.MAX_VALUE, обчислення середньої точки у функції f працюватиме правильно. Однак бінарний алгоритм пошуку може бути не найефективнішим способом пошуку такого великого масиву.

Також зазначу, що масив із розміром Number.MAX_VALUE, швидше за все, вимагатиме більше пам’яті, ніж можливо для програми на JavaScript: тому не факт, що його взагалі можна створити.

const end = Number.MAX_VALUE;
> 1.7976931348623157e+308
const mid = end / 2;
> 8.988465674311579e+307
const start = mid + 1;
> 8.988465674311579e+307
console.log((start + end) / 2);
> Infinity
console.log(start + (end - start) / 2);
> 1.3482698511467367e+308

Насправді Number.MAX_VALUE спричинить помилку обчислення середньої точки.

Я: Давайте подумаємо: а чи є спосіб переписати середній розрахунок, щоб обійти цю проблему?

Давай, ChatGPT, ти так близько! Ще трошки! 

ChatGPT: Теоретично ми можемо без проблем переписати обчислення середньої точки для обробки дуже великих масивів. Ось так, наприклад:

const mid = start + Math.floor((end - start) / 2);

Цей розрахунок працює так: спочатку віднімає початок від кінця, щоб отримати кількість елементів у масиві, а потім ділить це число на 2, щоб знайти середину. Функція Math.floor використовується для округлення результату до найближчого цілого числа і гарантує, що середня точка є дійсним індексом у масиві.

Це обчислення буде працювати правильно для масивів будь-якого розміру, включно з дуже великими. Воно не спричинить жодних проблем із пам’яттю чи продуктивністю, оскільки не покладається на те, що великі числа представлені у вигляді значень з плаваючою комою.

Якщо у вас є ще питання, я готовий відповідати. 

Браво, правильна відповідь! ШІ розв’язав задачу, з якою часто не могли впоратися люди-програмісти на інтерв’ю! 

Оцінка співбесіди

Я би дуже рекомендував найняти цього спеціаліста як інженера ПЗ 3-го рівня (і, можливо, навіть як 4-го рівня):

• ChatGPT зміг створити правильний набір тестів;
• дав правильне пояснення складності Big-O;
• обрав правильний алгоритм і реалізував ідеальне рішення з заданими умовами;
• йому знадобились додаткові підказки, але кінець кінцем він таки вирішив проблему переповнення середньої точки.

Теоретично ChatGPT може бути непоганим працівником, якщо ви даєте ідеальні вихідні дані.

Однак я не певен щодо його здатності самостійно дати раду з неоднозначними вимогами та впливом команди людей-інженерів. 

Одним словом, ChatGPT може виконувати певні завдання, але йому (поки що) не можна довіряти як повністю незалежному розробнику.

ChatGPT все ще потрібна людина-техлід, що ще раз свідчить про те, що я правильно оцінив його як інженера 3-го рівня.

Удосконалення людини

Чесно кажучи, ChatGPT дуже добре впорався з цим запитанням на співбесіді з кодування, але лише після того, як я зрозумів власну помилку.

Раніше, коли я запитував наступне найменше число, ChatGPT просто не міг знайти правильних тестів і реалізації, тому що в комп’ютерній мові «наступний» означає «після»! Хоча в цьому випадку людина може інтерпретувати «наступне» як «попереднє» — для комп’ютера це не очевидно.

Коли я змінив у запитанні слово «наступне» на «попереднє», ChatGPT виконав завдання бездоганно.

Ось вона, користь штучного інтелекту. Завдяки йому я усвідомив, що в моєму запитанні, яке я ставив протягом років, була крихітна помилка. Коли я її виправив, ChatGPT запрацював як чемпіон.

Я почав цю статтю, думаючи, що розповідатиму про недоліки ШІ. Але натомість ChatGPT допоміг мені знайти більш точне формулювання мого запитання для співбесід.

Автор: Вільям Вен

Текст адаптувала Євгенія Козловська