Graph Versioning And Path Discovery

What's being tested

These problems test mutable graph modeling plus versioned state access: can you support updates, point-in-time reads, traversal, and ranking without losing correctness. Expect to combine adjacency maps, snapshot logs, BFS/Dijkstra-style path search, and clean API design with explicit time/space tradeoffs.

Patterns & templates

• Adjacency map representation — Map<Node, Set<Node>> for unweighted graphs; updates are usually O(1) average, traversal is O(V + E).

• Snapshot versioning — store per-key history as sorted (version, value) arrays; get(key, version) uses binary search in O(log k).

• Copy-on-write snapshots — clone only changed nodes/edges per version; faster snapshot creation than full graph copy, but reads may chase deltas.

• BFS shortest path — use queue, visited, and parent map; reconstruct path from destination, O(V + E) time.

• Dijkstra for weighted conversions — priority queue over (cost, node); use when edges have nonnegative costs, O((V + E) log V).

• Recommendation ranking — count friends-of-friends or neighbors-of-neighbors with a Map<Candidate, Score>; exclude self and existing edges.

• Message/path protocols — separate correctness from transport: dedupe with messageId, prevent cycles with visited, bound retries/timeouts.

Common pitfalls

Pitfall: Treating snapshots as full deep copies; this passes small tests but explodes to O(S * (V + E)) space.

Pitfall: Forgetting deletion semantics in histories; use tombstones so old versions remain queryable while latest state removes the edge.

Pitfall: Using BFS for weighted type conversions; once edge costs differ, switch to Dijkstra or Bellman-Ford if negative weights are allowed.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.