DoorDash·Software Engineer·Technical Phone Screen
- Given an m x n character grid with dashmarts ('D'), impassable cells ('X'), and open cells, write a function that takes a list of query locations and returns the shortest distance from each location to the nearest dashmart. Return -1 if the cell is impassable or no dashmart is reachable.
- Extend the previous grid problem: each dashmart has a base busy score, and its effective busy score for a query at distance d is max(0, base - alpha * d). For each query, find the reachable dashmart that maximizes this effective busy score, breaking ties by shortest distance, then by row, then by column. Return the dashmart coordinates and its effective busy value.
“Multi-source BFS from all dashmarts simultaneously, precompute distances, then answer queries in O(1).”