Comments 172
Дано:
[1, 2, 3] // 123
[4, 5, 6] // 456
Шаг 1
Единицы: 4 + 6 = 10 → записываем 0, "сдача" 1
Можно поподробнее, откуда 4+6?
Опечатка, спасибо, поправил.
Еще 3 варианта Вам:
rec=(a,b)=>{
res=a||b?rec(a.slice(0,-1),b.slice(0,-1)):''
ab=1*a.slice(-1)+1*b.slice(-1)
return res.slice(0,-1)+(res.slice(-1)*10+ab)
}
rec('12345','321')rec=(a,b)=>{
if(!a[0]&&!b[0])return[]
const ab=(1*a.pop()||0)+(1*b.pop()||0)
const res=rec(a,b).reverse()
const [c=0,...rest]=res
const abcd=ab+c*10
const [f,e]=[abcd%10,Math.floor(abcd/10)]
return rest.reverse().concat([e,f])
}
rec([...'12345'],[...'111'])f=(a,b)=>{
let [carry,index,sum]=[0,1,'']
do{
carry=parseInt(carry/10)+(1*a[a.length-index]||0)+(1*b[b.length-index]||0)
sum=carry%10 + sum
index++
}while(index-1<Math.max(a.length,b.length))
return sum
}
f('12345','999')
Этот код навевает воспоминания о перле, поэтому — однозначный плюсик.
с циклом и редюсом:
f=(a,b)=>{
let [carry,sum]=[0,'']
for(let index=Math.max(a.length,b.length);index>0;index--){
carry=parseInt(carry/10)+
[a,b].reduce((a,b)=>a+[null,...b].slice(-index)[0]*1||0,0)
sum=sum+carry%10
}
return sum
}
f('12345','321')
на итераторах:
f=(a,b)=>{
const ab=[a,b].map(a=>[...a].reverse().map(c=>c*1))
return ab[a.length>b.length?0:1]
.map((e,i)=>ab[0][i]||0+ab[1][i]||0)
.map((d,i)=>d%10)
.reverse().join()
}
f('12345','321')
3. реверс
Не перевернули результат? Поздравляю, ваше 1000 станет 0001!
А если заменить result.push(total % 10); на result.unshift(total % 10);, то и переворачивать ничего не надо.
Можно сделать вывод, что соискатель не знает базовых операций над массивами :)
Стоит отметить, что сложность push — O(1), а для unshift — O(n). Так что использовать push и перевернуть один раз на очень больших инпутах, про которые идет речь в этой задаче, будет выгоднее.
Если бороться за производительность, то следовало бы создать для результата сразу массив требуемого размера (1 + max (arr1.length,arr2.length)) и заполнять его элементы по индексам в нужном порядке.
Это так для связных списков, но не для массивов.
Вынужден сослаться на википедию. https://en.wikipedia.org/wiki/Array_(data_structure)#Comparison_with_other_data_structures
Для списков вставка в начало и конец O(1).
Вы бы еще сами сумели прочитать и понять то, что там написано.
С каких пор в связном списке известен последний элемент? Я в последние 10 лет работаю с языками, в которых массивов из коробки нет, только односвязные списки. Напишите имплементацию сами, да гляньте на бенчмарки.
Вам никто не мешает сохранить ссылку на конец и начало. В таком случае вы всегда сможете вставить в эти места за O(1). Да, в вставка в произвольное место будет все еще O(n). Собственно об этом и сказано в таблице.
Мне лично мешает иммутабельность языка, с которым я работаю, например. А вам мешает то, что встроенный в ваш язык LinkedList этого не делает. Можно, конечно, написать собственную реализацию и пользоваться только ей, но это не имеет никакого отношения к обсуждаемым реалиям.
Таблица — это прекрасно, но я уже сказал: напишите бенчмарки, да попробуйте, вместо того, чтобы тут позориться.
Как идейный Erlanger не совсем поддерживаю. Операция добавления в начало списка быстрее чем в конец, но вроде операция reverse достаточно эффективная. (Про реализацию не смотрел, но думаю что должно быть сильно оптимизировано поскольку везде используется) тогда в принципе нет особой разницы между добавление в начало списка и в конец методом развернуть, добавить в начало, развернуть снова ;)
А что за язык такой, интересно же.
Близкая по духу задача:
ведь числа могут быть гигантскими, и bigint не спасет
Есть вероятность, что если число настолько длинное, что не влезает в bigInt, который на JS ограничен только размером доступной памяти, то ваше решение априори не будет более эффективным.
Как минимум, вы не сможете в массив запихнуть посимвольно число, которое не влезет в bigInt, просто потому что массив чисел исчерпает память быстрее.
Ну и есть сомнения, что где-то нужно работать с числами, которые весят хотя бы пару гигабайт. Если, кончено, вы пишите не какой-нибудь алгоритм хэширования, готовый принять на вход сообщение произвольной длины. Но даже при хешировании файла в условные 1тб, он обрабатывается блочно, а не целиком в памяти.
Я бы на собеседовании от соискателя ожидал именно такие рассуждения а не попытки запилить велосипед с кучей подводных камней ради решения тривиальной задачи, имхо..
И да, я работаю с большими числами. В криптографии случаются числа и по 4кб и даже больше. И единственная проблема с нативным bigInt была когда-то в том, что Сафари прыгала из окна, когда видела числа вида 123n. И приходилось прикручивать полифилловые решения.
Ну это зависит от того, кого вы набираете - кодеров или инженеров.
Кого бы ни набирали — нужно решение и обоснование области его применимости.
Для джунов — да. При собеседовании же на позицию синьора, если он не поспорит с дающим такую задачу что в таком виде это какая-то глупая херня и надо выяснить, зачем вообще она в таком виде понадобилась, что за запрос за этим стоит, или не предложит взять готовое решение, делать иначе, или не делать вообще, то похоже что он не синьор. Я всё же надеюсь, что синьорам подобные задачи уже никто не даёт на собеседованиях, как часто было раньше, из-за некомпетентности собеседующих
А вы не прочитали, что я написал. Я не написал, почему этого делать не надо, я написал, почему делать это надо через BigInt, а не костыли-велосипеды. А если вы нанимаете людей, чтобы они делали как вы хотите, даже если это не решение, а бомба замедленного действия, а не как правильно, то зачем они вам вообще? :)
Через bigint любой студент троечник a+b напишет. А вот если случится таки сложная задачка, где работнику придется аж целый цикл написать? Студент троечник уже не справится. И их таких надо отсечь. Именно для этого интервью и есть. Именно поэтому спрашивают писать код а не молоть языком о том, какие вы хорошие и крутые.
Задачка искусственная и на практике никто именно это делать не будет? Вообще не важно с точки зрения собеседующего. Настоящих практичных задач, которые можно запихнуть в рамки собеседования весьма мало, и в интернет они утекают с ошеломительной скоростью.
Когда вы здаете экзамен на вождение вас не просят проехать от вашего дома до вашей работы, а гоняют по удобному для инспектора маршруту.
Тогда давайте задание на циклы, а не на бигинт. Или не удивляйтесь, что работник будет через пень-колоду вымучивать странные алгоритмы там, где троечник сложит 2 числа через bigInt. Зато он прошёл собес так, как этого хотелось вам, да. Проводя отбор, надо тщательно думать, какие признаки отбираются.
Кто-то должен был реализовать сложение любых чисел любой длины в питоне, например. Или это тоже вымученная задача?
Еще раз, задачи утекают. Троечники еще могут зазубренный цикл написать, но если задача другая - нет. Поэтому задачи постоянно меняются. Когда-то давали задачи прям с прода, насколько это возможно. Потом скатились к немного искуственным задачам.
Аналогия с водительскими правами вам не понятна? Вы же не ругаетесь на инспектаров, что они заставляют вас ездить по тем дорогам, по которым вы ездить вообще никогда не собираетесь? Но вы при этом демонстрируете те же навыки, что вам понадоятся в настоящей езде. Так и тут, на этой, может и не самой классной, задаче кандидат показывает навыки, которые от него хотят увидеть - решает что-то не совсем тривиальное.
Или не удивляйтесь, что работник будет через пень-колоду вымучивать странные алгоритмы там, где троечник сложит 2 числа через bigInt.
Ваш аргумент звучит как: никогда не берите бегунов марафонцев в качестве курьеров. Там, где можно просто спокойно дойти до двери, он будет бежать! Нет же. Наличие сложных навыков не исключает наличие простых. И, продолжая аналогию, если у вас в городе иногда попадаются бродячие собаки, а всякие перцовые балончики запрещены из-за активистов, требовать от кандидата в курьеры способностьи хоть 20 метров до машины добежать - необходимость.
Сразу видно, что вы не сеньор)))
«Большие числа» были упомянуты (как я уже говорил где-то в соседней ветке) только для того, чтобы отсечь решения, построенные на рекурсии (которая отыквит джаваскрипт уже на 200 байтах, если я ничего не путаю, в общем — почти сразу). bigInt тут вообще ни при чем.
а почему сразу ведущие нули не записать?
def add_columnwise(num1, num2):
# Приводим числа к одинаковой длине, добавляя ведущие нули
max_len = max(len(num1), len(num2))
num1 = [0] * (max_len - len(num1)) + num1
num2 = [0] * (max_len - len(num2)) + num2
result = []
carry = 0 # Перенос
# Складываем поразрядно справа налево
for i in range(max_len - 1, -1, -1):
s = num1[i] + num2[i] + carry
result.append(s % 10) # Последняя цифра суммы
carry = s // 10 # Остаток для переноса
# Если остался перенос — добавляем в начало
if carry:
result.append(carry)
return result[::-1] # Переворачиваем, так как складывали справа налево
# Примеры:
print(add_columnwise([9, 9], [1])) # ➝ [1, 0, 0]
print(add_columnwise([1, 2, 3], [9, 8, 7])) # ➝ [1, 1, 1, 0]
print(add_columnwise([5, 6], [4, 7])) # ➝ [1, 0, 3]
Это кратный дополнительный расход памяти, а числа ожидаются большие.
Требования к памяти не было. С ведущими нулями проще проектировать.
Прямо под этим комментарием есть моя реализация, которая станет сложнее с добавлением ведущих нулей.
Пожалейте императивщиков )
Кстати на питоне есть оптимизация хвостовой рекурсии. Но это не точно
Да, и правда похоже есть.
>>> def fac(n, acc):
... return acc if n <= 1 else fac(n - 1, n * acc)
...
>>> print(fac(6, 1))
720
>>> print(fac(500, 1))
122013682599111006870123878542304692625357434…
Ну, 500 и в стандартный стек влезет
Вот я дебил, конечно. В джаваскриптовый не влезает, вот я и выставляю себя идиотом.
>>> print(fac(5000, 1))
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 2, in fac
File "<stdin>", line 2, in fac
File "<stdin>", line 2, in fac
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
Elixir:
iex|🌢|1 ▶ defmodule Fac do
...|🌢|1 ▶ def calc(num, acc \\ 1)
...|🌢|1 ▶ def calc(num, acc) when num <= 1, do: acc
...|🌢|1 ▶ def calc(num, acc), do: calc(num - 1, num * acc)
...|🌢|1 ▶ end
iex|🌢|2 ▶ Fac.calc(5_000)
4228577926605543522201064200233584…
Не пытайтесь умничать — простой цикл здесь элегантнее рекурсий или хитрых методов.
В смысле «элегантнее»? Вот решение на эликсире, рекурсивное, допустить ошибку тут практически невозможно.
defmodule Solution do
def add(l1, l2), do: l1 |> Enum.reverse() |> do_add(Enum.reverse(l2), {0, []})
defp do_add([], [], {remainder, acc}), do: [remainder | acc]
defp do_add([], l2, {1, acc}), do: do_add([1], l2, {0, acc})
defp do_add([], l2, {0, acc}), do: Enum.reverse(l2) ++ acc
defp do_add(l1, [], acc), do: do_add([], l1, acc)
defp do_add([h1 | t1], [h2 | t2], {remainder, acc}),
do: do_add(t1, t2, {div(h1 + h2 + remainder, 10), [rem(h1 + h2 + remainder, 10) | acc]})
end
Solution.add [5, 4, 4], [4, 5, 6]
#⇒ [1, 0, 0, 0]В JS нет оптимизации хвостовой рекурсии, поэтому рекурсивное решение (по-прежнему гораздо более элегантное) — отыквится на длинном вводе. Вам про гигантские числа именно поэтому сказали, а не из-за проблем с переполнением.
Простите, а Битрих это BigTech? Я думал по наивности что это Google/ FB и иже с ними ..
Эх, молодьож, reverse , рекурсии, как будто память на базаре по три копейки гигабайт!
Давненько я не брал в руки сишку!
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* mega_add(char* input_str1, char* input_str2) {
int digit1, digit2, d, carry = 0;
int len1 = strlen(input_str1);
int len2 = strlen(input_str2);
int res_len = (len1 > len2 ? len1 : len2) + 1 /* для замыкающего \0 */
+ 1 /* для потенциального переноса */;
char* ptr1 = input_str1 + len1;
char* ptr2 = input_str2 + len2;
char* result_str = malloc(res_len);
char* ptr3 = result_str + res_len;
*--ptr3 = '\0';
for(;;) {
digit1 = (ptr1 <= input_str1 ? 0 : *(--ptr1) - '0');
digit2 = (ptr2 <= input_str2 ? 0 : *(--ptr2) - '0');
d = digit1 + digit2 + carry;
if(d > 9) {
carry = 1;
d = d - 10;
} else {
carry = 0;
}
*--ptr3 = d + '0';
if ((ptr1 <= input_str1) && (ptr2 <= input_str2)) break;
}
if(carry == 0) {
return(ptr3);
} else {
*--ptr3 = '1';
return(ptr3);
}
}
void test(char *input_str1, char *input_str2) {
char *s = mega_add(input_str1,input_str2);
printf(" %10s\n+ %10s\n------------\n %10s\n\n", input_str1, input_str2, s);
/* Особождение s лежит за пределами этого упражнения - ибо есть нюанс */
}
void main(void) {
test("123", "1111111");
test("123", "9999999");
test("999", "999");
test("0", "0");
test("1111111", "234");
test("9999999", "234");
}
> $ gcc 1.c
eligovm@eligovm:/mnt/var/git$ ./a.out
123
+ 1111111
------------
1111234
123
+ 9999999
------------
10000122
999
+ 999
------------
1998
0
+ 0
------------
0
1111111
+ 234
------------
1111345
9999999
+ 234
------------
10000233«Как идейный коммунар я За!»
Ещё предложение:
Автор писал « O(max(m, n)) для хранения результата + O(1) для переменных (carry, индексы) = итого O(max(m, n)).
Это оптимально! Меньше нельзя — нужно хранить каждую цифру результата. Никакого скрытого мусора в памяти — только цифры и пара временных переменных.»
Если память не проблема- то можно выделить все что хочешь и не заморачиваться.
Если память действительно проблема,
То выделить M байт для хранения результата не получиться.
Так что решением должно быть: использовать самый длинный массив с данными для возврата результата.
В итоге функция (С) должна вернуть структуру : указатель на массив (так как мы не знаем в какой из параметров А или Б мы записали результат (пишем в самый длинный) и значен е переноса (curry) для самого левого значения, который в Массив не влезет.
В результате:
1 не используем дополнительной памяти- экономим
2. Экономив время на выделении памяти/ освобождении памяти
Про то что нельзя модифицировать входные данные сказано не было- но это и не может быт. Ограничением, если главное ограничение по используемой памяти.
Слегка усложняется интерпретация результата- но это тоже не проблема.
Как плюс: если вам необходимо сложить 10000 больших чисел, которые не влезают в память - программа будет работать.
Потребует небольшой доработки- возвращать массив curry и учитывать при добавлении нового числа.
как будто память на базаре по три копейки гигабайт!
я тоже докопаюсь до вашего кода, как будто у вас терагерцовые процы бесплатно!
Есть же SWAR да и про бранчлесс не надо забывать ))
Объясните, пожалуйста, зачем нужен замыкающий ноль?
Потому что сишники не любят хранить длину отдельно, а значит нужен какой-то другой механизм её определения.
— Это не хвост ноль, — сказал волк и густо покраснел. — А у тебя, Красная Шапочка, ещё молоко на губах не обсохло для таких вопросов! ©
Судя по вашему коду, молоко на губах не обсохло у кое-кого другого:
int len1 = strlen(input_str1);
int len2 = strlen(input_str2);Функция strlen возвращает значение беззнакового типа.
К тому же, этот тип может иметь размер, превышающий размер типа int.
В результате, могут получиться как отрицательные значения, так и значения, значительно меньшие, чем настоящий размер "чисел".
Лишь стажёры и джуны ещё могут допускать такие ошибки.
char* result_str = malloc(res_len);
char* ptr3 = result_str + res_len;
*--ptr3 = '\0';Функция malloc может вернуть NULL со всеми вытекающими последствиями.
В коде нет освобождения памяти, и дело не в оправданиях, что, мол, это — просто пример. В этом коде принципиально невозможно освободить память.
Если в последнем разряде был перенос, то функция mega_add вернёт ровно тот адрес, который вернула функция malloc.
Если же переноса не было, то функция mega_add вернёт адрес на 1 больше.
Определить в функции test, был перенос или нет, невозможно, поэтому невозможно и передать правильный адрес функции free.
Соответственно, освобождение памяти здесь принципиально невозможно.
Если добавить в mega_add вывод некоторых значений:
int res_len = (len1 > len2 ? len1 : len2) + 1 /* для замыкающего \0 */
+ 1 /* для потенциального переноса */;
printf("%s: len1: %i, len2: %i, res_len: %i\n", __func__, len1, len2, res_len);
char* ptr1 = input_str1 + len1;
char* ptr2 = input_str2 + len2;
char* result_str = malloc(res_len);
printf("%s: result_str: %p\n", __func__, result_str);и в функцию test — тоже, и ещё, оставив вывод только результата, без самих чисел:
char *s = mega_add(input_str1,input_str2);
printf("%s: s: %p\n", __func__, s);
printf("Result: %s\n", s);и переписать функцию main:
int main(void) {
static char a[((size_t)1 << (sizeof(int) * CHAR_BIT)) - 2];
memset(a, '9', sizeof a - 1);
test(a, a);
return EXIT_SUCCESS;
}то после запуска можно увидеть:
$ ./1
mega_add: len1: -3, len2: -3, res_len: -1
mega_add: result_str: (nil)
Segmentation fault
$ По значению result_str видно, что функция malloc вернула NULL, потому что не смогла выделить 18 квинтиллионов байт памяти.
Последствия не замедлили последовать, потому что в коде нет проверки значения, возвращаемого функцией malloc.
Ещё два варианта main, первый:
int main(void) {
test("9", "9");
return EXIT_SUCCESS;
}и второй:
int main(void) {
test("1", "1");
return EXIT_SUCCESS;
}В первом случае:
$ ./1
mega_add: len1: 1, len2: 1, res_len: 3
mega_add: result_str: 0x56058cd406b0
test: s: 0x56058cd406b0
Result: 18
$ видно, что функция test получила в переменную s ровно тот же адрес, который был выделен функцией malloc в mega_add и запомнен там в переменной result_str.
Во втором же случае:
$ ./1
mega_add: len1: 1, len2: 1, res_len: 3
mega_add: result_str: 0x5626942f16b0
test: s: 0x5626942f16b1
Result: 2
$ видно, что функция test получила в переменную s адрес, на 1 больше по сравнению с тем, который был выделен функцией malloc в mega_add.
Определить, увеличенный это на 1 адрес или нет, в общем случае невозможно.
Поэтому невозможно и правильно вызвать free.
Ещё один вариант функции main:
int main2(void) {
static char a[((size_t)1 << (sizeof(int) * CHAR_BIT - 1)) + 1];
memset(a, '9', sizeof a - 1);
test(a, "9");
return EXIT_SUCCESS;
}Результат:
$ ./1
mega_add: len1: -2147483648, len2: 1, res_len: 3
mega_add: result_str: 0x557e0b5ce6b0
test: s: 0x557e0b5ce6b1
Result: 9
$ Видно, что сложение числа 9 с огромным числом, состоящих из более, чем 2-х миллиардов цифр 9, в результате, дало всего лишь число 9, состоящее из одной цифры.
Рановато вам ещё перед молодёжью чваниться.
Челодой моловек, я там явно написал, что освобождение памяти оставляю за рамками этого упражнения — именно потому, что надо было бы возвращать два указателя (один — на результат, второй — на то, что alloc-нули), и о прочих краеугольных случаях, которые Вы описываете, я тоже подумал — но в какой-то момент комментарий стал выглядеть черезчур уж громоздким, и потому осетра пришлось урезать.
А так — да, нюансов много, очень много. Но кто про них будет читать?
и о прочих краеугольных случаях, которые Вы описываете, я тоже подумал — но в какой-то момент комментарий стал выглядеть черезчур уж громоздким, и потому осетра пришлось урезать.
Выбор правильного типа переменной для приёма значения от strlen нисколько не загромождает текст, оправдываться здесь бесполезно.
А так — да, нюансов много, очень много. Но кто про них будет читать?
Это — не те нюансы.
Вы пишете код на C на уровне джуна.
Само по себе это ни о чём не говорит.
Но когда вы начинаете чваниться перед молодежью своими умениями, это уже — совсем другое дело.
Выбор правильного типа переменной для приёма значения от strlen нисколько не загромождает текст
Ну да, ну да, unsigned long int «нисколько не загромождает текст». Речь не шла о том, чтобы написать код, готовый к выкату в прод вотпрямща — иначе я мог бы и с возвращением двух указателей заморочиться и т.п.
И да, я на C вплотную не писал уже лет эдак 25. Но опыт всё-таки не пропьёшь.
Ну да, ну да, unsigned long int «нисколько не загромождает текст».
Во-первых, int там не нужен, достаточно написать unsigned long.
Во-вторых, это тоже — неправильный тип.
Речь не шла о том, чтобы написать код, готовый к выкату в прод вотпрямща — иначе я мог бы и с возвращением двух указателей заморочиться и т.п.
Незнания такого уровня, которые вы продемонстрировали, — это не о коде, готовом к выкату.
И да, я на C вплотную не писал уже лет эдак 25.
Но знания у вас с того времени остались на том уровне, на котором по любому поводу используют int, что вы наглядно и продемонстрировали.
Керниган и Ритчи написали, что int — самый эффективный тип C.
Видимо, вы на этом уровне понимания языка и остановились.
Но опыт всё-таки не пропьёшь.
Опыт джуновского уровня?
Тип size_t появился в первом же стандарте C, C89/90.
Имя этого типа совершенно точно не загромождает текст.
Вам не хватило опыта, чтобы догадаться взглянуть на прототип strlen, чтобы увидеть, какой тип — правильный.
А чваниться перед молодёжью пытаетесь, как будто — сеньор.
Во-первых, сеньоры разные бывают. А во-вторых, я хотя бы написал рабочий код — а Вы только критикукуете.
А это особая каста людей, сами ничего работоспособного создать не могут, зато всегда наготове с придирками к чужой работающей кодовой базе. Они еще всегда рекомендуют «всё переписать» и начинают имплементацию FizzBuzz с оптимизаций тиков на делении.
А это особая каста людей, сами ничего работоспособного создать не могут
Можете обосновать в данном случае?
Или просто так сказали про "не могут"?
зато всегда наготове с придирками к чужой работающей кодовой базе.
То, что она неработающая, я аргументированно показал выше.
Они еще всегда рекомендуют «всё переписать» и начинают имплементацию FizzBuzz с оптимизаций тиков на делении.
А это своё голословное утверждение можете обосновать?
Где я рекомендовал всё переписать в данном случае?
Тем более, что здесь не особо что-то оптимизируется:
char *mega_add_eptr(char const *inp1, char const *inp2) {
size_t len1 = strlen(inp1);
size_t len2 = strlen(inp2);
if (len1 > len2) {
char const *const p = inp1;
size_t const l = len1;
inp1 = inp2;
inp2 = p;
len1 = len2;
len2 = l;
}
char *const res = malloc(len2 + 1 + 1);
if (res) {
int carry = 0;
char const *p1 = inp1 + len1;
char const *p2 = inp2 + len2;
char *p3 = res + len2;
*p3 = '\0';
while (p1 > inp1) {
int const s = (*--p1 - '0') + (*--p2 - '0') + carry;
*--p3 = s + ((carry = s > 9) ? '0' - 10 : '0');
}
while (p2 > inp2 && carry) {
int const s = (*--p2 - '0') + carry;
*--p3 = s + ((carry = s > 9) ? '0' - 10 : '0');
}
if (p2 > inp2) {
memcpy(res, inp2, p2 - inp2);
}
if (carry) {
memmove(res + 1, res, len2 + 1);
*res = '1';
}
}
return res;
}С такой функцией main:
int main(void) {
static char a[((size_t)1 << (sizeof(int) * CHAR_BIT - 1)) + 1];
memset(a, '9', sizeof a - 1);
test(a, "9");
return EXIT_SUCCESS;
}и замене в оригинальном коде проблемных int'ов на unsigned, чтобы оригинальный код заработал на этих конкретных данных, производительность растёт не очень сильно, хотя и растёт.
Типичное суммарное время исполнения вместе с инициализацией массива оригинального кода:
$ time ./1
real 0m4.365s
user 0m3.124s
sys 0m1.240s
$а представленного выше:
$ time ./1
real 0m3.808s
user 0m2.656s
sys 0m1.152s
$Хотя, разница на уровне чистого времени исполнения функции mega_add будет больше.
Есть такая каста людей, которая, не думая, любит бездоказательно и безответственно применять расхожее клише.
То, что она неработающая, я аргументированно показал выше.
То, что она работающая — как бы показано результатами тестов непосредственно вслед за собственно программой. А если Вам охота не «набросать код за пять минут и читать Хабр дальше», а придираться к запятым — то не смею Вам препятствовать. Но это уже без меня.
То, что она работающая — как бы показано результатами тестов непосредственно вслед за собственно программой.
Ваш набор тестов покрывает все случаи?
Мои варианты тестов, которые демонстрируют низкое качество вашего кода, вы предпочитаете не замечать?
А если Вам охота не «набросать код за пять минут и читать Хабр дальше»
В моменты "набросать код за пять минут" проявляются программистские рефлексы, потому что особо обдумывать некогда.
Ваши программистские рефлексы диктуют вам в любой непонятной ситуации использовать тип int и не обрабатывать возможные ошибки.
Да, это похоже на уровень джуна.
а придираться к запятым — то не смею Вам препятствовать.
То, что такие существенные вещи вы называете придиркой к запятым, дополнительно указывает на то, что гордиться и чваниться здесь нечем.
Что интересно, различные ИИ для этой задачи почти поголовно тоже пытаются применять int, и даже тот, кто сначала применил size_t, все равно потом использовал int.
Однако, ни один из 4-х не забыл проверить результат вызова malloc с самого начала.
И ни один, после указания на проблему с типом int, не пытался заменять int на unsigned long или, например, uint64_t, — все сразу переходили на size_t, очевидно, "понимая" его смысл.
Но это уже без меня.
Верно, чваниться умеете на хорошем уровне, а признавать ошибки не умеете совсем.
Все без исключения современные компиляторы применят в данном случае TCO, поэтому от синьёра я бы лично ожидал увидеть рекурсию.
Рекурсивный код тут будет в три раза короче, ему не потребуются ни O(n) вызовы strlen в начале, ни куча условных операторов, и, самое главное, ему не потребуется malloc, потому что можно по месту перезаписывать любой из двух наборов данных, а когда ввод отыквится — опционально переключиться на другой через memcpy.
Когда вызов вернется, потенциально придется разок вызвать realloc, если осталась неучтенная единица.
Я уже приводил реализацию на эликсире, переписать её на си — не так уж сложно.
Рекурсивный код тут будет в три раза короче, ему не потребуются ни O(n) вызовы strlen в начале,
Ему всего-то понадобится овердофига места в стеке.
Нет.
Я же даже написал специально:
Все без исключения современные компиляторы применят в данном случае TCO.
Там стек расти вообще не будет. Во-о-бще.
Ему всего-то понадобится овердофига места в стеке.
В отличие от вас, я проверил, что там происходит на самом деле.
Все 4 компилятора, которые я проверил, применили TCO, в этой части @cupraer прав.
А вы продолжаете генерировать безответственные заявления.
Скажите, пожалуйста,
Слова, которыми начался сей тред,
Вы и правда не заметили, или так, просто ради поддерджания срача дискуссии придуриваетесь? Не было ещё TCO 25 лет назад, прикиньте?
Не было ещё TCO 25 лет назад, прикиньте?
Но говорите-то вы про сейчас:
Ему всего-то понадобится овердофига места в стеке.
В вашем тексте нет указания на то, что вы говорите о компиляторах 25-летней давности.
В вашем тексте нет указания на то, что вы говорите о компиляторах 25-летней давности.
Эммммм.... алло, гараж?
Эммммм.... алло, гараж?
Нет, у вас написано по этому поводу:
Ему всего-то понадобится овердофига места в стеке.
Вы это написали?
Я вот это написал
#include <stdio.h>
int test(int n) {
printf("%d\n", n);
test(n + 1);
}
int main() {
test(1);
}Когда счёт дошёл примерно до четырёх миллионов:
PID SIZE RES TIME WCPU COMMAND
123456 65880K 63344K CPU1 81.69% a.out
Если у Вас 63 мегабайта, выжранное программой из трёх строчек — это не «как не в себя», то я даже и не знаю.
Я вот это написал
Так ведь необходимо не только написать.
Необходимо ещё и правильно скомпилировать.
Если взглянуть на то, как с вашим кодом справились 4 компилятора при правильной компиляции, то выяснится, что все они применили TCO.
Ассемблерный код от gcc:
test:
push rbx
mov ebx, edi
.L2:
mov esi, ebx
mov edi, OFFSET FLAT:.LC0
xor eax, eax
inc ebx
call printf
jmp .L2От clang'а:
test:
push r14
push rbx
push rax
mov ebx, edi
lea r14, [rip + .L.str]
.LBB0_1:
mov rdi, r14
mov esi, ebx
xor eax, eax
call printf@PLT
inc ebx
jmp .LBB0_1От Intel'овского icx:
test:
push rbx
mov ebx, edi
.LBB0_1:
mov edi, offset .L.str
mov esi, ebx
xor eax, eax
call printf
inc ebx
jmp .LBB0_1От MSVC:
test PROC
$LN7:
push rbx
sub rsp, 32 ; 00000020H
mov ebx, ecx
npad 8
$LL3@test:
mov edx, ebx
lea rcx, OFFSET FLAT:$SG9630
call printf
inc ebx
jmp SHORT $LL3@test
test ENDPДоработал ваш код, убрав UB и остановив рекурсию на моменте, когда кончатся положительные int'ы:
#include <stdio.h>
#include <limits.h>
int test(int n) {
printf("%d\n", n);
if (n == INT_MAX)
return n;
return test(n + 1);
}
int main() {
test(1);
}Собрал правильным образом локально у себя на машине, и ассемблерный код получился таким:
test:
.LFB3:
.cfi_startproc
push rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
lea rbp, .LC0[rip]
push rbx
.cfi_def_cfa_offset 24
.cfi_offset 3, -24
mov ebx, edi
sub rsp, 8
.cfi_def_cfa_offset 32
jmp .L3
.p2align 4,,10
.p2align 3
.L7:
add ebx, 1
.L3:
xor eax, eax
mov esi, ebx
mov rdi, rbp
call printf@PLT
cmp ebx, 2147483647
jne .L7
add rsp, 8
.cfi_def_cfa_offset 24
mov eax, 2147483647
pop rbx
.cfi_def_cfa_offset 16
pop rbp
.cfi_def_cfa_offset 8
ret
.cfi_endprocПо самой интересной его части:
.L7:
add ebx, 1
.L3:
xor eax, eax
mov esi, ebx
mov rdi, rbp
call printf@PLT
cmp ebx, 2147483647
jne .L7Видно, что компилятор применил TCO.
Далее, я запустил программу, вырезав середину её вывода и оставив только первые 3 и последние 3 строки:
$ (exec 3> >(head -n 3; echo '...'; cat > /dev/null 2>&1); exec 4> >(tail -n 3); ./1 | tee >(cat >&3) >(cat >&4) > /dev/null)
1
2
3
...
2147483645
2147483646
2147483647
$ Пришлось подождать минуты 3, но, как видно по результату, весь запас положительных значений int'а был успешно исчерпан.
Кстати, вы умудрились даже в таком простом коде допустить UB: функция test должна возвращать значение.
Да, я уже слышал про обратностороннего салфеточника, который пишет на обратной стороне салфетки код, не являющийся production-ready.
Однако, компиляторам — все равно, по какой причине в программе имеется UB, они не читают habr.
При наличии UB в программе компиляторы имеют право генерировать любой код, в том числе, неправильный.
Но в данном случае они этим правом не воспользовались, видимо, потому, что рекурсия — бесконечная, о чём они, кстати, и пишут в своих предупреждениях.
Если у Вас 63 мегабайта, выжранное программой из трёх строчек — это не «как не в себя»,
Вот, сколько памяти потребляет процесс у меня через 2 с половиной минуты исполнения, незадолго до его завершения:
PID VIRT RES %CPU %MEM TIME+ COMMAND
3342451 2460 892 100.0 0.0 2:31.19 1Даже до 1 МБайта не дотягивает.
то я даже и не знаю.
Да, вы почему-то многого не знаете.
Вот и выходит, что — нечем вам чваниться перед молодёжью, кроме того, что лет вам больше, чем представителям этой самой молодёжи.
(пританцовывая на месте:) Блин, ну сколько уже ему намёков давать можно? Когда, когда же он наконец спросит «а какой версией gcc эти примеры скомпилированы были?»
(пританцовывая на месте:) Блин, ну сколько уже ему намёков давать можно? Когда, когда же он наконец спросит «а какой версией gcc эти примеры скомпилированы были?»
Современной, поскольку вы сказали понадобится, а не понадобилось в бы прошлом:
Ему всего-то понадобится овердофига места в стеке.
то есть, без указания, что имеете ввиду не современные версии.
Но могли бы и сами проверить.
Сейчас самая древняя доступная работоспособная версия там — 3.4.6, это — 2005-ый год, 20 лет назад.
Вот результат:
test:
push %rbx
mov %ebx, %edi
.L2:
mov %esi, %ebx
mov %edi, OFFSET FLAT:.LC0
xor %eax, %eax
inc %ebx
call printf
jmp .L2Если отключить заголовочный файл, то относительно работоспособной становится случайно затесавшаяся туда версия 1.27, которая, действительно, не выполняет TCO:
test:
pushl %ebp
movl %esp,%ebp
pushl 8(%ebp)
pushl $.LC0
call printf
movl 8(%ebp),%eax
incl %eax
pushl %eax
call test
leave
retНо это, всё-таки, 1988-ой год.
А вы говорили о 25-и годах, а не о 37-и.
Современной
«When you assume, you make an ass of u and me» (непереводимая игра слов) ©
поскольку вы сказали понадобится, а не понадобилось в бы прошлом:
Ну да, а включить старый ящик, который последний раз апдейтился хз когда, и на котором уних с сями завалялся, конечно же, невозможно.
А он говорит такое:
~> gcc --version
gcc (GCC) 4.2.1 20070719
~> gcc 1.c -S
test:
pushl %ebp
movl %esp, %ebp
subl $8, %esp
movl 8(%ebp), %eax
movl %eax, 4(%esp)
movl $.LC0, (%esp)
call printf
movl 8(%ebp), %eax
addl $1, %eax
movl %eax, (%esp)
call test
leave
retКоторый всего-то 17 лет назад.
Ну да, а включить старый ящик, который последний раз апдейтился хз когда, и на котором уних с сями завалялся, конечно же, невозможно.
Да, прямо сейчас у меня нет такого.
Но оно и не нужно.
А он говорит такое:
~> gcc --version gcc (GCC) 4.2.1 20070719
~> gcc 1.c -S
Вы правда не понимаете или прикидываетесь?
Вот смотрите, компилятор gcc 3.4.6 НЕ осуществляет TCO:
test:
push %rbp
mov %rbp, %rsp
sub %rsp, 16
mov DWORD PTR [%rbp-4], %edi
mov %esi, DWORD PTR [%rbp-4]
mov %edi, OFFSET FLAT:.LC0
mov %eax, 0
call printf
mov %edi, DWORD PTR [%rbp-4]
inc %edi
call test
leave
retИ тот же самый компилятор теперь уже ОСУЩЕСТВЛЯЕТ:
test:
push %rbx
mov %ebx, %edi
.L2:
mov %esi, %ebx
mov %edi, OFFSET FLAT:.LC0
xor %eax, %eax
inc %ebx
call printf
jmp .L2Объяснять, почему, или сами догадаетесь?
Вы сначала объясните, что и кому Вы пытаетесь доказать. Что мой компилятор (не Васин, не Петин, не Кнута и даже не Страуструпа) НЕ сгенерил тот код, который я привёл (каковой код падает в корку, досчитав всего-то до 4193842)?
Вы сначала объясните, что и кому Вы пытаетесь доказать.
Доказать?
Когда вы показали командную строку, как вы компилируете, всё стало понятно.
Вы компилируете без оптимизации.
Знаете, что означает "O" в аббревиатуре TCO?
«Оппачки» же. Тэйл Колл Оппачки! — и готово.
Я приношу свои извинения и забираю назад слова про «ничего не умеют», которые я облыжно высказал в первом комментарии.
Я признаю́, что, возможно, погорячился в данном конкретном случае с рекурсией (хотя мне лично её все равно легче читать, чем императивные циклы).
Также хочу искренне поблагодарить за ваше профессиональное отношение к чужому непонятному коду — вы единственный, кого рекурсивный подход тут как минимум заинтересовал на «поиграться».
Все без исключения современные компиляторы применят в данном случае TCO, поэтому от синьёра я бы лично ожидал увидеть рекурсию.
Не очевидно, что это хорошее решение.
Рекурсивный код тут будет в три раза короче, ему не потребуются ни
O(n)вызовыstrlenв начале, ни куча условных операторов
Попробуйте выполнить reverse "in-place", и вы тут же обнаружите, что перед тем, как начать, вы будете вынуждены сначала найти конец строки.
Это и есть то, что, по сути, делает strlen.
И код не будет короче из-за всяких вспомогательных функций, которые потребуются при рекурсивном подходе.
и, самое главное, ему не потребуется
malloc, потому что можно по месту перезаписывать любой из двух наборов данных, а когда ввод отыквится — опционально переключиться на другой черезmemcpy.
Потребуется.
Я визуализировал ваш код на Elixir'е:
(6) do_add([h1 | t1]: [8, 4, 2], [h2 | t2]: [6, 8, 9], {remainder, acc}: {0, []})
(6) do_add([h1 | t1]: [4, 2], [h2 | t2]: [8, 9], {remainder, acc}: {1, [4]})
(6) do_add([h1 | t1]: [2], [h2 | t2]: [9], {remainder, acc}: {1, [3, 4]})
(2) do_add([], [], {1, acc: [2, 3, 4]})
(2) return: [1, 2, 3, 4]
(6) return: [1, 2, 3, 4]
(6) return: [1, 2, 3, 4]
(6) return: [1, 2, 3, 4]Здесь видно, что acc — это отдельный третий список.
Вот для него и нужен malloc.
Точнее, в данной реализации — многократный realloc.
Когда вызов вернется, потенциально придется разок вызвать
realloc, если осталась неучтенная единица.
А если передаются локальные или статические массивы?
Какой может быть realloc, если мы больший из них перезаписываем в качестве выходного?
Я уже приводил реализацию на эликсире, переписать её на си — не так уж сложно.
Это только так кажется.
Вам были не очевидны проблемы, которые я здесь обозначил.
Поэтому вы, наверняка, ошибаетесь и здесь.
Да, reverse по месту выполнить не удастся, это правда. Тут (и только тут) я ошибся.
всяких вспомогательных функций, которые потребуются при рекурсивном подходе
Это каких например?
Здесь видно, что
acc— это отдельный третий список.
Эликсир полностью иммутабелен. Си, когда я в последний раз заглядывал в спецификацию, — нет. И я черным по белому написал: по месту,
А если передаются локальные или статические массивы?
Это выходит за рамки задачи в том виде, как она была сформулирована. Если надо ничего не попортить — придется вызывать length и malloc, что попахивает.
Какой может быть
realloc, если мы больший из них перезаписываем в качестве выходного?
Я в том же предложении пояснил: единицу накопленную может потребоваться добавить.
проблемы, которые я здесь обозначил
Проблемы? Проблем нет, я погорячился с вызовом length, который на алгоритмическую сложность не влияет; все остальное — в силе.
Зато вам вообще не пришёл в голову единственно правильный и изящный способ решения, вы сразу приступили к код-ревью заведомо плохо поддерживаемого спагетти.
Да,
reverseпо месту выполнить не удастся, это правда. Тут (и только тут) я ошибся.
Я бы не был столь категоричен насчёт "только тут".
Это каких например?
Да тот же reverse.
Эликсир полностью иммутабелен. Си, когда я в последний раз заглядывал в спецификацию, — нет. И я черным по белому написал: по месту,
Все реализации, и даже изначально предложенная C-шная, возвращают третье значение, не трогая операнды.
Кстати, в изначально предложенном варианте в тестах в качестве операндов используются строковые литералы. Вы предлагаете в них писать?
Это выходит за рамки задачи в том виде, как она была сформулирована. Если надо ничего не попортить — придется вызывать
lengthиmalloc, что попахивает.
Это придётся делать в любом случае.
Вы почему-то верите в рекурсию как в волшебство какое-то.
Я в том же предложении пояснил: единицу накопленную может потребоваться добавить.
В realloc передаётся указатель.
Этот указатель должен быть получен от функций malloc, calloc или той же realloc.
Передача туда какого-то другого адреса приведёт к UB.
Проблемы? Проблем нет, я погорячился с вызовом
length, который на алгоритмическую сложность не влияет; все остальное — в силе.
Не получится использовать realloc, это все равно будет malloc, хотя это и не принципиально.
Но в предложенном вами варианте возникает неудобство, потому что, если переноса нет, то следует ли освобождать память, зависит от того, динамически она была выделена под операнд на вызывающей стороне или нет.
А если перенос был, то освобождать следует обязательно.
Более того, может быть использован один или другой операнд, что ещё больше усложняет дело.
Зато вам вообще не пришёл в голову единственно правильный и изящный способ решения, вы сразу приступили к код-ревью заведомо плохо поддерживаемого спагетти.
Вы имеет ввиду рекурсивную реализацию?
Я попробовал выполнить честную рекурсивную реализацию на C достаточно близко, насколько возможно, к вашему коду на Elixir'е, без reverse и без конкатенации.
Что интересно: 3 компилятора смогли применить TCO, а 4-ый не справился, а именно — MSVC.
char *do_addn(char const *const ns1,
char const *const ns2,
char const *const re,
char const *const n1,
char const *const n2,
char *const r,
char const c);
char *do_add1(char const *const re,
char *const r)
{
return memmove(r, r + 1, re - r);
}
char *do_add2(char *const r) {
*r = '1';
return r;
}
char *do_add3(char const *const ns1,
char const *const ns2,
char const *const re,
char const *const n2,
char *const r)
{
char const val = (*n2 - '0') + 1;
char const cry = val > 9;
*r = (cry ? val - 10 : val) + '0';
return do_addn(ns1, ns2, re, ns1, n2, r, cry);
}
char *do_add4(char const *const ns2,
char const *const re,
char const *const n2,
char *const r)
{
size_t const s = ns2 - n2 + 1;
memcpy(r - s + 1, ns2, s);
return do_add1(re, r - s);
}
char *do_add5(char const *const ns1,
char const *const ns2,
char const *const re,
char const *const n1,
char *const r,
char const c)
{
if (!c) {
return do_add4(ns1, re, n1, r);
}
return do_add3(ns2, ns1, re, n1, r);
}
char *do_add6(char const *const ns1,
char const *const ns2,
char const *const re,
char const *const n1,
char const *const n2,
char *const r,
char const c)
{
char const val = (*n1 - '0') + (*n2 - '0') + c;
char const cry = val > 9;
*r = (cry ? val - 10 : val) + '0';
return do_addn(ns1, ns2, re, n1, n2, r, cry);
}
char *do_addn(char const *const ns1,
char const *const ns2,
char const *const re,
char const *const n1,
char const *const n2,
char *const r,
char const c)
{
if (ns1 == n1) {
if (ns2 == n2) {
if (!c) {
return do_add1(re, r - 1);
}
return do_add2(r - 1);
} else {
if (!c) {
return do_add4(ns2, re, n2 - 1, r - 1);
}
return do_add3(ns1, ns2, re, n2 - 1, r - 1);
}
} else if (ns2 == n2) {
return do_add5(ns1, ns2, re, n1 - 1, r - 1, c);
}
return do_add6(ns1, ns2, re, n1 - 1, n2 - 1, r - 1, c);
}
char *pre_add(char const *const ns1,
char const *const ns2,
char const *const n1,
char const *const n2)
{
if (!*n1) {
if (!*n2) {
size_t const s1 = n1 - ns1;
size_t const s2 = n2 - ns2;
size_t const s = (s1 > s2 ? s1 : s2) + 1;
char *const r = malloc(s + 1);
if (!r) {
return NULL;
}
r[s] = '\0';
return do_addn(ns1, ns2, r + s, n1, n2, r + s, 0);
} else {
return pre_add(ns1, ns2, n1, n2 + 1);
}
} else if (!*n2) {
return pre_add(ns1, ns2, n1 + 1, n2);
}
return pre_add(ns1, ns2, n1 + 1, n2 + 1);
}
char *mega_add_recur(char const *const n1,
char const *const n2)
{
return pre_add(n1, n2, n1, n2);
}При этом на тех компиляторах. которые справились, производительность оставляет желать лучшего.
Я перемерил оригинальный код, свой код и этот код, что выше.
Для такого теста:
int main2(void) {
static char a[((size_t)1 << (sizeof(int) * CHAR_BIT - 1)) + 1];
memset(a, '9', sizeof a - 1);
test(a, "9");
return EXIT_SUCCESS;
}оригинальный код на некоторой машине исполняется, примерно, 5.184 секунд, мой вариант — 3.275 секунды, рекурсивный вариант выше — 10.984 секунд.
Чуда не произошло.
Ну, и рекурсивная реализация на C явно не блещет изяществом.
Мама дорогая.
Я никогда в жизни не зарабатывал денег написанием кода на c, но вот как примерно выглядит рекурсия здорового человека.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <limits.h>
void print_result(char* in1, char* in2, char *result) {
printf(" %10s\n+ %10s\n------------\n %10s\n\n", in1, in2, result);
}
char* do_mega_add(char* in1, size_t len1, char* in2, size_t len2, char* result, bool remainder) {
unsigned char current;
if (len1 == 0) {
if (remainder) {
[[clang::musttail]] return do_mega_add("1", 1, in2, len2, result, false);
} else {
result = result - len2 + 1;
memcpy(result, in2 - len2 + 1, len2);
return result;
}
} else if (len2 == 0) {
if (remainder) {
[[clang::musttail]] return do_mega_add(in1, len1, "1", 1, result, false);
} else {
result = result - len1 + 1;
memcpy(result, in1 - len1 + 1, len1);
return result;
}
}
current = *in1 - '0' + *in2 - '0';
*result = current % 10 + (remainder ? '1' : '0');
[[clang::musttail]] return do_mega_add(--in1, len1 - 1, --in2, len2 - 1, --result, current > 9);
}
void mega_add(char* in1, char* in2, void (*callback)(char* in1, char* in2, char* result)) {
size_t len1 = strlen(in1);
size_t len2 = strlen(in2);
size_t result_len = (len1 > len2 ? len1 : len2) + 1;
char* heap = malloc(result_len);
char* result = heap + result_len - 1;
*result = '\0';
result = do_mega_add(in1 + len1 - 1, len1, in2 + len2 - 1, len2, result, 0);
callback(in1, in2, result);
free(heap);
}
void test(char *in1, char *in2) {
mega_add(in1, in2, print_result);
}
// void main(void) {
// test("123", "1111111");
// test("12", "999");
// test("123", "9999999");
// test("999", "999");
// test("0", "0");
// test("1111111", "234");
// test("9999999", "234");
// }
int main(void) {
static char a[((size_t)1 << (sizeof(int) * CHAR_BIT - 1)) + 1];
memset(a, '9', sizeof a - 1);
test(a, "9");
return EXIT_SUCCESS;
}Сразу предупреждаю, что я всего лишь показал рекурсивный подход, я убежден, что если потратить еще полчаса, то его можно вылизать до более благоприятного состояния, и я не в курсе, как в c вообще принято.
И вот это всё - вместо простого цикла?
Мама дорогая.
Я портировал максимально близко к вашему коду Elixir'а.
О чём и написал.
Я никогда в жизни не зарабатывал денег написанием кода на
c,
Это — абсолютно перпендикулярная тема, которая не может быть критерием, ибо можно успешно зарабатывать и безобразным кодом.
Но дело — не в этом.
но вот как примерно выглядит рекурсия здорового человека.
Собственно, ваш код получится, если упростить мой, выбросив рекурсивное вычисление длин операндов, а также сдвиг результата для случая отсутствия финального переноса, и с'merge'ить большинство функций (do_add1...do_add6, do_addn) в одну, отойдя от кода на Elixir'е.
Также из-за отсутствия сдвига результата вам пришлось память освобождать, используя ранее запомненный указатель, который вернула функция malloc, а не возвращённый указатель с результатом, потому что без сдвига результата возвращённый указатель может не совпадать со значением, которое изначально вернула функция malloc.
В другом комментарии вы пишете:
Рекурсии не требуется знать длину списка, а обычному циклу с индексом — требуется.
Но в своём примере почему-то дважды вызвали strlen.
У меня эта работа выполнялась в pre_add.
Значит, чуда никакого нет, и рекурсии всё-таки требуется знать длину списка, просто это выглядит не так явно.
Если вашу рекурсивную реализацию сравнить с оригиналом (там — под спойлером), то выяснится, что ваша ничуть не меньше по объёму, и ничуть не более понятна.
Изящной её тоже не назовёшь, особенно, если доработать, чтобы не было упрощений, хотя реализация на Elixir'е ещё может таковой показаться.
Единственное изящное место у вас, по сравнению с моим кодом, это использование массива "1" в качестве числа с длиной 1 для, чтобы не обрабатывать отдельно случай распространения переноса с одним операндом, когда другой операнд уже "кончился", а скинуть эту работу на рекурсивную функцию, "прикинувшись" для неё, что второй операнд всё ещё не "кончился".
Однако, изящность в этом месте будет стоить быстродействия.
Собственно, когда я померил быстродействие своей рекурсивной реализации, то выяснилось, что она медленнее в разы по сравнению с не рекурсивной.
Ну, и самое главное, что касается рекурсии, TCO не гарантируется.
С вашим кодом MSVC справился, смог применить TCO.
С моим, который сложнее, — нет.
Все без исключения современные компиляторы применят в данном случае TCO, поэтому от синьёра я бы лично ожидал увидеть рекурсию.
Пока что единственный случай, где зачем-то понадобилась эта странная задача - собеседование на js. Где как раз TCO нет.
Пока что мы находимся в ветке, где достопочтенные господа меряются, у кого длиннее код на си.
Я в курсе, что существуют недоязыки без TCO, но эта задача взята с leetcode, где выбор решения не ограничен одним языком.
достопочтенные господа меряются, у кого длиннее код на си.
Достопочтенные господа меряются, у кого длиннее борода старше компилятор.
недоязыки без TCO
На мой субъективный (подчеркиваю) взгляд, ценность ТСО сильно преувеличена. Да, если в ЯП не завезли цикл, то фича жизненно необходима. В противном случае все эти ваши хвостовые рекурсии часто выглядят, как будто автору просто было скучно делать через цикл и захотелось чего-то этакого. По объему кода получается плюс-минус одинаково, по понятности тоже. Всё имхо, конечно.
Рекурсии не требуется знать длину списка, а обычному циклу с индексом — требуется. Из рекурсии легко выйти по очень сложному условию, в цикле это превратится в спагетти. В конце концов, рекурсия — это выражение (возвращает результат), а цикл — нет.
И это приводит к дикой области видимости переменных, размазанных по коду: тут объявлено, тут — внутри цикла — как-то изменено, зачастую — исподволь и очень скрытно.
Я бы еще понял, если бы вы сказали, что comprehersions заменяют рекурсию. Но циклы? Вы еще goto предложи́те.
а обычному циклу с индексом — требуется.
Совсем нет, если цикл while. Просто в условии цикла пишите ровно то же самое, что у вас в рекурсии проверяется. Все ваши остальные комментарии про выход и переменные - туда же.
Если ваша рекурсия с хвостовой оптимизацией, то она компилируется в тот же код, что и цикл.
Все ваши остальные комментарии про выход и переменные — туда же.
Там основной комментарий — про выражение и область видимости переменных, которые для цикла надо объявлять снаружи, что в 2025 году — прям не просто попахивает, а воняет.
Если ваша рекурсия с хвостовой оптимизацией, то она компилируется в тот же код, что и цикл.
Я в курсе, но мне взрослые дяди рассказывали, что люди придумали языки высокого уровня, чтобы не надо было читать машинные коды.
Там основной комментарий — про выражение и область видимости переменных, которые для цикла надо объявлять снаружи, что в 2025 году — прям не просто попахивает, а воняет.
Давайте с языком определимся, я могу про C++ сказать. Переменные можно объявлять и в цикле, если надо.
Если нужны переменные, которые существуют на всех итерациях, то в рекурсии они тоже должны быть объявлены где-то за вызовом функции. И еще при этом переданы во все вызовы. И от точки вызова они будут жить и после вызова, ровно как с циклами. А что, если у вас этих переменных 10 штук? Функции с 10+ параметрами нечитабельны вообще. Если же переменных мало и рекурсивный код выглядит терпимо, то в том же C++ можно нужные вам переменные объявить в инициализации цикла.
Если вам так надо ограничить видимость, можно завести блок.
Полная аналогия. Все, что вы можете сделать с областью видимости с рекурсией, можно сделать и с циклом, и оно будет не менее читабельно.
я могу про C++ сказать
Да хоть про B.
Вы специально игнорируете мои слова про loop is not an expression in c++?
# recursion
private int fac_rec(n, acc) {
return n <= 1 ? acc : fac_rec(n - 1, n * acc);
}
int fac(n) {
// ⇓⇓⇓⇓⇓⇓⇓⇓⇓⇓⇓⇓⇓⇓⇓
int result = fac_rec(n, 1);
return result;
}
# loop
int fac(n) {
// ⇓⇓⇓ а вот это ВООБЩЕ не скомпилируется
// int result = for (int acc=1;n>=1,n--) { acc * n }
// поэтому придется определить acc в скоупе функции
// и изменять его из дочернего скоупа (цикла)
int result = 1;
for (;n>=1,n--) { result * n };
return result;
}Такой код гораздо проще поломать, например, особенно когда между объявлением и изменением внутри цикла — десять других строк.
Все еще не очень понимаю проблему. Тут дело в том, что мы можем объявить result сильно далеко от того места, где мы циклом считаем? Ну допустим, мы считаем не факториал, а что-то сложное комбинаторное и делаем кучу вычислений с result до вот этого фаториала. Ну так и рекурсивном примере будет точно так же.
Учтите, что инициализация result=1 - это часть алгоритма рассчета. Это то, что у вас в рекурсии в параметре 1. И его-то где-то далеко делать совсем глупо. Хотя и в рекурсии вы тоже можете объявить acc где-то за экраном, там присвоить 1, и в точку вызова fac_rec протащить, но зачем? Тут ничего из рекурсивного подхода не мешает вам написать такой же ужасный код, если вы нацелены его написать. И ничто вам не подсказывает не писать его. То, что вы тут 1 передаете в первом вызове, а не заводите где-то далеко переменную - не является чем-то интуитивным для рекурсии.
int result = for (int acc=1;n>=1,n--) { acc * n }
У вас присовение 1 потерялось. Кроме того, если вам так хочеться логически обособить вычисление и показать, где получается результат, то можно обернуть вычисление в функцию.
Если у вас все из функций, то этот простой совет для логической организации программ автоматически получается, да. Но в целом функциональный подход не однозначно читабельнее. Где-то лучше, где-то хуже. Попробуйте на рекурсии какой-нибудь алгоритм Укконена рализовать, а потом сравните с итеративным, вам итеративный больше понравится.
Я нигде не утверждал, что рекурсия — панацея и лучше всегда. Нигде. Хотя бы потому, что я не идиот.
Я нигде не утверждал, что рекурсия — панацея и лучше всегда. Нигде. Хотя бы потому, что я не идиот.
А это тогда что было?
поэтому от синьёра я бы лично ожидал увидеть рекурсию
Хотел уже написать «подумайте и поймете», но вспомнил, что «подумайте» — это не ваш случай.
Это было моё ожидание того, как надо решать одну конкретно оговоренную задачу.
как надо решать одну конкретно оговоренную задачу.
и вот в этой конкретной задаче код циклом короче и понятнее рекурсивного. Но вы стали утверждать что этот код хуже, потому что объявлять переменную вне цикла - зашквар и не для сеньеров. Но в этом конкретном примере это вообще не проблема. Привели в пример факториал, в котором тоже никакой проблемы нет. Остается только вариант, что есть какие-то странные примеры, где эта проблема есть, но когда вам привели аргументы, что в общем случае эта же проблема есть и у рекурсии вы вдруг стали отрицать общий случай. Такое себе.
Ваш набор тестов покрывает все случаи?
Мой набор тестов покрывает все случаи за исключением случая реально длинных чисел, но я уже потерял счёт количеству раз, когда я сказал, что это proof‑of‑concept, демонстратор «смотри, как папа может» кода, а не o
Мои варианты тестов, которые демонстрируют низкое качество вашего кода, вы предпочитаете не замечать?
Я «Ваших тестов» вообще в упор не вижу. Мои были прямо под кодом — а Ваши где?
Ваши программистские рефлексы диктуют вам в любой непонятной ситуации использовать тип int и не обрабатывать возможные ошибки.
Алё, гараж, я на Си последний раз писал двадцать лет назад, когда 16 мегабайт памяти было овердофига. Естественно, что мои рефлексы не заморачивались поддержкой гигабайтов памяти.
признавать ошибки не умеете совсем.
Ви так говорите, как будто я с Вами спорю. Вот только это не «ошибки», а сознательно оставленные упущения, потому как это, ёпрст, комментарий на хабре, а не код, который вотпрямща пойдёт в прод!
Мой набор тестов покрывает все случаи за исключением случая реально длинных чисел,
Ну, то есть, не все.
но я уже потерял счёт количеству раз, когда я сказал, что это proof‑of‑concept, демонстратор «смотри, как папа может» кода, а не o
"Папа может" безобразно, на уровне джуна.
Я «Ваших тестов» вообще в упор не вижу. Мои были прямо под кодом — а Ваши где?
Очевидно, во фрагментах, которые я предоставлял:
int main(void) {
static char a[((size_t)1 << (sizeof(int) * CHAR_BIT - 1)) + 1];
memset(a, '9', sizeof a - 1);
test(a, "9");
return EXIT_SUCCESS;
}..Данный фрагмент как раз относится к случаю реально длинных чисел, о котором вы упоминали в том духе, что ваши тесты этот случай не покрывают.
Алё, гараж, я на Си последний раз писал двадцать лет назад, когда 16 мегабайт памяти было овердофига. Естественно, что мои рефлексы не заморачивались поддержкой гигабайтов памяти.
Разве в то время возвращаемое функцией malloc значение не требовалось проверять на NULL?
К тому же в то время ещё можно было реально встретить платформы с 16-битным int'ом.
Это значит, что достаточно было 32/64 КБайтных чисел, чтобы получить такой же эффект.
сознательно оставленные упущения
Вот про "сознательно оставленные" не верится совсем.
Вот про "сознательно оставленные" не верится совсем.
Повторяю в шестой раз: Вы реально ожидаете в комментарии на Хабре production-ready кода? Может, Вы ещё и в Деда Мороза верите?
Во-первых, сеньоры разные бывают.
Да, иногда очень разные.
А во-вторых, я хотя бы написал рабочий код — а Вы только критикукуете.
Код — не рабочий, и я это аргументированно показал.
Именно из-за такого кода, как ваш, многие современные программы глючат, особенно в условиях ограниченного запаса по памяти.
А "критикукуете" здесь вы, и, в основном, не по делу.
И ещё чванитесь перед молодёжью, хотя и нечем.
Именно из-за такого кода, как ваш, многие современные программы глючат, особенно в условиях ограниченного запаса по памяти.
С одной стороны у вас запас памяти ограничен, а с другой - у вас числа по 2 гигабайта, чтобы знаковый int переполнялся. Вы там определитесь как-нибудь.
Он ещё хочет, чтобы накорябанный на обороте салфетки код был прям хоть ща в прод.
С одной стороны у вас запас памяти ограничен, а с другой - у вас числа по 2 гигабайта, чтобы знаковый int переполнялся. Вы там определитесь как-нибудь.
Очевидно, вы не не поняли, на что был намёк.
В этом случае:
$ ./1
mega_add: len1: -3, len2: -3, res_len: -1
mega_add: result_str: (nil)
Segmentation fault
$ возникает Segmentation Fault.
Вы поняли, почему?
Поясняю: потому что после вызова функции malloc указатель, который она вернула, не был проверен на `NULL`.
То, что функция malloc может вернуть NULL, и что поэтому необходимо проверять на NULL это значение, ясно видно по распечатке значения result_str выше и по результату дальнейшего исполнения программы без проверки его на NULL.
Фрагмент кода, чтобы было понятно, причём тут result_str:
char* result_str = malloc(res_len);
printf("%s: result_str: %p\n", __func__, result_str);Отсутствием проверки значения, которое вернула функция malloc, часто грешит код современных программ, и в существенной степени именно поэтому они так себя ведут в случае очень малого запаса по памяти.
Переполнение знакового int'а может приводить к более широкому кругу глюков.
Замечу также, что в 2025-ом году 2 гигабайта — это уже относительно небольшой объём памяти, поэтому ваше "Вы там определитесь как-нибудь" звучит неубедительно.
И ещё чванитесь перед молодёжью
Конечно! Я что, зря этого момента джва года двадцать пять лет ждал?
Может не стоит так делать arr1[i--]?
Во-первых стиль статьи - какое-то прямо фе, прямо режет глаз. Тем более если человек считает такую задачу сложной и достойной хабра. Могу еще идей подкинуть - задача про банкомат, обход деревьев, проверка палиндромов. Тысяча статей уже написано, еще три тысячи на подходе.
Во-вторых задача решается в три строчки;
И в-третьих как уже правильно писали - сложить два числа любой длины можно через BigInt, потому что если они не влезают туда, то и не влезут в массив (помним же, что числа в js по умолчанию float?).
Вообще, эта длинная арифметика в столбик, это именно то, что в BigInt и написано. Только более оптимальное. Но ясно, что интервьюверу хочется посмотреть, как вы код пишите.
Далее, такие числа-массивы логично хранить перевернутыми. Младший разряд по индексу 0, старший - N-1. Тогда добавление новых разрядов идет в конец, а не начало, что обычно быстрее (правда в js все одинаково медленно, хоть и O(1), потому что это там не массивы а хешмапы на самом деле).
Так что мой первый инстинкт был бы числа развернуть. А потом уже сложение в столбик - это один простой цикл. Бонусом тут идет, что умножение на маленькое число - практически такой же цикл. Только теперь новых разрядов может быть больше одного.
правда в js все одинаково медленно, хоть и O(1), потому что это там не массивы а хешмапы на самом деле
Не одинаково.
push работает быстро, это только добавление элемента. А unshift меняет ключи у всех.
Да и оптимизирующий компилятор v8 давно умеет превращать эти структуры в настоящие массивы, если там элементы одного типа.
как вы код пишите.
Пишите, Шура, пишите! (почти ©)
Непонятно для чего такая большая статья? Автор не сталкивался с алго-задачками и его впечатлило решение? А так это easy-задача с leetcode, причем там есть много изи задач намного сложнее.
Здесь наивное решение, с созданием итогового массива с размером max(число разрядов 1 или 2 числа) + 1, заполненного 0. А потом проход с конца и суммирование с учетом переноса(суммируем цифры 1,2 числа и итогового, где может быть перенос, можно использовать деление по модулю, чтобы уйти от условий), если какое-то кончилось раньше, то его разряд равен 0…, перенос можно сразу писать в итоговый массив, разворот не нужен…
При выводе ответа, если первый(старший) разряд 0, то его не выводим
Я на js не пишу, но получилось как-то так:
/**
* @param arr1 int[]
* @param arr2 int[]
* @returns int[]
*/
function addArrays(arr1, arr2) {
const max = Math.max(arr1.length, arr2.length);
const result = new Array(max + 1).fill(0);
let i = arr1.length - 1;
let j = arr2.length - 1;
let carry = 0;
for (let k = max; k >= 0; i--, j--, k--) {
let sum = carry + (arr1[i] ?? 0) + (arr2[j] ?? 0);
if (sum < 10) {
carry = 0;
result[k] = sum;
} else {
carry = Math.floor(sum / 10);
result[k] = sum % 10;
}
}
if (result[0] === 0) {
result.shift();
}
return result;
}
console.log(addArrays([9,9], [9]));
console.log(addArrays([1, 3], [2, 2]));
- if (sum < 10) {
- carry = 0;
- result[k] = sum;
- } else {
- carry = Math.floor(sum / 10);
- result[k] = sum % 10;
- }
+ carry = Math.floor(sum / 10);
+ result[k] = sum % 10;
Лишний код же, там нет условия, если приглядеться.
На мой взгляд расточительство это ваше деление на 10, дорого, дорого.
Хотя if тоже не самое дешевое
Код не мой, я просто указал на лишнее условие, которое не делает ничего. «Деление на 10 — дорого» — это та самая premature optimization, которая по Кнуту — самый страшный грех в разработке. Перед тем, как этот код оптимизировать, нужны бенчмарки.
Я не знаю как по Кнуту, а меня учили, что деление и умножение дорого, если есть вариант обойтись без него, надо обходиться )
На самом деле самая дорогая операция тут - это получение метода floor у объекта Math.
Однако, подобные оптимизации - это экономия на спичках, они бессмысленны потому что отнимают время, которое могло бы быть потрачено на более сильные оптимизации.
if в цикле при современном состоянии дел обычно дороже любой арифметической операций.
не уверен насчет оптимизатора js, но после оптимизатора с++ не будет ни того, ни другого: деление превратится в умножение на reciprocal (throughput = 1 инструкция/такт), а if - в conditional move (2 инструкции/такт). Мне кажется, ни то, ни то не будет узким местом, скорее уж обращение к памяти
Если Math.floor (sum / 10) заменить на ~~(sum * 0.1), то будут сэкономлены ещё несколько тактов процессора.
Деление и умножение дробей отличаться по производительности не должны бы. Но вот первую конструкцию V8 почти наверняка развернет в целочисленное умножение. Вторую уже совсем не факт.
Я сделал такой HTML-файл для тестирования:
Скрытый текст
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>Mul-Div TEST</title>
</head>
<body>
<h1>Mul-Div TEST</h1>
<script>
function TestDiv (a)
{
document.write ("TestDiv<br>");
let s = 0, n = a.length;
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
s += a[j] / 10;
return s;
}
function TestMul (a)
{
document.write ("TestMul<br>");
let s = 0, n = a.length;
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
s += a[j] * 0.1;
return s;
}
let n = 10000, a = new Array (n);
document.writeln ("Start preparation.<br>");
for (let i = 0; i < n; i++)
a[i] = i;
document.writeln ("Start calculation.<br>")
let d1 = new Date ();
/* let s = TestDiv (a); */
let s = TestMul (a);
let d2 = new Date ();
let dt = d2.getTime () - d1.getTime ();
document.writeln ("Sum = " + s + "<br>");
document.writeln ("Calculation time: " + dt + " ms<br>");
</script>
</body>
</html>И загрузил его в браузер несколько раз, меняя let s = TestDiv (a) на let s = TestMul (a) и наоборот. Получилось вот что:
TestDiv
Sum = 49995000000
Calculation time: 511 ms
TestMul
Sum = 49995000000
Calculation time: 244 msСекундочку, надо ещё после умножения /деления сделать | 0 или что-то аналогичное, чтобы получить целочисленный результат. Ну и погреть надо ~10к раз перед тем как время мерить, чтобы JIT точно сработал.
Ещё бы желательно время мерить через performance.now, но для такого расхождения это не так критично.
Забыл, что мы о дробях. Да, показательно. Я бы конечно убедился, что умножение таки дробное, но думаю, всё сойдется таким же образом.
Upd2. Нет, всё-таки надо погреть. И всё-таки надо воткнуть / 10.0. На всякий случай)
Сразу в двоичном бы считали и всё, так можно хоть гигабайтные массивы складывать по-порядку
Миллениалы изобрели сложение в столбик)
Я тут не завсегдатай и это, кажется, мой первый комментарий. Но давно на хабре стало нормой публиковать статьи с явными признаками авторства ИИ (как минимум над некоторыми частями)? Об этом говорят и «опечатки» автора, и явно иишные выражения в тексте. Честно говоря, даже выглядит как пранк: статья про решение базовой задачи с литкода сгенеренная в чате ГПТ с целью проверить комьюнити.
Умение работать с строковыми данными (ведь числа могут быть гигантскими, и bigint не спасет).
Работа со строковыми данными не раскрыта.
Внимание к краевым случаям — это как раз то, что ломает продакшен в пятницу вечером.
...
5 ошибок, которые превратят ваш код в тыкву
addArrays(undefined, null)
Написаный алгоритм выглядит элигантно, но он совсем не удовлетворяет тезисам, которые заявлены в статье. Сложность задачи не только в том, чтобы написать красивое решение для идеальных данных, а чтобы результат был предсказуемый при любых данных. Да, красота при всех необходимых проверках, конечно же, пострадает
Вот решение, правда не на джаваскрипте, с предсказуемым результатом на любых данных. И это еще эликсир слабо типизирован. На хаскеле это будет еще проще, а идрис докажет результат в компайлтайме.
Вызов метода reverse в статье удваивает требования к памяти и времени. Со временем вряд ли что-то можно сделать принципиальное (хотя числа можно просто читать задом-наперёд, раз уж выбрали массив), а вот удвоение памяти вызывает большие вопросы.
Тут лучше было бы использовать разрушающее обращение массива или обойтись вообще без него.
С чего бы разворот массива на месте удваивал требования по памяти, и какой из способов разворота массива вы называете разрушающим?
В посте написано:
return result.reverse(); // ПереворачиваемЯ не знаток джаваскрипта, но понимаю так, что result – это объект-массив, а reverse() – его метод для разворота. Оттого, что вы вычислите значение result.reverse(), сам объект result ведь не изменится, так ведь? А это значит, что в памяти массив будет размещён дважды, один раз в виде поля объекта result, а второй раз – в виде временно построенного результата метода reverse().
Upd: посмотрел – как ни странно, это разрушающий метод. Так что я был неправ, замечание снимается. JS – удивительный язык.
Пару лет назад, по многочисленным просьбам трудящихся, добавились иммутабельные методы с копированием: toReversed, toSorted и т.д
Мутирующий он, а не разрушающий. Разрушающий метод - это немного про другое.
В чём Вы видите разницу?
Мутирующий метод оставляет объект в известном состоянии в соответствии со своим назначением. Разрушающий метод либо вовсе не оставляет объекта, либо оставляет его в непригодном для использования состоянии, либо в пустом (но перевод объекта в пустое состояние - побочный эффект, а не основное назначение метода).
Применительно к обсуждаемому методу, разница между мутирующим и разрушающим методом - в том, что можно написать вот так:
result.reverse();
return result;
С разрушающим методом такого бы не прокатило.
Разрушающий метод либо вовсе не оставляет объекта, либо оставляет его в непригодном для использования состоянии, либо в пустом
Это вообще возможно в джаваскрипте?
Беглый гуглинг по словам "destructive methods javascript" не находит ничего в вашей терминологии.
Удалить объект - невозможно, а оставить в непригодном состоянии - что может помешать?
Вот пример: ArrayBuffer.prototype.transfer()
(не туда)
Это из собеседования на фронтенд разработчика? В гробу я видал авторов таких вопросов на собеседованиях на фронтенд позиции. Я понимаю если еще речь идет о позиции бэкенд разработчика, где подобные алгоритмичные навыки действительно применимы, но для того будет писать UI логику скорее важней гуманитарные навыки, т.к. по большей части вам придется общаться с дизайнерами, чувствовать отдачу от интерфейса, разрабатывать интуитивно понятный API компонентов, где важнее навыки нейминга, знание популярных тенденций и шаблонов проектирования UI систем и т.п. Вообще главный навык фронтенд разработчика - это находить тонкий баланс между хотелками продакта, безудержной фантазией дизайнеров и кучей легаси кода, и техдолгов. А вот эта вся математика, алгоритмика - это то, что вам понадобиться в <1% случаев при разработке фронтенд приложений, а скорей всего не понадобиться никогда. И если кто то на собеседовании на фронт разработчика начинает втирать такую задротскую ботаническую дичь вроде "как создать язык программирования" , то разворачивайтесь и уходите, потому что это значит, что фронтендом в этой компании рулит какой то инженер-техник с императивным складом ума, и он понятия не имеет чем на самом деле дышит фронтенд. А для истинных фронтендеров, у кого функциональное и визуально-пространственное мышление, жизнь в такой компании станет адом, в котором их сильные стороны просто не будут восприниматься как что-то требующее внимания.
Сильные стороны — это сделать так, чтобы девять из десяти сайтов — адски тормозили на самой современной машине?
Если отвлечься от дичи примеров на leetcode, и вернуться к «истокам» то Первоначальная идея кодинга на собеседовании пошла от Джеффа Атвуда https://blog.codinghorror.com/why-cant-programmers-program/
Идея в том чтобы проверить что человек в принципе может понять проблему и написать код.
Но как всегда если индикатор становится целью, то он уже не является хорошим индикатором :)
Я тут накатал-таки "Письмо ученому соседу" ... https://habr.com/ru/articles/892838/
Сложить два числа-гиганта: как я прошел квест на собеседовании в Бигтех
У меня дежавю - лет 20 назад, когда я учился в школе и поехал на олимпиаду по информатике - там был такой вопрос. И тут ещё даже легче - есть управляемый язык и сразу сказали что числа в массиве. А тогда был C, Pascal и задание было простое - есть число в виде строки длинной 20 символов - нужно уметь складывать и вычитать. И всё. Мне тогда вообще в голову не пришло что эту строку можно рассматривать как массив символ, что бы использовать сложение в столбик. Только потом, после олимпиады, на разборе, рассказали.
А на литкоде разве нет такой задачи?
Есть, конечно. Она там easy: https://leetcode.com/problems/add-strings/description/
Напомнило как писал код для z80 на assembler. Там тоже длинные числа нужно было побайтово скадывать и перенос не забывать.
Интересно услышать от автора ответ на вопрос «А в итоге чем приходится заниматься?». Конечно после всех этих мифических задач с конями в квадрате.
Особенно зная репутацию Битрикса в PHP сообществе
Сложить два числа-гиганта: как я прошел квест на собеседовании в Бигтех