Design Splitwise

Scope it first

"Users create group expenses — one payer, many participants, split equally / by exact amounts / by percentages. Show who owes whom; simplify debts. Single currency, ignore payments/settlement execution and auth — OK?" That scope hits everything graders look for: a Strategy seam, a money-correctness invariant, and one genuine algorithm.

Entities & relationships

• Expense is an immutable record: who paid, how much, and the computed Splits. Edits create a new version (audit trail — finance code never destroys history).
• SplitStrategy — equal / exact / percent are interchangeable algorithms producing List<Split>: the cleanest Strategy showcase in any LLD classic. New split type (by shares, by adjustment) = new class, zero edits (Open/Closed, same seam as parking-lot pricing).
• BalanceSheet holds net balance per user (positive = is owed, negative = owes). Derived from expenses, so it's a cache — rebuildable by replay, which is your data-corruption escape hatch.

Each strategy validates its own args: exact amounts must sum to the total; percentages to 100. Validation inside the strategy, not the manager — the class that defines the rule enforces it (encapsulation).

Money: the two non-negotiables

1. Never floats. ₹0.10 isn't representable in binary; pennies leak. Integer paise/cents or BigDecimal (Level 1 said it; here it's load-bearing).
2. The conservation invariant: every expense's splits sum exactly to the amount, and the global net sums to zero. ₹100 split three ways is 33.33 + 33.33 + 33.34 — someone gets the spare paisa (convention: first participant). Write the assertion; mention it unprompted. It's the difference between candidates who've handled money and those who haven't:

def equal_split(amount_paise, users):
    base, remainder = divmod(amount_paise, len(users))
    return [Split(u, base + (1 if i < remainder else 0))
            for i, u in enumerate(users)]
    # sum of shares == amount_paise, ALWAYS — assert it in tests

The algorithm: debt simplification

A trip's raw expenses create a messy web of IOUs. But only net balances matter: compute each user's net, then match debtors to creditors:

Raw: A→B ₹20, B→C ₹20, C→A ₹10        Nets: A −10, B 0, C +10
Simplified: A pays C ₹10.  (3 transactions → 1; B vanished entirely)

The graph view is why this works: individual edges (who-paid-whom) are noise; only each node's net flow matters, and any set of transactions that produces the same nets is equally valid.

def simplify(net):                       # net: user → paise (sum == 0)
    owes  = [(u, -v) for u, v in net.items() if v < 0]
    owed  = [(u,  v) for u, v in net.items() if v > 0]
    txns, i, j = [], 0, 0
    while i < len(owes) and j < len(owed):
        debtor, debt = owes[i]
        creditor, credit = owed[j]
        pay = min(debt, credit)
        txns.append(Transaction(debtor, creditor, pay))
        owes[i], owed[j] = (debtor, debt - pay), (creditor, credit - pay)
        if owes[i][1] == 0: i += 1
        if owed[j][1] == 0: j += 1
    return txns

Two pointers over debtors and creditors — at most n−1 transactions for n users, each iteration retires at least one side. Greedily matching largest debtor to largest creditor (two heaps) tends to produce fewer transactions; the true minimum transaction count is NP-hard (subset-sum in disguise) — knowing that "good greedy, optimal is NP-hard, n−1 is fine" line is exactly the greedy-judgment graders want.

Watch it collapse a five-IOU web into the minimum transfers. First the raw debts become net balances; then each step pays the biggest debtor's debt to the biggest creditor, zeroing out at least one person per transfer. Edit the debts to try your own group.

Think it through like the interview

Walk a scenario + concurrency

"Trip group: A pays ₹300 dinner, equal among A,B,C" → EqualSplit.computeSplits → splits (100,100,100) → BalanceSheet: B −100, C −100, A +200. "B pays ₹150 taxi, exact: A 50, B 100" → A +50… → nets: A +150, B −50, C −100 → simplify → C pays A ₹100, B pays A ₹50. Two transactions settle the trip.

Concurrency follow-up: two expenses added to one group simultaneously → the balance update is read-modify-write. Same family as the parking-lot race: atomic per-group mutation (lock or serialized queue per group), or make balances derived only — append expenses to a log, compute nets on read; appends don't race (the event-sourcing instinct, in miniature).

Practice — level up

Splitwise's core is a graph of balances plus a greedy settlement. Train both halves on these: