← Back
00:00

Nearest DashMart

DoorDash interview questions · Medium · Coding round · 7 tests

You're given a city grid and a list of Dasher locations. Each cell is one of:

  • 'D' - a DashMart (a source you can reach)
  • 'X' - a blocked cell (cannot be entered or stood on)
  • ' ' - open road

For each given location, return the shortest grid distance (up / down / left / right moves only) to the nearest DashMart, or -1 if it's unreachable (including if the location itself is a blocked cell).

Interface

nearestDashMart(
  grid: string[][],
  locations: [number, number][], // [row, col]
): number[]

Requirements

  1. Movement is 4-directional (no diagonals) and cannot pass through 'X'.
  2. A location that is itself 'D' has distance 0.
  3. A location that is itself 'X', out of bounds, or cannot reach any 'D' returns -1.
  4. Must scale to many locations on a large grid. Running a fresh BFS per location is the obvious first approach and will time out - there's a performance test with thousands of queries.
Idle