First order id the feed re-sends

Question

After a reconnect your feed can replay events, and you want an early warning: as you read the stream once, report the first order_id whose second copy shows up. "First" means the earliest point in the stream at which any id is seen for the second time, not the id with the smallest value.

stream = [101, 102, 103, 102, 101]
-> 102          # 102's second copy (index 3) arrives before 101's (index 4)

Return the first id to repeat, or a sentinel if every id is unique. Aim for $O(1)$ per event.

Accepted Answer

Walk the stream keeping a set of ids seen so far. The moment you meet an id already in the set, that is by definition the first second-appearance, so return it immediately. If you reach the end, nothing repeated. Tracing the example: 101, 102, 103 are all new and go into seen. The next 102 is already present, so we return 102 right away, never even reading the final 101. Returning on the first hit is what makes it "first repeat" rather than "smallest repeated id" (which would need a full scan). Time O(n) but often less because we stop early; space O(u) up to the point we stop. The contrast in…

First order id the feed re-sends

Your answer

More Coding questions