Redundant Channel Merge (A/B Streams)
An exchange publishes market updates over two redundant channels; the channels are merged into a single arrival stream. packets is that arrival-ordered list, each element [seq, payload] with an integer sequence number seq and an arbitrary payload. Packets may be duplicated, reordered, or dropped. Implement merge_stream(packets: List[List], start_seq: int, buffer_bound: int) -> List returning the in-order, de-duplicated list of PAYLOADS, beginning at start_seq and emitting only consecutive sequence numbers with no gaps.
Process each arriving packet in order with this exact contract: (1) if its seq is below the next expected number, or its seq was already accepted, ignore it (stale or duplicate); (2) if its seq equals the next expected number, emit its payload, advance, then drain any consecutively buffered packets; (3) otherwise it is out of order, so buffer it, and if the buffer size then EXCEEDS buffer_bound, STOP and return what was emitted so far. Return the emitted payloads if the stream ends without overflow.
Example: packets = [[0, 'a'], [2, 'c'], [1, 'b']], start_seq = 0, buffer_bound = 3 -> ['a', 'b', 'c'] (emit a, buffer c, then b fills the gap and c drains).
Hints
- Track the next sequence number you still owe; emit immediately on an exact match and then drain any buffered packets that now become consecutive.
- Dedup with a seen-set and buffer out-of-order packets in a dict; stop the moment the buffer's size strictly exceeds the bound.
Worked Solution
Maintain next_expected (initialized to start_seq), a set seen of accepted sequence numbers (for dedup), and a dict buffer of out-of-order packets keyed by seq. For each arriving packet:
- If
seq < next_expectedorseq in seen, skip it (stale/duplicate). - Mark
seqseen. Ifseq == next_expected, append the payload, incrementnext_expected, and drain: whilenext_expected in buffer, pop and append it, incrementing each time. - Else store it in
buffer; iflen(buffer) > buffer_bound, return the output immediately (overflow).
Return the output when the stream ends. Each packet is O(1) amortized.
```python def merge_stream(packets, start_seq, buffer_bound): next_expected, seen, buffer, out = start_seq, set(), {}, [] for seq, payload in packets: if seq < next_expected or seq in seen: continue seen.add(seq) if seq == next_expected: out.append(payload); next_expected += 1 while next_expected in buffer: out.append(buffer.pop(next_expected)); next_expected += 1 else: buffer[seq] = payload if len(buffer) > buffer_bound: return out return out ```
Intuition
Redundant feeds mean you see each update possibly more than once and out of order; the consumer's job is to reconstruct the gap-free in-order stream. A next-expected pointer plus a small reorder buffer is the standard sequencer pattern, and the bounded buffer models finite memory before you must give up.