«Он, наверное, считает меня идиотом»: как 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 помог мне найти более точную формулировку моего вопроса для собеседований.

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

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