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

Евгений Жуков (@EvgeniiZhukov ^[1]) написал статью “Сложить два числа-гиганта: как я прошел квест на собеседовании в Бигтех” https://habr.com/ru/companies/bitrix/articles/891574/ ^[2]

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

Сценарий: вы на собеседовании, ожидаете вопросов про 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]);

У тебя ошибка ^[3] в 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 не спасет).”

Т.е. предполагается что у нас лимит по используемой памяти ^[4] и нам приходится городить огород, вместо того чтобы использовать встроенный тип: 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 систем и т.п. …

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

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

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

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

вернее не на мой а на: https://cs.stanford.edu/~knuth ^[6] :)