Snapshot Iterators And Versioned Sets

What's being tested

Candidates must demonstrate design and implementation of snapshot semantics over a mutable set, showing mastery of persistent data structures, iterator stability, and complexity trade-offs. Interviewers probe whether you can provide iterators that reflect a point-in-time view while keeping add()/remove() fast and memory usage bounded.

Patterns & templates

• Copy-on-write at mutation: on add()/remove() clone only touched nodes to give new version, enabling O(1) iterator creation and O(log n) mutation cost in trees.
• Versioned nodes with integer version stamps: iterator captures current versionId; nodes carry created/removed versions to decide visibility during traversal.
• Tombstone marking: mark removals with a tombstone timestamp instead of physical delete; iteration filters by snapshot versionId.
• Path-copying persistent tree (e.g., AVL/treap): O(log n) amortized updates, iterators cheaply reference root at snapshot creation.
• Append-only linked buckets for integer sets: add() appends, remove() appends tombstone; iterators scan and dedupe, trading space for O(1) updates.
• Garbage collection via refcounts or epoch-based reclamation: reclaim old nodes when no iterator references older versions.
• Complexity tradeoff template: iterator creation O(1) + iteration O(k) vs full-copy O(n) creation; pick based on expected concurrent iterators.

Common pitfalls

Pitfall: Returning a live iterator over the single backing container — it will reflect later mutations, violating snapshot semantics.

Pitfall: Naively full-copying at iterator() for correctness — correct but often fails memory/time constraints when iterators are frequent.

Pitfall: Forgetting to reclaim old versions — leads to unbounded memory growth; track active snapshots or use epoch GC.