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
- Movement is 4-directional (no diagonals) and cannot pass through
'X'. - A location that is itself
'D'has distance0. - A location that is itself
'X', out of bounds, or cannot reach any'D'returns-1. - 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.
Run your code with Ctrl+Enter to see results.