← Google Interview Insights

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

Intermediate
Apr 2026

Summary

Google SWE coding round, one question the whole time. Pretty standard BFS territory but the multi-source angle is the part people trip on if they haven't seen it before.

Questions Asked (1)

Q1

Given an m x n grid with taxis at certain positions and empty cells elsewhere, return a matrix where each cell contains the shortest 4-directional distance to the nearest taxi.

Algorithms & Data Structures
Author's notes

The key thing I almost missed was seeding all taxi positions into the queue at once before starting BFS.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use multi-source BFS starting from all taxi positions simultaneously to compute shortest distances to every cell in O(mn) time. Initialize a distance matrix with -1 (unvisited) and enqueue all taxis with distance 0, then process level by level.

Pro tip: Mention that multi-source BFS is optimal because it explores each cell once, and discuss how to handle edge cases like no taxis or all taxis. Also, note that you can avoid a separate visited array by using the distance matrix itself.

1. Clarify and define the problem

Confirm grid dimensions, taxi representation (e.g., 1 for taxi, 0 for empty), and that distance is Manhattan (4-directional). Ask about edge cases like no taxis.

2. Choose the algorithm

Select multi-source BFS over alternatives like running BFS from each taxi (O(k*mn)) or dynamic programming (which may not handle obstacles). Explain why BFS is optimal for unweighted grids.

3. Initialize data structures

Create a distance matrix initialized to -1, and a queue. Enqueue all taxi positions with distance 0 and set their distance in the matrix to 0.

4. Perform BFS

While the queue is not empty, dequeue a cell, explore its 4 neighbors. If a neighbor is within bounds and unvisited (distance -1), set its distance to current distance + 1 and enqueue it.

5. Return result and analyze complexity

After BFS, the distance matrix contains shortest distances. Return it. State time complexity O(mn) and space complexity O(mn) for the queue and distance matrix.

Key Points to Mention

  • Multi-source BFS treats all taxis as sources at distance 0, ensuring simultaneous exploration.
  • Time complexity is O(mn) because each cell is enqueued and dequeued at most once.
  • Space complexity is O(mn) for the distance matrix and queue.
  • Edge cases: no taxis (return matrix of -1 or infinity), all cells are taxis (return matrix of 0s).
  • Alternative approaches: BFS from each taxi (O(k*mn)) or dynamic programming (may not work with obstacles).
  • Use of a queue for BFS and marking visited by setting distance in the matrix.

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