31. How would you design an API to merge multiple sorted streams?
Design an API to merge multiple sorted streams into one sorted stream, even when the underlying stream types differ.
At a high level, I would expose one MergeService that accepts different sorted sources through SourceAdapter implementations plus a Comparator<TOut>. Each adapter converts its source into the Common Cursor Contract. The Merge Engine keeps one head item per cursor in a Min-Heap, removes the smallest item, emits it through MergedSortedStream<TOut>, and refills only the cursor that produced it. The caller consumes the result lazily with hasNext() and next(). I would also make failure handling explicit with ErrorPolicy and close every source resource. The trade-off is extra abstraction for better extensibility and bounded merge memory.
We need to combine several already ordered sources into one ordered result. The difficult part is that the sources do not all look the same. One may be a file, another may be a database result, Kafka partition, or REST page stream. We want the caller to use one simple result without understanding those differences. We also do not want to load every item into memory first. The design in the diagram solves this by converting every source to one common cursor shape, then choosing the smallest available value as the caller asks for more data.
- Are all input sources guaranteed to already be sorted?
- Should Comparator<TOut> define the common ordering across every source?
- Should the merged result be lazy and pull-based?
- What should happen if one source fails or times out?
I would begin with MergeService because it is the main API boundary. The diagram shows merge(List<SourceAdapter<?,TOut>>, Comparator<TOut>). The caller gives it the source adapters and the Comparator<TOut> that defines the final sort order. MergeService returns MergedSortedStream<TOut>. That result is pull-based, so the caller asks for values as needed instead of receiving one fully materialized collection. The configuration also includes SourceAdapter, Comparator<TOut>, and ErrorPolicy, which keeps the key design choices explicit.
Each underlying source has its own adapter. The diagram shows FileAdapter, JdbcAdapter, KafkaAdapter, and RestAdapter for a Sorted File Stream, Sorted JDBC ResultSet, Sorted Kafka Partition, and Sorted REST Page Stream. Each adapter extracts the sort key and maps its source value to TOut. This prevents the Merge Engine from containing file, JDBC, Kafka, or REST-specific code. The adapters expose the same Common Cursor Contract, so the rest of the algorithm works with one abstraction.
The Common Cursor Contract provides peek(), next(), hasNext(), and close(). The diagram shows separate File, JDBC, Kafka, and REST cursors behind this common contract. Conceptually, each cursor represents one already-sorted input. The important rule is that all values become a common TOut representation and follow the same Comparator<TOut> ordering. This lets the merge logic treat every source in exactly the same way while still allowing each adapter to own its source-specific reading behavior.
The Min-Heap, or PriorityQueue, holds one current head item from each active cursor. It is ordered by Comparator<TOut>. The Merge Engine first seeds the heap with the first available item from every cursor. Because each source is already sorted, the smallest value across all sources must be one of these current head items. We therefore do not need to load or sort every item again. The heap only needs about one active entry for each source.
When the caller needs another value, the Merge Engine pops the smallest item from the Min-Heap and emits that item through MergedSortedStream<TOut>. It then advances only the same cursor that supplied that item. If that cursor still has another value, its new head goes back into the heap. The other cursors stay where they are. This pop, emit, refill, and reinsert cycle continues until no cursor has data left. That is the key k-way merge behavior shown in the diagram.
MergedSortedStream<TOut> exposes hasNext(), next(), and close(). The caller first creates the merged stream through MergeService, then consumes it through this pull-based interface. Each next() request causes the merge state to produce the next globally ordered item. This keeps memory usage controlled because the API does not build the complete merged output before returning it. It also works naturally with sources whose complete size may not be known in advance.
The diagram routes a source error or timeout to Error Policy. The shown strategies are fail-fast, skip-source, and retry. Fail-fast protects completeness by stopping when a source cannot continue. Skip-source favors availability but can produce an incomplete merged result. Retry may recover a temporary problem, but it can increase latency. The chosen strategy is applied to the Merge Engine. Finally, close() must trigger the close-all-resources path so every cursor, adapter, and underlying source resource is released when processing finishes or the caller stops early.
Interviewers use this question to test API boundaries and algorithmic judgment together. They want to see whether you recognize a k-way merge and use a PriorityQueue instead of loading and sorting everything again. They also look for a clean abstraction that hides different source types, correct lazy-stream behavior, explicit resource cleanup, and sensible failure handling. A strong answer explains why each component exists and clearly states the trade-offs without changing the core design.
