DashMart Grid Routing And Spatial Matching
Asked of: Software Engineer
Last updated

What's being tested
These problems test grid shortest paths, multi-source BFS, time-aware graph traversal, and nearest-neighbor matching under deterministic tie-breaking. Interviewers want to see whether you can model DashMart/courier/customer locations as graphs or spatial points, pick the right data structure, and justify complexity.
Patterns & templates
-
Single-source BFS on an unweighted grid —
O(R*C)time,O(R*C)space; usedeque,visited, and 4-direction neighbors. -
Multi-source BFS for nearest
DashMartdistances — enqueue all stores at distance0; first visit gives shortest distance to any source. -
Dijkstra’s algorithm for weighted or time-dependent movement — use
heapq; complexityO((V+E) log V); BFS is wrong once edge costs vary. -
Time-grid constraints — store earliest arrival per cell; when entering cell
(r,c), compute wait time before pushing updated arrival. -
Spatial nearest neighbor — brute force is
O(C*K); for many dynamic queries, discuss k-d tree, grid bucketing, or geohash-style indexing. -
Deterministic tie-breaking — compare
(distance, id)or(distance, dashmart_id)tuples so equal-distance results are stable and testable. -
Sparse grid representation — use
setfor obstacles anddictfor distances when coordinates are large but occupied cells are few.
Common pitfalls
Pitfall: Using DFS for shortest path on an unweighted grid; DFS may find a path, but not the minimum path length.
Pitfall: Running BFS separately from every query when all queries ask distance to the nearest source; reverse it with multi-source BFS.
Pitfall: Ignoring tie rules; equal distances must usually be broken by stable
courier/storeid, not traversal order.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
- Find Each Cell's Nearest SourceDoorDash · Software Engineer · Onsite · medium
- Select the best dasher for an orderDoorDash · Software Engineer · Take-home Project · medium
- Design dasher-to-order assignment algorithmDoorDash · Software Engineer · Onsite · Medium
- Compute nearest dashmart distances for queriesDoorDash · Software Engineer · Technical Screen · Medium
- Compute delivery times on a gridDoorDash · Software Engineer · Technical Screen · Medium
- Find the nearest city sharing axisDoorDash · Software Engineer · Technical Screen · Medium
- Find nearest courier for each customerDoorDash · Software Engineer · Onsite · Medium
- Compute nearest courier for each customerDoorDash · Software Engineer · Onsite · Medium
- Solve string match and DashMart BFSDoorDash · Software Engineer · Technical Screen · Medium
- Compute earliest arrival in time-gridDoorDash · Software Engineer · Technical Screen · Medium
- Solve BFS grid delivery routingDoorDash · Software Engineer · Technical Screen · Medium
- Identify members lacking specialty coverageDoorDash · Software Engineer · Onsite · medium
Related concepts
- Graph Search, Pathfinding, And ConnectivityCoding & Algorithms
- BFS, DFS, Graph, And Grid TraversalCoding & Algorithms
- DFS/BFS Tree, Graph, And Grid TraversalCoding & Algorithms
- Graph, Grid, BFS/DFS, And Union-FindCoding & Algorithms
- Graph Search, State Space, And Path OptimizationCoding & Algorithms
- Grid, Matrix And Spatial AlgorithmsCoding & Algorithms