Delivery Billing System

Build an in-memory delivery payout service. Start with driver registration, delivery recording, and O(1) total cost; add pay-up-to cutoff processing; then compute the maximum number of distinct active drivers in the last 24 hours. Requirements There are tens of thousands of drivers; each submits hundreds of deliveries per week. Delivery records arrive immediately after a completed job; no persistence or thread-safety layer is required for the interview version. Each driver has an hourly rate. A delivery pays driverHourlyRate * (endTime - startTime) / 3600. Time is Unix epoch seconds using 64-bit integers. Each delivery has 0 < endTime - startTime <= 3 hours, and endTime is already in the past when recorded. A driver may run multiple deliveries concurrently. For billing, each overlapping delivery still pays its full amount — payouts simply add up (concurrency only matters for the Part 3 active-driver count, not for cost). Implement: addDriver(driverId: int, usdHourlyRate: double) -> void recordDelivery(driverId: int, startTime: long, endTime: long) -> void — the driver already exists. getTotalCost() -> double, ideally O(1) amortized. Part 2: implement pay_up_to(endTime: long) -> void, marking every delivery with delivery.endTime <= endTime as paid exactly once. The endTime cutoff is guaranteed monotonically non-decreasing across calls, which is what lets a min-heap keyed by endTime pop each delivery once and never revisit it. Part 2: implement getUnpaidAmount() -> double as total recorded cost minus total paid cost, O(1). Part 3: implement maxSimultaneousDriverInPast24Hours(now?: long) -> int, counting distinct drivers active at the same instant in [now - 86_400, now], not raw delivery count. Optional variant: return the interval or intervals during which the maximum holds. Signatures (canonical OA shape) class DeliveryBillingSystem: def add_driver(self, driver_id: int, usd_hourly_rate: float) -> None: ... def record_delivery(self, driver_id: int, start_time: int, end_time: int) -> None: ... # payout = usd_hourly_rate * (end_time - start_time) / 3600.0; add to running total_cost. def get_total_cost(self) -> float: ... # O(1): return the running total_cost. def pay_up_to(self, cutoff_time: int) -> None: ... # Pop min-heap (keyed by end_time) while top.end_time <= cutoff_time; add each payout to total_paid once. # cutoff_time is monotonically non-decreasing across calls. def get_unpaid_amount(self) -> float: ... # O(1): return total_cost - total_paid. def max_simultaneous_drivers_in_past_24_hours(self, now: int) -> int: ... # window = [now - 86_400, now]; clip, per-driver merge, then sweep. Returns the distinct-driver peak. Examples A delivery at $10/hour lasting 1 hour 30 minutes pays $15.00. system = DeliveryBillingSystem() system.add_driver(1, 10.00) system.record_delivery(1, 100, 3700) assert system.get_total_cost() == 10.00 For Part 3, driver 1 working 1:00–2:00 and 1:30–3:00 merges to a single active block 1:00–3:00, so that driver contributes 1 to the simultaneous count across the whole span, not 2. Notes Keep a running total for getTotalCost; do not scan all deliveries on every dashboard call. For pay_up_to, use a min-heap or ordered structure keyed by endTime; pop each delivery once and accumulate paidTotal. The monotonic cutoff means a popped delivery never re-enters the unpaid heap, so repeated pay_up_to calls stay idempotent and the amortized cost is O(K log D) for the K deliveries paid. For Part 3, first clip each delivery to the [now - 86_400, now) window (skip deliveries with no overlap, then start = max(start, window_start) / end = min(end, window_end)), merge overlapping deliveries per driver inside the window, then sweep the merged intervals globally. The outer sweep is the canonical maximum-overlapping-intervals pattern (sort start/end events, increment on start, decrement on end, track running max); the per-driver merge is what makes it count distinct active drivers rather than raw deliveries. Use half-open intervals [start, end) so equal start/end timestamps do not double-count (process the end event before a start event at the same timestamp). If the interviewer treats deliveries as closed intervals, clarify the boundary rule before coding. The money representation can be integer cents, decimal, or double, but be ready to explain the trade-off; one candidate lost time on cent conversion and fractional cents. Time and space complexity are explicitly probed for every method in some AI-coding sessions. A candidate who cleared the phone screen implemented only the first two parts and described Part 3, so a clean Part 1/2 plus a credible Part 3 interval plan can still pass. Cost trade-offs to be ready to articulate Approach record_delivery analytics call When it wins Running total + merge-and-sweep on demand O(log D) O(D log D) Frequent records, rare analytics reads. Keep events sorted as they arrive O(log D) O(D) Balanced read/write. Sliding window / cached result slower ~O(1) Dashboard polled constantly (e.g. every second). Likely follow-ups Add a per-driver query returning how much a single driver is owed. Return the exact peak time window (which interval[s]) rather than just the count. Make the analytics call cheap when invoked every second — cache or maintain a sliding window instead of recomputing from scratch. Enforce a cap such as "a driver may not have more than 3 active deliveries at once." Preparation Code the three parts under a 45-minute timer and write unit tests for overlapping deliveries, repeated pay_up_to, and same-timestamp boundaries. Practice explaining heap-based incremental payment versus sorted arrays with a pointer. For Part 3, pre-write a helper that merges intervals per driver before the sweep-line pass.