Quick Overview

This question evaluates a candidate's ability to reason about shortest-paths and reachability on grid graphs, testing skills in graph traversal, distance computation, and spatial problem modeling within the Coding & Algorithms domain.

Compute nearest bathroom distance for each desk

Company: Snowflake

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given an `m x n` grid of characters containing only: - `'B'` = bathroom - `'D'` = desk - `'_'` = empty cell From any cell you may move one step up/down/left/right (no diagonals). The distance between two cells is the length of the shortest such path. For every desk cell `'D'`, compute the distance to its nearest bathroom `'B'`. Return an `m x n` integer matrix where: - for a desk cell, the value is the nearest-bathroom distance, - for non-desk cells, you may return `-1` (or any clearly documented placeholder). If a desk cannot reach any bathroom, return `-1` for that desk.

Quick Answer: This question evaluates a candidate's ability to reason about shortest-paths and reachability on grid graphs, testing skills in graph traversal, distance computation, and spatial problem modeling within the Coding & Algorithms domain.

You are given an `m x n` grid of characters containing only: - `'B'` = bathroom - `'D'` = desk - `'_'` = empty cell From any cell you may move one step up/down/left/right (no diagonals). The distance between two cells is the length of the shortest such path. For every desk cell `'D'`, compute the distance to its nearest bathroom `'B'`. Return an `m x n` integer matrix where: - for a desk cell, the value is the nearest-bathroom distance, - for non-desk cells, return `-1` as a placeholder. If a desk cannot reach any bathroom, return `-1` for that desk as well. Function signature: `solution(grid: List[List[str]]) -> List[List[int]]`.

Constraints

  • 1 <= m, n <= 1000
  • grid[i][j] is one of 'B', 'D', '_'
  • The grid may contain zero bathrooms, in which case every desk returns -1.
  • Movement is 4-directional (up/down/left/right); no diagonal moves.

Examples

Input: ([['B', '_', 'D'], ['_', '_', '_'], ['D', '_', 'B']],)

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

Explanation: The top-right desk (0,2) is distance 2 from the top-left bathroom (0,0) going down-then-... actually its nearest bathroom is (2,2): path (0,2)->(1,2)->(2,2) = 2. The bottom-left desk (2,0) is distance 2 from (0,0): (2,0)->(1,0)->(0,0) = 2. Bathroom and empty cells become the -1 placeholder.

Input: ([['D', 'B']],)

Expected Output: [[1, -1]]

Explanation: The desk at (0,0) is adjacent to the bathroom at (0,1), so its distance is 1. The bathroom cell itself is a non-desk cell and gets -1.

Hints

  1. Instead of running a separate BFS from each desk, run a single multi-source BFS that starts from ALL bathroom cells at once. This computes the nearest bathroom distance for every cell in O(m*n).
  2. Seed a queue with all 'B' cells at distance 0, then relax neighbors level by level. Because every edge has weight 1, the first time you reach a cell is its shortest distance.
  3. Empty cells '_' are traversable and must be expanded during BFS, but their final value in the result is the -1 placeholder. Only cells originally marked 'D' get a real distance; any desk left at infinity is unreachable and stays -1.

Loading coding console...