Compute nearest dashmart and busiest assignments
DoorDashSoftware Engineer · Technical ScreenLast updated
Compute nearest dashmart and busiest assignments evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
You are given an m x n grid of characters where 'D' marks a dashmart, 'X' marks an impassable cell, and ' ' (space) marks a passable cell. Movement is allowed only in four directions (up, down, left, right) and cannot go outside the grid or into 'X'. You are also given a list of K query locations (row, col). Part A: For each query location, return the length (in steps) of the shortest path to any dashmart. If the starting cell is a dashmart, the distance is 0. If the starting cell is 'X' or no path to any dashmart exists, return -1. Implement a function nearestDistances(grid, queries) that handles multiple test cases and is bug-free. Part B (follow-up): Each dashmart at coordinates (r, c) has a non-negative base busy score B[r][c] (provided for all 'D' cells) and you are given an integer alpha ≥ 0. Define the effective busy of a dashmart for a location at grid distance d as max(0, B[r][c] - alpha * d). For each query location, among all reachable dashmarts, return the dashmart that maximizes effective busy; break ties by smaller distance d, then by smaller row, then by smaller column. If no dashmart is reachable, return (-1, - 1). Also return the chosen dashmart’s effective busy value for that location.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.