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 easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at DoorDash.

What role is this question designed for?

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

Compute Nearest Destination Distances | DoorDash Coding Question

Compute Nearest Destination Distances

Company: DoorDash

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

You are given an `m x n` grid representing a city map. Each cell contains one of the following characters: - `D`: a destination - `X`: an obstacle - `.`: an open cell For every cell in the grid, compute the length of the shortest path from that cell to the nearest destination. Movement is allowed only in the four cardinal directions: up, down, left, and right. Obstacle cells have a special rule: - An `X` cell cannot be used as an intermediate cell in a path. - However, you still must output a shortest distance value for every `X` cell as if the path starts from that obstacle cell and then moves to adjacent non-obstacle cells. If a cell cannot reach any destination, output `-1` for that cell. Return an `m x n` matrix of integers where each value is the shortest distance from the corresponding grid cell to its nearest destination. Example: Input: ```text [ ['.', '.', 'D'], ['X', '.', '.'], ['.', 'X', '.'] ] ``` Output: ```text [ [2, 1, 0], [3, 2, 1], [4, 3, 2] ] ```

Quick Answer: This question evaluates graph and grid traversal concepts, specifically multi-source shortest-path computation on a grid and handling special-cell constraints such as obstacles that cannot be used as intermediate steps.

You are given a rectangular city grid where each cell contains one of three characters: 'D' for a destination, 'X' for an obstacle, and '.' for an open cell. For every cell, compute the length of the shortest path from that cell to the nearest destination. Rules: - You may move only up, down, left, or right. - A path starting from a non-obstacle cell may move only through non-obstacle cells. - An 'X' cell cannot be used as an intermediate cell in any path. - However, you must still output a distance for every 'X' cell: treat the path as starting on that obstacle cell, then allow it to move to an adjacent non-'X' cell as its first step, and continue normally. - The distance from a destination cell to itself is 0. - If no destination is reachable, output -1 for that cell. Return a matrix of the same size where each entry is the shortest distance to the nearest destination under these rules.

Constraints

0 <= m, n <= 500
grid[i][j] is one of 'D', 'X', or '.'
All rows have the same length
An O(m * n) solution is expected

Examples

Input: ([['.', '.', 'D'], ['X', '.', '.'], ['.', 'X', '.']],)

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

Explanation: Normal cells use BFS without passing through obstacles. Cell (2,0) cannot reach any destination because both possible directions are blocked by 'X'. Each 'X' cell gets 1 plus the best reachable neighboring non-'X' distance.

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

Expected Output: [[0]]

Explanation: A destination is already at distance 0 from itself.

Input: ([['.', 'X'], ['X', '.']],)

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

Explanation: There is no destination anywhere in the grid, so every cell is unreachable.

Input: ([['D', 'X', '.']],)

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

Explanation: The obstacle cell can step directly to the destination in 1 move. The open cell on the far right cannot reach the destination because it would have to pass through the obstacle.

Input: ([['.', '.', 'X', 'D'], ['.', 'X', '.', '.'], ['D', '.', '.', 'X'], ['.', 'X', '.', '.']],)

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

Explanation: Using multi-source BFS from both destinations gives shortest distances for all non-'X' cells. Each obstacle cell then takes 1 plus the minimum reachable distance of its adjacent non-obstacle neighbors.

Input: ([],)

Expected Output: []

Explanation: An empty grid produces an empty result.

Hints

If several destinations exist, think about starting a BFS from all destination cells at the same time.
Because 'X' cells cannot be used as intermediate cells, compute distances for normal cells first, then derive each obstacle cell's answer from its adjacent non-obstacle cells.

Quick Overview

This question evaluates graph and grid traversal concepts, specifically multi-source shortest-path computation on a grid and handling special-cell constraints such as obstacles that cannot be used as intermediate steps.