Design Splitwise: Expense Sharing, Balance Sheets, and Debt Simplification

Why Splitwise is a great LLD problem

Splitwise looks deceptively simple — “people split bills” — but it hides three things interviewers love to probe: a polymorphic input format (equal vs exact vs percentage splits), a ledger/accounting invariant (every expense must net to zero), and a graph algorithm (minimizing the number of settlement transactions). A strong candidate carves the problem into those three layers and refuses to let any one bleed into the others.

In a 45-minute machine-coding round you will not finish everything. The skill being tested is sequencing: clarify, model entities, get a clean addExpense + balance update working, then — and only then — reach for the simplify-debts algorithm. This lesson follows that exact order.

Interview framing: Say out loud, “I’ll build the core ledger first so balances are always correct, then treat debt simplification as an optimization on top. They’re independent concerns.” This signals you separate correctness from optimization — a senior trait.

Step 1 — Clarify requirements

Do not start coding. Spend 2-3 minutes pinning down scope. Here are the questions that actually change the design, with the answers I’d assume if the interviewer waves me on.

Functional requirements (the ones that matter):

• Add an expense paid by one or more users, split among a set of users by one of three strategies: EQUAL, EXACT (explicit amounts), PERCENT.
• Multiple payers? Common follow-up. I’ll model paidBy as a map user -> amount from the start so a single payer is just a one-entry map. This costs nothing now and saves a refactor later.
• Query balances: “How much do I owe / am I owed”, both overall and per-counterparty.
• Groups: expenses scoped to a group of users (trip, flatmates). Balances can be queried within a group.
• Settle up / simplify debts: reduce the web of “A owes B owes C” into the minimum number of payments.

Non-functional / scope cuts (state them, then defer):

Step 2 — Core entities and responsibilities

Keep responsibilities sharp. Each class does one job.

• User — identity only: userId, name. No balance lives here; balances are derived from the ledger so there’s a single source of truth.
• Money / Amount — value in minor units (cents) as an integer to dodge floating-point drift. A thin wrapper buys you currency-tagging and safe arithmetic later (shown once below); the strategies use a bare Cents alias for brevity.
• Split — represents one participant’s resolved share of an expense: (user, amount). The split inputs carry the intent (a percent, an exact amount, or nothing for equal); after a strategy validates them, every split resolves to a concrete cents amount.
• SplitStrategy (the polymorphic core) — given the total and the participant inputs, produce the validated list of Splits. EqualSplitStrategy, ExactSplitStrategy, PercentSplitStrategy.
• Expense — record: id, description, totalAmount, paidBy: Map<User, amount>, splits: List<Split>. Validates that sum(paidBy) == sum(splits) == total.
• BalanceSheet (Ledger) — the heart. Holds net pairwise balances balances[debtor][creditor] = amount debtor owes creditor (with antisymmetry balances[a][b] == -balances[b][a]). Updated when an expense is added.
• Group — a named set of users plus its own expense list (or a filter over a shared ledger).
• ExpenseService / SplitwiseManager — façade the interviewer calls: addExpense(...), showBalances(user), simplify(group).
• DebtSimplifier — pure algorithm over a balance sheet; produces a minimal transaction list.

A real Money wrapper (referenced once, then aliased away)

The prose keeps promising a Money type, so here it is concretely. In a real codebase you would thread this through instead of a bare integer; in the strategy code below we alias it to Cents to keep the algorithm readable.

// Minimal value object: integer minor units + currency tag, immutable.
class Money {
constructor(readonly cents: number, readonly currency: string = "USD") {
  if (!Number.isInteger(cents)) throw new Error("money must be integer cents");
}
add(o: Money): Money {
  if (o.currency !== this.currency) throw new Error("currency mismatch");
  return new Money(this.cents + o.cents, this.currency);
}
negate(): Money { return new Money(-this.cents, this.currency); }
}

Step 3 — Class diagram (ASCII UML)

                 +---------------------+
                 |  SplitwiseManager   |  <-- façade / entry point
                 +---------------------+
                 | + addExpense(...)   |
                 | + showBalances(u)   |
                 | + simplify(group)   |
                 +----------+----------+
                            | uses
            +---------------+----------------+
            |                                |
   +--------v---------+            +----------v------------+
   |   BalanceSheet   |            |  SplitStrategyFactory |
   +------------------+            +-----------------------+
   | balances:        |            | + get(type):          |
   |   Map<U,Map<U,$>>|            |     SplitStrategy      |
   | + applyExpense() |            +----------+------------+
   | + balanceOf(u)   |                       | creates
   | + pairwise(a,b)  |            +----------v-----------+
   +--------+---------+            |  <<interface>>       |
            ^                      |   SplitStrategy      |
            | reads                +----------------------+
   +--------+---------+            | + computeSplits(     |
   | DebtSimplifier   |            |     total,           |
   +------------------+            |     inputs): Split[] |
   | + minimize(bs):  |            +----------+-----------+
   |     Transaction[]|                       ^
   +------------------+        +--------------+--------------+
                               |              |              |
                        +------+----+  +------+-----+ +------+------+
                        |EqualSplit |  |ExactSplit  | |PercentSplit |
                        |Strategy   |  |Strategy    | |Strategy     |
                        +-----------+  +------------+ +-------------+

   +-----------+        +------------------------------+
   |   User    |        |          Expense             |
   +-----------+        +------------------------------+
   | id        |<>------| paidBy : Map<User, amount>   |
   | name      |        | splits : List<Split>         |
   +-----------+        | total, description, id       |
        ^               +--------------+---------------+
        |                              | contains
        |                       +------v------+
        |                       |   Split     |  (user, amount)
        |                       +-------------+
        |
   +----+------+
   |   Group   |  has users + expenses
   +-----------+

Step 4 — The Strategy pattern for split types

This is the pattern the interviewer is fishing for. The split type is the thing that varies; the rest of addExpense is invariant. That is the textbook trigger for Strategy: encapsulate each algorithm behind a common interface and select at runtime. A SplitStrategyFactory maps the enum to a singleton strategy (the strategies are stateless, so one shared instance each is correct and avoids per-call allocation).

Each strategy validates and produces concrete cent amounts. The crucial validations:

• EQUAL: divide total by N. The remainder cents must go somewhere — distribute leftover 1-cent units to the first total % N participants so the sum still equals the total.
• EXACT: caller supplies an amount for every participant; reject any missing value, then assert sum(amounts) == total. A participant legitimately owing 0 must still pass an explicit 0, which is why a missing value and a 0 value must be distinguishable.
• PERCENT: every participant must carry a percent; percentages must sum to 100; convert to cents with the same remainder-distribution care.

type Cents = number; // integer minor units

// Resolved share of an expense. amount is mutable so the percent strategy
// can distribute rounding remainder cents in a round-robin pass.
class Split {
constructor(readonly user: User, public amount: Cents) {}
}

// value is undefined for EQUAL; an exact cents amount for EXACT;
// a percent (0..100) for PERCENT. undefined !== 0 is load-bearing.
interface SplitInput { user: User; value?: number; }

interface SplitStrategy {
computeSplits(total: Cents, inputs: SplitInput[]): Split[];
}

class EqualSplitStrategy implements SplitStrategy {
computeSplits(total: Cents, inputs: SplitInput[]): Split[] {
  const n = inputs.length;
  if (n === 0) throw new Error("no participants");
  const base = Math.floor(total / n);
  let remainder = total - base * n; // cents to sprinkle
  return inputs.map(({ user }) => {
    const extra = remainder > 0 ? 1 : 0;
    remainder -= extra;
    return new Split(user, base + extra);
  });
}
}

class ExactSplitStrategy implements SplitStrategy {
computeSplits(total: Cents, inputs: SplitInput[]): Split[] {
  if (inputs.length === 0) throw new Error("no participants");
  for (const i of inputs)
    if (i.value === undefined) throw new Error("exact split requires a value for every participant");
  const sum = inputs.reduce((s, i) => s + i.value!, 0);
  if (sum !== total) throw new Error(`exact splits sum ${sum} != total ${total}`);
  return inputs.map(i => new Split(i.user, i.value!));
}
}

class PercentSplitStrategy implements SplitStrategy {
computeSplits(total: Cents, inputs: SplitInput[]): Split[] {
  if (inputs.length === 0) throw new Error("no participants");
  for (const i of inputs)
    if (i.value === undefined) throw new Error("percent split requires a value for every participant");
  const pct = inputs.reduce((s, i) => s + i.value!, 0);
  if (pct !== 100) throw new Error(`percentages sum ${pct} != 100`);
  const splits = inputs.map(i => new Split(i.user, Math.floor(total * i.value! / 100)));
  let assigned = splits.reduce((s, x) => s + x.amount, 0);
  let remainder = total - assigned;            // distribute rounding leftover
  for (let k = 0; remainder > 0; k = (k + 1) % splits.length) {
    splits[k].amount += 1; remainder -= 1;
  }
  return splits;
}
}

class SplitStrategyFactory {
private static map: Record<string, SplitStrategy> = {
  EQUAL: new EqualSplitStrategy(),
  EXACT: new ExactSplitStrategy(),
  PERCENT: new PercentSplitStrategy(),
};
static get(type: string): SplitStrategy {
  const s = this.map[type];
  if (!s) throw new Error("unknown split type " + type);
  return s;
}
}

Step 5 — The balance sheet and addExpense

addExpense is the orchestration method: resolve the strategy, compute splits, validate the zero-sum invariant, then fold the result into the ledger.

The semantically correct ledger update is the part candidates botch. The naive trick is “compute each user’s net (paid - owed), then greedily match net-debtors to net-creditors.” That keeps per-user nets correct, but the pairwise edges it produces are arbitrary fiction — with multiple payers it can claim “B owes C” when neither paid for the other. If your class exposes pairwise(a, b), you must record the real relationships: every non-payer owes their share to the payer(s) who actually fronted the cash.

The clean, correct formulation: compute per-user net = paid - share. Net-debtors owe net-creditors; match them with a two-pointer greedy pass. For the overwhelmingly common single-payer case this is exact (everyone who owes, owes the one payer). For multiple payers it walks the debtor and creditor lists in iteration order, settling give = min(remaining debt, remaining credit) at each step and advancing whichever side hits zero — a first-fit greedy decomposition, not a proportional one. The resulting edges are still real (each debtor owes some actual payer), and the row/column sums still equal the per-user nets, so balanceOf and DebtSimplifier remain correct; the exact pairing just depends on list order rather than splitting each debt proportionally across payers.

type Cents = number;

class BalanceSheet {
// balances[debtor][creditor] = how much debtor owes creditor.
// Antisymmetric: balances[a][b] === -balances[b][a].
private balances = new Map<string, Map<string, number>>();

private bump(a: string, b: string, d: number) {
  const row = this.balances.get(a) ?? new Map<string, number>();
  row.set(b, (row.get(b) ?? 0) + d);
  this.balances.set(a, row);
}
// debtor owes creditor 'amt' more; keep the antisymmetric mirror in sync.
private adjust(debtor: string, creditor: string, amt: number) {
  if (debtor === creditor || amt === 0) return;
  this.bump(debtor, creditor, amt);
  this.bump(creditor, debtor, -amt);
}

applyExpense(paidBy: Map<User, number>, splits: Split[]) {
  // net per user = paid - owed
  const net = new Map<string, number>();
  paidBy.forEach((amt, u) => net.set(u.id, (net.get(u.id) ?? 0) + amt));
  for (const s of splits) net.set(s.user.id, (net.get(s.user.id) ?? 0) - s.amount);

  // creditors are owed money (net > 0); debtors owe (net < 0, stored positive)
  const creditors = [...net].filter(([, v]) => v > 0).map(([k, v]) => [k, v] as [string, number]);
  const debtors   = [...net].filter(([, v]) => v < 0).map(([k, v]) => [k, -v] as [string, number]);

  // Two-pointer greedy: walk debtors/creditors in order, settling
  // min(remaining debt, remaining credit) at each step (first-fit, not
  // proportional). Single creditor => every edge points straight at them.
  let i = 0, j = 0;
  while (i < debtors.length && j < creditors.length) {
    const give = Math.min(debtors[i][1], creditors[j][1]);
    this.adjust(debtors[i][0], creditors[j][0], give); // debtor owes creditor
    debtors[i][1] -= give; creditors[j][1] -= give;
    if (debtors[i][1] === 0) i++;
    if (creditors[j][1] === 0) j++;
  }
}

pairwise(a: string, b: string): number { return this.balances.get(a)?.get(b) ?? 0; }

balanceOf(u: string): number {
  let net = 0;
  const row = this.balances.get(u);
  if (row) for (const v of row.values()) net -= v; // positive => u is owed overall
  return net;
}

// snapshot of per-user net (used by DebtSimplifier)
nets(): Map<string, number> {
  const out = new Map<string, number>();
  for (const [a, row] of this.balances)
    for (const v of row.values()) out.set(a, (out.get(a) ?? 0) - v);
  return out;
}
}

Worked numeric trace

A pays 90 for an equal split of {A, B, C}.

1. EqualSplitStrategy: base = 30, remainder 0 → splits A:30, B:30, C:30.
2. Nets: A = 90 − 30 = +60 (creditor), B = 0 − 30 = −30 (debtor), C = −30 (debtor).
3. Match (two-pointer): debtors [B:30, C:30], creditors [A:60].
   • B owes min(30, 60)=30 to A → balances[B][A]=30, balances[A][B]=−30. Creditor A left = 30.
   • C owes min(30, 30)=30 to A → balances[C][A]=30, balances[A][C]=−30.
4. Result: pairwise("B","A") = 30, pairwise("A","B") = −30, and balanceOf("A") = −( −30 + −30 ) = +60 — A is owed 60. Every pairwise edge is a real debt to the actual payer. The antisymmetric invariant holds over genuine quantities, not fictional ones.

Step 6 — The marquee algorithm: DebtSimplifier

Now the graph payload. After many expenses you have a directed multigraph of “who owes whom.” Settle-up minimization: find the fewest transactions that zero everyone out. The exact minimum is NP-hard (it reduces to a partition-style problem), so production systems and interviews use the standard greedy min-cash-flow heuristic:

1. Collapse the graph to a single net balance per person (sum of their row in the ledger; positive = they are owed). Net of all nets is zero.
2. Repeatedly take the person with the largest debt and the person with the largest credit, settle min(debt, credit) between them in one transaction, and push the leftover back.
3. Continue until all nets are zero.

Each transaction zeroes at least one person, so it emits at most n − 1 transactions for n non-zero people — a strong, usually optimal-in-practice bound. Two max-heaps (one for debtors, one for creditors) give O(n log n).

interface Transaction { from: string; to: string; amount: number; }

class DebtSimplifier {
// greedy max-debtor vs max-creditor; <= n-1 transactions, O(n log n)
static minimize(nets: Map<string, number>): Transaction[] {
  // simple array-based priority selection keeps it dependency-free;
  // swap in a binary heap for O(n log n) instead of O(n^2).
  const debtors:   [string, number][] = []; // amount they owe (positive)
  const creditors: [string, number][] = []; // amount they are owed (positive)
  for (const [u, v] of nets) {
    if (v < 0) debtors.push([u, -v]);
    else if (v > 0) creditors.push([u, v]);
  }
  const txns: Transaction[] = [];
  while (debtors.length && creditors.length) {
    // pick max debtor and max creditor
    let di = 0, ci = 0;
    for (let k = 1; k < debtors.length; k++) if (debtors[k][1] > debtors[di][1]) di = k;
    for (let k = 1; k < creditors.length; k++) if (creditors[k][1] > creditors[ci][1]) ci = k;
    const pay = Math.min(debtors[di][1], creditors[ci][1]);
    txns.push({ from: debtors[di][0], to: creditors[ci][0], amount: pay });
    debtors[di][1] -= pay; creditors[ci][1] -= pay;
    if (debtors[di][1] === 0) debtors.splice(di, 1);
    if (creditors[ci][1] === 0) creditors.splice(ci, 1);
  }
  return txns;
}
}

Trace it back: with nets A:+60, B:−30, C:−30, the simplifier pops max-debtor B(30) vs max-creditor A(60) → “B pays A 30”, then C(30) vs A(30) → “C pays A 30”. Two transactions, matching the worked ledger above. For A:+10, B:+10, C:−20 it emits “C→A 10, C→B 10” — still n−1 = 2.

Step 7 — Edge cases interviewers probe

• Rounding leftover cents. Covered by remainder distribution; state it explicitly — 100 / 3 cents must still sum to 100.
• Exact/percent sum mismatch. Reject loudly (sum != total, pct != 100). Never silently re-normalize.
• Missing value vs explicit 0. The tri-state optional guard. Someone owing 0 is valid; a forgotten field is not.
• Self-payment / self-owe. adjust ignores debtor == creditor; a payer’s own share simply reduces their net.
• Empty participant list → error in every strategy (note the C++ empty-input guard is now in all three, not just equal).
• Duplicate user in inputs → decide: merge, or reject. State your choice.
• Settling a partial amount → recordPayment(from, to, amt) just calls adjust(from, to, -amt) (paying down a debt). Free, because the ledger is the source of truth.
• Concurrency → wrap applyExpense/recordPayment in a per-group lock; reads can be lock-free snapshots.

Step 8 — Patterns and extensibility

“What if they ask for X?”

• A new split type (e.g. SHARES/weights) → add one WeightedSplitStrategy, register it in the factory. No existing class changes — that’s the Strategy payoff (Open/Closed).
• Multi-currency → make Cents a Money{amount, currency}; balances become per-currency; simplification runs per currency. The wrapper shown in Step 2 already anticipates this.
• Group-scoped simplification → DebtSimplifier.minimize takes the nets of just that group’s members.
• Audit / history → already there: replay the expense log.
• Recurring expenses → a scheduler that calls addExpense on a cadence; pure orchestration, no domain change.