Grid, Matrix And Spatial Algorithms
Asked of: Software Engineer
Last updated

What's being tested
Grid and matrix algorithms here test whether you can model 2D state cleanly, choose the right traversal strategy, and reason about boundaries, mutation, and complexity. Expect divide-and-conquer, DFS/backtracking, dynamic programming, and graph reachability patterns rather than heavy system design.
Patterns & templates
-
QuadTree recursion with
build(r0, c0, size)— check uniform region, otherwise split into four quadrants;O(n^2 log n)naive,O(n^2)with prefix sums. -
2D prefix sums for constant-time area checks — compute
sum(r1,c1,r2,c2); uniform binary square if sum is0or area. -
Word search DFS/backtracking using
dfs(r, c, i)— mark visited, explore 4 directions, unmark on return; worst caseO(mn * 4^L). -
Fixed-direction grid scanning for simpler word search — test 8 directions with
(dr, dc)arrays; complexityO(mn * D * L). -
Largest square DP in binary matrices —
dp[i][j] = 1 + min(top, left, diag)when cell matches;O(mn)time,O(n)space possible. -
Graph eventual safety via DFS coloring —
0=unvisited,1=visiting,2=safe; cycles are unsafe, terminal-reaching DAG paths are safe. -
Boundary helpers like
in_bounds(r,c)and direction arrays reduce off-by-one bugs; clarify diagonal moves, cell reuse, and empty input early.
Common pitfalls
-
Pitfall: Reusing a cell in word search accidentally because visited state is not restored during backtracking.
-
Pitfall: Building QuadTrees by rescanning every subgrid without discussing prefix-sum optimization or worst-case complexity.
-
Pitfall: Treating “can reach a terminal node” as equivalent to “all paths eventually reach a terminal node” in graph safety problems.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
- Implement Minesweeper and Word SearchUber · Software Engineer · Onsite · medium
- Build a QuadTree From a GridUber · Software Engineer · Technical Screen · medium
- Find a Bounded Subarray and Largest SquareUber · Software Engineer · Onsite · medium
- Solve two interview coding problemsUber · Software Engineer · Technical Screen · medium
- Solve BFS and grid tasksUber · Software Engineer · Onsite · medium
- Build a Quadtree and Analyze a GraphUber · Software Engineer · Technical Screen · medium
- Simulate one-round color elimination on a gridUber · Software Engineer · Take-home Project · Medium
- Implement 2D word search variants and analyze complexityUber · Software Engineer · Technical Screen · Medium
- Develop test plan and TDD for word searchUber · Software Engineer · Technical Screen · medium
- Simulate fixed-shape tiling on a gridUber · Software Engineer · Take-home Project · Medium
- Perform matrix Candy Crush eliminationUber · Software Engineer · Take-home Project · Medium
- Simulate robot on grid with obstaclesUber · Software Engineer · Onsite · Medium
Related concepts
- Graph, Grid, BFS/DFS, And Union-FindCoding & Algorithms
- Graph Search, State Space, And Path OptimizationCoding & Algorithms
- Graphs, Grids, And Connected ComponentsCoding & Algorithms
- Match-3 Board SimulationCoding & Algorithms
- BFS, DFS, Graph, And Grid TraversalCoding & Algorithms
- Graph, Grid, And Connectivity AlgorithmsCoding & Algorithms