Integer Set with O(1) Snapshot Iterators Unaffected by Later Changes

Design SnapshotSet, a set of integers that can hand out iterators over a frozen view of its contents.

SnapshotSet supports:

• add(n): adds n if not present; returns whether it was added.
• remove(n): removes n if present; returns whether it was removed.
• contains(n): returns whether n is currently in the set.
• getIterator(): returns a SnapshotIterator that captures the set's exact contents at this moment, in original insertion order.

Later add/remove calls must not affect any iterator already created, and multiple iterators must behave independently. SnapshotIterator supports hasNext() and next(). In Python it should also work directly in a for loop.

Constraints

• add and remove must be amortized O(1).
• getIterator() must create the iterator in O(1): no copying of the set.
• Total space across the set and M live iterators must be O(N + M), where N is the number of elements ever added.

Clarifying Questions

• One version of this question required insertion order, and another said iteration order does not matter. Which applies here?
• If an element is removed and later added again, where does it appear in iteration order for snapshots taken after the re-add?
• Does N count every successful add call (including re-adds of the same value), or distinct values?
• What should next() do when there are no more elements?
• Is single-threaded access enough, or can iterators be consumed while other threads mutate the set?

Part 1 — Implement the set and its iterator

Write working code for both classes that meets the complexity bounds.

What This Part Should Cover

• The shared history the set maintains, and how each entry records when it became visible and when it became invisible
• How hasNext/next skip entries outside the iterator's snapshot, and their amortized cost
• A complete Python iterator protocol, and correct bookkeeping in remove

Part 2 — Compare an alternative layout

The interviewer suggests replacing the single history list shared by all keys with a separate history per key: a dictionary from each value to that value's own log. Compare the two layouts on time and space, decide whether either has a real advantage, and pick one to finish.

What This Part Should Cover

• Time and space of each layout for mutations, iterator creation and full iteration
• How iteration order and iteration safety differ between the two layouts
• A clear, defended choice, rather than switching designs mid-interview