DoorDash Interview Questions

Background: DoorDash relies on caching to enhance the responsiveness of its application, especially for frequently accessed data such as restaurant menus and user order histories. An efficient caching mechanism like LRU (Least Recently Used) helps optimize resource usage and increase performance.Problem statement: Design and implement a class LRUCache that supports the following operations: get(key) and put(key, value). The get method retrieves the value associated with the key if it exists, and also marks that key as recently used. The put method stores or updates the value associated with a specific key. If the cache exceeds its capacity, it should evict the least recently used item.Function/class signature:

• def get(self, key: int) -> int:


• def put(self, key: int, value: int) -> None:

Example 1:

• Input: cache = LRUCache(2); cache.put(1, 1); cache.put(2, 2); cache.get(1);


• Output: 1 (Explanation: returns 1 as it is the value for key 1)

Example 2:

• Input: cache.put(3, 3) (evicts key 2); cache.get(2);


• Output: -1 (Explanation: returns -1 since key 2 was evicted)

Constraints:

• 1 <= capacity <= 3000


• 0 <= key <= 10^4


• 0 <= value <= 10^4


• get and put operations will be called at most 3 * 10^4 times in total.

Background: In a real-time delivery service like DoorDash, understanding user preferences or delivery timeframes involves stream analysis, such as tracking customer ratings for their orders. This requires a mechanism to efficiently calculate the median of ratings as they come in over time.
Problem statement: Implement a class MedianFinder that supports the addition of numbers and can return the median of all added numbers efficiently. Ensure that the implementation uses two heaps to keep track of the lower half and the upper half of the numbers.
Function/class signature:

• def addNum(self, num: int) -> None:


• def findMedian(self) -> float:

Example 1:

• Input:

medianFinder = MedianFinder()
medianFinder.addNum(1)
medianFinder.addNum(2)
medianFinder.findMedian()

• Output:

1.5

• Explanation: The numbers are [1,2], and the median is (1 + 2) / 2 = 1.5.

Example 2:

• Input:

medianFinder.addNum(3)
medianFinder.findMedian()

• Output:

2.0

• Explanation: The numbers are [1, 2, 3], and the median is 2.

Constraints:

• All input numbers are integers.


• There will be at most 10000 calls to addNum and findMedian.


• The input stream will be non-empty at the time of calls to findMedian.

Background: DoorDash relies on efficient routing to ensure that food is delivered quickly and accurately. A well-designed routing algorithm can significantly reduce delivery times and improve customer satisfaction.
Problem statement: You need to implement a function that takes a list of delivery locations and computes the optimal route for Dashers, minimizing the total distance traveled. The function should use a simple heuristic to prioritize nearby deliveries first. Return the ordered list of delivery locations.
Function/class signature:

• def optimal_dasher_route(locations: List[Tuple[float, float]]) -> List[Tuple[float, float]]:

Example 1: Input: [(1.0, 1.0), (2.0, 2.0), (3.0, 1.5)] Output: [(1.0, 1.0), (2.0, 2.0), (3.0, 1.5)] Explanation: The optimal path starts from the first location, goes to the second, and finally to the third.
Example 2: Input: [(5.0, 5.0), (1.0, 1.0), (2.0, 2.0)] Output: [(1.0, 1.0), (2.0, 2.0), (5.0, 5.0)] Explanation: The optimal path starts from the closest location at (1.0, 1.0).
Constraints:

• 1 <= len(locations) <= 100


• Locations are given in (latitude, longitude) format


• Coordinate values will be between -10^[6] and 10^[6]

Background: DoorDash needs an efficient way to calculate driver payouts to ensure fair compensation for their services. This involves combining various bonus multipliers based on events like peak hours and completed deliveries.
Problem statement: You need to design an API that computes the total payout for a driver based on their events. Consider events as a list of tuples where each tuple contains a timestamp and a payout amount. Implement concurrency to handle situations where multiple bonus multipliers may apply.
Function/class signature:

• def compute_driver_payout(events: List[Tuple[datetime, float]], bonus_multipliers: List[Tuple[str, float]]) -> float:

Example 1:

• Input: events = [('2023-05-01T08:00:00', 10.0), ('2023-05-01T09:00:00', 5.0)], bonus_multipliers = [('peak_hour', 2.0), ('completing_5_deliveries', 1.5)]


• Output: 37.5


• Explanation: The driver earned $10 during a peak hour and $5 outside of it, applying multipliers results in $10*2 + $5*1.5 = $37.5.

Example 2:

• Input: events = [('2023-05-01T10:00:00', 20.0), ('2023-05-01T11:00:00', 15.0)], bonus_multipliers = [('non_peak', 1.0), ('bonus_for_10_deliveries', 2.0)]


• Output: 70.0


• Explanation: Earnings are $20 + $15 = $35; applying multipliers yields $35*2 = $70.

Constraints:

• 0 <= len(events) <= 100


• 0 <= len(bonus_multipliers) <= 10


• All payouts values are positive floats.


• Events are sorted by timestamp.

Note: Handle concurrency issues when multiple threads may call this API to calculate payouts simultaneously.

Background: DoorDash needs to compute driver payouts based on various factors such as delivery events and concurrency-based bonus multipliers. This requires a reliable API that can efficiently handle and process these events to calculate accurate payouts.
Problem statement: You are tasked with designing an API to compute driver payouts. Each driver can have multiple deliveries, and we need to calculate their total payout based on delivery events. Each event will have a base payout and may include bonuses based on concurrency rules. Implement the method compute_payout(driver_id: int, events: List[Tuple[int, float, int]]) -> float, which takes the driver's ID and a list of events where each event is a tuple containing:

• event_time (int): The timestamp of the event in seconds.


• base_payout (float): The base payout for the delivery.


• bonus_multiplier (int): A bonus multiplier applied if certain conditions are met (e.g., if two deliveries are made within a specific time frame).

Function/class signature:

• def compute_payout(driver_id: int, events: List[Tuple[int, float, int]]) -> float:

Example 1:

• Input: driver_id = 1, events = [(1, 10.0, 1), (2, 15.0, 2)]


• Output: 35.0


• Explanation: The driver made two deliveries within the time frame eligible for bonuses, resulting in a total payout of $10 + $15 + (1 * 10) + (1 * 15) = $35.0.

Example 2:

• Input: driver_id = 2, events = [(1, 5.0, 1), (10, 8.0, 2)]


• Output: 13.0


• Explanation: The driver made two deliveries without any bonus multiplier applied due to not meeting the concurrency condition.

Constraints:

• 1 ≤ driver_id ≤ 10000


• 0 ≤ event_time ≤ 10^6


• 0 ≤ base_payout ≤ 1000


• 1 ≤ bonus_multiplier ≤ 5


• The length of events can be at most 1000.

Background: DoorDash needs to efficiently track the number of unique deliveries made by different drivers over a certain period to analyze performance metrics and optimize routing. This problem relates to the data management aspect of delivery logistics.
Problem statement: Given a list of driver IDs and the corresponding delivery timestamps, implement a function to count the number of unique deliveries for each driver. You must ensure that each driver's unique deliveries are counted based on distinct timestamps. Assume the timestamps are in the format YYYY-MM-DD HH:MM:SS and each driver can have multiple deliveries at the same timestamp.
Function/class signature:

• def count_unique_deliveries(drivers: List[str], timestamps: List[str]) -> Dict[str, int]:

Example 1:

• Input: drivers = ['A', 'A', 'B', 'A', 'B'], timestamps = ['2023-10-01 14:00:00', '2023-10-01 14:00:00', '2023-10-01 14:05:00', '2023-10-01 14:10:00', '2023-10-01 14:05:00']


• Output: {'A': 3, 'B': 1}


• Explanation: Driver A has delivered at three unique times, while driver B has only one unique time.

Example 2:

• Input: drivers = ['C', 'C', 'C', 'C'], timestamps = ['2023-10-01 14:00:00', '2023-10-01 15:00:00', '2023-10-01 14:00:00', '2023-10-01 15:00:00']


• Output: {'C': 2}


• Explanation: Driver C has two unique delivery times.

Constraints:

• 1 <= len(drivers) <= 10^4


• 1 <= len(timestamps) <= 10^4


• Timestamps are unique across the drivers but may repeat for the same driver.

DoorDash needs to effectively match drivers to delivery requests based on location and time constraints.
Problem Statement: Given a grid of n x m representing a map where 1 represents an order location and 0 represents an empty space, implement a function maxDrivers(orders: List[List[int]], start: Tuple[int, int]) -> int that returns the maximum number of deliveries that can be assigned to drivers originating from start position.Example 1:
Input: orders = [[0,0,0],[0,1,0],[0,0,0]], start = (1, 1)
Output: 1
Explanation: The only reachable order is at (1,1).Constraints:

• 1 <= orders.length, orders[i].length <= 20


• 0 <= start[0] < orders.length


• 0 <= start[1] < orders[i].length

DoorDash needs a robust method to track orders and ensure timely deliveries based on real-time traffic data.
Problem Statement: Given an array of integers representing the estimated delivery times for incoming orders, implement a function maxDeliveryTime(orders: List[int], k: int) -> int that returns the maximum possible delivery time over any sub-array of size k, where k is the number of concurrent deliveries.Example 1:
Input: orders = [2, 1, 3, 5, 6, 4], k = 3
Output: 14
Explanation: The best sub-array is [5, 6, 4], which yields a delivery time of 5 + 6 + 4 = 15.Constraints:

• 1 <= orders.length <= 100000


• 1 <= orders[i] <= 1000


• 1 <= k <= orders.length

1. Background: As DoorDash scales and the number of drivers increases, calculating payouts accurately and efficiently is imperative for maintaining driver satisfaction and operational effectiveness. This system must account for various factors such as distance traveled, time taken, and any bonus multipliers based on peak hours or promotional events.
2. Requirements:
1. Must calculate base payout based on distance and time.
2. Must incorporate bonus multipliers for peak hours and special events.
3. Must handle concurrent requests to ensure performance at scale.
4. Must return detailed breakdown of payout (base, bonus, total).
3. Class API:
- def calculate_base_payout(distance: float, time: float) -> float: Calculates base payout based on distance and time.
- def apply_bonus_multiplier(base: float, multiplier: float) -> float: Applies a bonus multiplier to the base payout.
- def compute_total_payout(distance: float, time: float, multiplier: float) -> dict: Calculates total payout and returns a breakdown.
4. Example 1: compute_total_payout(10.0, 30.0, 1.5) → Output: {'base': 15.0, 'bonus': 7.5, 'total': 22.5} → Explanation: Based on distance and time, base payout is $15. Applying a 1.5x bonus gives $7.5, totaling $22.5.
5. Constraints:
- Maximum distance: 100 miles
- Maximum time: 180 minutes
- Multiplier range: 1.0 to 3.0 (for peak times)

DoorDash needs to cache the most frequently accessed delivery routes to improve API response time.
Problem Statement: Implement an LRUCache class with the following methods:

• __init__(self, capacity: int): Initialize the LRU cache with positive size capacity.


• get(self, key: int) -> int: Return the value of the key if the key exists, otherwise return -1.


• put(self, key: int, value: int) -> None: Update the value of the key if the key exists, or add the key-value pair if the key does not exist. When the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item.

Example 1:
Input: cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)
Output: 1
Explanation: The cache contains 1 and 2, and the value for key 1 is 1.Constraints:

• 1 <= capacity <= 3000


• 0 <= key, value <= 10000