# Build a Constant-Time Snapshot Set Iterator Design `SnapshotSet`, a set of integers whose iterators observe an immutable logical snapshot without copying the set at iterator creation. ```text add(value) -> bool remove(value) -> bool contains(value) -> bool getIterator() -> SnapshotIterator SnapshotIterator.hasNext() -> bool SnapshotIterator.next() -> int ``` `add` returns whether the value was newly present. `remove` returns whether a present value was removed. An iterator must yield exactly the values that were present when it was created, in insertion order. Later mutations must not alter that iterator, and multiple iterators must advance independently. If a removed value is later added again, treat it as a new insertion at the end. Each successful add therefore creates one historical insertion record. ## Constraints - `add`, `remove`, and `contains` must be amortized `O(1)`. - `getIterator` must be `O(1)` and may not copy current values. - With `N` historical insertion records and `M` live iterators, total structural space must be `O(N + M)`. - `next` may throw a standard exhausted-iterator error when no value remains. ## Example After `add(4)`, `add(9)`, create iterator `a`; then `remove(4)`, `add(7)`, create iterator `b`. Iterator `a` yields `4, 9`; iterator `b` yields `9, 7`. ## Clarifications Define the version or lifetime invariant that lets an iterator decide whether a historical insertion was active at its snapshot. Explain iterator cost, including skipped records. ## Hints Consider recording when an insertion becomes visible and when it stops being visible, while letting each iterator remember only a snapshot version and a cursor. ## Extensions - How would you reclaim history once old iterators are closed? - What thread-safety guarantees would you offer? - How would fail-fast iteration differ from snapshot iteration?