Google·Software Engineer·Onsite - Coding / Algorithms·Senior

SeniorPrefer not to say

May 2026

Summary

Google SWE coding round with a grid path problem that had a tricky one-step lookback constraint. Not your standard DFS on a grid, the extra state made it harder to think through cleanly under pressure.

Questions Asked (1)

Given an m x n integer grid, find the longest path starting from any cell where each move goes to an adjacent cell (4 directions) and the value is non-increasing, except that each step can also compare against the value two cells back (not just the immediately previous cell). Return the number of cells visited on the longest valid path.

Algorithms & Data Structures

Author's notes

The base idea looks like a standard longest decreasing path on a grid, which I've seen before, so I jumped into memoized DFS pretty fast.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the grid as a directed acyclic graph where edges represent valid moves, then use dynamic programming with memoization to compute the longest path from each cell. The twist is that the validity of a move depends on the previous two values, so the DP state must include the last two cells (or their values) to correctly enforce the non-increasing condition.

Pro tip: Clarify the exact rule: 'each step can also compare against the value two cells back' likely means the non-increasing condition must hold against both the immediately previous cell and the cell before that. If so, the state needs the last two values, and you should discuss how to handle the start of the path where fewer than two previous cells exist.

1. Clarify the problem statement

Ask the interviewer to confirm the exact condition: does 'compare against the value two cells back' mean the current value must be ≤ both the previous and the one before that? Also confirm if the path can revisit cells (likely no, since non-increasing would prevent cycles unless equal values allow revisiting).

2. Define the DP state

Since the validity of a move depends on the last two values, define DP state as (cell, prev_cell) or (cell, prev_value, prev_prev_value). Explain that this captures the necessary history to enforce the non-increasing condition.

3. Formulate recurrence and base cases

For a given state, try all 4 adjacent cells. A move to neighbor is valid if neighbor's value ≤ current value and (if prev exists) neighbor's value ≤ prev value. The path length from the state is 1 + max over valid moves. Base case: if no valid moves, length is 1 (the cell itself).

4. Implement with memoization

Use memoization (e.g., a hash map or 3D array) to store computed results for each state. Iterate over all cells as starting points, compute the longest path, and return the maximum. Discuss time complexity: O(m*n*4*V) where V is the number of possible previous values (or O(m*n) if values are bounded).

5. Analyze complexity and edge cases

Analyze time and space complexity. Consider edge cases: single cell, all equal values, strictly increasing/decreasing grids, and paths that start with only one previous cell. Discuss potential optimizations if needed.

Key Points to Mention

Dynamic programming with memoization to avoid recomputing overlapping subproblems.
State representation must include the last two values (or cells) to enforce the non-increasing condition correctly.
The problem can be modeled as finding the longest path in a directed acyclic graph (DAG) if we consider states as nodes.
Time complexity: O(m*n*4*K) where K is the number of possible previous values (or O(m*n) if values are bounded and we use a 3D DP array).
Space complexity: O(m*n*K) for memoization, which can be reduced if we only store necessary states.
Edge cases: paths of length 1, grids with all equal values (where any path is valid as long as non-increasing holds), and handling the start of the path where there is no previous value.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.