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
dmih January 26th, 2015
Мы N раз перемещаем блоки, которые имеют размер sqrt (N).
В двух словах, где я тупой?

wizzard0 January 26th, 2015
Я там выше сказал хуйню.

1. sqrt(N)*log(sqrt N) перемещаем головы блоков

2. sqrt(N) раз перемещаем блоки, которые имеют размер sqrt(N)

dmih January 26th, 2015
2 почему?

dmih January 26th, 2015
а на станице 41 внизу там что написано?

dmih January 26th, 2015
вообще в целом я отстал конечно от таких методов подсчета сложности.....

dmih January 26th, 2015
но в целом отлично, спасибо

после 5 лет работы с fft это не супер новости, но не думал, что почти линейно бывает

sassa_nf January 30th, 2015
У меня важный вопрос.

Означает ли это, что любой алгоритм сортировки N*log(N) мы можем улучшить до N*sqrt(log(N))? Потому что вместо N*log(N) у нас сортировка двух N/2*(log(N/2)) по сложности равно N*sqrt(log(N)), плюс мёрж стоимостью N не влияет на асимптоту.

Что-то тут не так.

dmih January 26th, 2015
Т.е. я прокомментирую своё удивление вольной трактовкой сложности.

Используя написанное, осознал ответы на свои вопросы, но осознать полноту соответствия задаче пока не смог.

Появились вопросы про память, про хранение координации подблоков, про которое я писал исходно в "а-ля доказательстве".

The two blocks are merge using an internal buffer of size ≈ ν, где v = sqrt (O(n)),

или

We encode these permutation cycles in either of the following two ways.
(1) With the use of O(lg(n)) extra bits or
(2) Permutation of individual block elements at the end of local block merge to encode the
correct sorted location of individual blocks.
- потому что это требуется для стабильности, без который данный мерж некорректен,

и так далее.

Т.е. эта категория алгоритма для своей реализации всё равно дает выхлоп либо в память, либо в свопы. Собственно, прочтя бумагу с начала, стало ясно, что его исходное самое простое состояние я практически сразу схематично придумал в момент формулировки того комментария и практически сразу и отбросил как не соответствующее условиям.

Поскольку поздно и я не осилил всю бумагу, остается вопрос: действительно они ходят вокруг и около оптимальной реализации по описанному ТОБОЙ сценарию, или ОДНОВРЕМЕННОЕ условие O(n) операций и O(1) памяти там ТОЧНО не выполняется?
На мой взгляд, ответ второй.

  • 1
?

Log in

No account? Create an account