Евгений Жуков (@EvgeniiZhukov) написал статью “Сложить два числа-гиганта: как я прошел квест на собеседовании в Бигтех” https://habr.com/ru/companies/bitrix/articles/891574/
Краткое содержание:
Сценарий: вы на собеседовании, ожидаете вопросов про React, WebGL или хотя бы про Event Loop. А вместо этого получаете: “Напишите функцию сложения двух чисел в столбик, но числа передаются как массивы.”
Зачем это вообще кому-то нужно:
А интервьюер смотрит, как вы справляетесь с базовой задачей, которая проверяет:
Умение работать с строковыми данными (ведь числа могут быть гигантскими, и 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 :)
Автор: Kahelman
