Compute Driver Pay with Double-Pay Windows
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are building payroll logic for a delivery platform.
Given a list of order records for one delivery driver, compute the total amount the driver should be paid.
Each order record contains:
- `order_id`: a unique identifier
- `status`: either `"delivered"` or `"canceled"`
- `start_time`: delivery start time, represented as an integer timestamp in minutes
- `end_time`: delivery end time, represented as an integer timestamp in minutes
- `hourly_rate`: the driver's normal hourly rate for that order
Additional inputs:
- `canceled_order_compensation`: a fixed payment amount for each canceled order
- `double_pay_windows`: a list of time intervals `[start_time, end_time)` during which delivered work should be paid at double the normal hourly rate
Payment rules:
1. For a delivered order, pay the driver based on the delivery duration and hourly rate.
2. Any portion of a delivered order that overlaps a double-pay window should be paid at double rate.
3. Portions that do not overlap any double-pay window should be paid at normal rate.
4. If multiple double-pay windows overlap, the driver should still receive at most double pay for any minute, not triple or more.
5. For a canceled order, pay only the fixed `canceled_order_compensation`; do not apply hourly or double-pay calculations.
6. Treat all intervals as half-open: `[start_time, end_time)`.
Return the driver's total pay as a numeric value.
Example:
```text
orders = [
{ order_id: "A", status: "delivered", start_time: 60, end_time: 120, hourly_rate: 30 },
{ order_id: "B", status: "canceled", start_time: 130, end_time: 160, hourly_rate: 30 },
{ order_id: "C", status: "delivered", start_time: 150, end_time: 210, hourly_rate: 24 }
]
canceled_order_compensation = 5
double_pay_windows = [
[90, 150],
[180, 240]
]
```
Order A lasts 60 minutes. Minutes `[60, 90)` are paid normally, and `[90, 120)` are paid at double rate.
Order B is canceled, so it pays `5`.
Order C lasts 60 minutes. Minutes `[150, 180)` are paid normally, and `[180, 210)` are paid at double rate.
Compute and return the total pay.
Quick Answer: This question evaluates a candidate's ability to perform interval arithmetic and aggregation for time-based pay computations, including handling overlapping intervals, half-open boundaries, capped double-pay application, and special-case handling for canceled orders.
You are given all order records for a single delivery driver. Each order is a dictionary with keys `order_id`, `status`, `start_time`, `end_time`, and `hourly_rate`.
Compute the driver's total pay using these rules:
- If an order is `delivered`, pay for its duration in minutes using `hourly_rate`.
- Any minute of a delivered order that falls inside at least one double-pay window is paid at double the normal hourly rate.
- Minutes outside double-pay windows are paid at the normal hourly rate.
- If double-pay windows overlap, a minute is still only paid at double rate once.
- If an order is `canceled`, ignore its duration and hourly rate, and pay only `canceled_order_compensation`.
- All intervals are half-open: `[start_time, end_time)`.
For a delivered order, pay is based on minutes worked: `minutes * hourly_rate / 60`.
Return the total pay as a numeric value.
Constraints
- 0 <= len(orders), len(double_pay_windows) <= 10^5
- For every order, `start_time <= end_time`
- For every double-pay window, `start_time <= end_time`
- Timestamps are integers in minutes
- Statuses are valid and are either `delivered` or `canceled`
Examples
Input: ([{'order_id': 'A', 'status': 'delivered', 'start_time': 60, 'end_time': 120, 'hourly_rate': 30}, {'order_id': 'B', 'status': 'canceled', 'start_time': 130, 'end_time': 160, 'hourly_rate': 30}, {'order_id': 'C', 'status': 'delivered', 'start_time': 150, 'end_time': 210, 'hourly_rate': 24}], 5, [[90, 150], [180, 240]])
Expected Output: 86.0
Explanation: Order A pays 45.0, order B pays 5.0, and order C pays 36.0, for a total of 86.0.
Input: ([{'order_id': 'X', 'status': 'delivered', 'start_time': 0, 'end_time': 60, 'hourly_rate': 60}, {'order_id': 'Y', 'status': 'delivered', 'start_time': 60, 'end_time': 120, 'hourly_rate': 60}], 7, [[80, 100], [20, 50], [40, 80]])
Expected Output: 200.0
Explanation: The windows merge into one covered interval [20, 100). Each 60-minute order has 40 double-paid minutes and 20 normal minutes, so each pays 100.0.
Hints
- First merge the double-pay windows so that overlapping windows do not cause the same minute to be counted more than once.
- After merging, use binary search plus prefix sums of covered minutes to compute how many minutes of each delivered order fall inside the union of double-pay windows.