Design receipt system with combo discounts

### Data model ``` Item { id: int, name: string, price: int } // price in cents to avoid float rounding Menu { lookupById(id) -> Item } Order { counts: Map<itemId, qty> } // single source of truth for the cart Combo { id, k: int, eligibleItemIds: Set<int>, discountType: AMOUNT_OFF|PERCENT_OFF, value: int } Display { show(receipt: string) } ``` Keep the cart as a `Map<itemId, qty>` (a hash map). This makes Part A O(1) per add and lets the receipt aggregate repeated items naturally. Store prices as integer cents so totals and percentage discounts round deterministically. ### Part A — incremental receipt ``` onUserUpdateSelected(itemId): order.counts[itemId] += 1 # add / increment quantity receipt = renderReceipt(order) # includes discounts once Part B is wired in display.show(receipt) renderReceipt(order): lines = [] subtotal = 0 for (itemId, qty) in order.counts (in a stable order, e.g. insertion or by id): item = menu.lookupById(itemId) lineTotal = item.price * qty subtotal += lineTotal lines.append(format("%s x %d @ %s = %s", item.name, qty, money(item.price), money(lineTotal))) (discountLines, discountTotal) = applyCombos(order) # Part B; [] and 0 before Part B lines += discountLines grandTotal = subtotal - discountTotal return join(lines, "\n") + "\nSubtotal: " + money(subtotal) + (discountTotal ? "\nDiscounts: -" + money(discountTotal) : "") + "\nTotal: " + money(grandTotal) ``` `toString`/formatting lives in a single `renderReceipt` (or `Item.toReceiptLine`) helper so the line format `"<name> x <qty> @ <unitPrice> = <lineTotal>"` is defined in one place. Iterate the map in a stable order (insertion order or sorted by id) so the receipt is deterministic across reprints. ### Part B — selecting a valid set of non-overlapping combos "Non-overlapping" means each physical unit of an item can count toward at most one combo. The cleanest model is: each combo consumes `k` units drawn from a pool that is the union of its eligible items' remaining quantities. We only need *a* valid set, not the optimal one, so a greedy pass with a backtracking fallback is enough. **Greedy (fast path):** ``` applyCombos(order): remaining = copy(order.counts) # mutable working copy of quantities applied = [] discountTotal = 0 progress = true while progress: progress = false for combo in combos: avail = sum(remaining[id] for id in combo.eligibleItemIds) if avail >= combo.k: consume k units from remaining across eligible items (any order) base = price of the consumed units (for percentOff) d = (combo.discountType == AMOUNT_OFF) ? combo.value : round(base * combo.value / 100) discountTotal += d applied.append(combo) progress = true return (formatComboLines(applied), discountTotal) ``` Greedy alone can over-commit a shared item to the wrong combo when combos have overlapping eligible sets and tight inventory. Because the prompt only requires *any* valid set, the safe, general solution is **backtracking** that treats the choice of which combo to fill next (and which units it consumes) as a search, returning the first complete, conflict-free assignment: ``` search(remaining, appliedSoFar): if no combo can still be formed from remaining: return appliedSoFar # any reachable set is valid for combo c that can be formed: for each way to pick k eligible units from remaining (or just one canonical pick): remaining' = remaining - those units result = search(remaining', appliedSoFar + [c]) if result is acceptable: return result # accept first valid set # also allow NOT forming c, to explore alternatives return appliedSoFar ``` In practice: run the greedy pass first; if it forms at least one combo, take it. Keep backtracking only as a fallback for the corner case where greedy stalls but a valid combo set still exists (overlapping eligibility + scarce units). Re-run `applyCombos` after every `onUserUpdateSelected` so the discount reflects the current cart. ### Assumptions - Item IDs are unique; quantities are positive integers. - Prices stored as integer cents; `percentOff` rounds with a fixed rule (e.g. round-half-up) to avoid floating-point drift. - A unit may belong to at most one combo (non-overlapping). - No requirement to maximize discount — first valid assignment wins. ### Complexity - **Part A:** O(1) amortized to add an item; O(n) to render the receipt where n = number of distinct items in the cart. - **Part B greedy:** each outer pass is O(C · A) where C = number of combos and A = average eligible-pool scan; it runs until no progress, bounded by total units / min(k). Overall roughly O(U · C) where U = total units in the cart. - **Part B backtracking fallback:** worst case exponential in the number of combos/units, but it only triggers in the rare overlapping-scarcity corner case and is bounded by the small cart sizes typical of a single order. - **Space:** O(n) for the cart map plus O(C) for combos and O(depth) for the backtracking recursion stack.

The interviewer is looking for: (1) a clean cart abstraction (a quantity map) that makes repeated-item aggregation and O(1) updates trivial; (2) receipt formatting isolated in one render/toString path that is re-invoked on every update; and (3) recognition that combo selection is a constraint-satisfaction / set-packing problem where, because only a *valid* (not optimal) set is required, greedy-with-backtracking-fallback is the right altitude. Strong candidates use integer cents to dodge rounding bugs, state explicit assumptions, and correctly analyze that the easy parts are linear while the combo search is the only place exponential blowup can hide.