Merge Sorted Event Streams Through an Iterator
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement an iterator that merges several event streams already sorted by timestamp. Return events chronologically without collecting and sorting every event before iteration.
Implement `merge_event_iterator(streams: string[][], operations: string[]) -> string[]`.
### Constraints & Assumptions
The nested arrays provide deterministic stream fixtures for practice. Your iterator may keep an index or iterator for each stream and at most one pending head per active stream; do not flatten or copy all events into a new collection.
- Each event string is `timestamp/payload`, with a nonnegative integer timestamp at most 1000000000 and a nonempty ASCII alphanumeric/underscore payload. Payloads need not be unique.
- Every input stream is sorted nondecreasingly by numeric timestamp. There may be empty streams, no streams, and identical timestamps.
- Ties use lower stream index first, preserving original order within a stream. This deterministic tie rule is a practice assumption; the source asks to handle identical timestamps without prescribing their order.
- At most 10000 streams, 200000 total events, and 300000 operations.
- `HAS_NEXT` returns `true` or `false` as a string without advancing. `NEXT` returns the next original event string, or `END` if exhausted. Repeated NEXT after exhaustion keeps returning END.
- Return one string for every operation. Output storage is excluded from the iterator's auxiliary-memory bound.
### Example
```text
streams = [["1/a","3/b"],[],["1/c","2/d"]]
operations = ["HAS_NEXT","NEXT","NEXT","NEXT","NEXT","HAS_NEXT","NEXT"]
result = ["true","1/a","1/c","2/d","3/b","false","END"]
```
Explain initialization, advancement, equal timestamps, and exhausted streams. Analyze time per returned event and memory in terms of the number of streams. Discuss what changes when stream heads are obtained from real blocking or asynchronous sources rather than already available fixtures.
```hint Only the current heads can be next
After emitting one stream's head, only that stream needs to supply a replacement candidate.
```
Overview: Implement a lazy chronological merge iterator with one head per active stream, stable timestamp ties, has-next semantics, exhausted streams, and bounded auxiliary memory.
Read the full Amazon Software Engineer interview experience this question came from
Community answers
Answer by janaki9sravya
import heapq
def merge_event_iterator(streams, operations):
n = len(streams)
s_ptrs = [0] * n
min_heap = []
def push_head(i):
if s_ptrs[i] < len(streams[i]):
k, v = streams[i][s_ptrs[i]].split("/")
heapq.heappush(min_heap, (int(k), v, i))
s_ptrs[i] += 1
for i in range(n):
push_head(i)
result = []
for op in operations:
if op == "HAS_NEXT":
result.append("true" if min_heap else "false")
else:
if not min_heap:
result.append("END")
continue
k, v, i = heapq.heappop(min_heap)
result.append(f"{k}/{v}")
push_head(i) # refill THIS stream right after popping it
return result
