40 — LLD: Cart System

Understanding the Problem

An e-commerce cart — add and remove items, compute a total, apply discounts, add tax. What makes this an LLD interview instead of a data-class exercise is the discount system: multiple discount types (fixed, percentage, BOGO, tiered) need to coexist and evolve. Strategy plus Observer turns the nested if/else into something maintainable.

What is a Cart System?

A per-user container for products and quantities. The total depends on base prices, product-level and cart-level discounts, an optional coupon, and tax. Discounts are the feature that keeps changing across releases, so the design must absorb new discount types cleanly.

---

Requirements

Clarifying Questions

You: Do coupons stack with product-level discounts?

Interviewer: Product discounts always apply. Coupons: only one cart-level coupon at a time.

So we can model product discounts as baked-in line-level adjustments, and coupon as a single cart-level strategy.

You: Is tax included in the product price or added separately?

Interviewer: Add tax at the end, after discounts.

Order of operations: subtotal → discounts → tax. Cleanly separated.

You: Multi-currency?

Interviewer: Single currency for simplicity.

One Money type is enough. No FX logic.

Final Requirements

1. addItem(product, qty) / removeItem(productId) / updateQty(productId, qty).
2. applyCoupon(discountStrategy) — replaces any previous coupon.
3. total() -> Money — subtotal → discounts → tax.
4. Multiple discount types: fixed amount, percentage, BOGO (buy-one-get-one), tiered (spend more, save more).
5. Observer — notify UI listeners on total changes.

Out of scope: Multi-currency, shipping costs, inventory reservation, user authentication.

Deferred tradeoff: Coupon validation (min spend, product restrictions) is baked into each strategy; a dedicated CouponValidator would be cleaner at scale, but adds an indirection we do not need yet.

---

Core Entities and Relationships

The discount zoo is the design challenge. Each discount needs to know how to compute itself given the cart state. They all share the signature (subtotal, cart) -> adjusted_total. That signature is a strategy interface.

Entity	Responsibility
Product	id, name, price, attributes.
CartLine	product, qty. subtotal() = product.price * qty.
Cart	per-user owner of lines, optional coupon, listeners.
DiscountStrategy	apply(subtotal, cart) -> newSubtotal.
TaxCalculator	compute tax on the discounted subtotal.
PriceListener	Observer for UI refresh.
CartService	Orchestrates (optional — Cart can expose methods directly).

Why not chain discounts as DiscountChain with multiple coupons? Because the requirement is one coupon at a time. A List<DiscountStrategy> is the natural extension if stacking arrives later. Today, a single field.

Design is iterative. When the next requirement "coupon restrictions by product" arrives, we will add a validator layer.

---

Class Design

Product

• id, name, price, attrs. Immutable.

CartLine

• product, qty. subtotal() convenience.

DiscountStrategy

Money apply(Money subtotal, Cart cart)

Concrete implementations: FixedAmountCoupon, PercentCoupon, TieredDiscount, BogoDiscount.

Cart

State:

• userId.
• lines: LinkedHashMap<String, CartLine> — preserves insertion order.
• coupon: DiscountStrategy | null.
• listeners: CopyOnWriteArrayList<PriceListener>.

Methods:

• addItem, removeItem, updateQty, applyCoupon.
• total() -> Money.
• subscribe(PriceListener).
• Private notifyPriceChange() called from every mutating method.

Java

public record Product(String id, String name, BigDecimal price, Map<String, String> attrs) {}

public class CartLine {
    final Product product;
    int qty;
    public CartLine(Product p, int q) { this.product = p; this.qty = q; }
    public BigDecimal subtotal() { return product.price().multiply(BigDecimal.valueOf(qty)); }
}

public interface DiscountStrategy {
    BigDecimal apply(BigDecimal subtotal, Cart cart);
}

public class PercentCoupon implements DiscountStrategy {
    private final BigDecimal percent;  // 0.10 for 10%
    public PercentCoupon(BigDecimal p) { this.percent = p; }
    public BigDecimal apply(BigDecimal subtotal, Cart cart) {
        return subtotal.multiply(BigDecimal.ONE.subtract(percent));
    }
}

public class TieredDiscount implements DiscountStrategy {
    private final List<Map.Entry<BigDecimal, BigDecimal>> tiers;
    public TieredDiscount(List<Map.Entry<BigDecimal, BigDecimal>> tiers) { this.tiers = tiers; }
    public BigDecimal apply(BigDecimal subtotal, Cart cart) {
        BigDecimal pct = BigDecimal.ZERO;
        for (var t : tiers) {
            if (subtotal.compareTo(t.getKey()) >= 0) pct = t.getValue();
            else break;
        }
        return subtotal.multiply(BigDecimal.ONE.subtract(pct));
    }
}

public class BogoDiscount implements DiscountStrategy {
    private final Set<String> eligibleProductIds;
    public BogoDiscount(Set<String> ids) { this.eligibleProductIds = ids; }
    public BigDecimal apply(BigDecimal subtotal, Cart cart) {
        BigDecimal off = BigDecimal.ZERO;
        for (CartLine l : cart.lines()) {
            if (eligibleProductIds.contains(l.product.id())) {
                int freeUnits = l.qty / 2;
                off = off.add(l.product.price().multiply(BigDecimal.valueOf(freeUnits)));
            }
        }
        return subtotal.subtract(off);
    }
}

public interface PriceListener { void onTotalChanged(Money newTotal); }

public class Cart {
    private final String userId;
    private final Map<String, CartLine> lines = new LinkedHashMap<>();
    private DiscountStrategy coupon;
    private final List<PriceListener> listeners = new CopyOnWriteArrayList<>();

    public Cart(String userId) { this.userId = userId; }
    public Collection<CartLine> lines() { return lines.values(); }

    public void addItem(Product p, int qty) { /* ... */ }
    public void applyCoupon(DiscountStrategy s) { this.coupon = s; notifyPriceChange(); }
    public void subscribe(PriceListener l) { listeners.add(l); }
    public Money total() { /* ... */ }
    private void notifyPriceChange() { Money t = total(); listeners.forEach(l -> l.onTotalChanged(t)); }
}

public record Money(BigDecimal amount, String currency) {}

C++

struct Product { std::string id, name; double price; };
struct CartLine { Product product; int qty; double subtotal() const { return product.price * qty; } };

struct DiscountStrategy {
    virtual double apply(double subtotal, const class Cart& c) = 0;
    virtual ~DiscountStrategy() = default;
};

class PercentCoupon : public DiscountStrategy {
    double pct;
public:
    explicit PercentCoupon(double p) : pct(p) {}
    double apply(double subtotal, const Cart&) override { return subtotal * (1 - pct); }
};

TypeScript

export interface Product { id: string; name: string; price: number; attrs: Record<string, string>; }
export interface DiscountStrategy { apply(subtotal: number, cart: Cart): number; }

export class PercentCoupon implements DiscountStrategy {
  constructor(private pct: number) {}
  apply(subtotal: number): number { return subtotal * (1 - this.pct); }
}

export class TieredDiscount implements DiscountStrategy {
  constructor(private tiers: Array<[number, number]>) {}  // sorted asc by threshold
  apply(subtotal: number): number {
    let pct = 0;
    for (const [threshold, percent] of this.tiers) {
      if (subtotal >= threshold) pct = percent; else break;
    }
    return subtotal * (1 - pct);
  }
}

export class BogoDiscount implements DiscountStrategy {
  constructor(private eligibleIds: Set<string>) {}
  apply(subtotal: number, cart: Cart): number {
    let off = 0;
    for (const l of cart.lines()) {
      if (this.eligibleIds.has(l.product.id)) {
        const free = Math.floor(l.qty / 2);
        off += l.product.price * free;
      }
    }
    return subtotal - off;
  }
}

Design principles at play:

• Strategy: DiscountStrategy is open for extension — new discount types plug in without touching Cart.
• Observer: PriceListener decouples UI refresh from cart logic.
• Decorator (alternative): If stacking returns, layer discounts on a base Pricer — each one wraps the next.
• Information Expert: CartLine knows its own subtotal; Cart composes them.

---

Implementation

Core Logic: addItem

1. Validate qty > 0.
2. Merge with existing line if present; else insert a new one.
3. Notify listeners.

Core Logic: total

1. Compute subtotal = sum of line subtotals.
2. Apply coupon if present.
3. Apply tax on the discounted subtotal.
4. Return as Money.

Implementations

Java

public void addItem(Product p, int qty) {
    if (qty <= 0) throw new IllegalArgumentException();
    lines.merge(p.id(),
        new CartLine(p, qty),
        (existing, fresh) -> { existing.qty += fresh.qty; return existing; });
    notifyPriceChange();
}

public void removeItem(String productId) {
    if (lines.remove(productId) != null) notifyPriceChange();
}

public void updateQty(String productId, int qty) {
    if (qty <= 0) { removeItem(productId); return; }
    CartLine l = lines.get(productId);
    if (l == null) throw new NoSuchElementException();
    l.qty = qty;
    notifyPriceChange();
}

public Money total() {
    BigDecimal subtotal = lines.values().stream()
        .map(CartLine::subtotal)
        .reduce(BigDecimal.ZERO, BigDecimal::add);
    BigDecimal afterDiscount = (coupon != null) ? coupon.apply(subtotal, this) : subtotal;
    BigDecimal tax = afterDiscount.multiply(BigDecimal.valueOf(0.18)).setScale(2, RoundingMode.HALF_UP);
    return new Money(afterDiscount.add(tax), "USD");
}

C++

double Cart::total() const {
    double subtotal = 0;
    for (auto& [_, l] : lines) subtotal += l.subtotal();
    double after = coupon ? coupon->apply(subtotal, *this) : subtotal;
    return after * 1.18;
}

TypeScript

total(): number {
  let subtotal = 0;
  for (const l of this.lines.values()) subtotal += l.product.price * l.qty;
  const after = this.coupon ? this.coupon.apply(subtotal, this) : subtotal;
  return +(after * 1.18).toFixed(2);
}

addItem(p: Product, qty: number): void {
  if (qty <= 0) throw new Error("bad qty");
  const existing = this.linesMap.get(p.id);
  if (existing) existing.qty += qty;
  else this.linesMap.set(p.id, { product: p, qty });
  this.notifyPriceChange();
}

Thread Safety

A Cart is naturally per-user, so contention is low. One synchronized on the mutating methods is enough. The listener list is CopyOnWriteArrayList — snapshot iteration avoids ConcurrentModificationException during notification.

If the cart is served from multiple hosts (user switches devices mid-session), move state to an external store (Redis) and use optimistic concurrency with a version field — the single-user assumption breaks, and so does our local-lock story.

Never call listeners while holding a lock if they might do I/O. Hand off via an executor in that case.

Verification

Add 2 × Book at $20, apply a 10% coupon, tax 18%:

1. Subtotal = $20 × 2 = $40.
2. After 10% discount = $40 × 0.90 = $36.
3. Tax = $36 × 0.18 = $6.48.
4. Total = $36 + $6.48 = $42.48.

BOGO trace: BogoDiscount({book-id}), 3 copies of that book at $20.

• Eligible line: qty=3. Free units = 3 / 2 = 1.
• Off = $20 × 1 = $20.
• New subtotal = previous - $20.

---

Complete Code Implementation

Java

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.*;
import java.util.concurrent.CopyOnWriteArrayList;

public record Product(String id, String name, BigDecimal price, Map<String, String> attrs) {}
public record Money(BigDecimal amount, String currency) {}

public class CartLine {
    final Product product;
    int qty;
    public CartLine(Product p, int q) { this.product = p; this.qty = q; }
    public BigDecimal subtotal() { return product.price().multiply(BigDecimal.valueOf(qty)); }
}

public interface DiscountStrategy {
    BigDecimal apply(BigDecimal subtotal, Cart cart);
}

public class FixedAmountCoupon implements DiscountStrategy {
    private final BigDecimal amount;
    public FixedAmountCoupon(BigDecimal a) { this.amount = a; }
    public BigDecimal apply(BigDecimal subtotal, Cart c) {
        return subtotal.subtract(amount).max(BigDecimal.ZERO);
    }
}

public class PercentCoupon implements DiscountStrategy {
    private final BigDecimal percent;
    public PercentCoupon(BigDecimal p) { this.percent = p; }
    public BigDecimal apply(BigDecimal subtotal, Cart c) {
        return subtotal.multiply(BigDecimal.ONE.subtract(percent));
    }
}

public class TieredDiscount implements DiscountStrategy {
    private final List<Map.Entry<BigDecimal, BigDecimal>> tiers;
    public TieredDiscount(List<Map.Entry<BigDecimal, BigDecimal>> tiers) { this.tiers = tiers; }
    public BigDecimal apply(BigDecimal subtotal, Cart c) {
        BigDecimal pct = BigDecimal.ZERO;
        for (var t : tiers) {
            if (subtotal.compareTo(t.getKey()) >= 0) pct = t.getValue();
            else break;
        }
        return subtotal.multiply(BigDecimal.ONE.subtract(pct));
    }
}

public class BogoDiscount implements DiscountStrategy {
    private final Set<String> eligibleProductIds;
    public BogoDiscount(Set<String> ids) { this.eligibleProductIds = ids; }
    public BigDecimal apply(BigDecimal subtotal, Cart c) {
        BigDecimal off = BigDecimal.ZERO;
        for (CartLine l : c.lines()) {
            if (eligibleProductIds.contains(l.product.id())) {
                int free = l.qty / 2;
                off = off.add(l.product.price().multiply(BigDecimal.valueOf(free)));
            }
        }
        return subtotal.subtract(off);
    }
}

public interface PriceListener { void onTotalChanged(Money newTotal); }

public class Cart {
    private final String userId;
    private final Map<String, CartLine> lines = new LinkedHashMap<>();
    private DiscountStrategy coupon;
    private final BigDecimal taxRate = new BigDecimal("0.18");
    private final List<PriceListener> listeners = new CopyOnWriteArrayList<>();

    public Cart(String userId) { this.userId = userId; }

    public Collection<CartLine> lines() { return lines.values(); }

    public synchronized void addItem(Product p, int qty) {
        if (qty <= 0) throw new IllegalArgumentException();
        lines.merge(p.id(), new CartLine(p, qty),
            (existing, fresh) -> { existing.qty += fresh.qty; return existing; });
        notifyPriceChange();
    }

    public synchronized void removeItem(String productId) {
        if (lines.remove(productId) != null) notifyPriceChange();
    }

    public synchronized void updateQty(String productId, int qty) {
        if (qty <= 0) { removeItem(productId); return; }
        CartLine l = lines.get(productId);
        if (l == null) throw new NoSuchElementException();
        l.qty = qty;
        notifyPriceChange();
    }

    public synchronized void applyCoupon(DiscountStrategy s) {
        this.coupon = s;
        notifyPriceChange();
    }

    public synchronized Money total() {
        BigDecimal subtotal = lines.values().stream()
            .map(CartLine::subtotal)
            .reduce(BigDecimal.ZERO, BigDecimal::add);
        BigDecimal afterDiscount = (coupon != null) ? coupon.apply(subtotal, this) : subtotal;
        BigDecimal tax = afterDiscount.multiply(taxRate).setScale(2, RoundingMode.HALF_UP);
        return new Money(afterDiscount.add(tax).setScale(2, RoundingMode.HALF_UP), "USD");
    }

    public void subscribe(PriceListener l) { listeners.add(l); }

    private void notifyPriceChange() {
        Money t = total();
        for (PriceListener l : listeners) {
            try { l.onTotalChanged(t); } catch (Exception ignore) {}
        }
    }
}

C++

#include <memory>
#include <string>
#include <unordered_map>
#include <vector>

struct Product { std::string id, name; double price; };
struct CartLine { Product product; int qty; double subtotal() const { return product.price * qty; } };

class Cart;

struct DiscountStrategy {
    virtual double apply(double subtotal, const Cart& c) = 0;
    virtual ~DiscountStrategy() = default;
};

class Cart {
    std::unordered_map<std::string, CartLine> linesMap;
    std::shared_ptr<DiscountStrategy> coupon;
    double taxRate = 0.18;
public:
    const std::unordered_map<std::string, CartLine>& lines() const { return linesMap; }

    void addItem(const Product& p, int qty) {
        auto it = linesMap.find(p.id);
        if (it == linesMap.end()) linesMap[p.id] = {p, qty};
        else it->second.qty += qty;
    }

    void applyCoupon(std::shared_ptr<DiscountStrategy> s) { coupon = std::move(s); }

    double total() const {
        double subtotal = 0;
        for (auto& [_, l] : linesMap) subtotal += l.subtotal();
        double after = coupon ? coupon->apply(subtotal, *this) : subtotal;
        return after * (1 + taxRate);
    }
};

class PercentCoupon : public DiscountStrategy {
    double pct;
public:
    explicit PercentCoupon(double p) : pct(p) {}
    double apply(double subtotal, const Cart&) override { return subtotal * (1 - pct); }
};

TypeScript

export interface Product { id: string; name: string; price: number; attrs: Record<string, string>; }
export interface CartLine { product: Product; qty: number; }
export interface DiscountStrategy { apply(subtotal: number, cart: Cart): number; }

export class FixedAmountCoupon implements DiscountStrategy {
  constructor(private amount: number) {}
  apply(subtotal: number): number { return Math.max(0, subtotal - this.amount); }
}

export class PercentCoupon implements DiscountStrategy {
  constructor(private pct: number) {}
  apply(subtotal: number): number { return subtotal * (1 - this.pct); }
}

export class TieredDiscount implements DiscountStrategy {
  constructor(private tiers: Array<[number, number]>) {}
  apply(subtotal: number): number {
    let pct = 0;
    for (const [threshold, percent] of this.tiers) {
      if (subtotal >= threshold) pct = percent; else break;
    }
    return subtotal * (1 - pct);
  }
}

export class BogoDiscount implements DiscountStrategy {
  constructor(private eligibleIds: Set<string>) {}
  apply(subtotal: number, cart: Cart): number {
    let off = 0;
    for (const l of cart.lines()) {
      if (this.eligibleIds.has(l.product.id)) off += l.product.price * Math.floor(l.qty / 2);
    }
    return subtotal - off;
  }
}

export interface PriceListener { onTotalChanged(total: number): void; }

export class Cart {
  private linesMap = new Map<string, CartLine>();
  private coupon: DiscountStrategy | null = null;
  private listeners: PriceListener[] = [];
  private taxRate = 0.18;

  constructor(public userId: string) {}

  lines(): CartLine[] { return [...this.linesMap.values()]; }

  addItem(p: Product, qty: number): void {
    if (qty <= 0) throw new Error("bad qty");
    const existing = this.linesMap.get(p.id);
    if (existing) existing.qty += qty;
    else this.linesMap.set(p.id, { product: p, qty });
    this.notifyPriceChange();
  }

  removeItem(pid: string): void {
    if (this.linesMap.delete(pid)) this.notifyPriceChange();
  }

  updateQty(pid: string, qty: number): void {
    if (qty <= 0) { this.removeItem(pid); return; }
    const l = this.linesMap.get(pid);
    if (!l) throw new Error("not in cart");
    l.qty = qty;
    this.notifyPriceChange();
  }

  applyCoupon(s: DiscountStrategy): void {
    this.coupon = s;
    this.notifyPriceChange();
  }

  total(): number {
    let subtotal = 0;
    for (const l of this.linesMap.values()) subtotal += l.product.price * l.qty;
    const after = this.coupon ? this.coupon.apply(subtotal, this) : subtotal;
    return +(after * (1 + this.taxRate)).toFixed(2);
  }

  subscribe(l: PriceListener): void { this.listeners.push(l); }

  private notifyPriceChange(): void {
    const t = this.total();
    for (const l of this.listeners) { try { l.onTotalChanged(t); } catch {} }
  }
}

---

Extensibility

1. "Stackable coupons — apply two at once?"

Replace the single coupon field with List<DiscountStrategy> applied in declared order:

for (DiscountStrategy s : coupons) subtotal = s.apply(subtotal, this);

Tradeoff: Stacking order matters for percentages vs. fixed amounts. Document the precedence clearly, or enforce it via a CouponOrdering strategy.

2. "Minimum-spend coupon?"

Each strategy validates its own preconditions:

public class MinSpendPercentCoupon implements DiscountStrategy {
    private final BigDecimal min;
    private final BigDecimal percent;
    public BigDecimal apply(BigDecimal subtotal, Cart c) {
        if (subtotal.compareTo(min) < 0) return subtotal;
        return subtotal.multiply(BigDecimal.ONE.subtract(percent));
    }
}

3. "Flash sale — product price changes mid-session?"

Snapshot the product price in the CartLine at add time so live price changes do not retroactively affect existing carts. This is a correctness-over-freshness trade-off; most e-commerce sites do this to avoid customer surprises at checkout.

public class CartLine {
    final String productId;
    final BigDecimal priceAtAdd;
    int qty;
    // ...
}

---

What is Expected at Each Level

Level	Expectations
Junior (L4)	Hard-coded if/else for each discount type inside total(). Works but not extensible.
Mid (L5)	DiscountStrategy interface, multiple implementations, clean total() method with ordered subtotal → discount → tax pipeline.
Senior (L5A)	Strategy + Observer, composable discounts, clear precedence documentation, snapshot prices on add, clean extensibility story for stacking.
Staff (L6)	Rules engine (Drools-like), A/B testing on pricing, cross-device cart sync with optimistic concurrency, abandoned-cart recovery, analytics integration.