Graph Versioning And Path Discovery
Asked of: Software Engineer
Last updated
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 usuallyO(1)average, traversal isO(V + E). -
Snapshot versioning — store per-key history as sorted
(version, value)arrays;get(key, version)uses binary search inO(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, andparentmap; 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 withvisited, 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.
Practice questions
- Implement follow graph with snapshots and recommendationsOpenAI · Software Engineer · Technical Screen · medium
- Implement KV store and plan type conversionsOpenAI · Software Engineer · Technical Screen · Medium
- Implement node messaging and path discoveryOpenAI · Software Engineer · Technical Screen · Medium
Related concepts
- Graph Search, State Space, And Path OptimizationCoding & Algorithms
- Graph Search, Pathfinding, And ConnectivityCoding & Algorithms
- Graph Algorithms For Relations And RoutingCoding & Algorithms
- Graph Traversal And Shortest PathsCoding & Algorithms
- Graph Algorithms, Dependency Resolution And ConnectivityCoding & Algorithms
- Graph, Grid, BFS/DFS, And Union-FindCoding & Algorithms