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
triampurum January 25th, 2015
Все там хорошо с памятью, реюз того же блока памяти.

dmih January 25th, 2015
Да нет же, но это сложно обсуждать без алгоритма. :) пока воздержимся.

Я уж не говорю о том (помимо первого возражения), что СТРОГО сложность подобной декомпозиции никогда не O(n), т.к. таковой не является, например, вычисление корня (в данном примере).

Это вот то, о чем я писал во втором комменте. Строгое O(n) нас ОЧЕНЬ ограничивает. Там к машине Тьюринга о трех пальцах всё сводится настолько стремительно, что пространство для маневра сужается фатально и сразу.

  • 1
?

Log in

No account? Create an account