Design receipt system with combo discounts
Company: CloudKitchens
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Question
You are building a point-of-sale ordering UI for a food-ordering workflow. You are given class stubs and a callback you must wire up:
- `Item(id, name, price)`
- `Menu` with `lookupById(itemId)`
- `Order` with `add`, `remove`, and per-item `quantities`
- `Display` with `show(receipt)`
- `onUserUpdateSelected(itemId)` — called by the framework each time the user taps an item
**Part A — Incremental receipt.** Each time `onUserUpdateSelected(itemId)` is called, add the item to the current `Order`, update its quantity, and print a receipt string via `Display.show(receipt)`. The receipt must:
1. List each line in the form `"<name> x <qty> @ <unitPrice> = <lineTotal>"`.
2. Print a subtotal and a grand total.
It must work correctly for repeated additions of the same item (quantities aggregate) and for multiple distinct items. Implement the data structures and the `toString`/formatting methods needed to support this.
**Part B — Combo discounts.** Extend the system to support combo discounts. A `Combo` is defined by:
- a required count `k` (number of qualifying items needed to form one combo),
- the set of eligible item IDs (or categories) that can satisfy it, and
- a discount value with a type, either `amountOff` (flat amount) or `percentOff`.
(In the simplest form a combo is just `k items -> discountAmount`.) After each item addition, find **any valid set of non-overlapping combos** that can be applied to the current `Order`, apply the resulting discount(s), and reprint the updated receipt showing which combos were applied and the final discounted total. You do **not** need to maximize the total discount or the number of combos — returning any valid application is sufficient.
In your answer, describe your data model for items, the cart/order, and combos; give pseudocode or code for `onUserUpdateSelected`; explain the algorithm you use to pick a valid set of non-overlapping combos (e.g., greedy with a backtracking fallback that guarantees a valid set if one exists); analyze the time and space complexity; and state your assumptions (e.g., unique item IDs, integer quantities, rounding rule for percentage discounts).
Overview: A CloudKitchens software-engineer technical screen: build a point-of-sale order that prints an itemized receipt on every item tap, then extend it to apply combo discounts. It tests cart data-structure design, receipt formatting, and the algorithm for selecting a valid set of non-overlapping combos.