Doordash Interview Question
Summary
I was presented with a challenging algorithmic problem during my Doordash interview that involved navigating a city grid to calculate distances to the nearest DashMart and then identifying the DashMart serving the most customers.
Full Experience
During my recent interview with Doordash, I encountered an interesting algorithmic challenge. The main problem revolved around a city map represented as a grid, where I had to determine the shortest distance from various given locations to their closest DashMart. This required careful consideration of open and blocked roads, suggesting a graph traversal algorithm like Breadth-First Search (BFS). A follow-up then extended this by introducing customers and asking to find the DashMart that would serve the maximum number of customers based on proximity. This entire scenario tested my ability to model real-world problems using data structures and algorithms.
Interview Questions (2)
A DashMart is a warehouse run by Doordash that houses items found in convenience stores, grocery stores, and restuarants. We have a city with open roads, blocked-off roads, and DashMarts.
City Planners want you to identify how far a location is from its closest DashMart. You can only travel over open roads (up, down, left, right). Locations are given in [row, col] format.
Example 1
[ ['X', ' ', ' ', 'D', ' ', ' ', 'X', ' ', 'X'],
['X', ' ', 'X', 'X', ' ', ' ', ' ', ' ', 'X'],
[' ', ' ', ' ', 'D', 'X', 'X', ' ', 'X', ' '],
[' ', ' ', ' ', 'D', 'X', 'X', ' ', 'X', ' '],
[' ', ' ', ' ', ' ', ' ', 'X', ' ', ' ', 'X'],
[' ', ' ', ' ', ' ', 'X', ' ', ' ', 'X', 'X'] ]
Such that:
' 'represents an open road that you can travel over in any direction (up, down, left, or right)'X'represents a blocked road that you cannot travel through.'D'represents a DashMart.
locations = [[200, 200], [1, 4], [0, 3], [5, 8], [1, 8], [5, 5]]
Return a list of the distances from a given point to its closest DashMart.
Expected Answer: In this case, you should return [-1, 2, 0, -1, 6, 9]
Find the DashMart that can serve the maximum number of customers. Customers will be served by their closest DashMart. Customers are represented by 'C' in the city plan.