First repeated order ID in a stream

Question

Order IDs stream in and should be unique, but a bug occasionally re-sends one. Return the first ID that appears for a second time, in stream order. If every ID is unique, return None.

order_ids = [3, 1, 4, 1, 5]
-> 1            # the second 1 is the first repeat seen

Return the first ID seen twice, else None. Aim for $O(n)$ .

Accepted Answer

Keep a set of IDs seen so far. For each incoming ID, if it is already in the set, it is the first repeat and you return it immediately; otherwise add it. Returning on first hit guarantees "first in stream order" rather than, say, the smallest duplicate. Tracing [3, 1, 4, 1, 5]: 3, 1, 4 are new; the second 1 is already in the set, so 1 is returned. Time O(n), space O(n) in the worst case (all distinct). Edge cases: an all-unique stream returns None, and the first repeat by stream position, not by value, is what the early return captures. Takeaway. A running set is the default tool for "have I …

First repeated order ID in a stream

Your answer

More Coding questions