Google·Software Engineer·Onsite - Coding / Algorithms
Jun 2026
Google onsite coding round, second interview of the day. The problem was a grid pathfinding variant where you minimize the maximum cell value on a path rather than the sum, with a follow-up that pushed into general weighted graphs. Harder than it looks if you haven't thought carefully about why Dijkstra even works when the cost function isn't additive.
- Given a grid of integer heights, find a path from the top-left to the bottom-right corner such that the maximum cell value along the path is minimized. You can move to any of the four adjacent cells.
- Follow-up: given a directed weighted graph and a source node, return the maximum shortest-path distance across all nodes, or -1 if any node is unreachable.
- Why does Dijkstra's algorithm remain correct when the path cost is defined as the maximum edge or node value encountered, rather than the sum of weights?
“I knew this was Dijkstra-flavored but fumbled the transition from 'minimize sum' to 'minimize max' for a bit.” The rest of the author's notes on Software Engineer interview at Google, Onsite - Coding / Algorithms round, covers how they worked through the question, what the panel pushed back on, and what they would do differently.
View Post