BFS, DFS, Graph, And Grid Traversal
Asked of: Machine Learning Engineer
Last updated

What's being tested
Graph traversal fluency: modeling matrices, grids, nested structures, and dependency lists as nodes plus edges, then choosing BFS for shortest paths or DFS for exhaustive exploration. Interviewers are probing correctness under edge cases, clean implementation, and complexity reasoning: for graphs, for grids.
Patterns & templates
-
Grid DFS component sizing — iterate every cell, launch
dfs(r,c)on unvisited valid cells, count region size;O(RC)time,O(RC)worst stack. -
Iterative DFS with
stack— safer than recursion for large matrices; mark visited when pushing, not popping, to avoid duplicates. -
BFS shortest path — use
deque, level distance, and optionalparent[(r,c)]map for reconstruction; handles obstacles and unweighted moves. -
Cycle detection in directed graphs — use
WHITE/GRAY/BLACKstates indfs(node); encounteringGRAYmeans cycle, postorder gives topological order. -
Adjacency construction — for dependency/order problems, build
dict[node] -> list[neighbors]; include isolated nodes so output size is correct. -
Bounds helper — centralize
in_bounds(r,c)andDIRS = [(1,0),(-1,0),(0,1),(0,-1)]; clarify whether diagonals count. -
Nested DFS aggregation — pass
depthinto recursion for depth-weighted sums; watch for empty lists and mixed integer/list nodes.
Common pitfalls
Pitfall: Using DFS for shortest path in an unweighted grid. DFS may find a path, but BFS guarantees minimum distance.
Pitfall: Marking grid cells visited too late. If multiple neighbors enqueue the same cell, runtime and parent reconstruction can break.
Pitfall: Forgetting recursion-depth limits. In
Python, a long chain or huge connected region can exceed the call stack; switch to iterative traversal.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
- Compute nested depth sum and grid distanceMeta · Machine Learning Engineer · Onsite · medium
- Solve linked list, tree, and grid problemsMeta · Machine Learning Engineer · Onsite · medium
- Find target using robot movement APIMeta · Machine Learning Engineer · Onsite · medium
- Detect cycles and order with DFSMeta · Machine Learning Engineer · Onsite · Medium
- Find connected region sizes in matrixMeta · Machine Learning Engineer · Onsite · Medium
- Implement bounds, minimum, pathfinding, and moving averageMeta · Machine Learning Engineer · Onsite · Medium
- Solve matrix components, median, and traversalsMeta · Machine Learning Engineer · Technical Screen · Medium
Related concepts
- DFS/BFS Tree, Graph, And Grid TraversalCoding & Algorithms
- Graph, Grid, BFS/DFS, And Union-FindCoding & Algorithms
- Graph Traversal And Shortest PathsCoding & Algorithms
- Depth-First Search, Connected Components, And CyclesCoding & Algorithms
- Graph, Grid, And Connectivity AlgorithmsCoding & Algorithms
- Graph Search, Pathfinding, And ConnectivityCoding & Algorithms