Grid Paths with Override Passes
Reported by candidates from Microsoft's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The robot in this Microsoft OA only moves Right or Down, and you get k override passes to burn on blocked cells. It was reported in September 2026. The hint says BFS, but don't buy it. Every path has a fixed length, so you're counting, not searching. This is a grid DP with an extra dimension for passes used. Cells are up to 200 x 200 and k is at most 10, so the state space is small. If you blank under the timer, StealthCoder runs invisibly on your screen and hands you the recurrence. Better to know it before you sit down.
The problem
A delivery robot navigates a city represented by an n x m grid. A cell containing 1 is an open street, while a cell containing 0 is blocked by construction. The robot starts at the top-left cell (0, 0) and must reach the bottom-right cell (n - 1, m - 1). The starting and ending cells may themselves be blocked. From any cell, the robot may move exactly one cell Right or one cell Down. The robot has k override passes. Including one blocked cell in a path consumes exactly one pass, and the robot may consume at most k passes over its entire path. Return the number of distinct paths from the start to the destination that use at most k override passes, modulo 10^9 + 7. Function numPaths(grid: int[][], k: int) → int Examples Example 1 grid = [[1,0,1],[1,0,1],[1,1,1]] k = 1 return = 4 Four paths use at most one override pass. Three enter exactly one blocked cell, while the path that moves Down, Down, Right, Right enters no blocked cells. Example 2 grid = [[1,0],[0,1]] k = 0 return = 0 Both possible first moves enter a blocked cell, but no override pass is available. Constraints 1 <= n, m <= 200 0 <= k <= 10 Every cell of grid is either 0 or 1.
Reported by candidates. Source: FastPrep
Pattern and pitfall
Define dp[i][j][p] as the number of paths reaching cell (i, j) having used exactly p passes. Transition from the top and left neighbors. If the current cell is 0, you shift p by one, so dp[i][j][p] = dp[i-1][j][p-1] + dp[i][j-1][p-1]. If it's 1, p stays the same. Seed the start cell: p=0 if open, p=1 if blocked. The answer is the sum of dp[n-1][m-1][p] for p from 0 to k. The common pitfall is forgetting that the start and end can be blocked, which costs a pass each. Another is skipping the modulo 10^9 + 7 on every addition. Roll the first dimension to save memory, though 200 x 200 x 11 fits fine. Complexity is O(n*m*k). If the recurrence slips away mid-assessment, StealthCoder is the safety net that shows you the state design.
The honest play: practice the pattern, and have StealthCoder ready for the one you didn't see coming.
You can drill Grid Paths with Override Passes cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built for the candidate who saw this exact problem leak two days before his OA and wondered if anyone had a play.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Microsoft's OA.
Microsoft reuses patterns across OAs. Built for the candidate who saw this exact problem leak two days before his OA and wondered if anyone had a play. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Grid Paths with Override Passes FAQ
Is this really a BFS problem?+
No. BFS finds shortest paths or reachability. Here every Right/Down path has the same length and you need a count modulo 10^9 + 7. That's dynamic programming over cell and passes used. BFS would blow up since the number of paths is exponential.
What's the trick for the override passes?+
Add a third dimension to the DP for passes used. Entering a blocked cell shifts you from p-1 to p. Entering an open cell keeps p. Sum the last cell across p from 0 to k for the final answer.
Do I need to handle a blocked start or end cell?+
Yes. The statement says both can be blocked, and each blocked cell on the path costs one pass, including those. Initialize dp[0][0] at p=1 if it's 0, and the end cell naturally uses the same shift rule.
How do I check Example 1 quickly?+
Grid [[1,0,1],[1,0,1],[1,1,1]] with k=1 gives 4. The Down, Down, Right, Right path uses zero passes. Three other paths each cross exactly one 0. Run your DP by hand on this 3 x 3 grid and confirm the sum is 4.
How do I prepare for this in 48 hours?+
Practice grid path counting with an obstacle limit. Write the 3D DP from scratch twice, then optimize to rolling rows. Test k=0, a 1 x 1 grid, and blocked corners. Those edge cases are where most wrong answers come from.