Bill Deliveries with Historical Rates and Deferred Rounding

Implement delivery billing with driver rate histories, duplicate-delivery protection, and exact accumulation before rounding.

Implement delivery_billing(operations: string[][], rounding: string) -> string[], returning one result string per operation.

Operations

• ["ADD",driverId,hourlyRate]: add a new driver with an initial rate effective at time 0; return OK.
• ["UPDATE",driverId,newRate,effectiveTime]: add a rate change; return OK.
• ["DELIVERY",deliveryId,driverId,start,end]: record a delivery and its charge; return OK when recorded, or IGNORED for a duplicate already-recorded ID or a duration exceeding three hours.
• ["TOTAL"]: return the cumulative charge formatted as dollars with exactly two fractional digits.

Constraints & Assumptions

• At most 100000 operations. IDs are nonempty ASCII identifiers. ADD IDs are new, and every referenced driver exists. All times are integer seconds from 0 through 1000000000, with 0 <= start <= end.
• Rates are nonnegative dollar strings with exactly two decimal places and are at most 10000.00 per hour.
• Delivery IDs are global across drivers. A recorded ID is ignored on every later DELIVERY even if its payload differs. An over-three-hour delivery is ignored without reserving its ID; this invalid-ID policy is an explicit practice choice.
• Exactly three hours is valid. Overlapping deliveries for the same driver are charged independently. Zero-duration deliveries are recorded with zero cost.
• Use the rate whose effective time is the greatest value not exceeding the delivery's start. A later operation at the same effective time replaces that rate for future lookups. Out-of-order effective times are allowed.
• The entire delivery uses its start-time rate; do not split at a rate change. Once recorded, its charge never changes after later rate updates, including backdated updates.
• Preserve fractional cents internally and round only when TOTAL returns. TOTAL must not mutate the accumulated exact amount.
• rounding is HALF_UP or HALF_EVEN. The source did not settle exact-half-cent ties, so this practice parameter makes both policies explicit: ties round upward for HALF_UP and to the even cent for HALF_EVEN. All amounts are nonnegative.
• Use integer arithmetic: a rate in cents multiplied by seconds gives an exact numerator with denominator 3600 cents. The stated bounds fit signed 64-bit arithmetic for the total numerator.

Examples

operations = [["ADD","d","15.15"],["DELIVERY","a","d","0","5400"],
 ["TOTAL"],["DELIVERY","b","d","5400","7200"],["TOTAL"],
 ["DELIVERY","a","d","0","5400"],["TOTAL"]]
rounding = "HALF_UP"
result = ["OK","OK","22.73","OK","30.30","IGNORED","30.30"]

The first delivery costs exactly 22.725 dollars and the second 7.575 dollars. Their exact sum is 30.30, not the sum of individually rounded charges. For the first TOTAL alone, HALF_EVEN would return 22.72. Querying between deliveries does not change the final sum.

Explain historical-rate lookup, duplicate handling, and the distinction among numeric representation, rounding time, and tie rule. For the reported debugging follow-up, describe how you would isolate a failing test: compare exact per-delivery charges, selected rate versions, duplicate IDs, and the final formatting step rather than labeling every discrepancy a floating-point issue.

Hint: Keep the common denominator

All durations are integer seconds and all rates are integer cents per hour. Sum exact integer numerators, then round the final quotient once per query.

Accumulate Delivery Charges with Historical Rates

Approach

Convert hourly dollar rates to integer cents. Each valid delivery contributes rateCents*(end-start) to a running integer numerator whose denominator is 3600 cents. Store recorded delivery IDs globally; reject already-recorded IDs and durations above 10800 seconds before reserving an ID. Zero-duration and exactly-three-hour deliveries are recorded. For each accepted delivery, select the currently known rate with greatest effective time at or before its start. Capture its charge immediately, so later updates cannot reprice it. Java and C++ use ordered rate maps. Python and JavaScript precollect and sort possible effective times, then activate only those encountered during operation processing in a Fenwick prefix-maximum structure. The maximum active coordinate in a start-time prefix identifies the correct current rate. Future timestamps are merely coordinates, not active rates. Same-time updates replace the stored rate at that coordinate. This supports arbitrary update order in O(log n) lookup/update time. At TOTAL, divide the accumulated numerator by 3600 into whole cents and remainder. Remainders below or above 1800 round down or up; ties round up for HALF_UP, or up only from an odd whole-cent value for HALF_EVEN. Format the resulting cents with two decimal places without changing the numerator. At most 100000 operations, 1000000 rate cents and 10800 valid duration seconds keep even JavaScript integer arithmetic exact; Java/C++ use signed 64-bit totals. For debugging, compare selected rate versions, duration and ID admission first, then exact per-delivery numerators, cumulative numerator and final tie handling. Numeric representation, rounding time and tie policy are separate decisions. For n operations, runtime is O(n log n) plus string work, state O(n), and each TOTAL has constant-sized arithmetic.

• Time complexity: O(n log n) plus string processing
• Space complexity: O(n) state plus strings and output