Compute nearest dashmart distances for queries
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an m x n grid where each cell is one of: -1 for a wall (impassable), 0 for a dashmart (a store), and INF = 2^31 - 1 for an empty room. Movement is allowed 4-directionally with cost 1 per step. You are also given an array queries of k coordinates (r, c), each guaranteed to be an empty room. For each query, return the length of the shortest path to any dashmart; return -1 if no dashmart is reachable or if the grid contains no dashmarts. Implement a function nearestDistances(grid, queries) that returns an array of k integers in the order of queries. Discuss and implement an approach that scales when k is large, and analyze its time and space complexity. Include how you would handle edge cases such as: duplicate queries, rooms completely blocked by walls, empty list of queries, or grids with zero dashmarts.
Quick Answer: This question evaluates a candidate's understanding of graph traversal and shortest-path computation on grids, spatial reasoning about obstacles and sources, and the ability to analyze algorithmic scalability and complexity when answering many queries.
Given a grid with -1 walls, 0 dashmarts, and INF empty rooms, return the shortest 4-directional distance from each query cell to any dashmart. Return -1 if no dashmart is reachable.
Constraints
- Movement is 4-directional
- Queries are answered in input order
Examples
Input: ([[2147483647, -1, 0, 2147483647], [2147483647, 2147483647, 2147483647, -1], [2147483647, -1, 2147483647, -1], [0, -1, 2147483647, 2147483647]], [[0, 0], [1, 1], [3, 3]])
Expected Output: [3, 2, 4]
Input: ([[-1, 2147483647], [2147483647, 2147483647]], [[0, 1], [1, 1]])
Expected Output: [-1, -1]
Hints
- Run one BFS from all dashmarts at once.
- Do not run a BFS per query when k is large.