Compute cart total with best promotion
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Assume you are implementing a checkout price calculator for an online shopping cart.
You are given:
- A list of items in the cart. Each item has:
- `price`: a non-negative decimal number representing the item's price.
- A `shipping_fee`: a non-negative decimal number representing the shipping cost for the entire order.
- A list of promotions. Each promotion is one of two types:
1. **Percentage discount**: represented as a percentage value `p` (e.g., 10 for 10%). This discount applies **only to the sum of item prices**, **not** to the shipping fee.
2. **Fixed-amount discount**: represented as a non-negative decimal `d`. This discount is subtracted from the **total amount including shipping**.
Rules and assumptions:
- Let `items_sum` be the sum of all item prices.
- Before discount, the total amount is `items_sum + shipping_fee`.
- For a percentage discount `p` (e.g., 10 for 10%), the discounted total is:
- `discounted_items = items_sum * (1 - p/100)`
- `total = discounted_items + shipping_fee`.
- For a fixed-amount discount `d`, the discounted total is:
- `total = max(0, items_sum + shipping_fee - d)`.
- You may assume percentage values are between 0 and 100, and fixed-amount discounts are non-negative.
- The payable total should never be negative; clamp it to 0 if a discount would make it negative.
- You must apply **at most one** promotion to the cart. Some carts may have no promotions.
**Task**
Given the list of item prices, the shipping fee, and a list of promotions of the two types above, write a function that:
1. Computes the final payable amount for each promotion.
2. Finds the promotion that yields the **lowest payable amount** (i.e., the maximum savings).
3. Returns:
- The minimum payable amount after applying the best promotion (or no promotion if that yields the lowest total).
- An indication of which promotion was chosen (you may assume each promotion has an ID or index; you can define a reasonable representation).
Handle relevant edge cases, such as:
- Empty cart (no items).
- No promotions.
- Zero or extremely small prices or fees.
- Promotions that do not improve the price (e.g., 0% discount or fixed discount of 0).
- Promotions that would otherwise drive the total below zero (must clamp to 0).
Specify the input and output formats for your function, including how you represent promotions and their types, and then implement the function.
Quick Answer: This question evaluates numerical reasoning for monetary calculations, handling of multiple promotion types, precision and rounding considerations, and edge-case handling such as empty carts and clamping totals within the Coding & Algorithms domain.
You are implementing a checkout price calculator for an online shopping cart.
You are given:
- `prices`: a list of non-negative item prices.
- `shipping_fee`: a non-negative shipping cost for the whole order.
- `promotions`: a list of at-most-one-applicable promotions. Each promotion is a pair `(type, value)`:
- `("percent", p)` — a `p`% discount applied **only to the sum of item prices**, never to shipping. `discounted_items = items_sum * (1 - p/100)`, then `total = discounted_items + shipping_fee`.
- `("fixed", d)` — a flat amount `d` subtracted from the **total including shipping**: `total = items_sum + shipping_fee - d`.
Rules:
- Let `items_sum = sum(prices)` and `base_total = items_sum + shipping_fee`.
- The payable total is never negative — clamp to `0`.
- Apply **at most one** promotion. Applying none is always an option.
Return a pair `(min_payable, best_index)` where `min_payable` is the lowest achievable payable amount (rounded to 2 decimals) and `best_index` is the 0-based index of the chosen promotion, or `-1` when applying no promotion is at least as good as every promotion (ties resolve to no-promotion / the earliest already-better option).
Constraints
- 0 <= len(prices); each price is a non-negative decimal.
- shipping_fee >= 0.
- 0 <= p <= 100 for percentage promotions; d >= 0 for fixed promotions.
- At most one promotion may be applied; applying none is always allowed.
- The payable amount is clamped to a minimum of 0.
Examples
Input: ([10.0, 20.0, 30.0], 5.0, [("percent", 10), ("fixed", 8.0)])
Expected Output: (57.0, 1)
Explanation: items_sum=60, base=65. percent 10 -> 60*0.9+5 = 59. fixed 8 -> 65-8 = 57. Fixed wins at index 1.
Input: ([100.0], 0.0, [("percent", 50), ("fixed", 40.0)])
Expected Output: (50.0, 0)
Explanation: base=100. percent 50 -> 50. fixed 40 -> 60. Percent wins at index 0.
Hints
- Compute items_sum and base_total = items_sum + shipping_fee once. The 'no promotion' option gives base_total (clamped to 0) and is your starting best.
- A percentage promo only discounts items_sum, so its total is items_sum*(1 - p/100) + shipping_fee. A fixed promo discounts the whole base_total: base_total - d.
- Track the running minimum and the index that produced it. Keep best_index = -1 unless a promotion strictly beats the current best, so 0% / 0-amount no-op promotions correctly leave you with no promotion. Round to 2 decimals to avoid float noise.