DashMart Grid Routing And Spatial Matching

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; use deque, visited, and 4-direction neighbors.

• Multi-source BFS for nearest DashMart distances — enqueue all stores at distance 0; first visit gives shortest distance to any source.

• Dijkstra’s algorithm for weighted or time-dependent movement — use heapq; complexity O((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 set for obstacles and dict for 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/store id, not traversal order.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.