DoorDash VO: Nearest DashMart Distance

oavoservice Original Review: For problems asking for "shortest distance from multiple sources," immediately think of Multi-source BFS.

Problem (Restated)

Given a 2D grid with the following characters:

• D: DashMart (Target)
• O: Open path (Traversable)
• X: Obstacle (Non-traversable)

Given a list of query coordinates locations, for each location, return the minimum number of steps (moving up, down, left, right) to the nearest DashMart.

• If out of bounds, return -1.
• If no DashMart is reachable, return -1.
• If the current location is D, return 0.

Key Idea: Multi-source BFS

Running a separate BFS for each query location would be too slow.

Better approach:

• Add all D locations to the queue simultaneously (distance 0).
• Run BFS to propagate and compute the shortest distance dist[r][c] for every cell to the nearest D.
• Then, answer queries in O(1) by looking up the precomputed table.

Complexity

• Preprocessing BFS: O(R * C)
• Per Query: O(1)

Python Reference Implementation

from collections import deque


def build_distance_to_dashmart(grid):
    if not grid or not grid[0]:
        return []

    R, C = len(grid), len(grid[0])
    INF = 10**15
    dist = [[INF] * C for _ in range(R)]
    q = deque()

    # Multi-source: Add all 'D's to queue
    for r in range(R):
        for c in range(C):
            if grid[r][c] == 'D':
                dist[r][c] = 0
                q.append((r, c))

    # BFS
    dirs = [(1,0), (-1,0), (0,1), (0,-1)]
    while q:
        r, c = q.popleft()
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != 'X':
                if dist[nr][nc] > dist[r][c] + 1:
                    dist[nr][nc] = dist[r][c] + 1
                    q.append((nr, nc))

    return dist


def query_locations(grid, locations):
    dist = build_distance_to_dashmart(grid)
    if not dist:
        return [-1] * len(locations)

    R, C = len(grid), len(grid[0])
    ans = []
    for r, c in locations:
        if not (0 <= r < R and 0 <= c < C):
            ans.append(-1)
            continue
        if grid[r][c] == 'X':
            ans.append(-1)
            continue
        d = dist[r][c]
        ans.append(-1 if d >= 10**15 else d)
    return ans

Common Pitfalls

• Grid might have no D: All reachable distances should be -1.
• Location on an obstacle: Should return -1.
• Query coordinates out of bounds: Return -1.

DoorDash VOs often replace BFS terminology with business language (DashMart/Restaurant), but the core is still Shortest Path. oavoservice trains you to quickly map business descriptions to "Multi-source BFS".

Need real interview questions? Contact WeChat Coding0201 immediately to get real questions.