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) времени.

alamar January 25th, 2015
Тоже не понимаю, в чем тут проблема. Там же только перестановкой интов обойтись можно?

wizzard0 January 25th, 2015
Наивная перестановка интов - это selection sort, он не O(n). Или имеется в виду другое что-то?

ufm January 25th, 2015
Так как не указан ни язык программирования, ни то, что после мержа массив должен быть сортированным, то в Ц подобном - указатель на первый массив и есть указатель на смерженный массив (один за другим, длины известны).
Если нужен отсортированный - натравить sort.

wizzard0 January 25th, 2015
> sort
O(n log n) времени

> что после мержа массив должен быть сортированным
Резонно, допишу

kodt_rsdn January 25th, 2015

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


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


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

anonim_legion January 25th, 2015
Очевидно, что итоговый алгоритм будет просто менять местами элементы двух массивов. А по какому условию это будет делаться - надо подумать.

Только вот зачем это вообще делать?


32bit_me January 25th, 2015
>Очевидно, что итоговый алгоритм будет просто менять местами элементы двух массивов.
Очевидно, ведь этим занимаются все алгоритмы сортировки.
> А по какому условию это будет делаться - надо подумать.
В этом и состоит задача.
> Только вот зачем это вообще делать?
Чтобы отсортировать массив, очевидно же.

kray_zemli January 25th, 2015
Около часа думал, но, кажется, допёр. Первый массив храним как бы кольцевым буфером. Мержим всё по частям константной длины M, в результате чего теряют актуальность головные части обоих массивов. Смерженные блоки помещаем в начало памяти по порядку (т.е. с начиная с начала первого массива), забирая эту память у кольцевого буфера по мере необходимости. Взамен даём кольцевому буферу память из уже обработанной части второго массива, куда переносим данные, вытесненные из отобранной памяти, одновременно дефрагментируя его с той стороны (что имеет порядок M). Писать код лень.

ЗЫ: А может, и не получится O(N)

Edited at 2015-01-25 11:05 am (UTC)

kodt_rsdn January 25th, 2015

Ну и вместо 2 упорядоченных массивов получим кучу мелких упорядоченных массивов.


_oxpa_ January 25th, 2015
я читаю условие и не понимаю, в чём сложность. А потом читаю пример входных данных и не понимаю, как оно соотносится с задачей

vp January 25th, 2015
Или O(N), и мерж с выделением доп памяти равной суммарной длине обоих массивов, куда вписывается минимальное из двух сравненных обоих массивов.

Или если без выделения памяти, тогда сложность будет уже никак не O(N). То есть сливаем два массива изменением длины 1го массива (т.к. лежат последовательно), и тупо сортируем результат.

Подписался на комменты, конечно же :)


bvlb January 25th, 2015
Имеется ввиду - "на месте"? Т.е. на месте этих двух массивов должен появится смерженый массив?

wizzard0 January 25th, 2015
Да

metamage January 25th, 2015
Может просто radix sort'ом отсортировать?

wizzard0 January 25th, 2015
Детальнее?

dmih January 25th, 2015
А я буду очень оригинален, если скажу, что за O(n) это не делается?

(а вот хотя вижу уже один такой коммент)

UPDATE; я бы даже взялся доказать объяснить, почему, хотя сто лет уже такого не делал и не уверен конечно в трезвом уме и здравой памяти :)

т.е. в ОЧЕНЬ общих словах и БЕЗ особых раздумий: Возьмем случай, когда m2[0] > m1[0] && m2[last] < m1[last], это дает нам необходимость перетасовать всё практически целиком;
В процессе перетасовки будет очевидная необходимость хранить кусочно-отсортированные куски первого массива, когда ни будут уезжать из своей области, в противном случае мы теряем начальное преимущество отсортированности.
Хранить эту промежуточную адресацию (= координаты частично сортированных областей) мы их очевидно можем либо явно, либо в стеке.
Само по себе это не вредно. Для нарушения o(n) требуется дополнительно показать, что количество случаев, когда необходим внешний отсортированный отрезок, больше любого фиксированного N.
Это скорее всего делается либо рекурсивно, либо с помощью контр-примера.

Edited at 2015-01-25 02:41 pm (UTC)

triampurum January 25th, 2015
почему, делается, это, оказалось, более-менее стандартная задачка.

happynewbear January 25th, 2015
может чушь написал, но быстро придумалось :)

Взять второй массив, читать с конца, сравнивать с концом первого, если больше - свапнуть, и так до головы, получили сортнутый хвост, проверили что начальный элемент меньше конечного во втором, иначе повторили с элемента второго массива который меньше хвоста в первом (хвост не до конца сортнут),
потом первый массив побили по первому неравенству соседних элементов и тем же алгоритмом.

sleepy_drago January 25th, 2015
это мне напомнило как мне один раз в жизни понадобился пул с O(1) очисткой (clear но без переаллокаций). Тоже пришлось помучаццо =)
а так вопрос зачем конечно убивает всю интригу =)

wizzard0 January 25th, 2015
Один раз в жизни, дада.

vp January 25th, 2015
Хозяин! Правильный ответ будет? Уже нет силы ждать! :)

amarao_san January 25th, 2015
А что тут придумывать-то. Идём по массивам, как единому массиву, свопим если больше, переходим к следующему, если меньше. О от н по памяти и цпу.

vp January 25th, 2015
Т.е. на приведенных тестовых данных вы это на бумажке не пытались делать? Так и запишем.

nsin real January 25th, 2015
Да легко. Ты написал слово "integer", а не "число", поэтому я исхожу из предположения, что имеется в виду что-то типа 32/64-битного числа (т.е. числа с ограниченной разрядностью). Хотя у тебя вообще походу байты, судя по входным данным.
Есть такая штука как counting sort, она же сортировка подсчетом. Одна из немногих сортировок, которые обладают линейным временем исполнения. Если быть точнее, то она по времени O(n+k) и по памяти O(k); где n - количество элементов в массиве, k - количество возможных элементов (т.е. для int32 мы получаем 4 миллиарда возможных элементов). Тем не менее, поскольку разрядность нашего числа ограничена, то K - это константа.
И тогда counting sort по времени исполнения превращается в O(n) и по памяти в O(1). Для байтов памяти всегда требуется 255, для int32 потребуется 4 гигабайта; для int64 считать страшно, но оперативы много - всегда можно докупить, чё. Ну и такой же оверхед в количестве инструкций, зато константа.

Для байтов вообще прекрасный и оптимальный алгоритм, работающий быстро (на массивах, которые значительно больше 255 элементов константный оверхед в 255 * c инструкций вообще не заметен).

Ну если у нас под числами имеется в виду что-то типа настоящих безразмерных чисел; то все грустно и этот алгоритм не катит.

juan_gandhi January 25th, 2015
У меня такое ощущение, что трех пойнтеров было бы достаточно.

vp January 25th, 2015
А как поконкретнее?

(Deleted comment)
osdm January 25th, 2015
Судя по комменту автора, подразумевается рекурсия, которая таки жрет стек.

vp January 26th, 2015
Если так, то это детский сад, конечно.

109 January 25th, 2015
видимо, торможу, ибо не понимаю, где трудно. ну два индекса, каждый ползёт по своему массиву.

zerkms January 25th, 2015
inplace же

jdevelop January 26th, 2015
Мне всегда было любопытно, что именно проверяется таким образом на интервью. Сможет мне кто-то внятно объяснить?

wizzard0 January 26th, 2015
"Что будет делать человек, если встретится с Неожиданной Непонятной Хуйнёй", например.
Олсо мышление, вот это всё.

Кодинг этим не проверяется, естественно. И да, я обычно просто про проекты расспрашиваю :)

aka_rider January 27th, 2015
Мне тут подумалось, что это частный случай AI для игры в пятнашки.
А вообще я рассуждаю так:
1. Нам нужно пройти оба массива за один раз O(N)
2. На каждой итерации нам нужно сделать константное число перестановок O(1)
3. Чтобы первое условие выполнялось, нужно чтобы массивы оставались сортированными после каждой итерации.
Получается, что на каждой итерации нужно вставить произвольное число в отсортированный массив за O(1), но это невозможно.
Т.е. при таких условиях задача не решается.

wizzard0 January 27th, 2015
Либо можно пройти массивы несколько раз, (но "несколько" не должно зависеть от их количества)

Либо можно пройти не весь массив много раз.

  • 1
?

Log in

No account? Create an account