First unique number in a stream

Numbers arrive one at a time. At any moment you may be asked for the first number, in arrival order, that has so far appeared exactly once. Build a structure that handles both operations quickly.

Interface

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

• FirstUnique() — starts empty.
• add(x: int) -> None — one more number from the stream.
• first_unique() -> int | None — the earliest number seen exactly once so far, or None when there is none.

Example

add(4)
first_unique()  ->  4
add(7)
add(4)
first_unique()  ->  7       # 4 is repeated now
add(7)
first_unique()  ->  None
add(9)
first_unique()  ->  9

Constraints

• Up to 10^5 calls in total; both operations should be O(1), amortized at worst.

Clarifying questions

• Should first_unique return None, -1 or raise when nothing qualifies?
• Can the structure start from an initial list?
• Is memory bounded, or can I keep a count for every distinct value seen?
• Do numbers ever leave the stream, for example after a time window?

What a strong answer covers

• A count per value, plus the values seen once kept in arrival order: an ordered dict or a doubly linked list with a hash map from value to node, so a repeat is removed in O(1).
• The simpler alternative: a queue of candidates whose front is popped lazily while its count is above 1, amortized O(1).
• Why scanning the counts on each query is too slow.
• Tests: empty stream, every value repeated, a value seen three times, the first unique changing several times.

Follow-ups

• Only the last w numbers count (a sliding window).
• Return the first k unique numbers.
• The stream is too large for one machine's memory.