?

Log in

No account? Create an account
Previous Entry Share Next Entry
photo25

Прекрасный трололо-вопрос для интервью

У вас есть 2 отсортированных массива integer'ов, расположенных в памяти, допустим, один за другим. (длины известны) Напишите алгоритм, который смержит их в один сортированный массив без дополнительной памяти, за O(n) времени.

(Вначале стоит просто спросить про мерж, потом добавить про память и время.)

Ну и да, придумать полный вариант за время интервью нереально, но если расслабить констрейнты - тогда всё хорошо. Т.е. это скорее personality test, нежели coding test.

UPD: Пример входных данных:

6 (длина), 7 (длина), 10, 11, 12, 100, 101, 102, 1, 2, 3, 4, 200, 210, 220 (13 байт данных)

This entry was originally posted at http://wizzard.dreamwidth.org/418797.html. It has comment count unavailable comments. Please comment there using OpenID.

  • 1
sassa_nf January 25th, 2015
нутк, а дубовый мёрдж разве не в "констант мемори" за O(n) времени?

wizzard0 January 25th, 2015
Дубовый мерж в O(n) памяти и O(n) времени.

sassa_nf January 25th, 2015
верно, а расскажи мне, как это задачи с массивами могут быть "констант мемори".

мемори у задачи с массивами и без того O(n).

wizzard0 January 25th, 2015
С обьемом дополнительной памяти, не зависящим от размера массивов.

sassa_nf January 25th, 2015
я понимаю, что ты хочеть спросить, но я не уверен, что "дополнительную память" можно выразить в виде O(...)

wizzard0 January 25th, 2015
"У нас нет malloc и new", во!

UPD: Бльоооо... А стэк кто-то считает во всех этих алгоритмах?

Edited at 2015-01-25 10:03 am (UTC)

sorcerer_ January 25th, 2015
Нет конечно, и вообще в современной архитектуре большинство O() бесполезны, т.к. ничего не говорят о перформансе.

sorcerer_ January 25th, 2015
Хмм, надо же, есть чуваки, которые разбираются в теме, даже про дарк силикон. :)

sharpc January 25th, 2015
Если это вопрос, то да, стек считают в асимптотике памяти.

sassa_nf January 25th, 2015
так у тебя со стеком решение? а то со стеком тривиальное решение есть.

wizzard0 January 26th, 2015
Нет, без стэка. Собственно там на пейпер уже кинули ссылку, правда я не уверен, что на тот)))

  • 1