Snapshotable Collections And Iterators
Asked of: Software Engineer
Last updated

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 inO(1)orO(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.
Featured in interview prep guides
Practice questions
Related concepts
- Nested Iterators And Lazy Stack TraversalCoding & Algorithms
- Stateful Data Structures And OOP API DesignCoding & Algorithms
- Caching And Stateful Data Structure DesignCoding & Algorithms
- Stateful In-Memory Data StructuresCoding & Algorithms
- TTL, Expiration, And Snapshot SemanticsCoding & Algorithms
- Persistent Key-Value StoresCoding & Algorithms