Implement a Snapshot Set Iterator
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a data structure `SnapshotSet<T>` with the following interface:
```java
interface SnapshotSet<T> {
void add(T e);
void remove(T e);
boolean contains(T e);
Iterator<T> iterator();
}
```
Requirements:
- `add(e)`: adds `e` to the set.
- `remove(e)`: removes `e` from the set.
- `contains(e)`: returns whether `e` is currently in the set.
- `iterator()`: returns an iterator over a **snapshot** of the set at the moment `iterator()` is called.
Important behavior:
- The returned iterator must continue to iterate over the elements that existed when it was created, even if the set is later modified.
- The snapshot is taken when `iterator()` is called, not when iteration begins.
- Iteration order does not matter.
- Because this is a set, duplicate adds should not create duplicate elements.
- Removing a non-existent element can be treated as a no-op.
Example:
1. `add(5)`, `add(2)`, `add(8)`
2. `remove(5)`
3. `it = iterator()` → snapshot should represent `{2, 8}`
4. `add(1)`
5. `contains(2)` returns `true`
6. `remove(2)`
7. `contains(2)` returns `false`
8. `add(2)`
9. `it2 = iterator()` → snapshot should represent `{1, 2, 8}`
10. Iterating `it` should still return `{2, 8}` in any order, for example `[2, 8]`
Design and implement this data structure.
Quick Answer: This question evaluates proficiency in data structure design, iterator semantics, and managing snapshot consistency for mutable collections. It is commonly asked in the Coding & Algorithms domain to assess practical implementation skills and conceptual understanding of producing an iterator that reflects the set's state at the moment iterator() is called, testing practical application with reasoning about immutability, consistency, and complexity.
Implement the behavior of a SnapshotSet of integers by processing a sequence of operations. The set supports add, remove, contains, and snapshot iterator creation.
Because this platform evaluates a function rather than a class, you must write a function that processes operations in order.
Operations:
- ("add", x): add x to the set.
- ("remove", x): remove x from the set if it exists.
- ("contains", x): check whether x is currently in the set.
- ("iterator", name): create a snapshot iterator identified by name.
- ("iterate", name): fully consume the snapshot iterator identified by name.
Important snapshot rule:
- The snapshot is taken when the "iterator" operation is executed, not when "iterate" happens later.
- Later modifications to the set must not affect previously created snapshot iterators.
- Since iteration order does not matter, return snapshot contents as a sorted list for deterministic grading.
- Duplicate adds must not create duplicates.
- Removing a non-existent element is a no-op.
Return a list containing the result of every "contains" and "iterate" operation, in the order they appear.