← Microsoft Interview Insights

Microsoft·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jul 2026

Summary

Microsoft SWE interview with a grid-based BFS problem. Pretty standard algorithmic round but the problem had enough edge cases to keep you honest.

Questions Asked (1)

Q1

You're given a 2D grid where cells are either walls, gates, or empty rooms. Fill each empty room with its shortest distance to any gate, moving only up/down/left/right. Walls and unreachable rooms stay as-is.

Algorithms & Data Structures
Author's notes

My first instinct was to BFS from every empty room individually and find the nearest gate.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a multi-source BFS starting from all gates simultaneously, propagating distances to empty rooms level by level. This ensures each room is reached via the shortest path from any gate, and walls are never enqueued. Unreachable rooms remain unchanged.

Pro tip: Mention that multi-source BFS is optimal because it processes each cell once, achieving O(mn) time, and that using a queue with level-order traversal avoids the need for a priority queue. Also note that you can modify the grid in-place to store distances, saving space.

1. Clarify and define constants

Confirm the representation of walls, gates, and empty rooms (e.g., -1, 0, INF). Clarify that unreachable rooms should remain as INF (or original value).

2. Initialize the queue with all gates

Scan the grid and enqueue the coordinates of every gate. This sets up the multi-source BFS.

3. Perform BFS level by level

While the queue is not empty, pop a cell and explore its four neighbors. If a neighbor is an empty room (INF), update its distance to current distance + 1 and enqueue it.

4. Return the modified grid

After BFS, the grid contains shortest distances for reachable rooms; unreachable rooms remain INF. Return the grid.

Key Points to Mention

  • Multi-source BFS ensures shortest paths from any gate simultaneously.
  • Time complexity is O(m*n) where m and n are grid dimensions.
  • Space complexity is O(m*n) for the queue in the worst case.
  • Walls are never enqueued or modified.
  • Unreachable rooms remain as INF (or original value).
  • In-place modification avoids extra space for distance storage.

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