Low-level design · Problem P11 of 15 · Bigger designs

Expense sharing (Splitwise)

Splitwise questions test two things: whether you model the different ways to split a bill cleanly, and whether you can keep money exact. Most bugs here are lost cents.

1. The prompt

The prompt"Design an app where friends record shared expenses and see who owes whom. Expenses can be split equally, by exact amounts or by percentages. Show a way to settle up."

2. Clarify the requirements

Spend the first five minutes here. Ask, then write the answers down where the interviewer can see them.

Ask	Assume (unless told otherwise)
Money type?	Integer cents; never floats.
Leftover cents in an equal split?	Given to the first participants, one each.
Must exact shares add up?	Yes, or the expense is rejected.
Is 'settle up' required to be minimal?	Short is enough; the greedy method gives at most n − 1 transfers.

Must do

Record an expense: payer, amount, participants, split type
Equal, exact and percent splits
Net balance per person
A short list of transfers that settles everyone

Must be

Shares always add up to the amount exactly
New split types without editing the ledger
Fast for groups of tens of people

Out of scope

Currencies
Groups and permissions
Payment integration

3. The classes

The class diagram: arrows show who uses or holds whom.

Class	Its one job
Ledger	Net balance per person; adds expenses; computes settlements
SplitStrategy	How an amount becomes shares
EqualSplit / ExactSplit / PercentSplit	The three split rules, each validating its own inputs

4. How it works

5. Patterns and why

Pattern	Where	Why it's worth it here
Strategy	SplitStrategy implementations	A new 'by shares' or 'by item' split is a new class
Net balances	One number per person instead of a matrix of debts	Settling only needs who is up and who is down
Greedy settlement	Largest debtor pays largest creditor	Each transfer settles at least one person: at most n − 1 transfers

Memory hook: "Cents in, nets out, greedy settle"Split in integer cents so shares add up exactly, keep one net balance per person, and settle biggest debtor against biggest creditor.

6. The code

All amounts are integer cents. Each strategy guarantees its shares add up to the amount, so the ledger always balances to zero.

from __future__ import annotations
from abc import ABC, abstractmethod


class SplitStrategy(ABC):
    """Turns one amount into each person's share. Cents only: shares always add up to the amount exactly."""

    @abstractmethod
    def shares(self, amount: int, people: list[str]) -> dict[str, int]: ...


class EqualSplit(SplitStrategy):
    def shares(self, amount: int, people: list[str]) -> dict[str, int]:
        base, extra = divmod(amount, len(people))
        return {p: base + (1 if i < extra else 0) for i, p in enumerate(people)}   # leftover cents go to the first people


class ExactSplit(SplitStrategy):
    def __init__(self, amounts: dict[str, int]) -> None:
        self.amounts = amounts

    def shares(self, amount: int, people: list[str]) -> dict[str, int]:
        if sum(self.amounts.values()) != amount:
            raise ValueError("exact shares must add up to the amount")
        return dict(self.amounts)


class PercentSplit(SplitStrategy):
    def __init__(self, percents: dict[str, int]) -> None:
        if sum(percents.values()) != 100:
            raise ValueError("percentages must add up to 100")
        self.percents = percents

    def shares(self, amount: int, people: list[str]) -> dict[str, int]:
        out = {p: amount * pc // 100 for p, pc in self.percents.items()}
        first = next(iter(out))
        out[first] += amount - sum(out.values())   # rounding leftover to the first person
        return out


class Ledger:
    def __init__(self) -> None:
        self.net: dict[str, int] = {}   # positive: is owed money; negative: owes money

    def add_expense(self, paid_by: str, amount: int, people: list[str], split: SplitStrategy) -> None:
        shares = split.shares(amount, people)
        self.net[paid_by] = self.net.get(paid_by, 0) + amount
        for p, s in shares.items():
            self.net[p] = self.net.get(p, 0) - s

    def settle_up(self) -> list[tuple[str, str, int]]:
        """Greedy: the biggest debtor pays the biggest creditor until everyone is square. At most n-1 transfers."""
        bal = {p: v for p, v in self.net.items() if v}
        transfers = []
        while bal:
            creditor = max(sorted(bal), key=lambda p: bal[p])
            debtor = min(sorted(bal), key=lambda p: bal[p])
            pay = min(bal[creditor], -bal[debtor])
            transfers.append((debtor, creditor, pay))
            for p, d in ((creditor, -pay), (debtor, pay)):
                bal[p] += d
                if bal[p] == 0:
                    del bal[p]
        return transfers


def money(c: int) -> str:
    sign = "-" if c < 0 else ""
    return f"{sign}${abs(c) // 100}.{abs(c) % 100:02d}"


if __name__ == "__main__":
    led = Ledger()
    led.add_expense("ana", 12000, ["ana", "ben", "cara", "dev"], EqualSplit())
    led.add_expense("ben", 9000, ["ben", "cara", "dev"], ExactSplit({"ben": 1000, "cara": 5000, "dev": 3000}))
    led.add_expense("cara", 10000, ["ana", "cara", "dev"], PercentSplit({"ana": 50, "cara": 25, "dev": 25}))
    led.add_expense("dev", 1000, ["ana", "ben", "cara"], EqualSplit())
    print("balances:", ", ".join(f"{p} {money(v)}" for p, v in sorted(led.net.items())))
    for debtor, creditor, amount in led.settle_up():
        print(f"{debtor} pays {creditor} {money(amount)}")

/** Turns one amount into each person's share. Cents only: shares always add up to the amount exactly. */
interface SplitStrategy { shares(amount: number, people: string[]): Map<string, number>; }

class EqualSplit implements SplitStrategy {
  shares(amount: number, people: string[]): Map<string, number> {
    const base = Math.floor(amount / people.length), extra = amount % people.length;
    return new Map(people.map((p, i) => [p, base + (i < extra ? 1 : 0)])); // leftover cents go to the first people
  }
}

class ExactSplit implements SplitStrategy {
  constructor(private amounts: Map<string, number>) {}
  shares(amount: number): Map<string, number> {
    if ([...this.amounts.values()].reduce((a, b) => a + b, 0) !== amount) throw new Error("exact shares must add up to the amount");
    return new Map(this.amounts);
  }
}

class PercentSplit implements SplitStrategy {
  constructor(private percents: Map<string, number>) {
    if ([...percents.values()].reduce((a, b) => a + b, 0) !== 100) throw new Error("percentages must add up to 100");
  }
  shares(amount: number): Map<string, number> {
    const out = new Map([...this.percents].map(([p, pc]) => [p, Math.floor((amount * pc) / 100)]));
    const first = out.keys().next().value as string;
    out.set(first, out.get(first)! + amount - [...out.values()].reduce((a, b) => a + b, 0)); // rounding leftover to the first person
    return out;
  }
}

class Ledger {
  readonly net = new Map<string, number>(); // positive: is owed money; negative: owes money

  addExpense(paidBy: string, amount: number, people: string[], split: SplitStrategy): void {
    const shares = split.shares(amount, people);
    this.net.set(paidBy, (this.net.get(paidBy) ?? 0) + amount);
    for (const [p, s] of shares) this.net.set(p, (this.net.get(p) ?? 0) - s);
  }

  /** Greedy: the biggest debtor pays the biggest creditor until everyone is square. At most n-1 transfers. */
  settleUp(): [string, string, number][] {
    const bal = new Map([...this.net].filter(([, v]) => v !== 0));
    const out: [string, string, number][] = [];
    while (bal.size) {
      const names = [...bal.keys()].sort();
      const creditor = names.reduce((a, b) => (bal.get(b)! > bal.get(a)! ? b : a));
      const debtor = names.reduce((a, b) => (bal.get(b)! < bal.get(a)! ? b : a));
      const pay = Math.min(bal.get(creditor)!, -bal.get(debtor)!);
      out.push([debtor, creditor, pay]);
      for (const [p, d] of [[creditor, -pay], [debtor, pay]] as [string, number][]) {
        bal.set(p, bal.get(p)! + d);
        if (bal.get(p) === 0) bal.delete(p);
      }
    }
    return out;
  }
}

const money = (c: number) => `${c < 0 ? "-" : ""}$${Math.floor(Math.abs(c) / 100)}.${String(Math.abs(c) % 100).padStart(2, "0")}`;

const led = new Ledger();
led.addExpense("ana", 12000, ["ana", "ben", "cara", "dev"], new EqualSplit());
led.addExpense("ben", 9000, ["ben", "cara", "dev"], new ExactSplit(new Map([["ben", 1000], ["cara", 5000], ["dev", 3000]])));
led.addExpense("cara", 10000, ["ana", "cara", "dev"], new PercentSplit(new Map([["ana", 50], ["cara", 25], ["dev", 25]])));
led.addExpense("dev", 1000, ["ana", "ben", "cara"], new EqualSplit());
console.log("balances:", [...led.net].sort((a, b) => a[0].localeCompare(b[0])).map(([p, v]) => `${p} ${money(v)}`).join(", "));
for (const [debtor, creditor, amount] of led.settleUp()) console.log(`${debtor} pays ${creditor} ${money(amount)}`);

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import java.util.stream.Collectors;

/** Turns one amount into each person's share. Cents only: shares always add up to the amount exactly. */
interface SplitStrategy {
    Map<String, Integer> shares(int amount, List<String> people);
}

class EqualSplit implements SplitStrategy {
    public Map<String, Integer> shares(int amount, List<String> people) {
        int base = amount / people.size(), extra = amount % people.size();
        Map<String, Integer> out = new LinkedHashMap<>();
        for (int i = 0; i < people.size(); i++) out.put(people.get(i), base + (i < extra ? 1 : 0)); // leftover cents go to the first people
        return out;
    }
}

class ExactSplit implements SplitStrategy {
    private final Map<String, Integer> amounts;

    ExactSplit(Map<String, Integer> amounts) {
        this.amounts = amounts;
    }

    public Map<String, Integer> shares(int amount, List<String> people) {
        if (amounts.values().stream().mapToInt(Integer::intValue).sum() != amount)
            throw new IllegalArgumentException("exact shares must add up to the amount");
        return new LinkedHashMap<>(amounts);
    }
}

class PercentSplit implements SplitStrategy {
    private final Map<String, Integer> percents;

    PercentSplit(Map<String, Integer> percents) {
        if (percents.values().stream().mapToInt(Integer::intValue).sum() != 100)
            throw new IllegalArgumentException("percentages must add up to 100");
        this.percents = percents;
    }

    public Map<String, Integer> shares(int amount, List<String> people) {
        Map<String, Integer> out = new LinkedHashMap<>();
        percents.forEach((p, pc) -> out.put(p, amount * pc / 100));
        String first = out.keySet().iterator().next();
        out.merge(first, amount - out.values().stream().mapToInt(Integer::intValue).sum(), Integer::sum); // rounding leftover to the first person
        return out;
    }
}

record Transfer(String debtor, String creditor, int amount) {}

class Ledger {
    final Map<String, Integer> net = new TreeMap<>(); // positive: is owed money; negative: owes money

    synchronized void addExpense(String paidBy, int amount, List<String> people, SplitStrategy split) {
        Map<String, Integer> shares = split.shares(amount, people);
        net.merge(paidBy, amount, Integer::sum);
        shares.forEach((p, s) -> net.merge(p, -s, Integer::sum));
    }

    /** Greedy: the biggest debtor pays the biggest creditor until everyone is square. At most n-1 transfers. */
    synchronized List<Transfer> settleUp() {
        TreeMap<String, Integer> bal = new TreeMap<>();
        net.forEach((p, v) -> { if (v != 0) bal.put(p, v); });
        List<Transfer> out = new ArrayList<>();
        while (!bal.isEmpty()) {
            String creditor = bal.firstKey(), debtor = bal.firstKey();
            for (String p : bal.keySet()) {
                if (bal.get(p) > bal.get(creditor)) creditor = p;
                if (bal.get(p) < bal.get(debtor)) debtor = p;
            }
            int pay = Math.min(bal.get(creditor), -bal.get(debtor));
            out.add(new Transfer(debtor, creditor, pay));
            for (Object[] pd : new Object[][] {{creditor, -pay}, {debtor, pay}}) {
                String p = (String) pd[0];
                int v = bal.get(p) + (Integer) pd[1];
                if (v == 0) bal.remove(p); else bal.put(p, v);
            }
        }
        return out;
    }
}

public class Main {
    static String money(int c) {
        int a = Math.abs(c);
        return (c < 0 ? "-" : "") + "$" + (a / 100) + "." + (a % 100 < 10 ? "0" : "") + (a % 100);
    }

    static Map<String, Integer> ordered(Object... kv) {
        Map<String, Integer> m = new LinkedHashMap<>();
        for (int i = 0; i < kv.length; i += 2) m.put((String) kv[i], (Integer) kv[i + 1]);
        return m;
    }

    public static void main(String[] args) {
        Ledger led = new Ledger();
        led.addExpense("ana", 12000, List.of("ana", "ben", "cara", "dev"), new EqualSplit());
        led.addExpense("ben", 9000, List.of("ben", "cara", "dev"), new ExactSplit(ordered("ben", 1000, "cara", 5000, "dev", 3000)));
        led.addExpense("cara", 10000, List.of("ana", "cara", "dev"), new PercentSplit(ordered("ana", 50, "cara", 25, "dev", 25)));
        led.addExpense("dev", 1000, List.of("ana", "ben", "cara"), new EqualSplit());
        System.out.println("balances: " + led.net.entrySet().stream().map(e -> e.getKey() + " " + money(e.getValue())).collect(Collectors.joining(", ")));
        for (Transfer t : led.settleUp()) System.out.println(t.debtor() + " pays " + t.creditor() + " " + money(t.amount()));
    }
}

Output (the same in all three languages)

balances: ana $36.66, ben $46.67, cara -$8.33, dev -$75.00
dev pays ben $46.67
dev pays ana $28.33
cara pays ana $8.33

7. Concurrency and edge cases

Lost cents: $10.00 split three ways is 334 + 333 + 333, not 333.33 × 3. Every strategy hands leftover cents to someone deterministically.
Two people adding expenses to one group at once: updates to the balances must be atomic (the Java version synchronizes; a database would update rows in one transaction).
Deleting an expense is easier if balances are derived from the list of expenses (recompute or apply the reverse), so keep the expenses, not just the totals.

8. Follow-up questions

What interviewers ask once the core works, and a short answer for each.

Is greedy settlement minimal?: Not always: the minimum number of transfers is NP-hard in general. Greedy gives at most n − 1, which is what users need.
Multiple currencies?: Store each expense in its own currency; convert at settlement time with a recorded rate.
Split by shares (2:1:1)?: A new SplitStrategy: amount × share / total shares, with leftover cents handed out.
Show who owes whom without settling?: Keep pairwise balances too, updated per expense, if users want 'you owe Ben $12'.

9. Common mistakes

Floats for moneyRounding errors accumulate; balances stop summing to zero.

A switch on split type in the ledgerEvery new split type edits the ledger. Use a strategy.

Not validating exact or percent splitsShares that don't add up create or destroy money.

10. Check yourself

Why integer cents?

Exact arithmetic keeps the ledger balanced to zero.

At most how many transfers does greedy settlement need for n people?

Each transfer settles at least one person.

A new 'split by shares' type is needed. What changes?

Strategy pattern.

Your turn

Add split by shares (10 min). 2:1:1 and so on, exact to the cent.
Support deleting an expense (10 min). Apply the reverse of its shares.