In grid backtracking, what goes wrong when the recursive step indexes a cell before checking bounds?
answer
- who is allowed to hand you a bad coordinate?
- the read happens before the rejection
- what does a flat row-major index do?
- column overflow lands on the next row
- range, then occupancy, then value, then base case
basics
~20 sIndexing first reads a cell that does not exist. Bounds-checked runtimes raise an error; unchecked ones read whatever memory is adjacent, and a flat row-major grid silently wraps a column overflow into the neighbouring row, producing a wrong answer with no error at all.
solid answer
~50 sThe recursion is called with coordinates that may be off the grid — that is the whole point of letting the callee validate. If the value comparison runs first, the out-of-range read happens before anything rejects it. In a bounds-checked environment that is a hard failure on a perfectly valid input. In an unchecked one it is worse: with a flat row-major buffer, column `cols` reads the first cell of the next row and column `-1` reads the last cell of the previous row, so the search happily matches a "neighbour" that wraps around the edge and reports a path that does not exist. The fix is guard ordering: range check, then occupancy check, then value comparison, then the base case. Alternatively validate in the caller before recursing — but pick one discipline and apply it at both the top-level loop and the recursion.
code
pseudocode · 15 linesSEARCH(grid, target, r, c, k):
if grid[r][c] != target[k]:
return false
if r < 0 or r >= rows or c < 0 or c >= cols:
return false
if k == length(target) - 1:
return true
mark(r, c)
found = false
for (nr, nc) in the four orthogonal neighbours of (r, c):
if not marked(nr, nc) and SEARCH(grid, target, nr, nc, k + 1):
found = true
break
unmark(r, c)
return foundgo deeper
Be ready to name the guard order out loud: range first, then whether the cell is blocked or already on the path, then the value comparison, then the completion check. Nothing may touch the grid above the range test.
Explain what the bad read actually does. A flat row-major grid turns a column overflow into a read of the next row's first cell, so the bug surfaces as a plausible wrong path rather than an error.
Show how you would catch it: property-test a search against grids whose edge columns differ, and assert that no returned path contains a step between cells that are not truly adjacent. Off-by-one wrap survives every happy-path test.
Own the precondition as an interface decision. Whether coordinates are validated by the caller or the callee should be stated once and enforced once across the whole codebase; mixed disciplines are where these gaps reopen after every refactor.
## The contract between caller and callee Grid backtracking has two places a coordinate can be validated: in the **caller**, before it recurses into a neighbour, or in the **callee**, as its first guard. Both work. What does not work is assuming one and writing the other. The callee-validates style is the common one because it collapses all the checking into a single place: the four neighbour coordinates are generated blindly, handed to the recursive call, and the call rejects the ones that are off the board. That style has a precondition it must honour — **the very first thing the function does has to be the range test**, because by construction it is called with coordinates that are frequently invalid. In the fragment for this question the order is inverted: the cell's value is compared to the target character, and only then are the coordinates range-tested. The dead code is not the danger; the read that happens before it is. ## What an out-of-range read actually does This splits by how the grid is stored and how strictly the environment checks: - **Bounds-checked, nested rows.** A row index past the end fails immediately. Loud, and the least damaging outcome — you get a crash on a legal input, which someone will notice. - **Bounds-checked, flat buffer.** A single index `r * cols + c` is computed first. For a column overflow this index is usually still *inside* the buffer, so no check fires: `c == cols` on row `r` lands on `(r+1, 0)`, and `c == -1` lands on `(r, cols-1)` of the previous row. Nothing complains. - **Unchecked.** A row overflow reads memory past the end of the grid entirely: undefined behaviour, and possibly a value that happens to match. The middle case is the one worth being able to explain in an interview, because it is the one that produces a **silently wrong answer**. On a warehouse floor grid the search will happily walk off the right edge of one aisle and continue on the left edge of the next one, and report a pick-path that the robot physically cannot follow. Every test on a grid whose rows all match at the wrap point still passes. ## The correct guard order The guards go cheapest-and-most-restrictive first, and any guard whose failure makes a later guard *unsafe* must precede it: 1. **Range.** Is the coordinate on the grid? Nothing below this line may touch the grid. 2. **Occupancy.** Is the cell blocked, or already on the current path? A cheap side-table read; no value comparison needed to reject. 3. **Value.** Does the cell's contents match the character the target wants at this depth? 4. **Base case.** Having matched, is this the last character? If so, succeed. Step 4's placement matters as much as step 1's. Testing "is this the last index" *before* the value comparison accepts a path whose final cell never matched — an off-by-one that reports phantom matches of length one more than reality. Match first, then check for completion. A second subtlety: the top-level loop that tries each cell as a start must not skip these guards. Coordinates it generates are always in range, but the value and occupancy checks still apply, and duplicating a slightly different guard set at the top level is a classic source of "works from most starts, not from that one". ## Caller-validates, and why you should not mix The alternative discipline tests the neighbour before recursing: skip out-of-range and already-marked neighbours in the loop, so the function may assume a valid, unmarked cell on entry. It saves one stack frame per rejected neighbour, which is a real constant-factor win when three of four neighbours are rejected at every node, and it makes the recursive function's precondition explicit. The cost is that the guard now exists in two places — the neighbour loop and the top-level start loop — and the two copies drift. Whichever you choose, the rule is that the function's precondition should be stated once and enforced once. Mixed code, where the caller filters some neighbours and the callee re-checks others, is where the gap opens. ## Defensive habits that are not the fix Wrapping the read in error handling to swallow out-of-range access "works" and is a bad answer: it converts a logic error into a silent control-flow path, costs far more per node than an integer comparison in a hot recursion, and does nothing for the flat-buffer wrap case, where no error is raised in the first place. The fix is ordering, not catching. Finally, the edge cases worth naming out loud: a target longer than the number of cells (answer is trivially false, and a cheap pre-check saves the whole search), a single-cell target (the base case must fire on the first cell without any recursion), and a grid with zero rows (the top-level loop must not assume `rows > 0` before computing `cols`).
- Why is the flat row-major storage case more dangerous than a hard failure?Because nothing fires. Column `cols` on row `r` computes an index that is still inside the buffer and lands on `(r+1, 0)`; column `-1` lands on the previous row's last cell. The search then treats cells on opposite edges as adjacent and reports a path that cannot be walked. A crash is a bug report; this is a wrong answer that ships.
- Where should the success base case sit relative to the value comparison, and why?After it. If you check "this is the last character of the target" before comparing the cell's value, you accept a path whose final cell never matched, reporting matches that do not exist. Match the current cell first, then ask whether matching it completed the target.
- Is it cheaper to filter neighbours in the caller than to reject them in the callee?Marginally, and it is a constant factor only. Filtering in the loop avoids pushing a frame for the three-in-four neighbours that are rejected at a typical node, which matters in a hot recursion. The cost is that the guard now lives in both the neighbour loop and the top-level start loop, and the two copies drift apart over time.
saying these in an interview costs you the question
- Assumes an out-of-range index always raises an error
- Fixes it by catching the error instead of reordering guards
- Says guard order in a recursive step never matters
- Believes the caller always passes in-range coordinates
- Puts the success base case before the value comparison