Snapshotable Collections And Iterators

What's being tested

Tests versioned collection design: preserving stable iterator views while the underlying set mutates. You must demonstrate clear iterator semantics, complexity tradeoffs, and an implementation that handles add/remove/re-add without leaking deleted state into active snapshots.

Patterns & templates

• Copy-on-iterator snapshot — `iterator()` copies current elements into an array/list; O(n) creation, O(1) next, simplest correctness story.

• Copy-on-write set — clone backing `HashSet` before mutation when snapshots exist; good when reads dominate, costly for frequent writes.

• Operation log with versions — store `addVersion` / `removeVersion` per element; iterator captures `snapshotVersion`, filters by visibility in O(1) or O(log k).

• Reference-counted snapshots — track active iterators; defer cleanup of tombstoned elements until all older snapshots are closed or exhausted.

• Stable iterator contract — define whether `hasNext()` is idempotent, whether iteration order matters, and whether mutations during iteration are visible.

• Complexity framing — compare `add`, `remove`, `contains`, `iterator`, `next`; strong answers explicitly optimize for expected read/write ratio.

Common pitfalls

Pitfall: Returning a raw `HashSet` iterator gives fail-fast or live-view behavior, not snapshot semantics.

Pitfall: Treating remove as physical deletion immediately breaks older iterators that still need to see the element.

Pitfall: Ignoring re-add after remove; visibility must depend on version intervals, not just current membership.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.