Сложить два числа-гиганта: как я прошел квест на собеседовании в Бигтех

Сложить два числа-гиганта: как я прошел квест на собеседовании в Бигтех

 Привет, Хабр! Меня зовут Евгений Жуков, я работаю в Битриксе мобильным разработчиком. Моя основная задача — создавать приложения, которые упрощают бизнес-процессы. А еще я обожаю разбирать задачи с собеседований: они как головоломки, которые не только проверяют знание алгоритмов, но и учат видеть не очевидные подходы к коду. Хочу делиться такими кейсами — вдруг это поможет кому-то пройти сложное интервью или вдохновит на новые идеи. Поехали?

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

«Что? — думаете вы. — Это же уровень начальной школы! Где мои хитрые асинхронные задачи?» Но не спешите радоваться. Я тоже недооценивал эту задачу, пока не попытался реализовать её на JavaScript. 

Зачем это JS-разработчику?

Казалось бы: берем, складываем по цифре… Но тут же всплывают вопросы:

• А если числа разной длины?

• Что, если одно из чисел — ноль?

• Как обработать ведущие нули в результате?

• Куда девать перенос, если после последней цифры осталась единица?

И вот вы уже не код пишете, а разгадываете ребус, где каждая строчка — это шаг через пропасть. А интервьюер смотрит, как вы справляетесь с базовой задачей, которая проверяет:

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

2. Понимание алгоритмической логики без подсказок гугла.

3. Внимание к краевым случаям — это как раз то, что ломает продакшен в пятницу вечером.

Подводные камни, или «Ой, а я это не учел»

Давайте разберемся, где можно наступить на грабли:

1. Перенос разряда после последней цифры.Пример: 999 + 1 = 1000. Если забыть про «лишнюю» единицу, случится катастрофа — 000 вместо 1000.

2. Числа разной длины.Что делать, если одно число длиннее? Дополнять нулями слева? Справа? Или обрабатывать «по остатку»?

3. Символы, которые не цифры.А если в строку закралась буква? Нужна ли валидация? (Спойлер: на собеседовании иногда ждут, что вы спросите об этом!)

Ход решения:

Дано:

[5, 4, 4] // 544

[4, 5, 6] // 456

Шаг 1

Единицы: 4 + 6 = 10 → записываем 0, «сдача» 1 

Шаг 2

Десятки: 4 + 5 + 1 = 10 → снова 0 и 1

Шаг 3

Сотни: 5 + 4 + 1 = 10 → 0 и 1. Но массивы кончились! Добавляем 1 в начало.

Запишем наши шаги в виде кода 

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(); // Переворачиваем
}

Фишка кода: Обратите внимание на i— и j— внутри тернарных операторов — это как два шага назад перед прыжком вперед. И да, carry > 0 в условии цикла — наш стражник, который не даст забыть последний перенос.

5 ошибок, которые превратят ваш код в тыкву

1. переносы

Забыли carry? Получите [0,0,0] вместо [1,0,0,0] для 999+1.

2.  массивы

«Мой массив длиннее!» — обрабатывайте края через digit = array[index] || 0.

3. реверс

Не перевернули результат? Поздравляю, ваше 1000 станет 0001!

4. фобия нулей

Пустые массивы? Возвращайте [0] — даже великаны когда-то были нулями.

5. Гонка за оптимизацией

Не пытайтесь умничать — простой цикл здесь элегантнее рекурсий или хитрых методов.

И напоследок: А что, если числа разной длины? Мой алгоритм берет их в оборот через «заполнители»-нули. Как шеф-повар, который из двух разных ингредиентов делает идеальное блюдо — главное правильно добавить «приправу» из переносов.

Попробуйте сами: сверьте свой код с примером [9,9] + [9] = [1,0,8]. Если получилось — вы мастер разрядов! Если нет — ищите потерянный «фантик» где-то в цикле.

Сложность алгоритма

Сколько раз мы пройдемся по циклу? Ровно столько, сколько цифр в самом длинном числе + 1 шаг для возможного переноса.

Пример:

 [9,9] (99) + [9] (9) = [1,0,8] (108)

Здесь самое длинное число имеет 2 цифры → 2 шага + 1 шаг для переноса = 3 итерации.

Формула:

O(max(m, n)), где m и n — длины массивов. 

Время работы растет линейно — если числа станут в 10 раз длиннее, алгоритм замедлится всего в 10 раз. 

Если появился перенос в новый разряд:

max(m, n) + 1 . 

Пример:

  [5,4,4] (3 цифры) + [4,5,6] (3 цифры) → [1,0,0,0] (4 цифры).

Формула:

O(max(m, n)) для хранения результата + O(1) для переменных (carry, индексы) = итого O(max(m, n)).

Это оптимально! Меньше нельзя — нужно хранить каждую цифру результата. Никакого скрытого мусора в памяти — только цифры и пара временных переменных.

Алгоритм масштабируемый — даже для чисел с миллионом цифр он отработает за доли секунд (если, конечно, JS не сломается ).

Почему это круто?

• Без скрытых сюрпризов: Нет рекурсий, нет вложенных циклов — только прямой проход. 

• Экономия: Каждая переменная на счету — никаких лишних массивов или хеш-таблиц. 

• Универсальность: Работает для чисел любой длины. 

Буду рад, если и вы оцените это решение или поделитесь в комментариях своими вариантами!