Versioned Graphs And Snapshotting

What's being tested

These problems test building a mutable directed graph that supports versioning and efficient snapshotting for point-in-time queries alongside live mutations. Interviewers probe data structures (per-edge logs, hash maps, balanced trees), algorithmic complexity for queries and updates, and memory/time tradeoffs when producing recommendations from historical graph state.

Patterns & templates

• Per-edge event lists: store adds/removes as timestamped ops in sorted arrays; use binary search for membership at version V, O(log m) per edge lookup.

• Immutable snapshots via copy-on-write: keep a root pointer to shared structures so snapshot creation is O(1) and mutations copy only changed nodes, amortized efficient for sparse updates.

• Sparse version index / change logs: maintain Map<version, root> or per-node change lists to replay until V; snapshot creation O(1), point-in-time rebuild cost depends on log length.

• In-memory adjacency map: Map<node, Map<neighbor, List<(ts, op)>>> gives O(1) node access; watch memory for high-degree vertices and prefer compressed neighbor lists.

• Ordered containers for fast range queries: use TreeMap/skiplist or arrays + bisect to find prefix/suffix of events in O(log n)+O(k) to scan k events.

• Recommendations via mutual intersections: iterate the smaller neighbor list and hash-count candidates, use a size-k heap for top-k, cost ~O(sum small_deg + m log k).

• Compaction/checkpointing: checkpoint full adjacency at intervals and drop old deltas to bound read/replay cost; tune checkpoint frequency to update rate.

Common pitfalls

Pitfall: Treating unfollow as instantaneous deletion without a timestamp makes point-in-time queries ambiguous and yields wrong historical membership.

Pitfall: Assuming snapshot = deep copy; naive copies are O(N) and blow up memory — prefer structural sharing or periodic checkpoint+delta strategies.

Pitfall: Building recommendations by intersecting all neighbors (all-pairs) — this can be O(n^2) on heavy nodes; always iterate the smaller set or use sampling.