Katkat
Back

Implement a snapshotable set with iterators

DatabricksSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates understanding of persistent/versioned data structures, iterator semantics, concurrency control, and complexity-aware design for mutable sets, and is categorized under Coding & Algorithms.

Implement a SnapshotSet data structure with the following API: add(x), remove(x), contains(x), snapshot() -> sid, and iterate(sid) -> iterator over the elements as of snapshot sid. Support many concurrent snapshots while allowing the live set to change. Optimize for O(log n) updates and O(

  1. iterator next on average. Discuss design choices (copy-on-write, persistent balanced tree, or versioned hash buckets), memory usage, and snapshot reclamation. Provide unit tests for empty set, deletions before/after snapshots, and concurrent mutation during iteration.