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. ```hint What an iterator must remember An iterator cannot hold a copy, so it needs a small, constant-size description of the moment it was created, one it can compare against history the set already keeps. ``` ```hint Don't lose track of removals Whatever structure answers `contains` must reflect a removal immediately, even though older snapshots still need to see the removed element. ``` #### 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. ```hint Where does iteration walk? Think about what an iterator must traverse in the per-key layout, and what happens to that traversal while the dictionary keeps changing. ``` #### 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 ### What a Strong Answer Covers - Snapshot semantics defined precisely through versions or sequence numbers - Every stated complexity bound met and justified, including iterator creation without copying - Independent iterators that do not interfere with each other or with later mutations - Edge cases: remove then re-add, removing a missing element, an empty set, exhausted iterators - Awareness that history grows with churn, and what reclaiming it would require ### Follow-up Questions - How would you reclaim history entries that no live iterator can see anymore? - How would you make the structure safe when one thread mutates while others iterate? - How would `next()` stay fast when most history entries have been removed?