Graph Traversal And Shortest Paths
Asked of: Software Engineer
Last updated

What's being tested
These problems test graph modeling, BFS/DFS traversal, shortest path under constraints, and connected-component reasoning. Interviewers are checking whether you can convert messy relationships—blocked stops, reporting chains, shared digits, word paths—into nodes, edges, state, and traversal rules.
Patterns & templates
-
BFS for unweighted shortest path — use
queue,visited, and distance levels;O(V + E)time,O(V)space. -
Dijkstra for weighted or penalty paths — use
heapqwith(cost, node); needed when dangerous nodes add non-uniform costs. -
Lexicographic shortest path state — optimize
(danger_count, steps)instead of one scalar; compare tuples directly in Python. -
DFS/backtracking for path existence — recursively match characters or constraints; mark/unmark
visitedto avoid cycles without blocking other branches. -
Connected components — build adjacency from shared attributes, then BFS/DFS each unvisited node; useful for grouping two-digit numbers.
-
Transitive relationship queries — model manager chains as a directed graph or parent map; use ancestor traversal, caching, or union-like grouping for peers.
-
Grid/graph neighbor generation — centralize
neighbors(node)logic; filter blocked nodes before enqueueing to avoid invalid states.
Common pitfalls
Pitfall: Treating weighted penalties like ordinary BFS; if costs differ, BFS no longer guarantees the optimal route.
Pitfall: Using one global
visitedset in backtracking; paths need branch-local state with unmarking on return.
Pitfall: Forgetting disconnected components, duplicate inputs, self-edges, cycles, or “start/end is blocked” edge cases.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
- Determine Whether a Word Exists in a GraphGoogle · Software Engineer · Onsite · medium
- Determine Reporting RelationshipsGoogle · Software Engineer · Technical Screen · none
- Validate parent array forms a treeGoogle · Software Engineer · Technical Screen · medium
- 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
- Solve three coding interview problemsGoogle · Software Engineer · Onsite · medium
- Group movies via graph traversalGoogle · Software Engineer · Onsite · 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
- Shortest Path And Graph TraversalCoding & Algorithms
- BFS, DFS, Graph, And Grid TraversalCoding & Algorithms
- Graph, Grid, BFS/DFS, And Union-FindCoding & Algorithms
- DFS/BFS Tree, Graph, And Grid TraversalCoding & Algorithms
- Graph Algorithms, Dependency Resolution And ConnectivityCoding & Algorithms
- Graph, Grid, And Connectivity AlgorithmsCoding & Algorithms