Graph Traversal, Shortest Paths, and Topological Sort
Asked of: Software Engineer
Last updated
What's being tested
Tests whether you can model arrays, grids, and similarity relationships as graphs, then choose the right traversal: BFS for unweighted shortest paths, DFS/Union-Find for components, Dijkstra-style ordering for weighted or multi-criteria paths, and topological sort for dependency DAGs. Interviewers look for correctness under constraints: blocked nodes, dangerous nodes, tie-breaking, revisits, and large input sizes.
Patterns & templates
-
BFS shortest path on unweighted graphs — queue
(node, dist),visitedon enqueue,O(V + E)time and space. -
Constrained BFS with blocked nodes — skip neighbors in
blockedbefore enqueue; validate source/target edge cases before traversal. -
Multi-criteria shortest path — use
heapqwith tuple(danger_count, steps, node); equivalent to Dijkstra over lexicographic costs. -
Connected components — run DFS/BFS from each unvisited node; count or track max component size in
O(V + E). -
Grid traversal — convert
(r, c)to implicit neighbors viadirs; bounds-check before accessing cells; mark visited immediately. -
Top-K graph ranking — BFS by distance, collect candidates, sort by
(distance, -rating, id)or maintain bounded heap for scale. -
Topological sort — use
indegree+ queue for Kahn’s algorithm; if output length< V, report cycle,O(V + E).
Common pitfalls
Pitfall: Marking nodes visited when popped instead of when enqueued can duplicate work and break shortest-path assumptions in dense graphs.
Pitfall: Using plain BFS when the optimization is lexicographic, such as minimizing dangerous stops before minimizing total steps.
Pitfall: Forgetting disconnected graphs, blocked start/end nodes, self-loops, duplicate edges, and deterministic tie-breaking for ranked output.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Practice questions
- Recommend top-K movies from similarity graphGoogle · Software Engineer · Onsite · medium
- Compute shortest delivery route with dangerous stopsGoogle · Software Engineer · Onsite · medium
- Find largest group of two-digit numbers sharing digitsGoogle · Software Engineer · Take-home Project · easy
- Group movies via graph traversalGoogle · Software Engineer · Onsite · Medium
- Compute shortest paths with blocked nodesGoogle · Software Engineer · Technical Screen · Medium
- Solve tree, graph, sliding-window problemsGoogle · Software Engineer · Technical Screen · Medium
- Validate course catalog dependenciesGoogle · Software Engineer · Technical Screen · Medium
- Find shortest path with blocked nodesGoogle · Software Engineer · Onsite · Medium
- Solve Grid and Counting ProblemsGoogle · Software Engineer · Technical Screen · medium
Related concepts
- Graph Traversal And Shortest PathsCoding & Algorithms
- Graph, Grid, And Connectivity AlgorithmsCoding & Algorithms
- Graph Search, State Space, And Path OptimizationCoding & Algorithms
- Graph Algorithms, Dependency Resolution And ConnectivityCoding & Algorithms
- Graph Search, Pathfinding, And ConnectivityCoding & Algorithms
- DFS/BFS Tree, Graph, And Grid TraversalCoding & Algorithms