Graph, Grid, BFS/DFS, And Union-Find
Asked of: Software Engineer
Last updated

What's being tested
These problems test graph modeling from strings, grids, and matrices, then choosing the right traversal: BFS for shortest path, DFS for connected components/topological ordering, and memoized DFS for DAG-style dynamic programming. Interviewers are probing correctness on edge cases, complexity discipline, and clean implementation under Meta-style time pressure.
Patterns & templates
-
Grid BFS shortest path — use
deque, mark visited on enqueue, explore 4 or 8 directions;O(mn)time and space. -
Island counting — scan every cell, launch
dfs(r,c)or iterative stack on unvisited land; mutate grid or maintainvisited. -
Longest increasing path — model matrix as DAG by value order;
dfs(r,c)withmemo[r][c]givesO(mn). -
Topological sort for unknown alphabet — build directed edges from first differing chars, then use
in_degree+ queue; detect cycles. -
Custom lexicographic validation — map
char -> rank, compare adjacent words only; handle prefix invalid case like"abc"before"ab". -
Union-Find alternative for components —
find,union, path compression, union by rank; useful when connections are streamed or repeated. -
Sparse representation — for sparse dot product, store
{index: value}or sorted pairs; iterate over smaller map forO(min(k1,k2)).
Common pitfalls
Pitfall: Marking grid nodes visited only when popped from BFS can enqueue the same cell many times and distort shortest-path logic.
Pitfall: In alien dictionary, adding constraints from every character position is wrong; only the first differing character between adjacent words matters.
Pitfall: Recursive DFS can hit recursion limits on large grids; mention iterative stack or recursion-limit handling if dimensions are large.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
- Infer an Unknown Alphabet OrderMeta · Software Engineer · Onsite · medium
- Check and infer custom alphabetMeta · Software Engineer · Technical Screen · hard
- Compute sparse dot product and count islandsMeta · Software Engineer · Technical Screen · medium
- Navigate unknown grid to locate targetMeta · Software Engineer · Technical Screen · Medium
- Solve grid path and top‑k frequencyMeta · Software Engineer · Technical Screen · Medium
- Implement encoding validation and grid shortest pathMeta · Software Engineer · Technical Screen · Medium
- Navigate unknown maze to find targetMeta · Software Engineer · Technical Screen · Medium
- Solve grid shortest path and robot cleaningMeta · Software Engineer · Onsite · Medium
- Solve UTF-8 Validation & Shortest PathMeta · Software Engineer · Technical Screen · Medium
- Solve island and frequency problemsMeta · Software Engineer · Onsite · Medium
- Solve island connectivity and string multiplicationMeta · Software Engineer · Technical Screen · Medium
- Solve diameter and shortest bridge problemsMeta · Software Engineer · Technical Screen · Medium
Related concepts
- DFS/BFS Tree, Graph, And Grid TraversalCoding & Algorithms
- BFS, DFS, Graph, And Grid TraversalCoding & Algorithms
- Graph, Grid, And Connectivity AlgorithmsCoding & Algorithms
- Graph Traversal And Shortest PathsCoding & Algorithms
- Graph Search, Pathfinding, And ConnectivityCoding & Algorithms
- Graph Search, State Space, And Path OptimizationCoding & Algorithms