Merge K sorted lists / iterators

Expected question

"Merge k sorted ascending integer lists into one sorted list (or yield via iterator)."

Variant forms

• "Merge K sorted lists — heap of size K."
• "Design a lazy iterator that merges without materializing all output."
• "What if some lists are empty or infinite streams?"
• "Merge K sorted files on disk that don't fit in memory."
• "Complexity vs pairwise merge tournament?"
• "Deduplicate while merging."
• "Merge by a custom comparator (timestamps + id)."
• "How do you unit-test the iterator contract (hasNext/next)?"

The question, as it might actually be asked

Merge k sorted ascending integer lists into one sorted list (or yield via iterator).

How you'd talk while coding

I'd confirm ascending sort, duplicate policy, total length N vs k, and list-vs-lazy return. Brute is concat + sort — O(N log N), throws away the sortedness. Correct is a min-heap of (value, list_i, elem_i) — O(N log k). I'd push the head of each non-empty list, then pop/push next. Tests: classic three-list merge, empty lists mixed in, single-list identity. Staff+ stop line: "Same algorithm as a lazy iterator or external k-way file merge. I won't design MapReduce compaction unless you open that door."

Where this actually gets asked

Heap classic. Staff+ cares about iterator API, laziness, and external sort / k-way merge for files.

Problem

Merge k sorted ascending integer lists into one sorted list (or yield via iterator).

Clarifying questions you should ask first

1. Lists already sorted ascending?
2. Duplicates allowed?
3. Total length N, k lists — memory bound?
4. Return list vs lazy iterator?

Approach ladder

Reference solution (Python)

from __future__ import annotations
import heapq
from typing import Iterator

def merge_k_sorted(lists: list[list[int]]) -> list[int]:
    heap: list[tuple[int, int, int]] = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))
    out: list[int] = []
    while heap:
        val, li, ei = heapq.heappop(heap)
        out.append(val)
        nxt = ei + 1
        if nxt < len(lists[li]):
            heapq.heappush(heap, (lists[li][nxt], li, nxt))
    return out

def merge_k_sorted_iter(lists: list[list[int]]) -> Iterator[int]:
    heap: list[tuple[int, int, int]] = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))
    while heap:
        val, li, ei = heapq.heappop(heap)
        yield val
        nxt = ei + 1
        if nxt < len(lists[li]):
            heapq.heappush(heap, (lists[li][nxt], li, nxt))

Complexity: O(N log k) time; O(k) heap space (+ output).

Verbal tests to narrate

1. [[1,4,5],[1,3,4],[2,6]] → [1,1,2,3,4,4,5,6]
2. Empty lists mixed in
3. Single list identity

Staff+ deep dive

What not to discuss

• MapReduce job design before the heap works
• Premature parallel merge without measuring

What's expected at each level

• Mid-level: Concat + sort.
• Senior: Heap merge + complexity.
• Staff+: Lazy API + external merge narrative.
• Principal: Connects to real log/compaction pipelines.

Follow-up questions to expect

• "Why not concatenate and sort?" — Burns the O(N log k) win and forces full materialization.
• "How do you keep it lazy?" — Heap yields one element at a time; I'd test that sources aren't over-read.
• "Source failure mid-merge?" — Document propagate-vs-skip before coding.
• "External sort connection?" — Same invariant, bounded buffers. Stop before distributed compaction design.

Related

• 00-staff-plus-coding-bar.md