Слияние k отсортированных логов: задача с собеседования

Условие

Есть k логов с разных серверов, каждый уже отсортирован по времени. Слей их в один отсортированный лог.

Ввод: число k, дальше для каждого лога строка с числом записей m, затем m строк <время> <сообщение> (время целое, сообщение может содержать пробелы). Внутри лога время не убывает.

Вывод: все записи целиком, по возрастанию времени. При равном времени раньше идёт запись из лога с меньшим номером, внутри одного лога исходный порядок сохраняется.

k ≤ 100, всего записей ≤ 1000. Решение должно быть лучше, чем «склеить всё и отсортировать»: представь, что логи это потоки, которые нельзя прочитать целиком.

Пример

2
2
1 api start
5 api ready
3
2 db start
5 db ready
7 db vacuum

1 api start
2 db start
5 api ready
5 db ready
7 db vacuum

Как подойти

k-way merge через кучу: O(N log k) по времени и O(k) дополнительной памяти на указатели.

Подсказки: 2

Держи в мин-куче по одному «текущему» элементу от каждого лога.
Ключ кучи: (время, номер лога). Достал минимум, положил следующий элемент того же лога.

Решите в тренажёре

Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.

Решить в тренажёре

Предыдущий вопрос

Итоги платежей из CSV-выгрузки

Следующий вопрос

Топ эндпоинтов по access-логу с нормализацией маршрутов

Урок по теме

Потоки и буферы в Node.js

Термины по теме

Backpressure в потоках Node.js Buffer в Node.js

Ещё по теме «Потоки и буферы»

Все вопросы модуля