Build a Constant-Time Snapshot Set Iterator
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
# 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?
Quick Answer: Design a mutable integer set whose iterators preserve insertion-order snapshots without copying the live set when they are created. Meet constant-time creation and update targets, support independent iterators and remove-then-readd behavior, and explain skipped history and safe reclamation.
`SnapshotSet` is a set of integers whose iterators observe an immutable logical snapshot of the set. Creating an iterator must not copy the set's current contents, yet that iterator must yield exactly the values that were present at the moment it was created, in insertion order. Later `add` / `remove` calls must not change what an already-created iterator yields, and multiple live iterators advance independently of one another.
If a value is removed and later added again, the re-add counts as a brand new insertion and takes its place at the **end** of insertion order. Every successful `add` therefore creates exactly one historical insertion record.
## What you implement
The console grades one function, so you build the structure and replay a command trace through it.
Implement `solution(operations, args)`:
- `operations[i]` is the name of the i-th operation.
- `args[i]` carries that operation's argument.
- Return a list of integers with **exactly one entry per operation**, in operation order.
| `operations[i]` | `args[i]` | value appended to the result |
| --- | --- | --- |
| `"add"` | `[value]` | `1` if `value` was absent and is now inserted, otherwise `0` |
| `"remove"` | `[value]` | `1` if `value` was present and is now removed, otherwise `0` |
| `"contains"` | `[value]` | `1` if `value` is currently in the set, otherwise `0` |
| `"iterator"` | `[]` | the handle of the newly created iterator: `0` for the first iterator created, `1` for the second, and so on |
| `"has_next"` | `[handle]` | `1` if iterator `handle` still has a value to yield, otherwise `0` |
| `"next"` | `[handle]` | the next value yielded by iterator `handle`, advancing that iterator by one |
Booleans are reported as `1` / `0` so that a single integer list can carry every operation's result.
## Example 1
```text
operations = ["add","add","iterator","remove","add","iterator",
"has_next","next","has_next","next","has_next",
"has_next","next","has_next","next","has_next"]
args = [[4],[9],[],[4],[7],[],
[0],[0],[0],[0],[0],
[1],[1],[1],[1],[1]]
output = [1,1,0,1,1,1,1,4,1,9,0,1,9,1,7,0]
```
`add(4)` and `add(9)` both insert, so both report `1`. The set is `{4, 9}` when iterator `0` is created, and `"iterator"` reports its handle `0`. `remove(4)` then reports `1` and `add(7)` reports `1`, leaving `{9, 7}` when iterator `1` is created (handle `1`). Iterator `0` still yields `4` then `9` and is then exhausted; iterator `1` yields `9` then `7`.
## Example 2
```text
operations = ["add","add","contains","remove","remove","contains","add","add",
"iterator","has_next","next","has_next","next","has_next"]
args = [[5],[5],[5],[5],[5],[5],[8],[5],
[],[0],[0],[0],[0],[0]]
output = [1,0,1,1,0,0,1,1,0,1,8,1,5,0]
```
The second `add(5)` finds `5` already present and reports `0`; the second `remove(5)` finds it already gone and reports `0`. `5` is then re-added *after* `8`, so it takes the last position in insertion order and the snapshot yields `8` before `5`.
## Output semantics
- One integer per operation, emitted in operation order.
- Iterator handles are assigned in creation order starting at `0`.
- A snapshot's values are yielded oldest-insertion-first, each at most once per iterator.
## A note on the interview's asymptotic requirements
The original interview requires amortized `O(1)` `add` / `remove` / `contains`, an `O(1)` `iterator` that does **not** copy the live values, and `O(N + M)` total structural space for `N` historical insertion records and `M` live iterators. Exact-output grading cannot observe any of that -- a solution that snapshots by copying the live values produces identical output and will be accepted. Solve it under the real constraints anyway; that is what the interviewer is scoring.
Constraints
- 0 <= operations.length <= 5000
- args.length == operations.length
- operations[i] is one of "add", "remove", "contains", "iterator", "has_next", "next"
- args[i] has exactly one element for "add", "remove", "contains", "has_next" and "next", and is empty for "iterator"
- -10^9 <= value <= 10^9 for every "add", "remove" and "contains" operation
- every handle given to "has_next" or "next" was returned by an earlier "iterator" operation
- "next" is never called on an exhausted iterator (that handle would report has_next == 1 at that point)
Examples
Input: ([], [])
Expected Output: []
Input: (['contains'], [[5]])
Expected Output: [0]
Hints
- Insertion order never changes for records that already exist, and a removed value that comes back is a new record at the end. That suggests an append-only list of historical insertion records that you never delete from.
- Keep a counter that ticks on every successful add and every successful remove, and stamp each record with the counter value at which it started being visible and the one at which it stopped.
- An iterator then needs only two integers -- the counter value it was born at, and a cursor into the record list. Deciding whether to yield or skip a record is a comparison against those stamps, so nothing has to be copied when the iterator is created.