Merge Sorted Event Streams Through an Iterator

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

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.

Merge Sorted Event Streams Through an Iterator

Approach

Keep a min-heap of triples (numeric timestamp, stream index, position), initially containing only the first event of each nonempty stream. HAS_NEXT checks whether the heap is empty and never modifies it. NEXT removes the smallest head, returns the original string at its stored position, and inserts only that stream's next event if present. Sorted input guarantees every unseen event follows its stream head, so the global next event must be among these heads. Comparing timestamp then stream index implements ties; only one head from a stream exists at a time, preserving its internal order even through repeated equal timestamps. Empty and exhausted streams are absent, and an empty heap always yields END for NEXT. No flattened event collection is built or sorted. With k streams, initialization is O(k log(k+1)) as an upper bound across languages, or O(k) with Python heapify; a returned event takes O(log(k+1)) heap work plus timestamp parsing and output string costs. HAS_NEXT and exhausted NEXT take O(1). Iterator state has O(k) entries excluding output and input fixtures; C++ takes fixtures by const reference. For real blocking/asynchronous streams, obtaining each initial or replacement head may require waiting. Correct global ordering requires a head, end-of-stream marker, or a trustworthy watermark from every relevant source; emitting whichever response arrives first can violate timestamp or tie order. Cancellation, backpressure, errors and delayed sources need an explicit interface policy.

• Time complexity: Initialization O(k log(k+1)); returned NEXT O(log(k+1)); HAS_NEXT/exhausted NEXT O(1), plus timestamp and output string costs
• Space complexity: O(k) iterator entries, excluding fixtures and returned output