Meta·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Meta coding screen, grid BFS problem. Pretty standard algorithmic round but the multi-source angle trips people up if they haven't seen it before.

Questions Asked (1)

You have an m x n grid where each cell is either a wall (-1), a gate (0), or an empty room (INF). Fill every empty room with its distance to the nearest gate, in-place. Rooms that can't reach any gate stay as INF.

Algorithms & Data Structures

Author's notes

The naive approach is to BFS from each gate separately and track minimums, but that tanks your runtime on large grids.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a multi-source BFS starting from all gates simultaneously, updating empty rooms with their distance to the nearest gate. This ensures each cell is visited once, achieving O(mn) time complexity.

Pro tip: Emphasize that multi-source BFS is optimal because it processes all gates in parallel, avoiding redundant traversals and naturally handling unreachable rooms. Also, mention that modifying the grid in-place is safe since gates and walls are never overwritten.

1. Identify all gates

Scan the grid to collect the coordinates of all gates (cells with value 0) and enqueue them for BFS.

2. Initialize BFS

Set up a queue with all gate coordinates and define the four possible movement directions (up, down, left, right).

3. Process queue level by level

While the queue is not empty, dequeue a cell and for each valid neighbor that is an empty room (INF), update its distance to current distance + 1 and enqueue it.

4. Handle unreachable rooms

After BFS, any remaining INF cells are unreachable from any gate and should stay as INF.

Key Points to Mention

Multi-source BFS ensures each cell is visited at most once, giving O(mn) time complexity.
Space complexity is O(mn) in the worst case for the queue, but can be optimized by using the grid itself for distance tracking.
The algorithm naturally handles unreachable rooms by leaving them as INF.
In-place modification is safe because gates (0) and walls (-1) are never overwritten.
Edge cases: grid with no gates, all walls, or gates already adjacent to all rooms.
Alternative approaches like DFS or BFS from each empty room are less efficient (O(mn * number of gates) or O(mn * number of rooms)).

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