Quick Overview

This Coding & Algorithms question evaluates algorithmic problem-solving with grid-based graph traversal and shortest-distance computation, assessing data-structure use and implementation-level efficiency for software engineers.

Fill rooms with nearest-gate distance

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given an m×n grid representing a building floor plan: - `-1` = wall/blocked cell - `0` = gate - A large positive number (e.g., `INF = 2^31-1`) = empty room Fill each empty room with the distance to its nearest gate (Manhattan distance: up/down/left/right). If a gate cannot be reached, leave the value as `INF`. Return the modified grid (or modify it in-place).

Quick Answer: This Coding & Algorithms question evaluates algorithmic problem-solving with grid-based graph traversal and shortest-distance computation, assessing data-structure use and implementation-level efficiency for software engineers.

You are given an m x n grid representing a building floor plan. Each cell contains one of the following values: - -1 for a wall or blocked cell - 0 for a gate - 2147483647 for an empty room Fill every empty room with the distance to its nearest gate, where distance is the minimum number of moves using only up, down, left, or right. Walls cannot be crossed. If an empty room cannot reach any gate, leave it as 2147483647. Return the modified grid.

Constraints

  • 0 <= m, n <= 250
  • Each cell is one of: -1, 0, or 2147483647
  • Movement is allowed only in 4 directions: up, down, left, right

Examples

Input: ([[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]],)

Expected Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Explanation: Distances are filled from both gates simultaneously. Each room gets the shortest path length to the nearest gate.

Input: ([[2147483647,-1,0],[2147483647,-1,2147483647],[2147483647,-1,2147483647]],)

Expected Output: [[2147483647,-1,0],[2147483647,-1,1],[2147483647,-1,2]]

Explanation: The middle column of walls blocks the left column completely, so those rooms remain 2147483647.

Hints

  1. Instead of running a search from every empty room, think about starting from every gate at the same time.
  2. A breadth-first search guarantees that the first time you reach a room, you found its shortest distance.

Loading coding console...