DoorDash OA Interview Question: Assigning Multiple Orders to a Dasher

Assigning Multiple Orders to a Dasher

DoorDash optimizes Dasher efficiency by assigning multiple orders from nearby restaurants to the same Dasher. This is called order stacking. Given a city map consisting of restaurants that have orders ready to be picked up at a specified time, determine the maximum number of orders that can be stacked/assigned to a single Dasher.

Cell i, j of city represents a restaurant, and city[i][j] represents the time at which an order is ready to be picked up from the restaurant.

An order can be assigned to the same Dasher if:

• The next restaurant is directly adjacent to the previous restaurant where an order was picked up.
• The pickup time for the next order is after the pickup time of the last order that was picked up.

Example 1:

Provided:

city = [[9, 9, 4],
    [6, 6, 8],
    [2, 1, 1]
]

Return:

maximumStackedOrders = 4

This problem is a longest increasing path problem on a grid. Each restaurant cell is a node, and a Dasher can move only to an adjacent cell with a strictly larger pickup time. The standard solution is DFS with memoization, or equivalently dynamic programming on the grid, to compute the longest valid chain starting from each cell and take the maximum over all cells. In the sample, the best chain length is 4.