Design a Shopping Cart & Checkout
A shopping cart looks like a list with a total. Then marketing asks for "buy two pens, get one free", finance asks why a coupon made one order total minus three cents, and support asks why a customer was charged twice after pressing Pay during a network blip. Meanwhile the warehouse wants to know how 101 people bought the last 100 units.
The cart itself is easy. The pricing rules change every week, the arithmetic must be exact to the cent, and checkout is a small transaction where stock, payment and order state must agree. A good answer keeps those three concerns in separate classes.
This page follows the LLD interview framework. It builds on Strategy, Specification and State, and the checkout race is a close cousin of seat booking in booking and inventory concurrency.
1. Requirements
Questions worth asking, with the answers we'll assume:
| Question | Assumption |
|---|---|
| One currency per cart? | Yes. Multi-currency is a pricing-service concern, out of scope. |
| Which promotions? | Percentage off matching items, buy-X-get-Y, amount off above a threshold, coupon codes. |
| Can coupons combine? | Some can (stackable), some can't (exclusive). The customer gets the better of the two options. |
| Tax? | A rate per product category, applied to the price after discounts. Region rules are an extension. |
| When is stock taken? | Reserved at checkout, committed on payment, released on failure or timeout. Adding to a cart reserves nothing. |
| Payment? | An external gateway behind an interface. It can approve, decline or time out. |
| Retries? | The client sends an idempotency key, and a retried checkout must never charge twice. |
Functional requirements
- Add, update and remove cart lines (product and quantity).
- Price the cart: subtotal, each discount with its rule, tax and total.
- Apply automatic promotions and customer-entered coupons, following the stacking rules.
- Check out: reserve stock for every line, charge the card, create an order.
- Track the order through
PENDING_PAYMENT → PAID → SHIPPED → DELIVERED, with cancellation where allowed.
Non-functional requirements
- Exact money. Integer minor units, no floats, and every split adds back up to the original.
- Explainable prices. The quote lists every adjustment.
- No overselling. Two buyers can't both get the last unit.
- Idempotent checkout. The same key gives the same order, however many times it arrives.
- Open for new promotions. A new promotion is a new class.
Out of scope: shipping, gift cards, split payments and the catalogue.
2. Core entities
| Entity | Responsibility |
|---|---|
Product | SKU, unit price in cents, category, tax rate. Immutable. |
Cart, CartLine | What one buyer intends to buy, plus entered coupon codes. Holds no prices. |
Spec<T> | A yes/no rule that composes with and and not: "is a book", "net ≥ $100". |
PricingRule | One promotion. Given a context, returns discounts. The Strategy interface. |
PricingContext | One pricing pass: net per line and adjustments so far. Thrown away after the quote. |
Coupon | A code, a pricing rule, a stackable flag, an eligibility spec. |
PricingEngine | Runs rules in a fixed order, picks the best coupons, adds tax. Stateless. |
TaxPolicy | Tax for one line given its net amount. A second Strategy. |
Quote | The immutable priced result, copied onto the order. |
Inventory | Stock on hand, reserved stock, expiring holds. The shared hot spot. |
Order | A snapshot of lines and quote, plus a status machine. |
PaymentGateway | Charges a card with an idempotency key. External. |
CheckoutService | Orchestrates quote, reserve, charge, commit. Owns idempotency. |
Two relationships matter. A Cart references products, but an Order copies the quantities, unit prices and the full Quote. If marketing changes a price tomorrow, yesterday's order must not change with it. And the Cart never stores a price or a discount, because prices are always derived. A cart that stores totals goes stale the moment a promotion ends.
3. Class diagram
classDiagram
class Cart {
+String id
+String userId
+String region
+add(Product, int)
+setQty(String, int)
+applyCoupon(String)
}
class CartLine {
+Product product
+int qty
+gross() long
}
class Product {
+String sku
+long price
+String category
+int taxBps
}
class PricingRule {
<<interface>>
+discounts(PricingContext) List~Adjustment~
}
class Spec~T~ {
<<interface>>
+ok(T) boolean
+and(Spec) Spec
+not() Spec
}
class PercentOff
class BuyXGetY
class AmountOff
class Coupon {
+String code
+boolean stackable
}
class TaxPolicy {
<<interface>>
+tax(Cart, CartLine, long) long
}
class PricingEngine {
+quote(Cart) Quote
}
class Quote {
+long subtotal
+long discount
+long tax
+long total
}
class Inventory {
+reserve(String, Map, long)
+commit(String)
+release(String)
}
class Order {
+String id
+Status status
+transition(Status)
}
class CheckoutService {
+checkout(Cart, String) Order
}
class PaymentGateway {
<<interface>>
+charge(String, long) boolean
}
Cart "1" *-- "many" CartLine
CartLine --> Product
PricingRule <|.. PercentOff
PricingRule <|.. BuyXGetY
PricingRule <|.. AmountOff
PercentOff --> Spec
AmountOff --> Spec
Coupon --> PricingRule
PricingEngine o-- PricingRule
PricingEngine o-- Coupon
PricingEngine --> TaxPolicy
PricingEngine ..> Quote : creates
CheckoutService --> PricingEngine
CheckoutService --> Inventory
CheckoutService --> PaymentGateway
CheckoutService ..> Order : creates
Order --> Quote
4. Key flows
Pricing a cart
The engine runs in four fixed phases. Line promotions first, because "10% off books" is about a book's price. Then cart promotions, which look at the net after line promotions, so "spend $100" means $100 after item discounts. Then coupons, and tax last, on what the customer actually pays.
sequenceDiagram
participant C as Client
participant E as PricingEngine
participant R as PricingRule
participant T as TaxPolicy
C->>E: quote(cart)
E->>E: lineNet = gross of each line
loop each line rule, then each cart rule
E->>R: discounts(ctx)
R-->>E: adjustments
E->>E: cap at zero, spread cart-level amounts over lines
end
E->>E: try stackable set and each exclusive coupon on copies
E->>E: keep the cheapest option
loop each line
E->>T: tax(cart, line, net)
end
E-->>C: Quote with adjustments, applied and rejected coupons
Checkout
sequenceDiagram
participant C as Client
participant S as CheckoutService
participant I as Inventory
participant G as PaymentGateway
C->>S: checkout(cart, key)
S->>S: lock key, return stored order if key seen
S->>S: quote = engine.quote(cart)
S->>I: reserve(orderId, items, ttl)
alt not enough stock
I-->>S: OutOfStock
S-->>C: error, nothing charged
else held
S->>G: charge(orderId, total)
alt approved
S->>I: commit(orderId)
S->>S: order PAID, clear cart, notify observers
else declined
S->>I: release(orderId)
S->>S: order CANCELLED
end
S->>S: store key to order
S-->>C: order
end
Stock is reserved before the charge, so we never take money for goods we can't ship. The hold has a TTL, so a crashed checkout can't keep stock forever. The order ID is also the gateway's idempotency key, a second line of defence against double charges.
Order lifecycle
stateDiagram-v2
[*] --> PENDING_PAYMENT : stock reserved
PENDING_PAYMENT --> PAID : charge approved
PENDING_PAYMENT --> CANCELLED : declined or reservation expired
PAID --> SHIPPED : handed to carrier
PAID --> CANCELLED : refunded before dispatch
SHIPPED --> DELIVERED : carrier confirms
DELIVERED --> [*]
CANCELLED --> [*]
A shipped order can't be cancelled, only returned, which is a separate flow with its own state machine.
Reservation lifecycle
stateDiagram-v2
[*] --> HELD : reserve
HELD --> COMMITTED : payment approved
HELD --> RELEASED : payment declined
HELD --> EXPIRED : ttl passes
COMMITTED --> [*]
RELEASED --> [*]
EXPIRED --> [*]
5. Patterns and why
| Pattern | Where | Why it fits | Rejected alternative |
|---|---|---|---|
| Strategy | PricingRule, TaxPolicy, PaymentGateway | Each promotion is one interchangeable algorithm. New promotion, new class. | A switch (promo.type) in the engine. Every new promotion edits and retests the engine. |
| Specification | Spec<CartLine>, Spec<PricingContext> | Eligibility rules combine ("books AND NOT clearance") and are reused across promotions. | Boolean flags on each rule (minSubtotal, categories, excludeSale). The flags multiply and never cover the next request. |
| State (table-driven) | Status.canMoveTo | Five states and six transitions. A table shows every legal move at a glance. | One class per state. Here only the legal moves differ, so the classes would be near-empty. |
| Observer | onPaid listeners | Emails, loyalty points and coupon ledgers react to a paid order without the checkout knowing about them. | Calling emailService.send() inside checkout. Every new reaction edits checkout and can fail it. |
| Snapshot (plain copy) | Order copies the lines and the Quote | The order is a legal record. It must not change when the catalogue does. | An order that points at live Products. Its total drifts after a price change. |
The engine, not the rules, decides stacking. Each rule knows only how much it would discount. The engine owns the policy: which rules run, in what order, and how coupons combine. If rules decided stacking, each would need to know about all the others.
Rules return adjustments instead of mutating totals. A rule says "I'd take 800 off BOOK". The engine applies it, caps it at zero and records it. Rules stay pure, the engine can run them on a copy to compare coupon combinations, and the quote explains itself line by line.
The stacking rule. All stackable coupons together, or exactly one exclusive coupon, whichever leaves the customer paying less. Losing and unknown codes go into rejectedCoupons, so the UI can say "SAVE15 beats WELCOME5 + EXTRA2". Fancier policies keep the same shape: generate combinations, price each on a copy, keep the best.
6. The code
All three versions implement the same design and run the same scenario. A cart has 2 books at $40, 3 pens at $2.50 and one mug at $12, so the gross is $99.50.
- "10% off books" takes $8.00. "Buy 2 pens, get 1 free" takes $2.50. That leaves a net of $89.00, which is below the $100 threshold.
- The buyer enters SAVE15 (exclusive, 15%) and WELCOME5 + EXTRA2 (stackable, $7 together). 15% of $89.00 is $13.35, which beats $7, so SAVE15 wins.
- Tax is per line (5% books, 10% the rest), so the $13.35 must be split across lines. Naive division loses cents.
allocategives each line its floor share, then hands leftover cents to the largest remainders, so the parts always sum to the whole. The total is $80.16.
Money is always an integer number of cents. Percentages are in basis points, where 1000 bps is 10%, so pct_of never touches a float.
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicLong;
import java.util.function.*;
// ---------- money: every amount is a long in minor units (cents) ----------
final class Money {
static long pctOf(long amount, int bps) { return (amount * bps + 5_000) / 10_000; } // half-up, 1000 bps = 10%
/** Split amount in proportion to weights. The parts always sum to amount. */
static Map<String, Long> allocate(long amount, Map<String, Long> weights) {
long total = weights.values().stream().mapToLong(Long::longValue).sum();
Map<String, Long> shares = new LinkedHashMap<>();
weights.forEach((k, w) -> shares.put(k, total == 0 ? 0 : amount * w / total));
if (total == 0) return shares;
List<String> byRemainder = new ArrayList<>(weights.keySet());
byRemainder.sort(Comparator.<String>comparingLong(k -> -(amount * weights.get(k) % total)).thenComparing(k -> k));
long left = amount - shares.values().stream().mapToLong(Long::longValue).sum();
for (int i = 0; i < left; i++) shares.merge(byRemainder.get(i), 1L, Long::sum);
return shares;
}
}
record Product(String sku, long price, String category, int taxBps) {}
final class CartLine {
final Product product;
int qty;
CartLine(Product product, int qty) { this.product = product; this.qty = qty; }
long gross() { return product.price() * qty; }
}
final class Cart {
final String id, userId, region;
final Map<String, CartLine> lines = new LinkedHashMap<>();
final List<String> coupons = new ArrayList<>();
Cart(String id, String userId) { this(id, userId, "US"); }
Cart(String id, String userId, String region) { this.id = id; this.userId = userId; this.region = region; }
void add(Product p, int qty) {
if (qty <= 0) throw new IllegalArgumentException("qty must be positive");
lines.computeIfAbsent(p.sku(), k -> new CartLine(p, 0)).qty += qty;
}
void setQty(String sku, int qty) { if (qty <= 0) lines.remove(sku); else lines.get(sku).qty = qty; }
void applyCoupon(String code) { if (!coupons.contains(code)) coupons.add(code); }
}
// ---------- Specification: composable yes/no rules ----------
@FunctionalInterface
interface Spec<T> {
boolean ok(T t);
default Spec<T> and(Spec<T> o) { return t -> ok(t) && o.ok(t); }
default Spec<T> not() { return t -> !ok(t); }
static <T> Spec<T> any() { return t -> true; }
static Spec<CartLine> inCategory(String c) { return l -> l.product.category().equals(c); }
static Spec<PricingContext> netAtLeast(long n) { return ctx -> ctx.netTotal() >= n; }
}
// ---------- pricing: one Strategy per promotion ----------
record Adjustment(String rule, long amount, String sku) {} // sku == null means cart-level
final class PricingContext {
final Cart cart;
final Map<String, Long> lineNet;
final List<Adjustment> adjustments;
PricingContext(Cart cart, Map<String, Long> lineNet, List<Adjustment> adjustments) {
this.cart = cart; this.lineNet = new LinkedHashMap<>(lineNet); this.adjustments = new ArrayList<>(adjustments);
}
long netTotal() { return lineNet.values().stream().mapToLong(Long::longValue).sum(); }
}
interface PricingRule { List<Adjustment> discounts(PricingContext ctx); }
record PercentOff(String name, Spec<CartLine> spec, int bps) implements PricingRule {
public List<Adjustment> discounts(PricingContext ctx) {
return ctx.cart.lines.entrySet().stream().filter(e -> spec.ok(e.getValue()))
.map(e -> new Adjustment(name, Money.pctOf(ctx.lineNet.get(e.getKey()), bps), e.getKey())).toList();
}
}
record BuyXGetY(String name, String sku, int buy, int free) implements PricingRule {
public List<Adjustment> discounts(PricingContext ctx) {
CartLine line = ctx.cart.lines.get(sku);
long units = line == null ? 0 : (long) line.qty / (buy + free) * free;
return units == 0 ? List.of() : List.of(new Adjustment(name, units * line.product.price(), sku));
}
}
record AmountOff(String name, long amount, Spec<PricingContext> spec) implements PricingRule {
AmountOff(String name, long amount) { this(name, amount, Spec.any()); }
public List<Adjustment> discounts(PricingContext ctx) {
return spec.ok(ctx) ? List.of(new Adjustment(name, amount, null)) : List.of();
}
}
record Coupon(String code, PricingRule rule, boolean stackable, Spec<PricingContext> eligible) {
Coupon(String code, PricingRule rule, boolean stackable) { this(code, rule, stackable, Spec.any()); }
}
interface TaxPolicy { long tax(Cart cart, CartLine line, long net); }
record Quote(long subtotal, long discount, long tax, long total, List<Adjustment> adjustments,
List<String> appliedCoupons, List<String> rejectedCoupons) {}
/** Line promotions -> cart promotions -> coupons -> tax. Holds no per-request state. */
final class PricingEngine {
final List<PricingRule> lineRules, cartRules;
final Map<String, Coupon> coupons;
final TaxPolicy taxPolicy;
PricingEngine(List<PricingRule> lineRules, List<PricingRule> cartRules, Map<String, Coupon> coupons, TaxPolicy tax) {
this.lineRules = lineRules; this.cartRules = cartRules; this.coupons = new ConcurrentHashMap<>(coupons); this.taxPolicy = tax;
}
PricingEngine(List<PricingRule> lineRules, List<PricingRule> cartRules, Map<String, Coupon> coupons) {
this(lineRules, cartRules, coupons, (cart, line, net) -> Money.pctOf(net, line.product.taxBps()));
}
Quote quote(Cart cart) {
Map<String, Long> gross = new LinkedHashMap<>();
cart.lines.forEach((sku, line) -> gross.put(sku, line.gross()));
PricingContext ctx = new PricingContext(cart, gross, List.of());
lineRules.forEach(r -> apply(ctx, r));
cartRules.forEach(r -> apply(ctx, r));
List<String> applied = new ArrayList<>();
PricingContext best = bestCoupons(ctx, applied);
long tax = 0;
for (var e : best.lineNet.entrySet()) tax += taxPolicy.tax(cart, cart.lines.get(e.getKey()), e.getValue());
long subtotal = gross.values().stream().mapToLong(Long::longValue).sum(), net = best.netTotal();
List<String> rejected = cart.coupons.stream().filter(c -> !applied.contains(c)).toList();
return new Quote(subtotal, subtotal - net, tax, net + tax, List.copyOf(best.adjustments), List.copyOf(applied), rejected);
}
/** Stacking rule: every stackable coupon together, OR one exclusive coupon. Cheapest wins. */
private PricingContext bestCoupons(PricingContext ctx, List<String> applied) {
List<Coupon> usable = ctx.cart.coupons.stream().map(coupons::get)
.filter(c -> c != null && c.eligible().ok(ctx)).toList();
List<List<Coupon>> options = new ArrayList<>(List.of(usable.stream().filter(Coupon::stackable).toList()));
usable.stream().filter(c -> !c.stackable()).forEach(c -> options.add(List.of(c)));
PricingContext best = ctx;
for (List<Coupon> option : options) {
PricingContext trial = new PricingContext(ctx.cart, ctx.lineNet, ctx.adjustments);
option.forEach(c -> apply(trial, c.rule()));
if (trial.netTotal() < best.netTotal()) {
best = trial;
applied.clear();
option.forEach(c -> applied.add(c.code()));
}
}
return best;
}
static void apply(PricingContext ctx, PricingRule rule) {
for (Adjustment adj : rule.discounts(ctx)) {
long amount;
if (adj.sku() != null) {
amount = Math.min(adj.amount(), ctx.lineNet.get(adj.sku())); // a line never goes negative
ctx.lineNet.merge(adj.sku(), -amount, Long::sum);
} else {
amount = Math.min(adj.amount(), ctx.netTotal()); // nor does the cart
Money.allocate(amount, ctx.lineNet).forEach((sku, part) -> ctx.lineNet.merge(sku, -part, Long::sum));
}
if (amount > 0) ctx.adjustments.add(new Adjustment(adj.rule(), amount, adj.sku()));
}
}
}
// ---------- inventory with expiring reservations ----------
final class OutOfStockException extends RuntimeException { OutOfStockException(Object s) { super("out of stock: " + s); } }
final class ReservationExpiredException extends RuntimeException { ReservationExpiredException(String id) { super(id); } }
final class Inventory {
private record Hold(Map<String, Integer> items, long expiresAt) {}
private final LongSupplier clock;
private final Map<String, Integer> onHand = new HashMap<>(), reserved = new HashMap<>();
private final Map<String, Hold> holds = new HashMap<>();
Inventory(LongSupplier clockMillis) { this.clock = clockMillis; }
Inventory() { this(System::currentTimeMillis); }
synchronized void addStock(String sku, int qty) { onHand.merge(sku, qty, Integer::sum); }
synchronized int available(String sku) { purge(); return free(sku); }
/** Check and hold under one lock: all or nothing. */
synchronized void reserve(String resId, Map<String, Integer> items, long ttlMillis) {
purge();
List<String> shortSkus = items.keySet().stream().filter(s -> free(s) < items.get(s)).toList();
if (!shortSkus.isEmpty()) throw new OutOfStockException(shortSkus);
items.forEach((s, q) -> reserved.merge(s, q, Integer::sum));
holds.put(resId, new Hold(Map.copyOf(items), clock.getAsLong() + ttlMillis));
}
synchronized void commit(String resId) {
purge();
Hold h = holds.remove(resId);
if (h == null) throw new ReservationExpiredException(resId);
h.items().forEach((s, q) -> { reserved.merge(s, -q, Integer::sum); onHand.merge(s, -q, Integer::sum); });
}
synchronized void release(String resId) { drop(resId); }
private int free(String sku) { return onHand.getOrDefault(sku, 0) - reserved.getOrDefault(sku, 0); }
private void drop(String resId) {
Hold h = holds.remove(resId);
if (h != null) h.items().forEach((s, q) -> reserved.merge(s, -q, Integer::sum));
}
private void purge() { // Simplification: linear scan, use a min-heap on expiry when holds number in the thousands
long now = clock.getAsLong();
holds.entrySet().stream().filter(e -> e.getValue().expiresAt() <= now).map(Map.Entry::getKey).toList().forEach(this::drop);
}
}
// ---------- order state machine ----------
enum Status {
PENDING_PAYMENT, PAID, SHIPPED, DELIVERED, CANCELLED;
boolean canMoveTo(Status next) {
return switch (this) {
case PENDING_PAYMENT -> next == PAID || next == CANCELLED;
case PAID -> next == SHIPPED || next == CANCELLED;
case SHIPPED -> next == DELIVERED;
case DELIVERED, CANCELLED -> false;
};
}
}
final class IllegalTransitionException extends RuntimeException { IllegalTransitionException(String m) { super(m); } }
final class Order {
final String id, userId;
final Map<String, long[]> lines; // sku -> {qty, unit price}, a snapshot taken at checkout
final Quote quote;
private Status status = Status.PENDING_PAYMENT;
Order(String id, String userId, Map<String, long[]> lines, Quote quote) {
this.id = id; this.userId = userId; this.lines = lines; this.quote = quote;
}
synchronized Status status() { return status; }
synchronized void transition(Status to) {
if (!status.canMoveTo(to)) throw new IllegalTransitionException(status + " -> " + to);
status = to;
}
}
// ---------- payment and checkout ----------
interface PaymentGateway { boolean charge(String idempotencyKey, long amount); }
final class FakeGateway implements PaymentGateway {
final boolean approve;
final Map<String, Long> charges = new ConcurrentHashMap<>();
FakeGateway(boolean approve) { this.approve = approve; }
public boolean charge(String key, long amount) {
if (approve) charges.putIfAbsent(key, amount); // real gateways dedupe on the key too
return approve;
}
}
final class IdempotencyConflictException extends RuntimeException { IdempotencyConflictException(String k) { super(k); } }
final class CheckoutService {
private record Result(String cartId, Order order) {}
final PricingEngine engine;
final Inventory inventory;
final PaymentGateway gateway;
final List<Consumer<Order>> onPaid = new CopyOnWriteArrayList<>(); // observers
private final long ttlMillis;
private final Map<String, Result> results = new ConcurrentHashMap<>();
private final Map<String, Object> keyLocks = new ConcurrentHashMap<>(); // Simplification: evict after the 24h key window
private final AtomicLong seq = new AtomicLong();
CheckoutService(PricingEngine engine, Inventory inventory, PaymentGateway gateway, long ttlMillis) {
this.engine = engine; this.inventory = inventory; this.gateway = gateway; this.ttlMillis = ttlMillis;
}
Order checkout(Cart cart, String key) {
synchronized (keyLocks.computeIfAbsent(key, k -> new Object())) { // a duplicate request waits, then replays
Result done = results.get(key);
if (done != null) {
if (!done.cartId().equals(cart.id)) throw new IdempotencyConflictException(key);
return done.order();
}
Order order = place(cart);
results.put(key, new Result(cart.id, order));
return order;
}
}
private Order place(Cart cart) {
if (cart.lines.isEmpty()) throw new IllegalStateException("cart is empty");
Quote quote = engine.quote(cart);
String orderId = "ord-" + seq.incrementAndGet();
Map<String, Integer> items = new LinkedHashMap<>();
Map<String, long[]> snapshot = new LinkedHashMap<>();
cart.lines.forEach((sku, l) -> { items.put(sku, l.qty); snapshot.put(sku, new long[]{l.qty, l.product.price()}); });
inventory.reserve(orderId, items, ttlMillis);
Order order = new Order(orderId, cart.userId, snapshot, quote);
if (gateway.charge(orderId, quote.total())) {
inventory.commit(orderId);
order.transition(Status.PAID);
cart.lines.clear();
cart.coupons.clear();
onPaid.forEach(l -> l.accept(order));
} else {
inventory.release(orderId);
order.transition(Status.CANCELLED);
}
return order;
}
}
public class Main {
record Shop(Map<String, Product> catalog, CheckoutService service) {}
static Shop buildShop(PaymentGateway gateway) {
Map<String, Product> catalog = new LinkedHashMap<>();
for (Product p : List.of(new Product("BOOK", 4000, "books", 500), new Product("PEN", 250, "stationery", 1000),
new Product("MUG", 1200, "kitchen", 1000))) catalog.put(p.sku(), p);
PricingEngine engine = new PricingEngine(
List.of(new PercentOff("books-10", Spec.inCategory("books"), 1000), new BuyXGetY("pens-3-for-2", "PEN", 2, 1)),
List.of(new AmountOff("spend-100-save-5", 500, Spec.netAtLeast(10_000))),
Map.of("SAVE15", new Coupon("SAVE15", new PercentOff("SAVE15", Spec.any(), 1500), false),
"WELCOME5", new Coupon("WELCOME5", new AmountOff("WELCOME5", 500), true),
"EXTRA2", new Coupon("EXTRA2", new AmountOff("EXTRA2", 200), true)));
Inventory inventory = new Inventory();
inventory.addStock("BOOK", 10); inventory.addStock("PEN", 100); inventory.addStock("MUG", 1);
return new Shop(catalog, new CheckoutService(engine, inventory, gateway, 600_000));
}
public static void main(String[] args) {
Shop shop = buildShop(new FakeGateway(true));
Cart cart = new Cart("c1", "alice");
cart.add(shop.catalog().get("BOOK"), 2);
cart.add(shop.catalog().get("PEN"), 3);
cart.add(shop.catalog().get("MUG"), 1);
Quote q = shop.service().engine.quote(cart);
assert q.subtotal() == 9950 && q.discount() == 1050 && q.tax() == 530 && q.total() == 9430 : q;
List.of("SAVE15", "WELCOME5", "EXTRA2").forEach(cart::applyCoupon);
q = shop.service().engine.quote(cart);
assert q.appliedCoupons().equals(List.of("SAVE15")) && q.rejectedCoupons().equals(List.of("WELCOME5", "EXTRA2"));
assert q.discount() == 2385 && q.tax() == 451 && q.total() == 8016 : q;
Order order = shop.service().checkout(cart, "key-1");
assert order.status() == Status.PAID && order.quote.total() == 8016;
assert shop.service().checkout(cart, "key-1") == order; // retry replays
assert ((FakeGateway) shop.service().gateway).charges.size() == 1;
assert shop.service().inventory.available("MUG") == 0;
System.out.println("Main.java: all assertions passed");
}
}
from __future__ import annotations
import threading
import time
from dataclasses import dataclass, field
from enum import Enum
from typing import Callable, Generic, Protocol, TypeVar
T = TypeVar("T")
# ---------- money: every amount is an int in minor units (cents) ----------
def pct_of(amount: int, bps: int) -> int:
return (amount * bps + 5_000) // 10_000 # half-up, 1000 bps = 10%
def allocate(amount: int, weights: dict[str, int]) -> dict[str, int]:
"""Split amount in proportion to weights. The parts always sum to amount."""
total = sum(weights.values())
if total == 0:
return {k: 0 for k in weights}
shares = {k: amount * w // total for k, w in weights.items()}
by_remainder = sorted(weights, key=lambda k: (-(amount * weights[k] % total), k))
for k in by_remainder[: amount - sum(shares.values())]:
shares[k] += 1
return shares
@dataclass(frozen=True)
class Product:
sku: str
price: int
category: str
tax_bps: int
@dataclass
class CartLine:
product: Product
qty: int
@property
def gross(self) -> int:
return self.product.price * self.qty
class Cart:
def __init__(self, cart_id: str, user_id: str, region: str = "US") -> None:
self.id, self.user_id, self.region = cart_id, user_id, region
self.lines: dict[str, CartLine] = {}
self.coupons: list[str] = []
def add(self, product: Product, qty: int = 1) -> None:
if qty <= 0:
raise ValueError("qty must be positive")
self.lines.setdefault(product.sku, CartLine(product, 0)).qty += qty
def set_qty(self, sku: str, qty: int) -> None:
if qty <= 0:
self.lines.pop(sku, None)
else:
self.lines[sku].qty = qty
def apply_coupon(self, code: str) -> None:
if code not in self.coupons:
self.coupons.append(code)
# ---------- Specification: composable yes/no rules ----------
class Spec(Generic[T]):
def __init__(self, test: Callable[[T], bool]) -> None:
self.ok = test
def __and__(self, o: Spec[T]) -> Spec[T]:
return Spec(lambda x: self.ok(x) and o.ok(x))
def __invert__(self) -> Spec[T]:
return Spec(lambda x: not self.ok(x))
ANY: Spec = Spec(lambda _: True)
def in_category(cat: str) -> Spec[CartLine]:
return Spec(lambda line: line.product.category == cat)
def net_at_least(amount: int) -> Spec[PricingContext]:
return Spec(lambda ctx: ctx.net_total() >= amount)
# ---------- pricing: one Strategy per promotion ----------
@dataclass(frozen=True)
class Adjustment:
rule: str
amount: int
sku: str | None = None # None = cart-level
@dataclass
class PricingContext:
cart: Cart
line_net: dict[str, int]
adjustments: list[Adjustment] = field(default_factory=list)
def net_total(self) -> int:
return sum(self.line_net.values())
class PricingRule(Protocol):
def discounts(self, ctx: PricingContext) -> list[Adjustment]: ...
@dataclass(frozen=True)
class PercentOff:
name: str
spec: Spec[CartLine]
bps: int
def discounts(self, ctx: PricingContext) -> list[Adjustment]:
return [Adjustment(self.name, pct_of(ctx.line_net[sku], self.bps), sku)
for sku, line in ctx.cart.lines.items() if self.spec.ok(line)]
@dataclass(frozen=True)
class BuyXGetY:
name: str
sku: str
buy: int
free: int
def discounts(self, ctx: PricingContext) -> list[Adjustment]:
line = ctx.cart.lines.get(self.sku)
units = line.qty // (self.buy + self.free) * self.free if line else 0
return [Adjustment(self.name, units * line.product.price, self.sku)] if line and units else []
@dataclass(frozen=True)
class AmountOff:
name: str
amount: int
spec: Spec[PricingContext] = ANY
def discounts(self, ctx: PricingContext) -> list[Adjustment]:
return [Adjustment(self.name, self.amount)] if self.spec.ok(ctx) else []
@dataclass(frozen=True)
class Coupon:
code: str
rule: PricingRule
stackable: bool
eligible: Spec[PricingContext] = ANY
class TaxPolicy(Protocol):
def tax(self, cart: Cart, line: CartLine, net: int) -> int: ...
class ProductRateTax:
def tax(self, cart: Cart, line: CartLine, net: int) -> int:
return pct_of(net, line.product.tax_bps)
@dataclass(frozen=True)
class Quote:
subtotal: int
discount: int
tax: int
total: int
adjustments: tuple[Adjustment, ...]
applied_coupons: tuple[str, ...]
rejected_coupons: tuple[str, ...]
class PricingEngine:
"""Line promotions -> cart promotions -> coupons -> tax. Holds no per-request state."""
def __init__(self, line_rules: list, cart_rules: list, coupons: dict[str, Coupon],
tax: TaxPolicy = ProductRateTax()) -> None:
self.line_rules, self.cart_rules, self.coupons, self.tax_policy = line_rules, cart_rules, coupons, tax
def quote(self, cart: Cart) -> Quote:
ctx = PricingContext(cart, {sku: line.gross for sku, line in cart.lines.items()})
for rule in self.line_rules + self.cart_rules:
apply_rule(ctx, rule)
ctx, applied = self._best_coupons(ctx, cart.coupons)
tax = sum(self.tax_policy.tax(cart, cart.lines[s], net) for s, net in ctx.line_net.items())
subtotal, net = sum(l.gross for l in cart.lines.values()), ctx.net_total()
rejected = tuple(c for c in cart.coupons if c not in applied)
return Quote(subtotal, subtotal - net, tax, net + tax, tuple(ctx.adjustments), tuple(applied), rejected)
def _best_coupons(self, ctx: PricingContext, codes: list[str]) -> tuple[PricingContext, list[str]]:
usable = [self.coupons[c] for c in codes if c in self.coupons and self.coupons[c].eligible.ok(ctx)]
# Stacking rule: every stackable coupon together, OR one exclusive coupon. Cheapest wins.
options = [[c for c in usable if c.stackable]] + [[c] for c in usable if not c.stackable]
best, best_codes = ctx, []
for option in options:
trial = PricingContext(ctx.cart, dict(ctx.line_net), list(ctx.adjustments))
for coupon in option:
apply_rule(trial, coupon.rule)
if trial.net_total() < best.net_total():
best, best_codes = trial, [c.code for c in option]
return best, best_codes
def apply_rule(ctx: PricingContext, rule: PricingRule) -> None:
for adj in rule.discounts(ctx):
if adj.sku is not None:
amount = min(adj.amount, ctx.line_net[adj.sku]) # a line never goes negative
ctx.line_net[adj.sku] -= amount
else:
amount = min(adj.amount, ctx.net_total()) # nor does the cart
for sku, part in allocate(amount, ctx.line_net).items():
ctx.line_net[sku] -= part
if amount:
ctx.adjustments.append(Adjustment(adj.rule, amount, adj.sku))
# ---------- inventory with expiring reservations ----------
class OutOfStock(Exception):
pass
class ReservationExpired(Exception):
pass
class Inventory:
def __init__(self, clock: Callable[[], float] = time.monotonic) -> None:
self._clock, self._lock = clock, threading.Lock()
self._on_hand: dict[str, int] = {}
self._reserved: dict[str, int] = {}
self._holds: dict[str, tuple[dict[str, int], float]] = {} # id -> (items, expires_at)
def add_stock(self, sku: str, qty: int) -> None:
with self._lock:
self._on_hand[sku] = self._on_hand.get(sku, 0) + qty
def available(self, sku: str) -> int:
with self._lock:
self._purge()
return self._on_hand.get(sku, 0) - self._reserved.get(sku, 0)
def reserve(self, res_id: str, items: dict[str, int], ttl: float) -> None:
with self._lock: # check and hold under one lock: all or nothing
self._purge()
short = [s for s, q in items.items() if self._on_hand.get(s, 0) - self._reserved.get(s, 0) < q]
if short:
raise OutOfStock(short)
for s, q in items.items():
self._reserved[s] = self._reserved.get(s, 0) + q
self._holds[res_id] = (dict(items), self._clock() + ttl)
def commit(self, res_id: str) -> None:
with self._lock:
self._purge()
if res_id not in self._holds:
raise ReservationExpired(res_id)
for s, q in self._holds.pop(res_id)[0].items():
self._reserved[s] -= q
self._on_hand[s] -= q
def release(self, res_id: str) -> None:
with self._lock:
self._drop(res_id)
def _drop(self, res_id: str) -> None:
for s, q in self._holds.pop(res_id, ({}, 0))[0].items():
self._reserved[s] -= q
def _purge(self) -> None:
# Simplification: linear scan, use a min-heap on expiry when holds number in the thousands
now = self._clock()
for res_id in [r for r, (_, exp) in self._holds.items() if exp <= now]:
self._drop(res_id)
# ---------- order state machine ----------
class Status(Enum):
PENDING_PAYMENT = 1
PAID = 2
SHIPPED = 3
DELIVERED = 4
CANCELLED = 5
ALLOWED = {
Status.PENDING_PAYMENT: {Status.PAID, Status.CANCELLED},
Status.PAID: {Status.SHIPPED, Status.CANCELLED},
Status.SHIPPED: {Status.DELIVERED},
Status.DELIVERED: set(),
Status.CANCELLED: set(),
}
class IllegalTransition(Exception):
pass
class Order:
def __init__(self, order_id: str, user_id: str, lines: dict[str, tuple[int, int]], quote: Quote) -> None:
self.id, self.user_id, self.lines, self.quote = order_id, user_id, lines, quote # sku -> (qty, unit price)
self.status = Status.PENDING_PAYMENT
self._lock = threading.Lock()
def transition(self, to: Status) -> None:
with self._lock:
if to not in ALLOWED[self.status]:
raise IllegalTransition(f"{self.status.name} -> {to.name}")
self.status = to
# ---------- payment and checkout ----------
class PaymentGateway(Protocol):
def charge(self, idempotency_key: str, amount: int) -> bool: ...
class FakeGateway:
def __init__(self, approve: bool = True) -> None:
self.approve, self.charges = approve, {}
def charge(self, idempotency_key: str, amount: int) -> bool:
if self.approve:
self.charges.setdefault(idempotency_key, amount) # real gateways dedupe on the key too
return self.approve
class IdempotencyConflict(Exception):
pass
class CheckoutService:
def __init__(self, engine: PricingEngine, inventory: Inventory, gateway: PaymentGateway, ttl: float = 600) -> None:
self.engine, self.inventory, self.gateway, self.ttl = engine, inventory, gateway, ttl
self.on_paid: list[Callable[[Order], None]] = [] # observers
self._results: dict[str, tuple[str, Order]] = {} # key -> (cart id, order)
self._key_locks: dict[str, threading.Lock] = {} # Simplification: evict after the 24h key window
self._guard = threading.Lock()
self._seq = 0
def checkout(self, cart: Cart, key: str) -> Order:
with self._guard:
key_lock = self._key_locks.setdefault(key, threading.Lock())
with key_lock: # a duplicate request waits, then replays
if key in self._results:
cart_id, order = self._results[key]
if cart_id != cart.id:
raise IdempotencyConflict(key)
return order
order = self._place(cart)
self._results[key] = (cart.id, order)
return order
def _place(self, cart: Cart) -> Order:
if not cart.lines:
raise ValueError("cart is empty")
quote = self.engine.quote(cart)
with self._guard:
self._seq += 1
order_id = f"ord-{self._seq}"
self.inventory.reserve(order_id, {s: l.qty for s, l in cart.lines.items()}, self.ttl)
order = Order(order_id, cart.user_id, {s: (l.qty, l.product.price) for s, l in cart.lines.items()}, quote)
if self.gateway.charge(order_id, quote.total):
self.inventory.commit(order_id)
order.transition(Status.PAID)
cart.lines.clear()
cart.coupons.clear()
for listener in self.on_paid:
listener(order)
else:
self.inventory.release(order_id)
order.transition(Status.CANCELLED)
return order
def build_shop(gateway: PaymentGateway | None = None) -> tuple[dict[str, Product], CheckoutService]:
catalog = {p.sku: p for p in [Product("BOOK", 4000, "books", 500),
Product("PEN", 250, "stationery", 1000),
Product("MUG", 1200, "kitchen", 1000)]}
engine = PricingEngine(
[PercentOff("books-10", in_category("books"), 1000), BuyXGetY("pens-3-for-2", "PEN", 2, 1)],
[AmountOff("spend-100-save-5", 500, net_at_least(10_000))],
{"SAVE15": Coupon("SAVE15", PercentOff("SAVE15", ANY, 1500), stackable=False),
"WELCOME5": Coupon("WELCOME5", AmountOff("WELCOME5", 500), stackable=True),
"EXTRA2": Coupon("EXTRA2", AmountOff("EXTRA2", 200), stackable=True)})
inventory = Inventory()
for sku, qty in [("BOOK", 10), ("PEN", 100), ("MUG", 1)]:
inventory.add_stock(sku, qty)
return catalog, CheckoutService(engine, inventory, gateway or FakeGateway())
if __name__ == "__main__":
catalog, shop = build_shop()
cart = Cart("c1", "alice")
cart.add(catalog["BOOK"], 2)
cart.add(catalog["PEN"], 3)
cart.add(catalog["MUG"])
q = shop.engine.quote(cart)
assert (q.subtotal, q.discount, q.tax, q.total) == (9950, 1050, 530, 9430), q
for code in ["SAVE15", "WELCOME5", "EXTRA2"]:
cart.apply_coupon(code)
q = shop.engine.quote(cart)
assert q.applied_coupons == ("SAVE15",) and q.rejected_coupons == ("WELCOME5", "EXTRA2")
assert (q.discount, q.tax, q.total) == (2385, 451, 8016), q
order = shop.checkout(cart, "key-1")
assert order.status is Status.PAID and order.quote.total == 8016
assert shop.checkout(cart, "key-1") is order and len(shop.gateway.charges) == 1 # retry replays
assert shop.inventory.available("MUG") == 0
print("cart.py: all assertions passed")
import assert from "node:assert/strict";
// ---------- money: integer minor units (cents). Exact up to 2^53, use bigint beyond. ----------
export const pctOf = (amount: number, bps: number) => Math.floor((amount * bps + 5_000) / 10_000); // half-up
/** Split amount in proportion to weights. The parts always sum to amount. */
export function allocate(amount: number, weights: Map<string, number>): Map<string, number> {
const total = [...weights.values()].reduce((a, b) => a + b, 0);
const shares = new Map([...weights].map(([k, w]) => [k, total ? Math.floor((amount * w) / total) : 0]));
if (!total) return shares;
const rem = (k: string) => (amount * weights.get(k)!) % total;
const byRemainder = [...weights.keys()].sort((a, b) => rem(b) - rem(a) || a.localeCompare(b));
const left = amount - [...shares.values()].reduce((a, b) => a + b, 0);
for (let i = 0; i < left; i++) shares.set(byRemainder[i], shares.get(byRemainder[i])! + 1);
return shares;
}
export interface Product { readonly sku: string; readonly price: number; readonly category: string; readonly taxBps: number }
export class CartLine {
constructor(readonly product: Product, public qty: number) {}
get gross(): number { return this.product.price * this.qty; }
}
export class Cart {
readonly lines = new Map<string, CartLine>();
readonly coupons: string[] = [];
constructor(readonly id: string, readonly userId: string, readonly region = "US") {}
add(p: Product, qty = 1): void {
if (!Number.isInteger(qty) || qty <= 0) throw new Error("qty must be a positive integer");
const line = this.lines.get(p.sku) ?? new CartLine(p, 0);
line.qty += qty;
this.lines.set(p.sku, line);
}
setQty(sku: string, qty: number): void { if (qty <= 0) this.lines.delete(sku); else this.lines.get(sku)!.qty = qty; }
applyCoupon(code: string): void { if (!this.coupons.includes(code)) this.coupons.push(code); }
}
// ---------- Specification: composable yes/no rules ----------
export class Spec<T> {
constructor(readonly ok: (t: T) => boolean) {}
and(o: Spec<T>): Spec<T> { return new Spec((t) => this.ok(t) && o.ok(t)); }
not(): Spec<T> { return new Spec((t) => !this.ok(t)); }
static any<T>(): Spec<T> { return new Spec<T>(() => true); }
}
export const inCategory = (c: string) => new Spec<CartLine>((l) => l.product.category === c);
export const netAtLeast = (n: number) => new Spec<PricingContext>((ctx) => ctx.netTotal() >= n);
// ---------- pricing: one Strategy per promotion ----------
export interface Adjustment { readonly rule: string; readonly amount: number; readonly sku: string | null } // null = cart-level
export class PricingContext {
constructor(readonly cart: Cart, readonly lineNet: Map<string, number>, readonly adjustments: Adjustment[] = []) {}
netTotal(): number { return [...this.lineNet.values()].reduce((a, b) => a + b, 0); }
}
export interface PricingRule { discounts(ctx: PricingContext): Adjustment[] }
export class PercentOff implements PricingRule {
constructor(readonly name: string, readonly spec: Spec<CartLine>, readonly bps: number) {}
discounts(ctx: PricingContext): Adjustment[] {
return [...ctx.cart.lines].filter(([, l]) => this.spec.ok(l))
.map(([sku]) => ({ rule: this.name, amount: pctOf(ctx.lineNet.get(sku)!, this.bps), sku }));
}
}
export class BuyXGetY implements PricingRule {
constructor(readonly name: string, readonly sku: string, readonly buy: number, readonly free: number) {}
discounts(ctx: PricingContext): Adjustment[] {
const line = ctx.cart.lines.get(this.sku);
const units = line ? Math.floor(line.qty / (this.buy + this.free)) * this.free : 0;
return line && units ? [{ rule: this.name, amount: units * line.product.price, sku: this.sku }] : [];
}
}
export class AmountOff implements PricingRule {
constructor(readonly name: string, readonly amount: number, readonly spec = Spec.any<PricingContext>()) {}
discounts(ctx: PricingContext): Adjustment[] {
return this.spec.ok(ctx) ? [{ rule: this.name, amount: this.amount, sku: null }] : [];
}
}
export interface Coupon { readonly code: string; readonly rule: PricingRule; readonly stackable: boolean; readonly eligible?: Spec<PricingContext> }
export interface TaxPolicy { tax(cart: Cart, line: CartLine, net: number): number }
export const productRateTax: TaxPolicy = { tax: (_cart, line, net) => pctOf(net, line.product.taxBps) };
export interface Quote {
readonly subtotal: number; readonly discount: number; readonly tax: number; readonly total: number;
readonly adjustments: readonly Adjustment[]; readonly appliedCoupons: readonly string[]; readonly rejectedCoupons: readonly string[];
}
/** Line promotions -> cart promotions -> coupons -> tax. Holds no per-request state. */
export class PricingEngine {
constructor(readonly lineRules: PricingRule[], readonly cartRules: PricingRule[],
readonly coupons: Map<string, Coupon>, readonly taxPolicy: TaxPolicy = productRateTax) {}
quote(cart: Cart): Quote {
const ctx = new PricingContext(cart, new Map([...cart.lines].map(([sku, l]) => [sku, l.gross])));
for (const rule of [...this.lineRules, ...this.cartRules]) applyRule(ctx, rule);
const [best, applied] = this.bestCoupons(ctx);
let tax = 0;
for (const [sku, net] of best.lineNet) tax += this.taxPolicy.tax(cart, cart.lines.get(sku)!, net);
const subtotal = [...cart.lines.values()].reduce((a, l) => a + l.gross, 0);
const net = best.netTotal();
return { subtotal, discount: subtotal - net, tax, total: net + tax, adjustments: best.adjustments,
appliedCoupons: applied, rejectedCoupons: cart.coupons.filter((c) => !applied.includes(c)) };
}
/** Stacking rule: every stackable coupon together, OR one exclusive coupon. Cheapest wins. */
private bestCoupons(ctx: PricingContext): [PricingContext, string[]] {
const usable = ctx.cart.coupons.map((c) => this.coupons.get(c))
.filter((c): c is Coupon => c !== undefined && (c.eligible?.ok(ctx) ?? true));
const options = [usable.filter((c) => c.stackable), ...usable.filter((c) => !c.stackable).map((c) => [c])];
let best = ctx;
let bestCodes: string[] = [];
for (const option of options) {
const trial = new PricingContext(ctx.cart, new Map(ctx.lineNet), [...ctx.adjustments]);
for (const c of option) applyRule(trial, c.rule);
if (trial.netTotal() < best.netTotal()) { best = trial; bestCodes = option.map((c) => c.code); }
}
return [best, bestCodes];
}
}
export function applyRule(ctx: PricingContext, rule: PricingRule): void {
for (const adj of rule.discounts(ctx)) {
let amount: number;
if (adj.sku !== null) {
amount = Math.min(adj.amount, ctx.lineNet.get(adj.sku)!); // a line never goes negative
ctx.lineNet.set(adj.sku, ctx.lineNet.get(adj.sku)! - amount);
} else {
amount = Math.min(adj.amount, ctx.netTotal()); // nor does the cart
for (const [sku, part] of allocate(amount, ctx.lineNet)) ctx.lineNet.set(sku, ctx.lineNet.get(sku)! - part);
}
if (amount > 0) ctx.adjustments.push({ ...adj, amount });
}
}
// ---------- inventory with expiring reservations ----------
export class OutOfStockError extends Error {}
export class ReservationExpiredError extends Error {}
export class Inventory {
private readonly onHand = new Map<string, number>();
private readonly reserved = new Map<string, number>();
private readonly holds = new Map<string, { items: Map<string, number>; expiresAt: number }>();
constructor(private readonly clock: () => number = Date.now) {}
addStock(sku: string, qty: number): void { this.onHand.set(sku, (this.onHand.get(sku) ?? 0) + qty); }
available(sku: string): number { this.purge(); return this.free(sku); }
/** Synchronous on purpose: no await between the check and the hold, so nothing can interleave. */
reserve(resId: string, items: Map<string, number>, ttlMs: number): void {
this.purge();
const short = [...items].filter(([s, q]) => this.free(s) < q).map(([s]) => s);
if (short.length) throw new OutOfStockError(`out of stock: ${short}`);
for (const [s, q] of items) this.reserved.set(s, (this.reserved.get(s) ?? 0) + q);
this.holds.set(resId, { items: new Map(items), expiresAt: this.clock() + ttlMs });
}
commit(resId: string): void {
this.purge();
const hold = this.holds.get(resId);
if (!hold) throw new ReservationExpiredError(resId);
this.release(resId);
for (const [s, q] of hold.items) this.onHand.set(s, this.onHand.get(s)! - q);
}
release(resId: string): void {
for (const [s, q] of this.holds.get(resId)?.items ?? []) this.reserved.set(s, this.reserved.get(s)! - q);
this.holds.delete(resId);
}
private free(sku: string): number { return (this.onHand.get(sku) ?? 0) - (this.reserved.get(sku) ?? 0); }
private purge(): void { // Simplification: linear scan, use a min-heap on expiry when holds number in the thousands
for (const [id, h] of [...this.holds]) if (h.expiresAt <= this.clock()) this.release(id);
}
}
// ---------- order state machine ----------
export type Status = "PENDING_PAYMENT" | "PAID" | "SHIPPED" | "DELIVERED" | "CANCELLED";
const ALLOWED: Record<Status, readonly Status[]> = {
PENDING_PAYMENT: ["PAID", "CANCELLED"], PAID: ["SHIPPED", "CANCELLED"], SHIPPED: ["DELIVERED"], DELIVERED: [], CANCELLED: [],
};
export class IllegalTransitionError extends Error {}
export class Order {
status: Status = "PENDING_PAYMENT";
constructor(readonly id: string, readonly userId: string,
readonly lines: ReadonlyMap<string, { qty: number; unitPrice: number }>, readonly quote: Quote) {}
transition(to: Status): void {
if (!ALLOWED[this.status].includes(to)) throw new IllegalTransitionError(`${this.status} -> ${to}`);
this.status = to;
}
}
// ---------- payment and checkout ----------
export interface PaymentGateway { charge(idempotencyKey: string, amount: number): Promise<boolean> }
export class FakeGateway implements PaymentGateway {
readonly charges = new Map<string, number>();
constructor(readonly approve = true) {}
async charge(key: string, amount: number): Promise<boolean> {
await new Promise((r) => setTimeout(r, 5)); // network round trip
if (this.approve && !this.charges.has(key)) this.charges.set(key, amount);
return this.approve;
}
}
export class IdempotencyConflictError extends Error {}
export class CheckoutService {
readonly onPaid: Array<(o: Order) => void> = []; // observers
private readonly attempts = new Map<string, { cartId: string; result: Promise<Order> }>(); // Simplification: evict after 24h
private seq = 0;
constructor(readonly engine: PricingEngine, readonly inventory: Inventory, readonly gateway: PaymentGateway,
private readonly ttlMs = 600_000) {}
/** Storing the promise (not the order) makes a concurrent duplicate await the same attempt. */
checkout(cart: Cart, key: string): Promise<Order> {
const prior = this.attempts.get(key);
if (prior) return prior.cartId === cart.id ? prior.result : Promise.reject(new IdempotencyConflictError(key));
const result = this.place(cart);
this.attempts.set(key, { cartId: cart.id, result });
result.catch(() => this.attempts.delete(key)); // no order was created, so a retry may run
return result;
}
private async place(cart: Cart): Promise<Order> {
if (cart.lines.size === 0) throw new Error("cart is empty");
const quote = this.engine.quote(cart);
const orderId = `ord-${++this.seq}`;
this.inventory.reserve(orderId, new Map([...cart.lines].map(([s, l]) => [s, l.qty])), this.ttlMs);
const order = new Order(orderId, cart.userId,
new Map([...cart.lines].map(([s, l]) => [s, { qty: l.qty, unitPrice: l.product.price }])), quote);
if (await this.gateway.charge(orderId, quote.total)) {
this.inventory.commit(orderId);
order.transition("PAID");
cart.lines.clear();
cart.coupons.length = 0;
for (const listener of this.onPaid) listener(order);
} else {
this.inventory.release(orderId);
order.transition("CANCELLED");
}
return order;
}
}
export function buildShop(gateway: PaymentGateway = new FakeGateway()) {
const catalog = new Map<string, Product>([
{ sku: "BOOK", price: 4000, category: "books", taxBps: 500 },
{ sku: "PEN", price: 250, category: "stationery", taxBps: 1000 },
{ sku: "MUG", price: 1200, category: "kitchen", taxBps: 1000 },
].map((p) => [p.sku, p]));
const engine = new PricingEngine(
[new PercentOff("books-10", inCategory("books"), 1000), new BuyXGetY("pens-3-for-2", "PEN", 2, 1)],
[new AmountOff("spend-100-save-5", 500, netAtLeast(10_000))],
new Map<string, Coupon>([
["SAVE15", { code: "SAVE15", rule: new PercentOff("SAVE15", Spec.any(), 1500), stackable: false }],
["WELCOME5", { code: "WELCOME5", rule: new AmountOff("WELCOME5", 500), stackable: true }],
["EXTRA2", { code: "EXTRA2", rule: new AmountOff("EXTRA2", 200), stackable: true }],
]));
const inventory = new Inventory();
inventory.addStock("BOOK", 10); inventory.addStock("PEN", 100); inventory.addStock("MUG", 1);
return { catalog, service: new CheckoutService(engine, inventory, gateway) };
}
if (process.argv[1]?.endsWith("cart.ts")) {
const { catalog, service } = buildShop();
const cart = new Cart("c1", "alice");
cart.add(catalog.get("BOOK")!, 2); cart.add(catalog.get("PEN")!, 3); cart.add(catalog.get("MUG")!);
let q = service.engine.quote(cart);
assert.deepEqual([q.subtotal, q.discount, q.tax, q.total], [9950, 1050, 530, 9430]);
for (const c of ["SAVE15", "WELCOME5", "EXTRA2"]) cart.applyCoupon(c);
q = service.engine.quote(cart);
assert.deepEqual([q.appliedCoupons, q.rejectedCoupons], [["SAVE15"], ["WELCOME5", "EXTRA2"]]);
assert.deepEqual([q.discount, q.tax, q.total], [2385, 451, 8016]);
const [a, b] = await Promise.all([service.checkout(cart, "key-1"), service.checkout(cart, "key-1")]); // double click
assert.ok(a === b && a.status === "PAID");
assert.equal((service.gateway as FakeGateway).charges.size, 1);
assert.equal(service.inventory.available("MUG"), 0);
console.log("cart.ts: all assertions passed");
}
Run with java -ea, python or tsx. Each prints a success line only if every assertion holds.
7. Concurrency
Name the shared mutable state first.
| State | Shared by | Protection |
|---|---|---|
Inventory counts and holds | every checkout | one lock around each method (synchronized / threading.Lock) |
| idempotency results | duplicate requests with one key | a lock per key, held for the whole checkout |
Order.status | checkout, warehouse, support tools | lock inside transition |
PricingEngine | every quote | nothing, it's read-only |
Cart | one buyer's session | not shared, two tabs are last-write-wins |
Two buyers and the last item
sequenceDiagram
participant B as Bob
participant I as Inventory
participant C as Carol
Note over B,C: Broken: check and write are separate steps
B->>I: available(MUG) returns 1
C->>I: available(MUG) returns 1
B->>I: decrement
C->>I: decrement
Note over B,C: on hand is now -1, two orders for one mug
The bug is check-then-act. reserve makes the check and the write one atomic step, for every line at once, so a cart is never half-reserved. Bob takes the lock and holds the unit. Carol waits, sees zero and gets OutOfStock before her card is touched.
Three details make it correct:
- The payment call is outside the inventory lock. Holding it for a gateway round trip would serialise every checkout in the shop.
- The reservation makes releasing the lock safe. Between reserve and charge the unit is held, not sold, and it expires if we crash.
commitre-checks the hold. If the TTL passed during a slow payment,committhrowsReservationExpiredinstead of overselling. Production code then refunds or re-reserves.
Lock granularity. One inventory lock is correct and simple, but buyers of different products queue behind each other. If that shows up in profiling, lock per SKU and acquire the locks in sorted SKU order to avoid deadlock. In a database the same idea is UPDATE stock SET reserved = reserved + ? WHERE sku = ? AND on_hand - reserved >= ?, checking the affected row count.
Idempotency under concurrency. With a per-key lock, a duplicate request blocks, then finds and returns the stored order. Different keys don't block each other. A failure before an order exists (out of stock) stores nothing, so the same key may retry. A declined payment stores its cancelled order, so another card needs a new key. For the HTTP side of this, see idempotency in API design.
TypeScript is different. Node runs JavaScript on one thread, so the synchronous reserve can't interleave with another, which is why the TypeScript Inventory has no lock. The danger is an await between a check and a write. place awaits the gateway only after reserving. Put an await between the stock check and the hold and the race comes back. checkout stores the promise per key, so a same-tick double click awaits the first attempt.
8. The interviewer adds…
Each extension is one new class in an existing seam, with no edits to PricingEngine or CheckoutService.
"Buy any three books, the cheapest is free"
A new PricingRule. It expands matching lines into units, sorts by price and gives away the cheapest unit of each full group. Flags can't express this, because it compares items across lines.
import java.util.*;
/** "Buy any 3 books, the cheapest one is free." One new class, no edits to PricingEngine. */
record CheapestFreeInCategory(String name, String category, int groupSize) implements PricingRule {
public List<Adjustment> discounts(PricingContext ctx) {
List<CartLine> units = new ArrayList<>(); // one entry per physical unit
ctx.cart.lines.values().stream().filter(l -> l.product.category().equals(category))
.forEach(l -> { for (int i = 0; i < l.qty; i++) units.add(l); });
units.sort(Comparator.comparingLong((CartLine l) -> l.product.price()).reversed());
Map<String, Long> perSku = new LinkedHashMap<>(); // every full group gives away its cheapest unit
for (int i = groupSize - 1; i < units.size(); i += groupSize)
perSku.merge(units.get(i).product.sku(), units.get(i).product.price(), Long::sum);
return perSku.entrySet().stream().map(e -> new Adjustment(name, e.getValue(), e.getKey())).toList();
}
}
public class ExtCheapestFree {
public static void main(String[] args) {
PricingEngine engine = new PricingEngine(List.of(new CheapestFreeInCategory("3-for-2-books", "books", 3)), List.of(), Map.of());
Cart cart = new Cart("c", "u");
cart.add(new Product("TOME", 6000, "books", 0), 2);
cart.add(new Product("NOVEL", 2000, "books", 0), 1);
cart.add(new Product("ZINE", 500, "books", 0), 3); // units by price: 6000 6000 2000 | 500 500 500
assert engine.quote(cart).discount() == 2000 + 500;
System.out.println("ExtCheapestFree: ok");
}
}
If "10% off books" also runs, rule order decides whether the free book is worth its full or discounted price. Agree it with the product owner and pin it with a test.
"Each buyer can redeem FIRST10 once"
Eligibility is a Specification, and recording a redemption is an on_paid observer.
import threading
from cart import AmountOff, Cart, Coupon, Order, Spec, build_shop
class CouponLedger:
"""Remembers which buyer has redeemed which single-use coupon."""
def __init__(self) -> None:
self._used: set[tuple[str, str]] = set()
self._lock = threading.Lock()
def unused_by_buyer(self, code: str) -> Spec:
return Spec(lambda ctx: (ctx.cart.user_id, code) not in self._used)
def record(self, order: Order) -> None: # registered as an on_paid observer
with self._lock:
self._used.update((order.user_id, c) for c in order.quote.applied_coupons)
catalog, shop = build_shop()
ledger = CouponLedger()
shop.engine.coupons["FIRST10"] = Coupon("FIRST10", AmountOff("FIRST10", 1000), stackable=True,
eligible=ledger.unused_by_buyer("FIRST10"))
shop.on_paid.append(ledger.record)
for cart_id in ["c1", "c2"]:
cart = Cart(cart_id, "erin")
cart.add(catalog["BOOK"])
cart.apply_coupon("FIRST10")
applied = shop.checkout(cart, f"k-{cart_id}").quote.applied_coupons
assert applied == (("FIRST10",) if cart_id == "c1" else ()), applied
print("ext_coupon_ledger: ok")
Name the race: two simultaneous checkouts by one buyer both pass the check before either records. For a high-value coupon, make redemption part of checkout: reserve the coupon atomically next to the stock, INSERT a row with a unique (user, code) constraint, and release it if payment fails. That's the same reserve, commit or release shape as inventory.
"Tax depends on the shipping region"
Swap the TaxPolicy. The region-aware policy looks up a rate by region and category, and falls back to the product rate.
import assert from "node:assert/strict";
import { Cart, CartLine, PricingEngine, pctOf, productRateTax, type TaxPolicy } from "./cart.ts";
/** Tax depends on where the parcel ships, then on the product category. */
export class RegionTax implements TaxPolicy {
constructor(private readonly rates: Map<string, Map<string, number>>, // region -> category -> bps
private readonly fallback: TaxPolicy) {}
tax(cart: Cart, line: CartLine, net: number): number {
const bps = this.rates.get(cart.region)?.get(line.product.category);
return bps === undefined ? this.fallback.tax(cart, line, net) : pctOf(net, bps);
}
}
const engine = new PricingEngine([], [], new Map(),
new RegionTax(new Map([["UK", new Map([["books", 0], ["kitchen", 2000]])]]), productRateTax));
const book = { sku: "BOOK", price: 4000, category: "books", taxBps: 500 };
const mug = { sku: "MUG", price: 1200, category: "kitchen", taxBps: 1000 };
for (const [region, expected] of [["UK", 0 + 240], ["US", 200 + 120]] as const) {
const cart = new Cart("c", "u", region);
cart.add(book); cart.add(mug);
assert.equal(engine.quote(cart).tax, expected);
}
console.log("ext-region-tax: ok");
Tax-inclusive regions change the formula to gross × rate / (1 + rate), behind the same interface.
9. Testing
Test the rules that are easy to get subtly wrong: rounding, rule interaction, the race, and idempotency. Inject the clock so expiry tests don't sleep. Use a fake gateway so payment outcomes are scripted. The general technique is in designing for testability.
import threading
from cart import (Cart, FakeGateway, IdempotencyConflict, IllegalTransition, Inventory, OutOfStock,
ReservationExpired, Status, allocate, build_shop)
def test_allocation_always_sums_to_the_amount():
assert allocate(100, {"a": 1, "b": 1, "c": 1}) == {"a": 34, "b": 33, "c": 33}
assert all(sum(allocate(n, {"x": 333, "y": 667, "z": 1}).values()) == n for n in range(500))
def test_stackable_coupons_win_when_they_save_more_and_total_never_goes_negative():
catalog, shop = build_shop()
cart = Cart("c", "u")
cart.add(catalog["PEN"]) # 250, so 15% saves 38 but 5 + 2 dollars saves all of it
for code in ["SAVE15", "WELCOME5", "EXTRA2", "BOGUS"]:
cart.apply_coupon(code)
q = shop.engine.quote(cart)
assert q.applied_coupons == ("WELCOME5", "EXTRA2") and q.total == 0
assert "BOGUS" in q.rejected_coupons
def test_reservation_expires_and_late_commit_fails():
now = [0.0]
inv = Inventory(clock=lambda: now[0])
inv.add_stock("MUG", 1)
inv.reserve("r1", {"MUG": 1}, ttl=10)
assert inv.available("MUG") == 0
now[0] = 11
assert inv.available("MUG") == 1
try:
inv.commit("r1")
raise AssertionError("expected ReservationExpired")
except ReservationExpired:
pass
def test_declined_card_cancels_and_releases_stock_and_state_machine_guards():
catalog, shop = build_shop(FakeGateway(approve=False))
cart = Cart("c", "u")
cart.add(catalog["MUG"])
order = shop.checkout(cart, "k")
assert order.status is Status.CANCELLED and shop.inventory.available("MUG") == 1
try:
order.transition(Status.PAID)
raise AssertionError("expected IllegalTransition")
except IllegalTransition:
pass
def test_last_item_race_has_exactly_one_winner():
for _ in range(20):
catalog, shop = build_shop() # one MUG in stock
statuses: list[str] = []
barrier = threading.Barrier(8)
def buy(i: int) -> None:
c = Cart(f"c{i}", f"u{i}")
c.add(catalog["MUG"])
barrier.wait()
try:
statuses.append(shop.checkout(c, f"k{i}").status.name)
except OutOfStock:
statuses.append("OUT")
threads = [threading.Thread(target=buy, args=(i,)) for i in range(8)]
[t.start() for t in threads]
[t.join() for t in threads]
assert statuses.count("PAID") == 1 and statuses.count("OUT") == 7, statuses
def test_same_key_for_another_cart_conflicts_and_observers_fire_once():
catalog, shop = build_shop()
paid: list[str] = []
shop.on_paid.append(lambda o: paid.append(o.id))
c1, c2 = Cart("c1", "u"), Cart("c2", "u")
c1.add(catalog["PEN"])
c2.add(catalog["PEN"])
order = shop.checkout(c1, "k")
assert shop.checkout(c1, "k") is order
try:
shop.checkout(c2, "k")
raise AssertionError("expected IdempotencyConflict")
except IdempotencyConflict:
pass
assert paid == [order.id]
if __name__ == "__main__":
for name, fn in list(globals().items()):
if name.startswith("test_"):
fn()
print("ok", name)
What each test pins:
- Allocation sums exactly for 500 different amounts with awkward weights. This is a property test in miniature.
- Stacking picks the cheaper option, and the total never goes negative.
- Expiry and late commit. The fake clock jumps past the TTL, and
commitmust refuse. - Decline path. The order is
CANCELLED, stock comes back, andCANCELLEDis terminal. - The race, twenty times over, with a barrier so all eight threads hit
checkouttogether. Exactly onePAIDevery time. A race test that runs once proves little, so repeat it. - Idempotency. The same key replays the same order, the same key on another cart is a conflict, and observers fire exactly once.
10. Common mistakes
- Using
doublefor money.0.1 + 0.2 != 0.3. Use integer minor units, orBigDecimalwith an explicit rounding mode. - Rounding each share of a split independently. Three lines sharing a $1.00 discount get $0.33 each, and a cent disappears. Allocate with a largest-remainder pass.
- Applying tax before discounts, or computing tax on the cart total when lines have different rates. Tax follows the line's net amount.
- Hard-coding promotions in a
switch. Every new promotion edits and retests the engine. - Letting a discount drive a total negative. Cap at the line and the cart.
- Storing totals in the cart. They go stale when a promotion expires or a price changes. Derive them every time.
- Decrementing stock when an item is added to the cart. Abandoned carts then lock up stock forever. Reserve at checkout, with a TTL.
- Charging before reserving. You hold money for goods you can't ship.
- Holding a lock across the payment call. The shop now runs at one checkout per gateway round trip.
- No idempotency key, or keying on cart contents. A retry after a timeout charges twice. A cart hash fails too: the cart is cleared on success, so the retry no longer matches.
11. Interview follow-ups
Why not floats with rounding at the end?
Intermediate results feed decisions: net >= 100.00 can fail at 99.99999. Rounding at the end also can't say which line absorbs the cent, and tax and refunds need that. Integers make every step exact.
How would you handle multiple currencies?
Wrap amounts in a Money(minor, currency) value object whose arithmetic throws on mismatched currencies, and price each cart in one currency. Conversion belongs in the catalogue, not the arithmetic. Minor units vary: JPY has 0 decimals and KWD has 3.
The payment call timed out. Did it charge?
You don't know. Don't release stock or fail the order. Leave it PENDING_PAYMENT and retry with the same gateway key (the order ID), which completes the charge or returns the original result. A reconciler asks the gateway about orders stuck past a deadline. Only a definite decline releases stock.
Two promotions both want the same pen. Which wins? Make it explicit. Our line rules run in list order and compound. "Best single promotion per line" is a different engine policy: try each rule alone and keep the best per line. Either way the policy lives visibly in the engine.
How would this run across many servers?
Inventory becomes a conditional UPDATE (or a SELECT … FOR UPDATE per SKU). Idempotency keys go in a table with a unique constraint: the insert winner does the work, losers poll for its result. A scheduled job sweeps expired holds. The classes stay. Only the implementations behind Inventory and the key store change.
What about flash sales with 10,000 buyers for 100 units? The one hot SKU row becomes the bottleneck. Shard the stock into buckets and reserve from a random one, trying another when it's empty. Or queue buyers and reject at the door once units run out. For auction-style contention, see the online auction case study.
Where would you send the order confirmation email?
In an onPaid observer that enqueues a message, so a slow email provider never slows a checkout. The notification service case study designs the delivery side.