How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Snowflake.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Snowflake during technical interviews.

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.

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

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

Explanation: There are no bathrooms anywhere, so the single desk cannot reach any 'B' and returns -1. Every other cell is non-desk and also returns -1.

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

Expected Output: [[-1]]

Explanation: A 1x1 grid with only a bathroom: there are no desks, so the only cell is the -1 placeholder.

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

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

Explanation: Both desks sit two cells away from the central bathroom along the single row, so each desk reports distance 2; the empty and bathroom cells are -1.

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

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

Explanation: With the only bathroom in the top-left corner, each desk's distance equals its Manhattan distance to (0,0): the BFS produces an increasing diagonal pattern (max 4 at the far corner). The bathroom corner is the -1 placeholder.

Hints

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).
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.
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.

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.