Shopping cart with discounts, undo and redo

Agree on a small, precise API before coding. A reasonable version:

• add_item(sku, unit_price, qty=1), remove_item(sku, qty=None) (all of it when qty is None), set_quantity(sku, qty).
• apply_discount(code) and remove_discount(code). Discounts come from a catalog the cart is constructed with:
  • percent off one SKU (SKU_PERCENT, e.g. 20% off mug),
  • percent off the cart (CART_PERCENT),
  • fixed amount off the cart with a minimum spend (CART_FIXED, e.g. $10 off orders over $50).
• total() in integer cents. Money is never a float.
• undo() and redo() for every mutation above. A new mutation after an undo clears the redo history. Undo with nothing to undo returns False.

Ask how discounts stack. A common rule: SKU discounts first, then cart percentages, then fixed amounts, never below zero, and at most one cart-level discount at a time (applying a second replaces the first). Write it down; the tests depend on it.

Keep two concerns apart:

1. State and pricing. The cart holds items: sku -> (unit_price, qty) and discounts: set of codes. total() is a pure function of that state. Never store a running total that undo would also have to fix.
2. History. Use the command pattern. Every mutation is a command object with apply() and revert(). The cart keeps an undo stack and a redo stack:
   • execute(cmd): run cmd.apply(); if it changed something, push it on the undo stack and clear the redo stack.
   • undo(): pop from undo, revert(), push on redo.
   • redo(): pop from redo, apply(), push on undo.

The simplest correct revert is a before-image: when a command applies, it records the previous value of exactly what it touches (one SKU's line, or the discount set). Revert writes those values back. That is O(1) memory per command, unlike snapshotting the whole cart per mutation, and it is hard to get wrong because no command has to compute an inverse by hand.

Two details interviewers check:

• No-op mutations are not recorded. Removing a SKU that is not in the cart, or applying a code already applied, returns False and leaves the history alone. Otherwise one undo would appear to do nothing.
• Redo replays the same command, which re-captures its before-image on apply. That keeps redo correct even if the command's effect depends on current state.

from dataclasses import dataclass
from typing import Dict, List, Optional, Set, Tuple

Line = Tuple[int, int]  # (unit_price_cents, qty)


@dataclass(frozen=True)
class Discount:
    code: str
    kind: str                 # "SKU_PERCENT" | "CART_PERCENT" | "CART_FIXED"
    value: int                # percent (0-100) or cents
    sku: Optional[str] = None
    min_subtotal: int = 0

    @property
    def cart_level(self) -> bool:
        return self.kind != "SKU_PERCENT"


class _Command:
    def apply(self, cart: "Cart") -> bool: ...
    def revert(self, cart: "Cart") -> None: ...


class _SetLine(_Command):
    """Set one SKU's line (None removes it). Before-image: the old line."""

    def __init__(self, sku: str, line: Optional[Line]) -> None:
        self.sku, self.line, self.before = sku, line, None

    def apply(self, cart: "Cart") -> bool:
        self.before = cart.items.get(self.sku)
        if self.before == self.line:
            return False
        cart._put(self.sku, self.line)
        return True

    def revert(self, cart: "Cart") -> None:
        cart._put(self.sku, self.before)


class _SetDiscounts(_Command):
    def __init__(self, codes: Set[str]) -> None:
        self.codes, self.before = frozenset(codes), frozenset()

    def apply(self, cart: "Cart") -> bool:
        self.before = frozenset(cart.discounts)
        if self.before == self.codes:
            return False
        cart.discounts = set(self.codes)
        return True

    def revert(self, cart: "Cart") -> None:
        cart.discounts = set(self.before)


class Cart:
    def __init__(self, catalog: Dict[str, Discount]) -> None:
        self.catalog = catalog
        self.items: Dict[str, Line] = {}
        self.discounts: Set[str] = set()
        self._undo: List[_Command] = []
        self._redo: List[_Command] = []

    # ---- mutations --------------------------------------------------------
    def add_item(self, sku: str, unit_price: int, qty: int = 1) -> bool:
        if qty <= 0 or unit_price < 0:
            raise ValueError("qty must be positive and price non-negative")
        _, have = self.items.get(sku, (unit_price, 0))
        return self._execute(_SetLine(sku, (unit_price, have + qty)))

    def remove_item(self, sku: str, qty: Optional[int] = None) -> bool:
        if sku not in self.items:
            return False
        price, have = self.items[sku]
        left = 0 if qty is None else max(0, have - qty)
        return self._execute(_SetLine(sku, (price, left) if left else None))

    def set_quantity(self, sku: str, qty: int) -> bool:
        if sku not in self.items:
            return False
        price, _ = self.items[sku]
        return self._execute(_SetLine(sku, (price, qty) if qty > 0 else None))

    def apply_discount(self, code: str) -> bool:
        d = self.catalog.get(code)
        if d is None:
            raise KeyError(f"unknown discount {code}")
        codes = set(self.discounts)
        if d.cart_level:  # one cart-level discount at a time: replace
            codes = {c for c in codes if not self.catalog[c].cart_level}
        codes.add(code)
        return self._execute(_SetDiscounts(codes))

    def remove_discount(self, code: str) -> bool:
        return self._execute(_SetDiscounts(self.discounts - {code}))

    # ---- history ----------------------------------------------------------
    def undo(self) -> bool:
        if not self._undo:
            return False
        cmd = self._undo.pop()
        cmd.revert(self)
        self._redo.append(cmd)
        return True

    def redo(self) -> bool:
        if not self._redo:
            return False
        cmd = self._redo.pop()
        cmd.apply(self)
        self._undo.append(cmd)
        return True

    def _execute(self, cmd: _Command) -> bool:
        if not cmd.apply(self):
            return False
        self._undo.append(cmd)
        self._redo.clear()
        return True

    def _put(self, sku: str, line: Optional[Line]) -> None:
        if line is None:
            self.items.pop(sku, None)
        else:
            self.items[sku] = line

    # ---- pricing ----------------------------------------------------------
    def subtotal(self) -> int:
        return sum(price * qty for price, qty in self.items.values())

    def total(self) -> int:
        active = [self.catalog[c] for c in sorted(self.discounts)]
        amount = 0
        for sku, (price, qty) in self.items.items():
            line = price * qty
            for d in active:
                if d.kind == "SKU_PERCENT" and d.sku == sku:
                    line -= line * d.value // 100
            amount += line
        for d in active:
            if d.kind == "CART_PERCENT" and amount >= d.min_subtotal:
                amount -= amount * d.value // 100
        for d in active:
            if d.kind == "CART_FIXED" and amount >= d.min_subtotal:
                amount -= d.value
        return max(0, amount)

Rounding: line * pct // 100 rounds the discount down, so the customer never gets more off than advertised. Say this out loud; some interviewers want half-up rounding per line instead.

• Every mutation, undo and redo: O(1) time (the discount set is tiny) and O(1) extra memory per history entry.
• total(): O(items × discounts). Cache it and invalidate on any mutation if it is called far more often than the cart changes.
• History grows without bound; cap the undo stack (a deque(maxlen=100)) if carts live long.

1. Grouped undo. "Apply a coupon bundle" or "reorder last week's cart" should undo as one step. Add a CompositeCommand holding a list of commands: apply in order, revert in reverse.
2. Price changes while items sit in the cart. Store the unit price at add time (as here) and reconcile at checkout, or store only SKUs and look prices up in total(). Undo then restores quantities, not prices.
3. Persisting history. For a server-side cart, store the command log (event sourcing) rather than snapshots: the cart is a fold over events, undo is a compensating event, and the log doubles as an audit trail.
4. Concurrency. Two devices editing one cart: give each command a cart version and reject stale ones, or merge per SKU (last writer wins per line). Undo becomes per-device: you undo your own last action, not the other device's.
5. Richer discounts. Buy-one-get-one, tiered quantity breaks, and exclusive coupons push pricing into a rule engine with an explicit order of application. Keep it a pure function of the cart so history stays simple.

Mid-level (L4)

• Correct cart operations and totals in integer cents, with clear discount stacking rules.
• Undo and redo with two stacks; a new action clears redo.
• Handles the edge cases: removing a missing SKU, undo on an empty history, quantity dropping to zero.

Senior (L5)

• Uses the command pattern with before-images, so revert is mechanical and O(1) per step, and explains why full snapshots or hand-written inverses are worse.
• Keeps pricing a pure function of state rather than a running total that undo must also fix.
• Does not record no-op mutations, and tests the full undo-redo round trip, ideally with a randomized test.

Staff (L6+)

• Extends cleanly to grouped commands, persisted history (event sourcing) and multi-device carts.
• Raises product questions: rounding policy, coupon exclusivity, prices changing while items wait.
• Weighs bounding history, caching totals and where this logic should live (client versus server).