How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at DoorDash.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at DoorDash during technical interviews.

Compute courier pay and implement load balancing

Quick Overview

This problem evaluates skills in interval arithmetic and aggregation for time-based pay computation alongside routing and load-balancing knowledge covering round-robin and consistent hashing with virtual nodes, testing time-interval handling, rate mapping, hashing, and data-structure design for high-volume inputs.

Compute courier pay and implement load balancing

Company: DoorDash

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Problem 1: Compute courier (delivery driver) pay You are given a sequence of delivery-related events for a courier during a day. Your task is to compute the courier’s total pay. ### Inputs - A list of pay-rate intervals for the day (rates can change over time): - Each interval is `(start_minute, end_minute, rate_per_minute)` where `0 <= start < end <= 1440`. - Intervals do not overlap and together may or may not cover the whole day. - A list of delivery trips: - Each trip is `(pickup_minute, dropoff_minute, per_trip_bonus)`. - Trip time contributes time-based pay according to the rate schedule; bonus is added once per trip. ### Output Return the total pay for the courier for all trips combined. ### Notes / constraints - If a trip spans multiple rate intervals, split its time accordingly. - If a trip overlaps a time range with no defined rate interval, assume rate is `0` for that portion. - Minutes are integers; treat intervals as half-open: `[start_minute, end_minute)`. - Constraints (typical): up to `1e5` intervals and `1e5` trips. --- ## Problem 2: Implement request routing (Round Robin → Consistent Hashing) Design a small in-memory request router for a set of backend servers. ### Part A: Round Robin router Implement a router that supports: - `addServer(serverId)` - `removeServer(serverId)` - `route(requestId) -> serverId` Behavior: - `route()` should return servers in round-robin order over the *current* set of servers. - The implementation should be robust to adds/removals between calls. ### Part B: Consistent hashing router Modify/replace the round-robin approach with consistent hashing so that: - When a server is added/removed, only a small fraction of requests remap. - You may use virtual nodes. ### Notes / constraints - `serverId` is a string. - `requestId` is a string. - Aim for near-`O(log N)` routing time.

Quick Answer: This problem evaluates skills in interval arithmetic and aggregation for time-based pay computation alongside routing and load-balancing knowledge covering round-robin and consistent hashing with virtual nodes, testing time-interval handling, rate mapping, hashing, and data-structure design for high-volume inputs.

Part 1: Compute Courier Pay

You are given a day's pay-rate intervals and a list of delivery trips. Each trip earns minute-by-minute pay based on the active rate at each minute, plus its per-trip bonus once. Intervals are half-open [start_minute, end_minute). If a trip covers minutes with no defined rate interval, that portion pays 0. Return the courier's total pay for all trips.

Constraints

0 <= start_minute < end_minute <= 1440
0 <= pickup_minute <= dropoff_minute <= 1440
Rate intervals do not overlap, but they may leave gaps in the day
1 <= len(rate_intervals), len(trips) <= 100000 is possible, but the day length is fixed at 1440 minutes
rate_per_minute and per_trip_bonus are non-negative integers

Examples

Input: ([(0, 60, 2), (60, 120, 1)], [(30, 90, 5)])

Expected Output: 95

Explanation: From minute 30 to 60 the rate is 2 for 30 minutes, and from 60 to 90 the rate is 1 for 30 minutes. Total time pay is 60 + 30, plus bonus 5.

Input: ([(0, 100, 1), (200, 300, 2)], [(50, 250, 10), (260, 280, 0)])

Expected Output: 200

Explanation: First trip pays 50*1 + 100*0 + 50*2 + 10 = 160. Second trip pays 20*2 = 40. Combined total is 200.

Input: ([], [(10, 20, 3)])

Expected Output: 3

Explanation: No pay-rate intervals exist, so time-based pay is 0. Only the trip bonus is earned.

Input: ([(0, 1440, 4)], [])

Expected Output: 0

Explanation: There are no trips, so total pay is 0.

Hints

Because the day has only 1440 minutes, you can precompute the pay rate for every minute of the day.
After building per-minute rates, a prefix-sum array lets you answer each trip's time-based pay in O(1).

Part 2: Implement Request Routing with Round Robin

Build an in-memory round-robin router and process a sequence of operations. Active servers are kept in insertion order. Each route operation should return the next server in the current cycle and then advance the pointer. If a server is removed, it disappears from the cycle without resetting the round-robin state. Adding an already active server should do nothing, and removing a missing server should do nothing.

Constraints

1 <= len(operations) <= 200000
serverId and requestId are non-empty strings
Servers should be routed in the order they were added among currently active servers
Duplicate addServer operations are ignored
removeServer on a missing server is ignored

Examples

Input: ([('addServer', 'A'), ('addServer', 'B'), ('route', 'r1'), ('route', 'r2'), ('route', 'r3')],)

Expected Output: ['A', 'B', 'A']

Explanation: With servers A and B active, routing cycles A -> B -> A.

Input: ([('addServer', 'A'), ('addServer', 'B'), ('addServer', 'C'), ('route', 'x'), ('removeServer', 'B'), ('route', 'y'), ('route', 'z')],)

Expected Output: ['A', 'C', 'A']

Explanation: After routing to A, the next server would have been B. Removing B moves the cycle forward to C, then back to A.

Input: ([('route', 'r1'), ('addServer', 'X'), ('removeServer', 'X'), ('route', 'r2')],)

Expected Output: [None, None]

Explanation: There is no active server for either route call.

Input: ([('addServer', 'A'), ('addServer', 'A'), ('addServer', 'B'), ('route', 'p'), ('addServer', 'C'), ('removeServer', 'Z'), ('route', 'q'), ('route', 'r'), ('route', 's')],)

Expected Output: ['A', 'B', 'C', 'A']

Explanation: The second add of A is ignored, removing Z does nothing, and the cycle continues through A, B, C.

Hints

Think about keeping a pointer to the next server that should receive traffic.
A hash map plus a circular doubly linked list gives O(1) add, remove, and route.

Part 3: Implement Request Routing with Consistent Hashing

Build an in-memory consistent-hashing router and process a sequence of operations. Use virtual nodes for each server. The hash function is fixed for this problem: H(s) = sum((i + 1) * ord(s[i]) for i in range(len(s))). Each serverId creates virtual nodes with keys serverId + '#' + str(vnodeIndex) for vnodeIndex from 0 to virtual_nodes - 1. Put all virtual nodes on a ring sorted by (hash, serverId, vnodeIndex). To route a request, compute H(requestId), find the first virtual node whose tuple hash is at least that value, and return its serverId. If none exists, wrap around to the first virtual node. Adding an already active server should do nothing, and removing a missing server should do nothing.

Constraints

1 <= len(operations) <= 100000
1 <= virtual_nodes <= 1000
serverId and requestId are non-empty strings
Use the exact hash function and ring rule described in the statement so routing is deterministic
Duplicate addServer operations are ignored, and removeServer on a missing server is ignored

Examples

Input: ([('addServer', 'A'), ('addServer', 'B'), ('route', 'Ne'), ('route', 'Oe'), ('route', 'Qe'), ('route', 'zz')], 2)

Expected Output: ['B', 'A', 'B', 'A']

Explanation: With 2 virtual nodes each, the ring positions are A#0=279, B#0=280, A#1=282, B#1=283. The request hashes are Ne=280, Oe=281, Qe=283, zz=366, so routing is B, A, B, then wrap to A.

Input: ([('addServer', 'A'), ('addServer', 'B'), ('route', 'Ne'), ('removeServer', 'B'), ('route', 'Ne'), ('route', 'Oe')], 2)

Expected Output: ['B', 'A', 'A']

Explanation: Before removal, Ne hashes to B. After removing B, both Ne=280 and Oe=281 route to A's next virtual node at 282.

Input: ([('addServer', 'A'), ('route', 'Ne'), ('addServer', 'B'), ('route', 'Ne'), ('route', 'Pe')], 2)

Expected Output: ['A', 'B', 'A']

Explanation: With only A active, Ne routes to A. After adding B, Ne remaps to B's virtual node at 280, while Pe=282 still maps to A.

Input: ([('route', 'x'), ('addServer', 'A'), ('removeServer', 'A'), ('route', 'y')], 3)

Expected Output: [None, None]

Explanation: There are no active servers at either route call.

Hints

Store all virtual nodes in a sorted structure by hash so you can binary-search the destination for each request.
Keep track of which virtual-node entries belong to each server so removal is straightforward.

Quick Overview

Compute courier pay and implement load balancing

Company: DoorDash

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Part 1: Compute Courier Pay

Constraints

0 <= start_minute < end_minute <= 1440
0 <= pickup_minute <= dropoff_minute <= 1440
Rate intervals do not overlap, but they may leave gaps in the day
1 <= len(rate_intervals), len(trips) <= 100000 is possible, but the day length is fixed at 1440 minutes
rate_per_minute and per_trip_bonus are non-negative integers

Examples

Input: ([(0, 60, 2), (60, 120, 1)], [(30, 90, 5)])

Expected Output: 95

Explanation: From minute 30 to 60 the rate is 2 for 30 minutes, and from 60 to 90 the rate is 1 for 30 minutes. Total time pay is 60 + 30, plus bonus 5.

Input: ([(0, 100, 1), (200, 300, 2)], [(50, 250, 10), (260, 280, 0)])

Expected Output: 200

Explanation: First trip pays 50*1 + 100*0 + 50*2 + 10 = 160. Second trip pays 20*2 = 40. Combined total is 200.

Input: ([], [(10, 20, 3)])

Expected Output: 3

Explanation: No pay-rate intervals exist, so time-based pay is 0. Only the trip bonus is earned.

Input: ([(0, 1440, 4)], [])

Expected Output: 0

Explanation: There are no trips, so total pay is 0.

Hints

Because the day has only 1440 minutes, you can precompute the pay rate for every minute of the day.
After building per-minute rates, a prefix-sum array lets you answer each trip's time-based pay in O(1).

Part 2: Implement Request Routing with Round Robin

Constraints

1 <= len(operations) <= 200000
serverId and requestId are non-empty strings
Servers should be routed in the order they were added among currently active servers
Duplicate addServer operations are ignored
removeServer on a missing server is ignored

Examples

Input: ([('addServer', 'A'), ('addServer', 'B'), ('route', 'r1'), ('route', 'r2'), ('route', 'r3')],)

Expected Output: ['A', 'B', 'A']

Explanation: With servers A and B active, routing cycles A -> B -> A.

Input: ([('addServer', 'A'), ('addServer', 'B'), ('addServer', 'C'), ('route', 'x'), ('removeServer', 'B'), ('route', 'y'), ('route', 'z')],)

Expected Output: ['A', 'C', 'A']

Explanation: After routing to A, the next server would have been B. Removing B moves the cycle forward to C, then back to A.

Input: ([('route', 'r1'), ('addServer', 'X'), ('removeServer', 'X'), ('route', 'r2')],)

Expected Output: [None, None]

Explanation: There is no active server for either route call.

Input: ([('addServer', 'A'), ('addServer', 'A'), ('addServer', 'B'), ('route', 'p'), ('addServer', 'C'), ('removeServer', 'Z'), ('route', 'q'), ('route', 'r'), ('route', 's')],)

Expected Output: ['A', 'B', 'C', 'A']

Explanation: The second add of A is ignored, removing Z does nothing, and the cycle continues through A, B, C.

Hints

Think about keeping a pointer to the next server that should receive traffic.
A hash map plus a circular doubly linked list gives O(1) add, remove, and route.

Part 3: Implement Request Routing with Consistent Hashing

Constraints

1 <= len(operations) <= 100000
1 <= virtual_nodes <= 1000
serverId and requestId are non-empty strings
Use the exact hash function and ring rule described in the statement so routing is deterministic
Duplicate addServer operations are ignored, and removeServer on a missing server is ignored

Examples

Input: ([('addServer', 'A'), ('addServer', 'B'), ('route', 'Ne'), ('route', 'Oe'), ('route', 'Qe'), ('route', 'zz')], 2)

Expected Output: ['B', 'A', 'B', 'A']

Explanation: With 2 virtual nodes each, the ring positions are A#0=279, B#0=280, A#1=282, B#1=283. The request hashes are Ne=280, Oe=281, Qe=283, zz=366, so routing is B, A, B, then wrap to A.

Input: ([('addServer', 'A'), ('addServer', 'B'), ('route', 'Ne'), ('removeServer', 'B'), ('route', 'Ne'), ('route', 'Oe')], 2)

Expected Output: ['B', 'A', 'A']

Explanation: Before removal, Ne hashes to B. After removing B, both Ne=280 and Oe=281 route to A's next virtual node at 282.

Input: ([('addServer', 'A'), ('route', 'Ne'), ('addServer', 'B'), ('route', 'Ne'), ('route', 'Pe')], 2)

Expected Output: ['A', 'B', 'A']

Explanation: With only A active, Ne routes to A. After adding B, Ne remaps to B's virtual node at 280, while Pe=282 still maps to A.

Input: ([('route', 'x'), ('addServer', 'A'), ('removeServer', 'A'), ('route', 'y')], 3)

Expected Output: [None, None]

Explanation: There are no active servers at either route call.

Hints

Store all virtual nodes in a sorted structure by hash so you can binary-search the destination for each request.
Keep track of which virtual-node entries belong to each server so removal is straightforward.