Deduplicate a replayed order stream

Question

After a reconnect, your exchange feed replays messages, so the same order event can appear multiple times. Each event is (order_id, payload). Downstream consumers must see each order_id exactly once, in original arrival order.

events = [(101, "new"), (102, "new"), (101, "new"), (103, "new"), (102, "new")]
-> [(101, "new"), (102, "new"), (103, "new")]

Return the stream with duplicates removed, keeping the first occurrence of each id and preserving order. Aim for $O(1)$ per event.

Accepted Answer

Order matters, so you can't just dump everything into a set, sets don't preserve arrival order of first occurrence and you need the payloads. Keep a set of ids already emitted; for each event, emit it only if its id is new. Membership test and insert are both O(1) expected. On the example, ids 101, 102, 103 pass through once each; the replays of 101 and 102 are dropped. Time O(n), space O(u) where u is the number of unique ids. The follow-up that separates candidates: the feed never ends, the seen set grows without bound. Good answers exploit structure: if the exchange guarantees duplicates a…

Deduplicate a replayed order stream

Your answer

More Coding questions