← Google Interview Insights

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

IntermediatePrefer not to say
Jun 2026

Summary

Google SWE coding round, one question the whole time. Grid BFS problem that looks straightforward but has a few ways to mess it up if you're not careful about initialization.

Questions Asked (1)

Q1

Given a 2D grid where some cells contain taxis, find the shortest distance from every cell to the nearest taxi.

Algorithms & Data Structures
Author's notes

Multi-source BFS is the right move here.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a multi-source shortest path on a grid, where all taxi cells are sources with distance 0. Use BFS from all taxis simultaneously to compute the shortest distance to every cell in O(m*n) time, since each edge has unit weight. Discuss the approach, then implement it cleanly with a queue and visited array.

Pro tip: Mention that BFS is optimal here because the grid is unweighted, and contrast it with running BFS from each cell (which would be O((mn)^2)). This shows you understand complexity trade-offs and can optimize early.

1. Clarify the problem and constraints

Ask about grid size, whether taxis are given as a list or marked in the grid, and if distance is Manhattan or path-based (with obstacles). Confirm that movement is 4-directional and that unreachable cells should be marked as -1 or infinity.

2. Choose the right algorithm

Recognize that this is a multi-source shortest path problem on an unweighted graph. BFS from all sources simultaneously is optimal, as it explores cells in increasing order of distance.

3. Outline the BFS approach

Initialize a queue with all taxi positions and set their distance to 0. Then perform BFS, updating distances for unvisited neighbors and enqueueing them.

4. Analyze complexity and edge cases

State that time and space are O(m*n). Handle edge cases: no taxis (return -1 or infinity for all), all cells are taxis (distance 0), and obstacles if present.

5. Implement and test

Write clean code with a queue and a distance matrix. Test with a small example, including a case with unreachable cells, to verify correctness.

Key Points to Mention

  • Multi-source BFS treats all taxis as sources at distance 0, avoiding redundant searches.
  • Time and space complexity are O(m*n), which is optimal for this problem.
  • Use a queue (FIFO) to ensure cells are processed in order of increasing distance.
  • Initialize distances to -1 or infinity to mark unvisited cells, and update when first reached.
  • If obstacles are present, BFS still works but skip blocked cells; if movement is 8-directional, adjust neighbor checks.
  • Alternative approaches like dynamic programming or Dijkstra are unnecessary because all edges have unit weight.

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