Apply Item Coupons with Exact Per-Item Cent Rounding
Company: Palantir
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
Apply item-specific percentage coupons to a shopping cart and return its subtotal, total discount, and final total. Prices and all returned monetary amounts are integer cents.
### Function Contract
Implement `apply_discounts_and_calculate_total(items, discounts) -> dict`.
Each item is an object with `name` (string) and `price` (nonnegative integer cents). Each discount is an object with `name` (the matching item name) and `percent_off` (an integer percentage).
Return exactly these integer-valued keys:
- `subtotal`: sum of original item prices.
- `total_discount`: sum of the individually rounded item discount amounts.
- `final_total`: `subtotal - total_discount`.
### Rounding and Matching
A matching coupon's unrounded discount is `price * percent_off / 100`. Round that final amount to the nearest integer cent, breaking exact half-cent ties toward the even integer, matching Python's ties-to-even `round` convention. Do not round any earlier calculation, and do not round only the cart-wide sum. Treat the percentage calculation exactly, without relying on binary floating-point error to resolve a tie.
There is at most one coupon per item name. Matching is exact and case-sensitive. A coupon applies to every cart row with that name; unmatched coupons are ignored. Items without a coupon have zero discount. This initial version has no 80-percent cap.
### Constraints and Clarifications
- Both arrays may be empty and have at most `100000` entries each.
- Names are nonempty ASCII strings of length at most 100.
- `0 <= price <= 1000000000`.
- `0 <= percent_off <= 100`.
- Bounds, integral percentages, and exact arithmetic are explicit portable practice conventions.
- Cart totals may exceed signed 32-bit range.
### Examples
```text
items = [{"name": "Bananas", "price": 399}, {"name": "Bread", "price": 250}]
discounts = [{"name": "Bananas", "percent_off": 10}]
Output: {"subtotal": 649, "total_discount": 40, "final_total": 609}
```
```text
items = [{"name": "A", "price": 5}, {"name": "B", "price": 7}]
discounts = [{"name": "A", "percent_off": 50}, {"name": "B", "percent_off": 50}]
Output: {"subtotal": 12, "total_discount": 6, "final_total": 6}
```
The discounts `2.5` and `3.5` cents round to `2` and `4`, respectively.
```hint Keep the matching and rounding steps separate
First find the coupon for the item name, then calculate and round that item's final discount exactly once.
```
Overview: Calculate cart totals from item coupons with exact half-even cent rounding, unmatched-coupon handling, and integer monetary totals.
Read the full Palantir Software Engineer interview experience this question came from
You are given a shopping cart and a list of percentage coupons. Every price and every amount you return is an integer number of cents.
`items` is a list of `[name, price]` pairs, one per cart row, in cart order: `name` is the row's item name and `price` is its original price in cents. The same name may appear on several rows.
`discounts` is a list of `[name, percent_off]` pairs, where `percent_off` is an integer percentage. There is at most one coupon per name.
Return a dictionary with exactly these three integer-valued keys:
- `subtotal`: the sum of the original prices of every cart row.
- `total_discount`: the sum of the individually rounded item discount amounts.
- `final_total`: `subtotal - total_discount`.
Matching and rounding:
- A cart row is discounted when a coupon's name equals the row's name exactly; matching is exact and case-sensitive. A coupon applies to every cart row with that name. A row with no matching coupon has a discount of 0, and a coupon that matches no row is ignored.
- A matched row's unrounded discount is `price * percent_off / 100`. Round that final amount to the nearest integer cent, breaking an exact half-cent tie toward the even integer, matching Python's ties-to-even `round` convention: a discount of 2.5 cents rounds to 2 and a discount of 3.5 cents rounds to 4.
- Do not round any earlier calculation, and do not round only the cart-wide sum: every row is rounded on its own before the discounts are added together. Treat the percentage calculation exactly, without relying on binary floating-point error to resolve a tie.
- This initial version has no 80-percent cap; `percent_off` may be anything from 0 through 100.
The result is a single dictionary of three sums, so the only output semantics are the three key names and their exact integer values.
Cart totals may exceed signed 32-bit range: with up to 100000 rows priced up to 1000000000 cents each, `subtotal`, `total_discount` and `final_total` can reach 10^14, which is larger than 2^31 - 1. Use `long` in Java and `long long` in C++.
Example 1:
```text
items = [["Bananas", 399], ["Bread", 250]]
discounts = [["Bananas", 10]]
Output: {"subtotal": 649, "total_discount": 40, "final_total": 609}
```
Bananas: 399 * 10 / 100 = 39.9 cents, which rounds to 40. Bread has no coupon, so its discount is 0.
Example 2:
```text
items = [["A", 5], ["B", 7]]
discounts = [["A", 50], ["B", 50]]
Output: {"subtotal": 12, "total_discount": 6, "final_total": 6}
```
The discounts 2.5 and 3.5 cents round to 2 and 4, respectively.
Constraints
- Both arrays may be empty and have at most 100000 entries each.
- Each item is a pair [name, price]; each discount is a pair [name, percent_off].
- Names are nonempty ASCII strings of length at most 100.
- 0 <= price <= 1000000000.
- 0 <= percent_off <= 100, and percent_off is an integer.
- There is at most one coupon per item name; matching is exact and case-sensitive, and unmatched coupons are ignored.
- This initial version has no 80-percent cap.
- Cart totals may exceed signed 32-bit range (use long in Java and long long in C++).
- Prices and all returned monetary amounts are integer cents; the three returned keys are exactly subtotal, total_discount and final_total.
Examples
Input: ([], [])
Expected Output: {'subtotal': 0, 'total_discount': 0, 'final_total': 0}
Explanation: Minimum valid input: an empty cart and no coupons give three zeros.
Input: ([], [['Bread', 50]])
Expected Output: {'subtotal': 0, 'total_discount': 0, 'final_total': 0}
Explanation: An empty cart with a coupon: the coupon matches no row and is ignored.
Hints
- Keep the matching and the rounding steps separate: first find the coupon that belongs to an item's exact name, then calculate and round that one item's final discount exactly once.
- Each matched row is rounded on its own and only the rounded amounts are summed; rounding the cart-wide total instead can give a different answer, so decide which quantity you are rounding before you write the loop.
- The statement forbids letting binary floating-point error settle an exact half-cent tie, and every input value is an integer, so an exact treatment of price * percent_off / 100 is available.