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
kodt_rsdn January 25th, 2015

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


А в реальной задаче лучше сделать что-нибудь простое, вплоть до тупо отсортировать за логлинейное время и логарифмичную память.


dennis_chikin January 25th, 2015
Я ничего не понял про "константчего-то-там", но это разве не частный (наилучший) случай для сортировки "слиянием" ?

wizzard0 January 25th, 2015
Сортировка слиянием требует буфера, куда сливаем. Тут буфера нет.

dennis_chikin January 25th, 2015
Зачем буфер-то ? Всю жизнь делалось в той памяти, которая есть. Для того оно, собственно, и "слиянием".

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

zerkms January 25th, 2015
Обычная сортировка слиянием - n*logn.

Та сортировка, которая слиянием и линейная - называется external и требует буфера в размере всех данных (т.е. плюс O(n) сверху)

wizzard0 January 25th, 2015
1) Это вопрос именно на поговорить
2) Там всё хорошо с константами

  • 1
?

Log in

No account? Create an account