Graph Algorithms For Relations And Routing

What's being tested

You’re being tested on graph modeling: turning relations like similarity, exchange rates, or roads into nodes, edges, weights, and traversal rules. Interviewers look for correct algorithm choice, clean data structures, edge-case handling, and clear complexity reasoning.

Patterns & templates

• Adjacency list with `dict[node] -> list[(neighbor, weight)]` — best default for sparse graphs; build in O(E) space.

• DFS/BFS traversal for connected components or reachability — O(V+E) time; track visited before enqueueing to avoid cycles.

• Weighted path accumulation for ratios/conversions — multiply edge weights along a path; add reciprocal edges for bidirectional rates.

• Dijkstra’s algorithm for nonnegative route costs — O((V+E) log V) with heapq; don’t use plain BFS on weighted edges.

• Topological sort for DAG dependency chains — O(V+E) using indegree queue; detect cycles when processed count < V.

• Union-Find for grouping linked records — near-constant amortized find()/union(); useful when edges imply equivalence components.

• Consistency checking in weighted graphs — compare implied versus supplied ratios with epsilon tolerance; floating-point equality is unsafe.

Common pitfalls

Pitfall: Treating every graph as unweighted; bicycle routes and conversion rates require preserving edge costs or multiplicative weights.

Pitfall: Forgetting disconnected components; queries may involve two nodes with no valid path.

Pitfall: Overengineering dynamic updates; first solve the static graph correctly, then discuss incremental rebuilds or cached components.

Practice these

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