Implement a snapshotable set with iterators

Q: Implement a snapshotable set with iterators

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.

Q: How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

Q: What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Databricks.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Databricks during technical interviews.

Question

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.

PracHub · Accepted Answer

def solution(operations): import random import sys sys.setrecursionlimit(1_000_000) rng = random.Random(0) class Node: __slots__ = ('key', 'prio', 'left', 'right') def __init__(self, key, prio, left=None, right=None): self.key = key self.prio = prio self.left = left self.right = right def contains(root, x): while root is not None: if x < root.key: root = root.left elif x > root.key: root = root.right else: return True return False def merge(a, b): if a is None: return b if b is None: return a if a.prio < b.prio: return Node(a.key, a.prio, a.left, merge(a.right, b)) return Node(b.key, b.prio, merge(a, b.left), b.right) def split(root, key): # Returns (< key, >= key) if root is None: return None, None if key <= root.key: left_part, right_left = split(root.left, key) return left_part, Node(root.key, root.prio, right_left, root.right) left_right, right_part = split(root.right, key) return Node(root.key, root.prio, root.left, left_right), right_part def add(root, x): if contains(root, x): return root left, right = split(root, x) node = Node(x, rng.getrandbits(64)) return merge(merge(left, node), right) def remove(root, x): if not contains(root, x): return root left, mid_right = split(root, x) _, right = split(mid_right, x + 1) return merge(left, right) def push_left(node, stack): while node is not None: stack.append(node) node = node.left current_root = None snapshots = [] iterators = [] result = [] for op in operations: kind = op[0] if kind == 'add': current_root = add(current_root, op[1]) elif kind == 'remove': current_root = remove(current_root, op[1]) elif kind == 'contains': result.append(contains(current_root, op[1])) elif kind == 'snapshot': snapshots.append(current_root) result.append(len(snapshots) - 1) elif kind == 'iterator': sid = op[1] stack = [] push_left(snapshots[sid], stack) iterators.append(stack) result.append(len(iterators) - 1) elif kind == 'next': iid = op[1] stack = iterators[iid] if not stack: result.append(None) else: node = stack.pop() push_left(node.right, stack) result.append(node.key) else: raise ValueError(f'Unknown operation: {kind}') return result

Quick Overview

Examples

Solution

Hints

Quick Overview