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.