Doordash onsite coding interview: DashMart shortest distance and follow-up

Problem Statement You are given a city represented as a 2D grid containing the following cell types: * ' ': Open road. Travel is allowed in four directions (up, down, left, right). * 'X': Bloc

Problem Statement You are given a city represented as a 2D grid containing the following cell types: * ' ': Open road. Travel is allowed in four directions (up, down, left, right). * 'X': Blocked road. Cannot be traversed or used as a starting point. * 'D': DashMart.

Task 1: Distance Calculation Given a list of locations in [row, col] format, calculate the shortest distance from each location to its nearest DashMart. * If the location is a DashMart, the distance is 0. * If the location is an obstacle ('X'), out of bounds, or cannot reach any DashMart,

return -1.

Example Grid:

text [['X', ' ', ' ', 'D', ' ', ' ', 'X', ' ', 'X'], ['X', ' ', 'X', 'X', ' ', ' ', ' ', ' ', 'X'], [' ', ' ', ' ', 'D', 'X', 'X', ' ', 'X', ' '], [' ', ' ', ' ', 'D', 'X', 'X', ' ', 'X', ' '], [' ', ' ', ' ', ' ', ' ', 'X', ' ', ' ', 'X'], [' ', ' ', ' ', ' ', 'X', ' ', ' ', 'X', 'X']]

Input Locations: [[200, 200], [1, 4], [0, 3], [5, 8], [1, 8], [5, 5]] Output: [-1, 2, 0, -1, 6, 9] Logic: 1. [200, 200]: Out of bounds -> -1 2. [1, 4]: 2 steps to DashMart at [0, 3] -> 2 3. [0, 3]: Is a DashMart -> 0 4. [5, 8]: Is blocked road 'X' -> -1 5. [1, 8]: 6 steps to DashMart at [0, 3] -> 6 6. [5, 5]: 9 steps to DashMart at [3, 3] -> 9

**Task 2:

Follow-up (Maximum Customer Coverage)** The city grid is updated to include Customers represented by 'C'. * Each Customer is served by the DashMart closest to them (shortest path via open roads). * If a Customer is equidistant to multiple DashMarts, tie-breaking logic applies (e.g., choose any). * Identify and return the DashMart that serves the highest total number of Customers.