ORIGINAL TECHNICAL PRACTICE
Merge ordered event streams
Two event lists are sorted by timestamp. How would you merge them while preserving order when timestamps tie?
Written for independent practice. The model answer presents one approach; clarify constraints and explain alternatives.
A REASONED APPROACH
Model answer.
Use two forward pointers and append the smaller current event. Define a tie rule explicitly, such as preferring the left stream, to preserve a deterministic stable order.
Work through it
- Specify whether timestamps alone define order or whether a secondary event ID is part of the contract. Validate that each input is sorted under that same order.
- Advance exactly one pointer for each appended item. Once a stream is exhausted, append the remaining suffix of the other.
- Test empty streams, equal timestamps within and across streams, and already disjoint timestamp ranges. Distinguish deterministic merging from duplicate-event removal.
Tradeoffs to discuss
- Time is O(n+m). A materialized result needs O(n+m) output storage; an iterator can stream results but must still manage unread input and downstream backpressure.
Common pitfalls
- Using a set to remove duplicates can silently discard distinct events sharing a timestamp. Comparing timestamps lexically requires a compatible normalized representation.