Cложить два числа-гиганта или почему я прошел квест на собеседовании а на работу в BigTech взяли ChatGPT?

Евгений Жуков (@EvgeniiZhukov) написал статью «Сложить два числа‑гиганта: как я прошел квест на собеседовании в Бигтех».

Краткое содержание:

Сценарий: вы на собеседовании, ожидаете вопросов про React, WebGL или хотя бы про Event Loop. А вместо этого получаете: «Напишите функцию сложения двух чисел в столбик, но числа передаются как массивы.»

Зачем это вообще кому‑то нужно:

А интервьюер смотрит, как вы справляетесь с базовой задачей, которая проверяет:

1. Умение работать с строковыми данными (ведь числа могут быть гигантскими, и bigint не спасет).

Предложенное решение:

function addArrays(arr1, arr2) { let i = arr1.length - 1; let j = arr2.length - 1; let carry = 0; const result = [];   while (i >= 0 || j >= 0 || carry > 0) { const digit1 = i >= 0 ? arr1[i--] : 0; // Берем цифру или 0 (как замену) const digit2 = j >= 0 ? arr2[j--] : 0; const total = digit1 + digit2 + carry; // Сумма + 1 из прошлого carry = Math.floor(total / 10); // Новый 1 result.push(total % 10); // Записываем остаток } return result.reverse(); // Переворачиваем } 

Тесты:

[9,9] + [9] = [1,0,8]. [5,4,4]  [4,5,6] = [1,0,0,0] 

Следующий кандидат — ChatGPT

Парень из BigTech:

Напишите функцию сложения двух чисел в столбик, но числа передаются как массивы.

function addColumnwise(arr1, arr2) {     let carry = 0;     let result = [];     let maxLength = Math.max(arr1.length, arr2.length);      for (let i = 0; i < maxLength; i++) {         let digit1 = arr1[arr1.length - 1 - i] || 0;         let digit2 = arr2[arr2.length - 1 - i] || 0;         let sum = digit1 + digit2 + carry;          result.unshift(sum % 10);         carry = Math.floor(sum / 10);     }      if (carry) {         result.unshift(carry);     }      return result; }  // Пример использования console.log(addColumnwise([1, 2, 3], [9, 8, 7])); // [1, 1, 1, 0] console.log(addColumnwise([9, 9], [1])); // [1, 0, 0]

Добавь тестовые функции чтобы проверить что все работает.

Hе используй тестовые модули.

Просто добавь вызов функций с параметрами arr1,arr2 и expected.

Выведи в консоль: OK или Failed.

// Функция тестирования function testAddColumnwise(arr1, arr2, expected) {     const result = addColumnwise(arr1, arr2);     const success = JSON.stringify(result) === JSON.stringify(expected);     console.log(`Test ${success ? 'OK' : 'Failed'}:`, arr1, '+', arr2, '=', result, '| Expected:', expected); }  // Запуск тестов testAddColumnwise([1, 2, 3], [9, 8, 7], [1, 1, 1, 0]); testAddColumnwise([9, 9], [1], [1, 0, 0]); testAddColumnwise([0], [0], [0]); testAddColumnwise([5, 6, 7], [2, 4, 3], [8, 0, 0]); testAddColumnwise([9, 9, 9], [1], [1, 0, 0, 0]); testAddColumnwise([1, 0, 0], [1, 0, 0], [2, 0, 0]);

У тебя ошибка в testAddColumnwise([5, 6, 7], [2, 4, 3], [8, 0, 0]);

ChatGPT:

Ты прав! Ошибка в ожидаемом результате. Должно быть [8, 1, 0], а не [8, 0, 0].

// Запуск тестов testAddColumnwise([1, 2, 3], [9, 8, 7], [1, 1, 1, 0]); // OK testAddColumnwise([9, 9], [1], [1, 0, 0]); // OK testAddColumnwise([0], [0], [0]); // OK testAddColumnwise([5, 6, 7], [2, 4, 3], [8, 1, 0]); // Исправлено, должно быть [8, 1, 0] testAddColumnwise([9, 9, 9], [1], [1, 0, 0, 0]); // OK testAddColumnwise([1, 0, 0], [1, 0, 0], [2, 0, 0]); // OK

Парень из BigTech:

Добавь тесты:

[9,9] + [9] = [1,0,8].
[5,4,4] [4,5,6] = [1,0,0,0]

Добавляем тесты и поста

// Запуск тестов testAddColumnwise([1, 2, 3], [9, 8, 7], [1, 1, 1, 0]); // OK testAddColumnwise([9, 9], [1], [1, 0, 0]); // OK testAddColumnwise([0], [0], [0]); // OK testAddColumnwise([5, 6, 7], [2, 4, 3], [8, 1, 0]); // Исправлено, должно быть [8, 1, 0] testAddColumnwise([9, 9, 9], [1], [1, 0, 0, 0]); // OK testAddColumnwise([1, 0, 0], [1, 0, 0], [2, 0, 0]); // OK // Тесты из сходного поста testAddColumnwise([9,9], [9], [1, 0, 8]); // OK testAddColumnwise([5,4,4], [4,5,6], [1, 0, 0,0]); // OK

"Test OK:", [1, 2, 3], "+", [9, 8, 7], "=", [1, 1, 1, 0], "| Expected:", [1, 1, 1, 0] "Test OK:", [9, 9], "+", [1], "=", [1, 0, 0], "| Expected:", [1, 0, 0] "Test OK:", [0], "+", [0], "=", [0], "| Expected:", [0] "Test OK:", [5, 6, 7], "+", [2, 4, 3], "=", [8, 1, 0], "| Expected:", [8, 1, 0] "Test OK:", [9, 9, 9], "+", [1], "=", [1, 0, 0, 0], "| Expected:", [1, 0, 0, 0] "Test OK:", [1, 0, 0], "+", [1, 0, 0], "=", [2, 0, 0], "| Expected:", [2, 0, 0] "Test OK:", [9, 9], "+", [9], "=", [1, 0, 8], "| Expected:", [1, 0, 8] "Test OK:", [5, 4, 4], "+", [4, 5, 6], "=", [1, 0, 0, 0], "| Expected:", [1, 0, 0, 0]

Все тесты прошли. ChatGPT успешно справился с заданием.

Счет 1 : 1 — ничья

• ChatGPT успешно реализовал функцию

• Немного накосячил с тестом — выбрал неправильное ожидаемое значение

• Учитывыя что он обойдется нам в 20 USD/месяц в редации Plus и 200 USD/месяц в редакции PRO — прощаем мелкий недочет

Что по поводу оптимизации?

Автор оригинально поста, в качестве одной из идей почему такая задача в принципе имеет место быть «Умение работать с строковыми данными (ведь числа могут быть гигантскими, и bigint не спасет).»

Т.е. предполагается что у нас лимит по используемой памяти и нам приходится городить огород, вместо того чтобы использовать встроенный тип: bigint

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

Посмотрим как с этим справиться ChatGPT:

Парень из BigTech:

Есть функция для сложения двух чисел в столбик где числа передаются как массивы.

Функция может быть использована для сложения гигантских чисел, которые не поместятся в bigint.

Не меняя интрефейс функции addColumnwise(arr1, arr2). предложи решение чтобы уменьшить потребление памяти.

ChatGpt:

Чтобы уменьшить использование памяти, можно оптимизировать алгоритм так, чтобы не создавать новый массив result, а модифицировать один из входных массивов (например, arr1 или arr2).

Это сократит количество выделяемой памяти и уменьшит количество операций с массивами.

К сожалению первая реализация содержала ошибку и тесты упали. Но после подсказки:

Парень из BigTech:

не работает в случае если длина result.length > arr1.length + arr2.length

ChatGPT выдал рабочий код:

function addColumnwise(arr1, arr2) {     let carry = 0;     let maxLength = Math.max(arr1.length, arr2.length);     let minArr = arr1.length < arr2.length ? arr1 : arr2;     let result = arr1.length >= arr2.length ? arr1 : arr2; // Изменяем на месте      let diff = Math.abs(arr1.length - arr2.length);      for (let i = maxLength - 1; i >= 0; i--) {         let digit1 = result[i] || 0;         let digit2 = i - diff >= 0 ? minArr[i - diff] || 0 : 0;         let sum = digit1 + digit2 + carry;          result[i] = sum % 10;         carry = Math.floor(sum / 10);     }      if (carry) {         result.unshift(carry); // Это единственное место, где увеличивается размер массива     }      return result; }

В общем и целом, не плохо, но интервьюер хотел бы увидеть другой подход, чтобы понять кандидат в чем-то кроме решений задач с LeetCode понимает или нет 🙂

Парень из BigTech:

Посказка. Что если использовать другую систему счисления при передаче параметров и получении результата?

тут наш ChatGPT себя показал — «задание партии выполним!»

ChatGPT:

Отличная подсказка! Если использовать другую систему счисления, например, основание 2³² (4294967296, 2^32) или 10⁹ (1000000000), то можно значительно сократить количество элементов в массиве, что существенно уменьшит потребляемую память и ускорит вычисления.

Парень из BigTech

напиши реализацию которая использует base 16. Незабудь, что числа передаются в виде текста.

Числа должны быть предствлены как: arr1: [’01’,’03’,’FF’], arr2: [’03’,’05’,AA’] и т.д.

после нескольких итераций:

unction addHexArrays(arr1, arr2) {     let carry = 0;     let maxLength = Math.max(arr1.length, arr2.length);     let result = new Array(maxLength).fill('00'); // Результирующий массив      for (let i = maxLength - 1; i >= 0; i--) {         let digit1 = i - (maxLength - arr1.length) >= 0 ? parseInt(arr1[i - (maxLength - arr1.length)], 16) : 0;         let digit2 = i - (maxLength - arr2.length) >= 0 ? parseInt(arr2[i - (maxLength - arr2.length)], 16) : 0;          let sum = digit1 + digit2 + carry;         result[i] = (sum % 256).toString(16).padStart(2, '0').toUpperCase(); // Формат 'XX'         carry = Math.floor(sum / 256);     }      if (carry) {         result.unshift(carry.toString(16).padStart(2, '0').toUpperCase());     }      return result; }  // Функция тестирования function testAddHexArrays(arr1, arr2, expected) {     const result = addHexArrays([...arr1], [...arr2]);     const success = JSON.stringify(result) === JSON.stringify(expected);     console.log(`Test ${success ? 'OK' : 'Failed'}:`, arr1, '+', arr2, '=', result, '| Expected:', expected); }  // Исправленные тесты testAddHexArrays(['09', '09'], ['01'], ['09', '0A']); //OK testAddHexArrays(['00'], ['00'], ['00']); // OK testAddHexArrays(['05', '06', '07'], ['02', '04', '03'], ['07', '0A', '0A']); // OK testAddHexArrays(['09', '09', '09'], ['01'], ['09', '09', '0A']); // OK testAddHexArrays(['01', '00', '00'], ['01', '00', '00'], ['02', '00', '00']); // OK testAddHexArrays(['09', '09'], ['09'], ['09', '12']); // OK (99 + 9 = 112) testAddHexArrays(['05', '04', '04'], ['04', '05', '06'], ['09', '09', '0A']); // OK testAddHexArrays(['FF'], ['01'], ['01', '00']); // OK  testAddHexArrays(['FF', 'FF'], ['01'], ['01', '00', '00']); // OK testAddHexArrays(['FF', 'FF'], ['FF', 'FF'], ['01', 'FF', 'FE']); // OK testAddHexArrays(['01'], ['09', '09', '09'], ['09', '09', '0A']); // OK 

ChatGPT побеждает со счетом 3 : 1 — и получает работу за 20 USD/Month….

• ChatGPT без проблем реализовал исходный алгоритм как и автор оригинального поста

• Предложил вариант оптимизации памяти за счет переиспользования массива

• После нескольких итераций выдал рабочий код

• С энтузиазмом воспринял идею кодировать данные используя base 16

• После нескольких итераций выдал рабочее решение. В основом косячил с данными для тестов.

Парень из BigTech:

Оцени на сколько сократиться потребление памяти если кодировать строки как массив символов с основанием 64 по сравнению с основанием 10

ChatGPT:

Основание 64 сокращает количество цифр примерно в 1.8 раза.
Потребление памяти сокращается примерно в 2.44 раза за счёт уменьшения количества цифр и использования 6-битных значений вместо байтов.
Чем больше число, тем больше экономия!

Вывод: Использование основания 64 позволяет сократить память в 2.4 — 2.5 раза по сравнению с основанием 10, что делает его отличным выбором для работы с большими числами.

Парень из BigTech становиться «ChatGPT Team Lead», получает бонус за сокращение издержек.

Желающие «войти в IT» отправляются массово учиться писать промты к ChatGpt, поскольку:

Это из собеседования на фронтенд разработчика? В гробу я видал авторов таких вопросов на собеседованиях на фронтенд позиции.

.. где важнее навыки нейминга, знание популярных тенденций и шаблонов проектирования UI систем и т.п. …

А вот эта вся математика, алгоритмика — это то, что вам понадобиться в <1% случаев при разработке фронтенд приложений, а скорей всего не понадобиться никогда.

Как оказалось мыслить современные разработчики могут в лучшем случае на уровне ChatGPT. И предложить решение которое выходит за рамки простого кодинга судя по комментариям к оригинальной статье не могут.

В общем — учимся писать промты для ChatGPT.

P.S. Если хотите обеспечить себе безбедное существование в недалеком будущем и без страха сражаться за рабочие места с AI, то подписывайтесь на мой телеграм канал …

вернее не на мой а на: https://cs.stanford.edu/~knuth 🙂