Release out-of-order sequence numbers in order without gaps

Integers 1, 2, 3, ... are each sent once, but they arrive out of order. The consumer must see them strictly in order. Build the buffer between the two: each time a number arrives, release every number that can now be delivered without a gap.

Interface

Unless you agree on a different interface with the interviewer, assume:

• OrderedStream(start: int = 1) — the first number expected.
• insert(value: int) -> list[int] — accepts a number and returns, in order, the numbers released by this call (possibly none). A number already released or already waiting is ignored and returns [].

Example

s = OrderedStream()
s.insert(3)  -> []
s.insert(1)  -> [1]
s.insert(2)  -> [2, 3]
s.insert(5)  -> []
s.insert(2)  -> []           # duplicate, ignored
s.insert(6)  -> []
s.insert(4)  -> [4, 5, 6]

Constraints

• Up to 10^5 inserts. Values are positive integers and may be far ahead of the next expected one.
• Each insert should cost O(1) amortized plus the numbers it releases.

Clarifying questions

• Can numbers repeat, and what should a duplicate or an already released number do?
• Is the range known in advance (1 to n), which allows an array, or open-ended?
• Should a gap that never fills block forever, or release after a timeout?
• Is there a bound on how far ahead a number can arrive (so the buffer has a maximum size)?

What a strong answer covers

• A pointer to the next expected number and a set (or array, when the range is known) of numbers waiting.
• On insert: add the number, then advance the pointer while the next one is waiting, removing each from the set. Each number is released once, so total work is O(inserts).
• Why a heap is not needed here, and when it would be (values that aren't consecutive integers, such as sequence numbers with known gaps or timestamps).
• Tests for in-order arrival, fully reversed arrival, duplicates and a large jump ahead.

Follow-ups

• Values carry payloads keyed by sequence number, like messages over an unordered network. Release the payloads in order.
• Memory is bounded: only accept numbers within W of the next expected one, and say what happens to the rest.
• Release after a timeout even if a gap remains, and report the missing numbers.
• Several producers each send their own increasing sequence: merge them into one ordered output.