DoorDash Backend Engineer Interview Questions

To ensure timely deliveries, DoorDash requires a job scheduler capable of scheduling deliveries at specific times and managing overlaps. The service should allow adding and querying scheduled deliveries.
Class Signature: class JobScheduler:
- def __init__(self): - Initializes the scheduler.
- def add_job(self, start_time: int, end_time: int) -> bool: - Attempts to add a job and returns true if successful; false if it overlaps with an existing job.
- def get_jobs(self) -> List[Tuple[int, int]]: - Returns a list of all scheduled jobs.Example 1:
Input: scheduler = JobScheduler()
scheduler.add_job(1, 2)
Output: True
scheduler.add_job(2, 3)
Output: True
scheduler.add_job(1, 2)
Output: False Constraints:
- 1 <= start_time < end_time <= 10^9
- 0 <= total_jobs <= 10^4

DoorDash requires a rate limiter to control API access from clients, preventing abuse and ensuring fair usage. The rate limiter should allow a maximum requests_per_second from each client, while providing methods to log requests and check if a request is allowed.
Class Signature: class RateLimiter:
- def __init__(self, requests_per_second: int): - Initializes the rate limiter with a limit on requests per second.
- def allow_request(self, client_id: int, timestamp: int) -> bool: - Returns true if the request is allowed, false otherwise.
- def log_request(self, client_id: int, timestamp: int) -> None: - Logs a request for the client at the given timestamp.Example 1:
Input: rate_limiter = RateLimiter(2)
rate_limiter.allow_request(1, 1)
Output: True
rate_limiter.allow_request(1, 2)
Output: True
rate_limiter.allow_request(1, 3)
Output: False Constraints:
- 1 <= requests_per_second <= 100
- 1 <= client_id <= 10^6
- 1 <= timestamp <= 10^9

DoorDash needs to determine the most popular restaurants within a geographical area. To accomplish this, a graph traversal algorithm can be applied to search for the connected components in the restaurant delivery network.
Using n restaurants where each restaurant is a node connected by edges (deliverable routes), write a function that returns the number of connected components in the graph representing the available restaurants.
Function Signature: def count_connected_components(n: int, edges: List[Tuple[int, int]]) -> int: - Returns the number of connected components in the given graph.Example 1:
Input: n = 5, edges = [(0, 1), (1, 2), (3, 4)]
Output: 2
Explanation: There are two connected components: {0, 1, 2} and {3, 4}. Constraints:
- 1 <= n <= 10^4
- 0 <= len(edges) <= n*(n-1)/2

In order to maximize delivery efficiency, DoorDash needs to determine the optimal delivery window for a set of orders. By using a sliding window technique, we can minimize the time taken to deliver all orders without exceeding a certain capacity.
Given an array of orders where each order contains the pickup_time and delivery_time, return the maximum number of orders that can be delivered within a given time_limit.
Function Signature: def max_orders(orders: List[Tuple[int, int]], time_limit: int) -> int: - Returns the maximum number of orders that can be fulfilled within the given time limit.Example 1:
Input: orders = [(1, 4), (2, 6), (3, 8), (5, 10)], time_limit = 8
Output: 3
Explanation: Orders (1, 4), (2, 6), and (3, 8) can be delivered within the time limit. Constraints:
- 1 <= len(orders) <= 10^5
- 0 <= pickup_time < delivery_time <= 10^6
- 0 <= time_limit <= 10^6