Написать сортировку файла за 3 часа (брутал-собес)

Сортировать надо индекс, а потом создать новый сортированный файл.

Если средняя строка ~ 50 байт, то места для индекса хватит (~320Мб); нужно сделать inplace_merge_sort индексов. Но при этом получим O(n log n) операций чтения с диска, причём с очень приличным множителем.

Если действовать похитрее можно сделать (вроде бы) O (n) операций чтения с небольшим множителем.

Судя по тэгу «Яндех» это актуально.

Ну, а если средняя длина строки больше 75 байт (например, волшебные кириллические домены), то сортировка индексов вообще не прокатит - не хватит на них места.

Ну, а если средняя длина строки больше 75 байт (например, волшебные кириллические домены), то сортировка индексов вообще не прокатит - не хватит на них места.

я думал над этим. Я думаю достаточно отсортировать только по первым n байт. Скажем n=10 более чем достаточно. А дальше на финальном этапе сделать второй прогон по файлу и досортировать если что-то не по порядку.

O (n) операций чтения с небольшим множителем

Это как интересно?

bucket sort? (правда он тут не к месту)

А какая разница по скольким первым байтам сортировать? Количество записей от этого не уменьшится же.

> O (n) операций чтения с небольшим множителем

Это как интересно?

Гнать не буду, я написал «вроде бы». Мне кажется, если применить принципы inplace_merge c O(n), то можно добиться такого результата, но не уверен. Это может оказаться не проверкой на 10 минут. Подумаю на досуге. Разумеется, в оперативке log, а то и его квадрат никуда не денутся.

Да, мне тоже только что подумалось, что inplace просто перемещает проблему с диска в память. А вообще задачка экономически нецелесообразна после трех часов изучения, за немалой ценой часа программиста дешевле купить и смонтировать флешку USB 2.0 на 8 гигов. И дальше обычным merge.

А какая разница по скольким первым байтам сортировать?

размер индекса

Не понял. Всего индексов будет столько, сколько записей же. Размер одного индекса зависит от схемы позиционирования в данных (тут смещения внутри 4г). 80млн записей — 80млн индексов по 4 байта — 320Мб как ни крути.

задачка экономически нецелесообразна

Задача [для Яндекса] экономически очень целесообразна: «Найти программиста, который может оценивать и решать (желательно сторонними средствами), подобные проблемы.» )))

Думаю, после обсуждения вариантов решения этой задачи на собеседовании Яндекса, соискатель не будет писать 3 часа код. Либо собеседование продолжится другим вопросом, либо «мы очень ценим опыт общения с вами и обязательно свяжемся!».

Думаю, после обсуждения вариантов решения этой задачи на собеседовании Яндекса, соискатель не будет писать 3 часа код

Нет, именно написать работающий код. За 3 часа. Они ноут дают для этой задачи. С шindows(!), кстати :D

Нет, именно написать работающий код. За 3 часа. Они ноут дают для этой задачи. С шindows(!), кстати :D

Наверное, это не ранняя стадия собеседования. На ранней слишком нерационально, там отсев приличный.

А у тебя знакомый ходил туда?

надо было приходить со своим ноутбуком...