Google·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Google SWE technical phone screen, one graph problem, pretty standard stuff but the specific variant they wanted tripped me up a bit.

Questions Asked (1)

Given an n x n grid where each cell has an elevation value, water rises uniformly over time such that at time t the water level equals t. You can move between adjacent cells only when the water level covers both. Find the minimum time needed to travel from the top-left to the bottom-right cell.

Algorithms & Data Structures

Author's notes

I recognized it as a graph problem pretty fast but my first instinct was BFS with binary search on the answer, which works but they pushed me toward something cleaner.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the grid as a graph where each cell's weight is its elevation, and the time to traverse a path is the maximum elevation along that path. Use a modified Dijkstra's algorithm (or a priority queue) to find the path from top-left to bottom-right that minimizes this maximum elevation. Alternatively, use binary search on time t and BFS to check if a path exists where all cells have elevation ≤ t.

Pro tip: Clarify that the problem is equivalent to finding the minimax path (bottleneck shortest path) and mention that both Dijkstra and binary search + BFS are valid, but Dijkstra is more efficient for large grids. Also, discuss edge cases like n=1 and the fact that the start and end cells' elevations are always included in the maximum.

1. Understand the problem

Restate the problem: water rises uniformly, and you can move between adjacent cells only when the water level covers both. The minimum time to travel from start to end is the minimum possible maximum elevation along any path.

2. Choose an approach

Decide between Dijkstra-like algorithm (minimax path) or binary search on time with BFS. Explain the trade-offs: Dijkstra runs in O(n^2 log n) while binary search + BFS runs in O(n^2 log(max_elevation)).

3. Implement the algorithm

For Dijkstra: use a priority queue storing (max_elevation_so_far, row, col), and update neighbors with max(current_max, neighbor_elevation). For binary search: define check(t) that runs BFS from start to end only through cells with elevation ≤ t.

4. Analyze complexity and edge cases

Discuss time and space complexity. Handle edge cases: n=1 (answer is grid[0][0]), unreachable cells (though problem guarantees connectivity? Actually water rises so eventually all cells are covered, so always reachable).

5. Test with examples

Walk through a small example to verify the approach. For instance, a 2x2 grid with elevations [[0,2],[1,3]]: the minimax path is 0->1->3 with max 3, or 0->2->3 with max 3, so answer is 3.

Key Points to Mention

The problem reduces to finding a path that minimizes the maximum elevation along the path (minimax path).
Dijkstra's algorithm can be adapted by using the maximum edge weight instead of sum, and the priority queue orders by this maximum.
Binary search on time t combined with BFS/DFS is an alternative, where you only traverse cells with elevation ≤ t.
Time complexity: Dijkstra O(n^2 log n) vs binary search O(n^2 log(max_elevation)).
The start and end cells' elevations are always part of the maximum, so the answer is at least max(grid[0][0], grid[n-1][n-1]).
Water rises uniformly, so at time t all cells with elevation ≤ t are submerged; movement is possible only through submerged cells.

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