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.