Lazy Merge of Sorted Event Streams
Amazon● MediumFULLTIMEONSITE INTERVIEWProblem statement
Implement a forward iterator that merges timestamp-sorted event streams in chronological order without loading every event into merge working memory.
For this exercise, assume each event is represented only by its integer timestamp. Every row of streams is sorted in nondecreasing order. Preserve every event, including equal timestamps within or across streams.
Use one current event per nonempty stream as merge lookahead. The iterator must expose whether another event exists and return the next timestamp while advancing only the chosen stream. Exhausted streams contribute no more events.
The function returns the complete iterator output as an int[] for judging. The already-supplied input handles and serialized output are excluded from the O(k) merge-working-memory limit, where k is the number of streams.
Function
mergeEventStreams(streams: int[][]) → int[]Examples
Example 1
streams = [[1,4,4],[1,2,9],[],[3]]return = [1,1,2,3,4,4,9]Both timestamp-1 events and both timestamp-4 events remain in the merged sequence.
Example 2
streams = [[],[-3,-1],[-3,0]]return = [-3,-3,-1,0]Empty streams contribute nothing, and negative timestamps are ordered normally.
Constraints
- For this exercise, assume
0 <= streams.length <= 10000. - Rows are sorted in nondecreasing order and may be empty.
- The total number of events is at most
200000. - Every timestamp is a signed 32-bit integer.
- Merge working memory is
O(k), excluding input handles and returned output.