Low Level DesignWorked problems
Design Splitwise
Design an expense-sharing app like Splitwise step by step for a low level design interview. Grow from one equal split to equal, exact and percent splits that never lose a cent, balances kept as a running ledger, groups with settle-up and deletes, simplifying who owes whom, and expenses added from many phones at once, with code in Java, Python, C#, Go and TypeScript.
- Patterns
- Strategy
“Design Splitwise: friends add shared expenses, the app tracks who owes whom, and they settle up.” Usually followed by “and can you reduce the number of payments?”
Splitwise looks like bookkeeping, and most of it is. But the design questions are small and sharp. How do you split 100.00 three ways without a cent going missing? Where do the rules for equal, exact and percent splits live, so a fourth kind doesn’t touch the rest? How do balances stay right when an expense is deleted or a payment is made? And how do you turn a tangle of debts into a few payments?
Interviewers use this question to see whether you handle money with care, and whether the split
logic can take new kinds without an if for each one.
The answer in one minute
Section titled “The answer in one minute”If you only have a minute, this is the design. The rest of the page explains how we get here.
- Money is whole cents, and every split adds up exactly. 100.00 three ways is 33.34, 33.33 and 33.33. The leftover cents go to someone by a fixed rule, and none disappear.
- Each kind of split is its own class. Equal, exact amounts and percentages each turn a total into shares behind one interface. A new kind is a new class.
- Balances are a running total. Each expense updates them as it arrives. Deleting an expense applies it again with the signs flipped, so nothing is ever rebuilt from history.
- Simplifying debts only needs each person’s net. Match the person who owes the most with the person owed the most, again and again. A group of n people settles in at most n − 1 payments.
- One lock per group. Expenses added from several phones at once are all counted.
We’ll build this in four stages, then deal with three phones adding expenses at once.
Scope it
Section titled “Scope it”Before drawing anything, we ask a few questions. Each answer changes a class. Anything that doesn’t, we assume and move on.
Design Splitwise.
What they are testing
Whether you pin down the kinds of split, and how money is stored, within two minutes. Candidates who start with user profiles, friend requests and notifications rarely reach the balance logic, which is the question.
Here are the questions that matter:
- Which kinds of split? Equal, exact amounts, and percentages. Shares by weight (“2 adults, 1 child”) would be one more kind.
- One currency? Yes, with amounts in cents. Several currencies come later as an extension.
- Who pays? One person pays each expense.
- Groups? Yes: a trip, a flat. Balances are kept per group. Expenses between two friends are a group of two.
- Simplify debts? Yes, as a suggested list of payments.
These answers give us one promise that matters more than the others: every split adds up to exactly what was paid, to the cent, and so do the balances. Three smaller promises come with it. An invalid split (exact amounts that don’t add up, percentages that aren’t 100) is refused, and nothing is recorded. Deleting an expense puts every balance back to what it would have been without it. And expenses added at the same moment from several phones are all counted.
We leave out moving real money, receipts and photos, notifications, and currency conversion.
Go deeperThree more questions, and what each changes1 min
| Question | We assume | If the answer were different |
|---|---|---|
| Edit and delete expenses? | Delete, and edit as delete then add | A history of changes is an extension |
| Does the app move money? | No: settling up records a payment made elsewhere | Real payments add a payment provider and a “pending” state |
| How big are groups? | A few to a few dozen people | Huge groups change nothing; the busy spot is one active group |
Build it
Section titled “Build it”We’ll build the design in four stages. Each stage adds only the classes that a new requirement needs. In each diagram, the new parts are outlined, and the colors show what each class does (the key is under every diagram).
Stage 1: An expense split equally
Section titled “Stage 1: An expense split equally”Start simple: Ana pays 30.00 for lunch for Ana, Ben and Cy. How do you record it, and how do you answer “how much does Ben owe Ana?”
What they are testing
Whether the payer’s own share is handled (Ana doesn’t owe herself), and whether “owes” has a direction and can be negative. They also notice what type you use for money.
Start with the smallest thing that works. An Expense records who paid, the total in cents, and who
shared it. Splitwise keeps the users and the list of expenses.
To answer “how much does Ben owe Ana?”, it goes through every expense. Each one Ana paid that Ben shared adds Ben’s share. Each one Ben paid that Ana shared takes away Ana’s share. A negative answer means Ana owes Ben.
Scroll or pinch to zoom, drag to pan
- Color key
- Facade
- Entity
- Value object
- Enum
- Interface
- Implementation
- New in this step
// Money is a whole number of cents. A double can't hold 0.10 exactly, and a ledger that drifts// by a fraction of a cent per expense is wrong by real money after a year of dinners.record Expense(String id, String paidBy, long total, List<String> people) {}
class Splitwise { private final Set<String> users = new HashSet<>(); private final List<Expense> expenses = new ArrayList<>(); private final Supplier<String> ids;
Splitwise(Supplier<String> ids) { this.ids = ids; }
void addUser(String user) { users.add(user); }
// flaw 1: only equal splits. Rent is split by room size, a dinner by what each person ate. // flaw 2: total / n drops cents. 100.00 three ways records 33.33 for each of them, and the // third cent the payer spent is owed by nobody. Expense addExpense(String paidBy, long total, List<String> people) { if (!users.contains(paidBy) || !users.containsAll(people)) return null; Expense e = new Expense(ids.get(), paidBy, total, people); expenses.add(e); return e; }
// How much the debtor owes the creditor; negative when it's the other way round. // flaw 3: every question replays every expense the app has ever recorded. long owes(String debtor, String creditor) { long sum = 0; for (Expense e : expenses) { long share = e.total() / e.people().size(); if (e.paidBy().equals(creditor) && e.people().contains(debtor)) sum += share; if (e.paidBy().equals(debtor) && e.people().contains(creditor)) sum -= share; } return sum; }}from dataclasses import dataclassfrom typing import Callable
# Money is a whole number of cents. A float can't hold 0.10 exactly, and a ledger that drifts by# a fraction of a cent per expense is wrong by real money after a year of dinners.@dataclass(frozen=True)class Expense: id: str paid_by: str total: int people: list[str]
class Splitwise: def __init__(self, ids: Callable[[], str]): self._users: set[str] = set() self._expenses: list[Expense] = [] self._ids = ids
def add_user(self, user: str) -> None: self._users.add(user)
# flaw 1: only equal splits. Rent is split by room size, a dinner by what each person ate. # flaw 2: total // n drops cents. 100.00 three ways records 33.33 for each of them, and the # third cent the payer spent is owed by nobody. def add_expense(self, paid_by: str, total: int, people: list[str]) -> Expense | None: if paid_by not in self._users or not self._users.issuperset(people): return None e = Expense(self._ids(), paid_by, total, people) self._expenses.append(e) return e
# How much the debtor owes the creditor; negative when it's the other way round. # flaw 3: every question replays every expense the app has ever recorded. def owes(self, debtor: str, creditor: str) -> int: total = 0 for e in self._expenses: share = e.total // len(e.people) if e.paid_by == creditor and debtor in e.people: total += share if e.paid_by == debtor and creditor in e.people: total -= share return total// Money is a whole number of cents. A double can't hold 0.10 exactly, and a ledger that drifts// by a fraction of a cent per expense is wrong by real money after a year of dinners.public sealed record Expense(string Id, string PaidBy, long Total, IReadOnlyList<string> People);
public sealed class Splitwise(Func<string> ids){ private readonly HashSet<string> _users = []; private readonly List<Expense> _expenses = [];
public void AddUser(string user) => _users.Add(user);
// flaw 1: only equal splits. Rent is split by room size, a dinner by what each person ate. // flaw 2: Total / n drops cents. 100.00 three ways records 33.33 for each of them, and the // third cent the payer spent is owed by nobody. public Expense? AddExpense(string paidBy, long total, IReadOnlyList<string> people) { if (!_users.Contains(paidBy) || !people.All(_users.Contains)) return null; var e = new Expense(ids(), paidBy, total, people); _expenses.Add(e); return e; }
// How much the debtor owes the creditor; negative when it's the other way round. // flaw 3: every question replays every expense the app has ever recorded. public long Owes(string debtor, string creditor) { long sum = 0; foreach (var e in _expenses) { var share = e.Total / e.People.Count; if (e.PaidBy == creditor && e.People.Contains(debtor)) sum += share; if (e.PaidBy == debtor && e.People.Contains(creditor)) sum -= share; } return sum; }}// Money is a whole number of cents. A float64 can't hold 0.10 exactly, and a ledger that drifts// by a fraction of a cent per expense is wrong by real money after a year of dinners.type Expense struct { ID string PaidBy string Total int64 People []string}
type Splitwise struct { users map[string]bool expenses []*Expense ids func() string}
func NewSplitwise(ids func() string) *Splitwise { return &Splitwise{users: map[string]bool{}, ids: ids}}
func (s *Splitwise) AddUser(user string) { s.users[user] = true }
// AddExpense has two flaws. Only equal splits exist (flaw 1): rent is split by room size, a// dinner by what each person ate. And Total / n drops cents (flaw 2): 100.00 three ways records// 33.33 for each of them, and the third cent the payer spent is owed by nobody.func (s *Splitwise) AddExpense(paidBy string, total int64, people []string) *Expense { if !s.users[paidBy] { return nil } for _, p := range people { if !s.users[p] { return nil } } e := &Expense{ID: s.ids(), PaidBy: paidBy, Total: total, People: people} s.expenses = append(s.expenses, e) return e}
// Owes is how much the debtor owes the creditor; negative when it's the other way round.// flaw 3: every question replays every expense the app has ever recorded.func (s *Splitwise) Owes(debtor, creditor string) int64 { var sum int64 for _, e := range s.expenses { share := e.Total / int64(len(e.People)) if e.PaidBy == creditor && slices.Contains(e.People, debtor) { sum += share } if e.PaidBy == debtor && slices.Contains(e.People, creditor) { sum -= share } } return sum}// Money is a whole number of cents. A JavaScript number can't hold 0.10 exactly, and a ledger// that drifts by a fraction of a cent per expense is wrong by real money after a year of dinners.interface Expense { readonly id: string; readonly paidBy: string; readonly total: number; readonly people: readonly string[];}
class Splitwise { private readonly users = new Set<string>(); private readonly expenses: Expense[] = [];
constructor(private readonly ids: () => string) {}
addUser(user: string): void { this.users.add(user); }
// flaw 1: only equal splits. Rent is split by room size, a dinner by what each person ate. // flaw 2: rounding each share down drops cents. 100.00 three ways records 33.33 for each of // them, and the third cent the payer spent is owed by nobody. addExpense(paidBy: string, total: number, people: string[]): Expense | null { if (!this.users.has(paidBy) || !people.every((p) => this.users.has(p))) return null; const e = { id: this.ids(), paidBy, total, people }; this.expenses.push(e); return e; }
// How much the debtor owes the creditor; negative when it's the other way round. // flaw 3: every question replays every expense the app has ever recorded. owes(debtor: string, creditor: string): number { let sum = 0; for (const e of this.expenses) { const share = Math.floor(e.total / e.people.length); if (e.paidBy === creditor && e.people.includes(debtor)) sum += share; if (e.paidBy === debtor && e.people.includes(creditor)) sum -= share; } return sum; }}It works, but it has three problems, and we leave them in on purpose. Only equal splits exist. Whole-number division drops cents: 100.00 three ways records 33.33 each, and the third cent Ana paid is owed by nobody. And every balance question goes through every expense ever recorded.
Stage 2: Splits that add up, and a running ledger
Section titled “Stage 2: Splits that add up, and a running ledger”Rent is split by room size: Ana pays 45%, Ben 35%, Cy 20%. And dinner was 62.40, where Ben had the steak. Add both, and make 100.00 three ways come out right.
What they are testing
Whether each kind of split becomes its own class behind one interface, or an if on a type
field inside addExpense. They also want to hear where the leftover cent goes, and that an
exact split that doesn’t add up is refused.
Each kind of split becomes a Split: an object that carries its own inputs, and turns a total into
a share per person. EqualSplit holds the people, ExactSplit the amounts, PercentSplit the
percentages. The expense code asks the split for shares and doesn’t know which kind it has. So a
fourth kind (by weight, by nights stayed) is one new class. This is the Strategy pattern.
Every split must return shares that add up to the total exactly. Equal and percent splits share
one helper, allocate. It works in three steps:
- Work out each person’s share, and round it down to a whole cent.
- Add up the rounded shares and see how many cents are left over.
- Give the leftover cents to the first people listed, one each.
So 100.00 three ways becomes 33.33 each, which is 99.99, with 1 cent left over. The first person gets it: 33.34, 33.33 and 33.33. Any rule works, as long as it always gives the same answer and nothing is lost.
An exact split checks that its amounts add up to what was paid. A percent split checks that its percentages add up to 100. If not, the expense is refused before anything is recorded.
Balances move into a Balances ledger, which is updated whenever an expense is added. So a
question is one lookup, not a trip through history. It’s two-sided: when Ben owes Ana 10.00,
owed[ben][ana] is 10.00 and owed[ana][ben] is −10.00. Recording a debt updates both. A person’s
net (are they up or down overall?) is the sum of their row, with the sign flipped. Positive
means they get money back.
Scroll or pinch to zoom, drag to pan
- Color key
- Facade
- Entity
- Value object
- Enum
- Interface
- Implementation
- New in this step
// How an expense is divided. Each kind of split carries its own inputs (who shares equally, the// exact amounts, the percentages) and turns a total into a share per person that adds up to// the total exactly. An impossible split returns null.interface Split { Map<String, Long> shares(long total);}
// Everyone listed pays the same. A name listed twice is a mistake, so the split is refused.class EqualSplit implements Split { private final List<String> people;
EqualSplit(List<String> people) { this.people = people; }
public Map<String, Long> shares(long total) { if (people.isEmpty() || new HashSet<>(people).size() != people.size()) return null; return Shares.allocate(total, people, Collections.nCopies(people.size(), 1L)); }}
class ExactSplit implements Split { private final Map<String, Long> amounts; // insertion order kept by the caller's LinkedHashMap
ExactSplit(Map<String, Long> amounts) { this.amounts = amounts; }
// The amounts are the shares, as long as they add up to what was paid. public Map<String, Long> shares(long total) { long sum = amounts.values().stream().mapToLong(Long::longValue).sum(); boolean negative = amounts.values().stream().anyMatch(a -> a < 0); return sum == total && !negative ? new LinkedHashMap<>(amounts) : null; }}
// Each person pays a percentage. The percentages must add up to exactly 100.class PercentSplit implements Split { private final Map<String, Integer> percents;
PercentSplit(Map<String, Integer> percents) { this.percents = percents; }
public Map<String, Long> shares(long total) { int sum = percents.values().stream().mapToInt(Integer::intValue).sum(); if (sum != 100 || percents.values().stream().anyMatch(p -> p < 0)) return null; List<Long> weights = percents.values().stream().map(Integer::longValue).toList(); return Shares.allocate(total, new ArrayList<>(percents.keySet()), weights); }}
// Used by the equal and percent splits: it turns weights into cents that add up exactly.class Shares { // Divides the total by weight, rounding each share down, then hands the cents left over to // the first people listed, one each. Any rule works if it's deterministic and the shares add // up to the total: 100.00 three ways is 33.34, 33.33 and 33.33, and no cent disappears. static Map<String, Long> allocate(long total, List<String> people, List<Long> weights) { long weightSum = weights.stream().mapToLong(Long::longValue).sum(); Map<String, Long> out = new LinkedHashMap<>(); long given = 0; for (int i = 0; i < people.size(); i++) { long share = total * weights.get(i) / weightSum; out.put(people.get(i), share); given += share; } for (int i = 0; given < total; i++, given++) out.merge(people.get(i), 1L, Long::sum); return out; }}
// Who owes whom, kept up to date as expenses arrive, so a question is one lookup. The map is// two-sided: when Ben owes Ana 10, owed[ben][ana] is 10 and owed[ana][ben] is -10.class Balances { private final Map<String, Map<String, Long>> owed = new HashMap<>();
void record(String debtor, String creditor, long amount) { if (debtor.equals(creditor) || amount == 0) return; add(debtor, creditor, amount); add(creditor, debtor, -amount); }
long owes(String debtor, String creditor) { return owed.getOrDefault(debtor, Map.of()).getOrDefault(creditor, 0L); }
// What everyone else owes this user in total: positive gets money back, negative pays. long net(String user) { return -owed.getOrDefault(user, Map.of()).values().stream().mapToLong(Long::longValue).sum(); }
private void add(String a, String b, long amount) { owed.computeIfAbsent(a, k -> new HashMap<>()).merge(b, amount, (x, y) -> x + y == 0 ? null : x + y); }}
// One bill, already split. It keeps the shares, not the split rule, so deleting it later undoes// exactly what it did.record Expense(String id, String description, String paidBy, long total, Map<String, Long> shares) {}
enum Result { OK, UNKNOWN_USER, INVALID_SPLIT }
// The result, plus the new expense when it worked.record ExpenseResult(Result result, Expense expense) {}
class Splitwise { private final Set<String> users = new HashSet<>(); private final Map<String, Expense> expenses = new HashMap<>(); private final Balances balances = new Balances(); private final Supplier<String> ids;
Splitwise(Supplier<String> ids) { this.ids = ids; }
void addUser(String user) { users.add(user); }
// Each person's share is owed to whoever paid. The payer's own share is money they spent on // themselves, so it creates no debt. ExpenseResult addExpense(String description, String paidBy, long total, Split split) { Map<String, Long> shares = split.shares(total); if (total <= 0 || shares == null) return new ExpenseResult(Result.INVALID_SPLIT, null); if (!users.contains(paidBy) || !users.containsAll(shares.keySet())) return new ExpenseResult(Result.UNKNOWN_USER, null); Expense e = new Expense(ids.get(), description, paidBy, total, shares); expenses.put(e.id(), e); shares.forEach((person, share) -> balances.record(person, paidBy, share)); return new ExpenseResult(Result.OK, e); }
long owes(String debtor, String creditor) { return balances.owes(debtor, creditor); }}from enum import Enum, autofrom typing import Protocol
# How an expense is divided. Each kind of split carries its own inputs (who shares equally, the# exact amounts, the percentages) and turns a total into a share per person that adds up to# the total exactly. An impossible split returns None.class Split(Protocol): def shares(self, total: int) -> dict[str, int] | None: ...
# Everyone listed pays the same. A name listed twice is a mistake, so the split is refused.class EqualSplit: def __init__(self, people: list[str]): self._people = people
def shares(self, total: int) -> dict[str, int] | None: if not self._people or len(set(self._people)) != len(self._people): return None return allocate(total, self._people, [1] * len(self._people))
class ExactSplit: def __init__(self, amounts: dict[str, int]): self._amounts = amounts
# The amounts are the shares, as long as they add up to what was paid. def shares(self, total: int) -> dict[str, int] | None: if sum(self._amounts.values()) != total or any(a < 0 for a in self._amounts.values()): return None return dict(self._amounts)
# Each person pays a percentage. The percentages must add up to exactly 100.class PercentSplit: def __init__(self, percents: dict[str, int]): self._percents = percents
def shares(self, total: int) -> dict[str, int] | None: if sum(self._percents.values()) != 100 or any(p < 0 for p in self._percents.values()): return None return allocate(total, list(self._percents), list(self._percents.values()))
# Divides the total by weight, rounding each share down, then hands the cents left over to the# first people listed, one each. Any rule works if it's deterministic and the shares add up to# the total: 100.00 three ways is 33.34, 33.33 and 33.33, and no cent disappears.def allocate(total: int, people: list[str], weights: list[int]) -> dict[str, int]: weight_sum = sum(weights) out = {p: total * w // weight_sum for p, w in zip(people, weights)} left = total - sum(out.values()) for p in people[:left]: out[p] += 1 return out
# Who owes whom, kept up to date as expenses arrive, so a question is one lookup. The map is# two-sided: when Ben owes Ana 10, owed[ben][ana] is 10 and owed[ana][ben] is -10.class Balances: def __init__(self): self._owed: dict[str, dict[str, int]] = {}
def record(self, debtor: str, creditor: str, amount: int) -> None: if debtor == creditor or amount == 0: return self._add(debtor, creditor, amount) self._add(creditor, debtor, -amount)
def owes(self, debtor: str, creditor: str) -> int: return self._owed.get(debtor, {}).get(creditor, 0)
# What everyone else owes this user in total: positive gets money back, negative pays. def net(self, user: str) -> int: return -sum(self._owed.get(user, {}).values())
def _add(self, a: str, b: str, amount: int) -> None: row = self._owed.setdefault(a, {}) row[b] = row.get(b, 0) + amount if row[b] == 0: del row[b]
# One bill, already split. It keeps the shares, not the split rule, so deleting it later undoes# exactly what it did.@dataclass(frozen=True)class Expense: id: str description: str paid_by: str total: int shares: dict[str, int]
class Result(Enum): OK = auto() UNKNOWN_USER = auto() INVALID_SPLIT = auto()
class Splitwise: def __init__(self, ids: Callable[[], str]): self._users: set[str] = set() self._expenses: dict[str, Expense] = {} self._balances = Balances() self._ids = ids
def add_user(self, user: str) -> None: self._users.add(user)
# Each person's share is owed to whoever paid. The payer's own share is money they spent on # themselves, so it creates no debt. def add_expense(self, description: str, paid_by: str, total: int, split: Split) -> tuple[Result, Expense | None]: shares = split.shares(total) if total <= 0 or shares is None: return Result.INVALID_SPLIT, None if paid_by not in self._users or not self._users.issuperset(shares): return Result.UNKNOWN_USER, None e = Expense(self._ids(), description, paid_by, total, shares) self._expenses[e.id] = e for person, share in shares.items(): self._balances.record(person, paid_by, share) return Result.OK, e
def owes(self, debtor: str, creditor: str) -> int: return self._balances.owes(debtor, creditor)// How an expense is divided. Each kind of split carries its own inputs (who shares equally, the// exact amounts, the percentages) and turns a total into a share per person that adds up to// the total exactly. Shares are a list of pairs, so their order (who gets a leftover cent) is// the order the caller listed them. An impossible split returns null.public interface ISplit{ List<(string Person, long Amount)>? Shares(long total);}
// Everyone listed pays the same. A name listed twice is a mistake, so the split is refused.public sealed class EqualSplit(IReadOnlyList<string> people) : ISplit{ public List<(string Person, long Amount)>? Shares(long total) => people.Count == 0 || people.Distinct().Count() != people.Count ? null : Allocation.Allocate(total, people, people.Select(_ => 1L).ToList());}
public sealed class ExactSplit(IReadOnlyList<(string Person, long Amount)> amounts) : ISplit{ // The amounts are the shares, as long as they add up to what was paid. public List<(string Person, long Amount)>? Shares(long total) => amounts.Sum(a => a.Amount) == total && amounts.All(a => a.Amount >= 0) ? amounts.ToList() : null;}
// Each person pays a percentage. The percentages must add up to exactly 100.public sealed class PercentSplit(IReadOnlyList<(string Person, int Percent)> percents) : ISplit{ public List<(string Person, long Amount)>? Shares(long total) => percents.Sum(p => p.Percent) == 100 && percents.All(p => p.Percent >= 0) ? Allocation.Allocate(total, percents.Select(p => p.Person).ToList(), percents.Select(p => (long)p.Percent).ToList()) : null;}
// Used by the equal and percent splits: it turns weights into cents that add up exactly.public static class Allocation{ // Divides the total by weight, rounding each share down, then hands the cents left over to // the first people listed, one each. Any rule works if it's deterministic and the shares add // up to the total: 100.00 three ways is 33.34, 33.33 and 33.33, and no cent disappears. public static List<(string Person, long Amount)> Allocate(long total, IReadOnlyList<string> people, IReadOnlyList<long> weights) { var weightSum = weights.Sum(); var shares = people.Select((p, i) => (Person: p, Amount: total * weights[i] / weightSum)).ToList(); var left = total - shares.Sum(s => s.Amount); for (var i = 0; i < left; i++) shares[i] = (shares[i].Person, shares[i].Amount + 1); return shares; }}
// Who owes whom, kept up to date as expenses arrive, so a question is one lookup. The map is// two-sided: when Ben owes Ana 10, owed[ben][ana] is 10 and owed[ana][ben] is -10.public sealed class Balances{ private readonly Dictionary<string, Dictionary<string, long>> _owed = [];
public void Record(string debtor, string creditor, long amount) { if (debtor == creditor || amount == 0) return; Add(debtor, creditor, amount); Add(creditor, debtor, -amount); }
public long Owes(string debtor, string creditor) => _owed.TryGetValue(debtor, out var row) ? row.GetValueOrDefault(creditor) : 0;
// What everyone else owes this user in total: positive gets money back, negative pays. public long Net(string user) => _owed.TryGetValue(user, out var row) ? -row.Values.Sum() : 0;
private void Add(string a, string b, long amount) { if (!_owed.TryGetValue(a, out var row)) _owed[a] = row = []; var next = row.GetValueOrDefault(b) + amount; if (next == 0) row.Remove(b); else row[b] = next; }}
// One bill, already split. It keeps the shares, not the split rule, so deleting it later undoes// exactly what it did.public sealed record Expense(string Id, string Description, string PaidBy, long Total, List<(string Person, long Amount)> Shares);
public enum Result { Ok, UnknownUser, InvalidSplit }
public sealed class Splitwise(Func<string> ids){ private readonly HashSet<string> _users = []; private readonly Dictionary<string, Expense> _expenses = []; private readonly Balances _balances = new();
public void AddUser(string user) => _users.Add(user);
// Each person's share is owed to whoever paid. The payer's own share is money they spent on // themselves, so it creates no debt. public (Result, Expense?) AddExpense(string description, string paidBy, long total, ISplit split) { var shares = split.Shares(total); if (total <= 0 || shares is null) return (Result.InvalidSplit, null); if (!_users.Contains(paidBy) || !shares.All(s => _users.Contains(s.Person))) return (Result.UnknownUser, null); var e = new Expense(ids(), description, paidBy, total, shares); _expenses[e.Id] = e; foreach (var (person, share) in shares) _balances.Record(person, paidBy, share); return (Result.Ok, e); }
public long Owes(string debtor, string creditor) => _balances.Owes(debtor, creditor);}// Share is one person's part of an expense. Shares are a slice, not a map, so their order (who// gets a leftover cent) is the order the caller listed them.type Share struct { Person string Amount int64}
// Split says how an expense is divided. Each kind carries its own inputs (who shares equally,// the exact amounts, the percentages) and turns a total into shares that add up to the total// exactly. An impossible split returns false.type Split interface { Shares(total int64) ([]Share, bool)}
// EqualSplit charges everyone listed the same. A name listed twice is a mistake, so the split// is refused.type EqualSplit struct{ People []string }
func (s EqualSplit) Shares(total int64) ([]Share, bool) { if len(s.People) == 0 { return nil, false } weights := make([]int64, len(s.People)) for i, p := range s.People { if slices.Contains(s.People[:i], p) { return nil, false // listed twice } weights[i] = 1 } return allocate(total, s.People, weights), true}
// ExactSplit's amounts are the shares, as long as they add up to what was paid.type ExactSplit struct{ Amounts []Share }
func (s ExactSplit) Shares(total int64) ([]Share, bool) { var sum int64 for _, a := range s.Amounts { if a.Amount < 0 { return nil, false } sum += a.Amount } return slices.Clone(s.Amounts), sum == total}
// Percent is one person's percentage in a PercentSplit.type Percent struct { Person string Percent int64}
// PercentSplit charges each person a percentage. The percentages must add up to exactly 100.type PercentSplit struct{ Percents []Percent }
func (s PercentSplit) Shares(total int64) ([]Share, bool) { var sum int64 people := make([]string, len(s.Percents)) weights := make([]int64, len(s.Percents)) for i, p := range s.Percents { if p.Percent < 0 { return nil, false } sum += p.Percent people[i], weights[i] = p.Person, p.Percent } if sum != 100 { return nil, false } return allocate(total, people, weights), true}
// allocate divides the total by weight, rounding each share down, then hands the cents left// over to the first people listed, one each. Any rule works if it's deterministic and the// shares add up to the total: 100.00 three ways is 33.34, 33.33 and 33.33, and no cent// disappears.func allocate(total int64, people []string, weights []int64) []Share { var weightSum, given int64 for _, w := range weights { weightSum += w } out := make([]Share, len(people)) for i, p := range people { out[i] = Share{p, total * weights[i] / weightSum} given += out[i].Amount } for i := 0; given < total; i, given = i+1, given+1 { out[i].Amount++ } return out}
// Balances keeps who owes whom up to date as expenses arrive, so a question is one lookup. The// map is two-sided: when Ben owes Ana 10, owed[ben][ana] is 10 and owed[ana][ben] is -10.type Balances struct { owed map[string]map[string]int64}
func NewBalances() *Balances { return &Balances{owed: map[string]map[string]int64{}} }
func (b *Balances) Record(debtor, creditor string, amount int64) { if debtor == creditor || amount == 0 { return } b.add(debtor, creditor, amount) b.add(creditor, debtor, -amount)}
func (b *Balances) Owes(debtor, creditor string) int64 { return b.owed[debtor][creditor] }
// Net is what everyone else owes this user in total: positive gets money back, negative pays.func (b *Balances) Net(user string) int64 { var sum int64 for _, v := range b.owed[user] { sum -= v } return sum}
func (b *Balances) add(x, y string, amount int64) { if b.owed[x] == nil { b.owed[x] = map[string]int64{} } if b.owed[x][y] += amount; b.owed[x][y] == 0 { delete(b.owed[x], y) }}
// Expense is one bill, already split. It keeps the shares, not the split rule, so deleting it// later undoes exactly what it did.type Expense struct { ID string Description string PaidBy string Total int64 Shares []Share}
// Result is what a request gets back, so the app can say what went wrong.type Result int
const ( OK Result = iota UnknownUser InvalidSplit)
type Splitwise struct { users map[string]bool expenses map[string]*Expense balances *Balances ids func() string}
func NewSplitwise(ids func() string) *Splitwise { return &Splitwise{users: map[string]bool{}, expenses: map[string]*Expense{}, balances: NewBalances(), ids: ids}}
func (s *Splitwise) AddUser(user string) { s.users[user] = true }
// AddExpense records each person's share as owed to whoever paid. The payer's own share is// money they spent on themselves, so it creates no debt.func (s *Splitwise) AddExpense(description, paidBy string, total int64, split Split) (Result, *Expense) { shares, ok := split.Shares(total) if total <= 0 || !ok { return InvalidSplit, nil } if !s.users[paidBy] || slices.ContainsFunc(shares, func(sh Share) bool { return !s.users[sh.Person] }) { return UnknownUser, nil } e := &Expense{ID: s.ids(), Description: description, PaidBy: paidBy, Total: total, Shares: shares} s.expenses[e.ID] = e for _, sh := range shares { s.balances.Record(sh.Person, paidBy, sh.Amount) } return OK, e}
func (s *Splitwise) Owes(debtor, creditor string) int64 { return s.balances.Owes(debtor, creditor) }// How an expense is divided. Each kind of split carries its own inputs (who shares equally, the// exact amounts, the percentages) and turns a total into a share per person that adds up to// the total exactly. A Map keeps the order people were listed in. An impossible split returns// null.interface Split { shares(total: number): Map<string, number> | null;}
// Everyone listed pays the same. A name listed twice is a mistake, so the split is refused.class EqualSplit implements Split { constructor(private readonly people: string[]) {}
shares(total: number): Map<string, number> | null { if (this.people.length === 0 || new Set(this.people).size !== this.people.length) return null; return allocate( total, this.people, this.people.map(() => 1), ); }}
class ExactSplit implements Split { constructor(private readonly amounts: Map<string, number>) {}
// The amounts are the shares, as long as they add up to what was paid. shares(total: number): Map<string, number> | null { const values = [...this.amounts.values()]; if (values.reduce((a, b) => a + b, 0) !== total || values.some((a) => a < 0)) return null; return new Map(this.amounts); }}
// Each person pays a percentage. The percentages must add up to exactly 100.class PercentSplit implements Split { constructor(private readonly percents: Map<string, number>) {}
shares(total: number): Map<string, number> | null { const values = [...this.percents.values()]; if (values.reduce((a, b) => a + b, 0) !== 100 || values.some((p) => p < 0)) return null; return allocate(total, [...this.percents.keys()], values); }}
// Divides the total by weight, rounding each share down, then hands the cents left over to the// first people listed, one each. Any rule works if it's deterministic and the shares add up to// the total: 100.00 three ways is 33.34, 33.33 and 33.33, and no cent disappears.function allocate(total: number, people: string[], weights: number[]): Map<string, number> { const weightSum = weights.reduce((a, b) => a + b, 0); const out = new Map(people.map((p, i) => [p, Math.floor((total * weights[i]) / weightSum)])); let left = total - [...out.values()].reduce((a, b) => a + b, 0); for (const p of people) { if (left-- <= 0) break; out.set(p, out.get(p)! + 1); } return out;}
// Who owes whom, kept up to date as expenses arrive, so a question is one lookup. The map is// two-sided: when Ben owes Ana 10, owed[ben][ana] is 10 and owed[ana][ben] is -10.class Balances { private readonly owed = new Map<string, Map<string, number>>();
record(debtor: string, creditor: string, amount: number): void { if (debtor === creditor || amount === 0) return; this.add(debtor, creditor, amount); this.add(creditor, debtor, -amount); }
owes(debtor: string, creditor: string): number { return this.owed.get(debtor)?.get(creditor) ?? 0; }
// What everyone else owes this user in total: positive gets money back, negative pays. net(user: string): number { let sum = 0; for (const v of this.owed.get(user)?.values() ?? []) sum -= v; return sum; }
private add(a: string, b: string, amount: number): void { let row = this.owed.get(a); if (!row) this.owed.set(a, (row = new Map())); const next = (row.get(b) ?? 0) + amount; if (next === 0) row.delete(b); else row.set(b, next); }}
// One bill, already split. It keeps the shares, not the split rule, so deleting it later undoes// exactly what it did.interface Expense { readonly id: string; readonly description: string; readonly paidBy: string; readonly total: number; readonly shares: ReadonlyMap<string, number>;}
type Result = 'ok' | 'unknown-user' | 'invalid-split';
class Splitwise { private readonly users = new Set<string>(); private readonly expenses = new Map<string, Expense>(); private readonly balances = new Balances();
constructor(private readonly ids: () => string) {}
addUser(user: string): void { this.users.add(user); }
// Each person's share is owed to whoever paid. The payer's own share is money they spent on // themselves, so it creates no debt. addExpense(description: string, paidBy: string, total: number, split: Split): { result: Result; expense?: Expense } { const shares = split.shares(total); if (total <= 0 || !shares) return { result: 'invalid-split' }; if (!this.users.has(paidBy) || ![...shares.keys()].every((p) => this.users.has(p))) { return { result: 'unknown-user' }; } const e = { id: this.ids(), description, paidBy, total, shares }; this.expenses.set(e.id, e); for (const [person, share] of shares) this.balances.record(person, paidBy, share); return { result: 'ok', expense: e }; }
owes(debtor: string, creditor: string): number { return this.balances.owes(debtor, creditor); }}What does a class per split cost? The phone has to build the right split object, so the app needs a
way to name the kind and its inputs. In a web API that’s a type field plus the inputs, mapped to a
class in one place.
Go deeperAna pays 100.00 for three, step by step1 min
Ana adds an expense of 10,000 cents, split equally between Ana, Ben and Cy. The group asks the
EqualSplit for shares and gets 3,334, 3,333 and 3,333, which add up to 10,000. Ana’s own share is
skipped: she doesn’t owe herself. The ledger records that Ben owes Ana 3,333 and Cy owes Ana 3,333,
updating both sides of each pair.
Scroll or pinch to zoom, drag to pan
- Color key
- Entity
- Implementation
- Facade
Stage 3: Groups, deleting, and settling up
Section titled “Stage 3: Groups, deleting, and settling up”The flat and the ski trip should have separate balances. Ben entered a taxi twice, so he wants to delete one. And Ben pays Ana back 15.00. Handle all three.
What they are testing
Whether deleting is the exact reverse of adding, and whether a payment is recorded in the same ledger as expenses. Rebuilding all balances from the remaining expenses works, but they listen for why it isn’t needed.
A Group owns its members, expenses, payments and its own Balances. So the flat’s bills never mix
with the trip’s. Adding an expense now also checks that everyone in it is a member. Splitwise
becomes the front door that knows the users and creates groups.
Deleting an expense applies it again with every share made negative. Ben’s 33.33 debt to Ana goes back to 0, and every other balance is untouched. Because the ledger is a running total, undoing one entry is as cheap as adding it, and nothing is rebuilt from history. Deleting twice finds no expense the second time, so it can’t be undone twice.
Settling up records a Payment: Ben paid Ana 15.00. In the ledger, that’s Ana owing Ben 15.00,
which cancels 15.00 of what Ben owed her. Any positive amount is accepted. Friends pay in round
numbers, and paying a little too much simply flips who owes whom, which is what really happened.
Scroll or pinch to zoom, drag to pan
- Color key
- Facade
- Entity
- Value object
- Enum
- Interface
- Implementation
- New in this step
// What a request gets back, so the app can say what went wrong.enum Result { OK, NOT_A_MEMBER, INVALID_SPLIT, INVALID_AMOUNT, NO_SUCH_EXPENSE }
// Money moving between two people outside of any expense: Ben pays Ana back.record Payment(String from, String to, long amount) {}
// A trip, a flat, a couple. Expenses and payments belong to one group, and so do the balances,// so the flat's electricity bill never mixes with the ski trip.class Group { private final String name; private final Set<String> members; private final Map<String, Expense> expenses = new LinkedHashMap<>(); private final List<Payment> payments = new ArrayList<>(); private final Balances balances = new Balances(); private final Supplier<String> ids;
Group(String name, Set<String> members, Supplier<String> ids) { this.name = name; this.members = members; this.ids = ids; }
// Check everything first, then change the balances. A bad expense changes nothing. ExpenseResult addExpense(String description, String paidBy, long total, Split split) { Map<String, Long> shares = split.shares(total); if (total <= 0 || shares == null) return new ExpenseResult(Result.INVALID_SPLIT, null); if (!members.contains(paidBy) || !members.containsAll(shares.keySet())) return new ExpenseResult(Result.NOT_A_MEMBER, null); Expense e = new Expense(ids.get(), description, paidBy, total, shares); expenses.put(e.id(), e); apply(e, 1); return new ExpenseResult(Result.OK, e); }
// A mistake is undone by applying the expense again with the sign flipped, so balances stay // a running sum and never need rebuilding from history. Deleting twice finds nothing. Result deleteExpense(String expenseId) { Expense e = expenses.remove(expenseId); if (e == null) return Result.NO_SUCH_EXPENSE; apply(e, -1); return Result.OK; }
// Paying someone back is recorded as money owed the other way. Any positive amount is // accepted: friends settle in round numbers, and paying a little too much just flips who // owes whom. Result settle(String from, String to, long amount) { if (!members.contains(from) || !members.contains(to)) return Result.NOT_A_MEMBER; if (amount <= 0 || from.equals(to)) return Result.INVALID_AMOUNT; payments.add(new Payment(from, to, amount)); balances.record(to, from, amount); return Result.OK; }
long owes(String debtor, String creditor) { return balances.owes(debtor, creditor); }
long net(String member) { return balances.net(member); }
Set<String> members() { return members; }
// Each person's share is money they owe the payer. sign is 1 to add the expense, -1 to undo it. private void apply(Expense e, int sign) { e.shares().forEach((person, share) -> balances.record(person, e.paidBy(), sign * share)); }}
// The front door: who has an account, and which groups exist.class Splitwise { private final Set<String> users = new HashSet<>(); private final Map<String, Group> groups = new HashMap<>(); private final Supplier<String> ids;
Splitwise(Supplier<String> ids) { this.ids = ids; }
void addUser(String user) { users.add(user); }
Group createGroup(String name, Set<String> members) { if (!users.containsAll(members)) return null; Group g = new Group(name, new HashSet<>(members), ids); groups.put(name, g); return g; }}# What a request gets back, so the app can say what went wrong.class Result(Enum): OK = auto() NOT_A_MEMBER = auto() INVALID_SPLIT = auto() INVALID_AMOUNT = auto() NO_SUCH_EXPENSE = auto()
# Money moving between two people outside of any expense: Ben pays Ana back.@dataclass(frozen=True)class Payment: from_: str to: str amount: int
# A trip, a flat, a couple. Expenses and payments belong to one group, and so do the balances,# so the flat's electricity bill never mixes with the ski trip.class Group: def __init__(self, name: str, members: set[str], ids: Callable[[], str]): self.name = name self.members = members self._expenses: dict[str, Expense] = {} self._payments: list[Payment] = [] self._balances = Balances() self._ids = ids
# Check everything first, then change the balances. A bad expense changes nothing. def add_expense(self, description: str, paid_by: str, total: int, split: Split) -> tuple[Result, Expense | None]: shares = split.shares(total) if total <= 0 or shares is None: return Result.INVALID_SPLIT, None if paid_by not in self.members or not self.members.issuperset(shares): return Result.NOT_A_MEMBER, None e = Expense(self._ids(), description, paid_by, total, shares) self._expenses[e.id] = e self._apply(e, 1) return Result.OK, e
# A mistake is undone by applying the expense again with the sign flipped, so balances stay # a running sum and never need rebuilding from history. Deleting twice finds nothing. def delete_expense(self, expense_id: str) -> Result: e = self._expenses.pop(expense_id, None) if e is None: return Result.NO_SUCH_EXPENSE self._apply(e, -1) return Result.OK
# Paying someone back is recorded as money owed the other way. Any positive amount is # accepted: friends settle in round numbers, and paying a little too much just flips who # owes whom. def settle(self, from_: str, to: str, amount: int) -> Result: if from_ not in self.members or to not in self.members: return Result.NOT_A_MEMBER if amount <= 0 or from_ == to: return Result.INVALID_AMOUNT self._payments.append(Payment(from_, to, amount)) self._balances.record(to, from_, amount) return Result.OK
def owes(self, debtor: str, creditor: str) -> int: return self._balances.owes(debtor, creditor)
def net(self, member: str) -> int: return self._balances.net(member)
# Each person's share is money they owe the payer. sign is 1 to add the expense, -1 to undo it. def _apply(self, e: Expense, sign: int) -> None: for person, share in e.shares.items(): self._balances.record(person, e.paid_by, sign * share)
# The front door: who has an account, and which groups exist.class Splitwise: def __init__(self, ids: Callable[[], str]): self._users: set[str] = set() self._groups: dict[str, Group] = {} self._ids = ids
def add_user(self, user: str) -> None: self._users.add(user)
def create_group(self, name: str, members: set[str]) -> Group | None: if not self._users.issuperset(members): return None g = Group(name, set(members), self._ids) self._groups[name] = g return g// What a request gets back, so the app can say what went wrong.public enum Result { Ok, NotAMember, InvalidSplit, InvalidAmount, NoSuchExpense }
// Money moving between two people outside of any expense: Ben pays Ana back.public sealed record Payment(string From, string To, long Amount);
// A trip, a flat, a couple. Expenses and payments belong to one group, and so do the balances,// so the flat's electricity bill never mixes with the ski trip.public sealed class Group(string name, IReadOnlySet<string> members, Func<string> ids){ private readonly Dictionary<string, Expense> _expenses = []; private readonly List<Payment> _payments = []; private readonly Balances _balances = new();
public string Name { get; } = name; public IReadOnlySet<string> Members { get; } = members;
// Check everything first, then change the balances. A bad expense changes nothing. public (Result, Expense?) AddExpense(string description, string paidBy, long total, ISplit split) { var shares = split.Shares(total); if (total <= 0 || shares is null) return (Result.InvalidSplit, null); if (!Members.Contains(paidBy) || !shares.All(s => Members.Contains(s.Person))) return (Result.NotAMember, null); var e = new Expense(ids(), description, paidBy, total, shares); _expenses[e.Id] = e; Apply(e, 1); return (Result.Ok, e); }
// A mistake is undone by applying the expense again with the sign flipped, so balances stay // a running sum and never need rebuilding from history. Deleting twice finds nothing. public Result DeleteExpense(string id) { if (!_expenses.Remove(id, out var e)) return Result.NoSuchExpense; Apply(e, -1); return Result.Ok; }
// Paying someone back is recorded as money owed the other way. Any positive amount is // accepted: friends settle in round numbers, and paying a little too much just flips who // owes whom. public Result Settle(string from, string to, long amount) { if (!Members.Contains(from) || !Members.Contains(to)) return Result.NotAMember; if (amount <= 0 || from == to) return Result.InvalidAmount; _payments.Add(new Payment(from, to, amount)); _balances.Record(to, from, amount); return Result.Ok; }
public long Owes(string debtor, string creditor) => _balances.Owes(debtor, creditor);
public long Net(string member) => _balances.Net(member);
// Each person's share is money they owe the payer. sign is 1 to add the expense, -1 to undo it. private void Apply(Expense e, int sign) { foreach (var (person, share) in e.Shares) _balances.Record(person, e.PaidBy, sign * share); }}
// The front door: who has an account, and which groups exist.public sealed class Splitwise(Func<string> ids){ private readonly HashSet<string> _users = []; private readonly Dictionary<string, Group> _groups = [];
public void AddUser(string user) => _users.Add(user);
public Group? CreateGroup(string name, IEnumerable<string> members) { var set = members.ToHashSet(); if (!set.All(_users.Contains)) return null; var g = new Group(name, set, ids); _groups[name] = g; return g; }}const ( OK Result = iota NotAMember InvalidSplit InvalidAmount NoSuchExpense)
// Payment is money moving between two people outside of any expense: Ben pays Ana back.type Payment struct { From, To string Amount int64}
// Group is a trip, a flat, a couple. Expenses and payments belong to one group, and so do the// balances, so the flat's electricity bill never mixes with the ski trip.type Group struct { Name string members map[string]bool expenses map[string]*Expense payments []Payment balances *Balances ids func() string}
// AddExpense checks everything first, then changes the balances. A bad expense changes nothing.func (g *Group) AddExpense(description, paidBy string, total int64, split Split) (Result, *Expense) { shares, ok := split.Shares(total) if total <= 0 || !ok { return InvalidSplit, nil } if !g.members[paidBy] || slices.ContainsFunc(shares, func(sh Share) bool { return !g.members[sh.Person] }) { return NotAMember, nil } e := &Expense{ID: g.ids(), Description: description, PaidBy: paidBy, Total: total, Shares: shares} g.expenses[e.ID] = e g.apply(e, 1) return OK, e}
// DeleteExpense undoes a mistake by applying the expense again with the sign flipped, so// balances stay a running sum and never need rebuilding from history. Deleting twice finds// nothing.func (g *Group) DeleteExpense(id string) Result { e := g.expenses[id] if e == nil { return NoSuchExpense } delete(g.expenses, id) g.apply(e, -1) return OK}
// Settle records paying someone back as money owed the other way. Any positive amount is// accepted: friends settle in round numbers, and paying a little too much just flips who owes// whom.func (g *Group) Settle(from, to string, amount int64) Result { if !g.members[from] || !g.members[to] { return NotAMember } if amount <= 0 || from == to { return InvalidAmount } g.payments = append(g.payments, Payment{from, to, amount}) g.balances.Record(to, from, amount) return OK}
func (g *Group) Owes(debtor, creditor string) int64 { return g.balances.Owes(debtor, creditor) }
func (g *Group) Net(member string) int64 { return g.balances.Net(member) }
func (g *Group) Members() []string { return slices.Sorted(maps.Keys(g.members)) }
// apply records each person's share as money they owe the payer. sign is 1 to add the expense,// -1 to undo it.func (g *Group) apply(e *Expense, sign int64) { for _, sh := range e.Shares { g.balances.Record(sh.Person, e.PaidBy, sign*sh.Amount) }}
// Splitwise is the front door: who has an account, and which groups exist.type Splitwise struct { users map[string]bool groups map[string]*Group ids func() string}
func NewSplitwise(ids func() string) *Splitwise { return &Splitwise{users: map[string]bool{}, groups: map[string]*Group{}, ids: ids}}
func (s *Splitwise) AddUser(user string) { s.users[user] = true }
func (s *Splitwise) CreateGroup(name string, members []string) *Group { g := &Group{Name: name, members: map[string]bool{}, expenses: map[string]*Expense{}, balances: NewBalances(), ids: s.ids} for _, m := range members { if !s.users[m] { return nil } g.members[m] = true } s.groups[name] = g return g}// What a request gets back, so the app can say what went wrong.type Result = 'ok' | 'not-a-member' | 'invalid-split' | 'invalid-amount' | 'no-such-expense';
// Money moving between two people outside of any expense: Ben pays Ana back.interface Payment { readonly from: string; readonly to: string; readonly amount: number;}
// A trip, a flat, a couple. Expenses and payments belong to one group, and so do the balances,// so the flat's electricity bill never mixes with the ski trip.class Group { private readonly expenses = new Map<string, Expense>(); private readonly payments: Payment[] = []; private readonly balances = new Balances();
constructor( readonly name: string, readonly members: ReadonlySet<string>, private readonly ids: () => string, ) {}
// Check everything first, then change the balances. A bad expense changes nothing. addExpense(description: string, paidBy: string, total: number, split: Split): { result: Result; expense?: Expense } { const shares = split.shares(total); if (total <= 0 || !shares) return { result: 'invalid-split' }; if (!this.members.has(paidBy) || ![...shares.keys()].every((p) => this.members.has(p))) { return { result: 'not-a-member' }; } const e = { id: this.ids(), description, paidBy, total, shares }; this.expenses.set(e.id, e); this.apply(e, 1); return { result: 'ok', expense: e }; }
// A mistake is undone by applying the expense again with the sign flipped, so balances stay // a running sum and never need rebuilding from history. Deleting twice finds nothing. deleteExpense(id: string): Result { const e = this.expenses.get(id); if (!e) return 'no-such-expense'; this.expenses.delete(id); this.apply(e, -1); return 'ok'; }
// Paying someone back is recorded as money owed the other way. Any positive amount is // accepted: friends settle in round numbers, and paying a little too much just flips who // owes whom. settle(from: string, to: string, amount: number): Result { if (!this.members.has(from) || !this.members.has(to)) return 'not-a-member'; if (amount <= 0 || from === to) return 'invalid-amount'; this.payments.push({ from, to, amount }); this.balances.record(to, from, amount); return 'ok'; }
owes(debtor: string, creditor: string): number { return this.balances.owes(debtor, creditor); }
net(member: string): number { return this.balances.net(member); }
// Each person's share is money they owe the payer. sign is 1 to add the expense, -1 to undo it. private apply(e: Expense, sign: number): void { for (const [person, share] of e.shares) this.balances.record(person, e.paidBy, sign * share); }}
// The front door: who has an account, and which groups exist.class Splitwise { private readonly users = new Set<string>(); private readonly groups = new Map<string, Group>();
constructor(private readonly ids: () => string) {}
addUser(user: string): void { this.users.add(user); }
createGroup(name: string, members: string[]): Group | null { if (!members.every((m) => this.users.has(m))) return null; const g = new Group(name, new Set(members), this.ids); this.groups.set(name, g); return g; }}Go deeperWhy not store only each person's net?1 min
Because people ask “what do I owe Ben?”, not just “am I up or down?”. A net per person can’t answer that. The two-sided ledger answers both: a pair is one lookup, and a net is the sum of a row. Stage 4 needs only the nets. The app’s screens need the pairs.
Go deeperHow does editing an expense work?1 min
As a delete of the old expense and an add of the corrected one, together in one step under the group’s lock. The ledger sees two entries that add up to the change. Keeping the old version in a history list gives the “Ben changed the taxi from 40.00 to 20.00” line in the activity feed for free.
Stage 4: Simplifying who owes whom
Section titled “Stage 4: Simplifying who owes whom”After a week away, Ana owes Ben, Ben owes Cy, Cy owes Dee, and a few more. Twelve payments to sort it out. Can you do it in fewer?
What they are testing
Whether you see that only each person’s net matters, and know a simple rule that needs at most n − 1 payments. Strong candidates also say that the true minimum is a very hard problem, and that the simple rule is what apps use.
Who owed whom along the way doesn’t matter for settling up. What matters is each person’s net: how much they’re up or down overall. And the nets of a group always add up to zero, because every cent someone owes, someone else is owed.
A small example: Ana owes Ben 10.00, and Ben owes Cy 10.00. Ben’s net is zero: he’s just passing money along. So Ana can pay Cy directly, and that’s one payment instead of two.
The rule is simple:
- Take the person who owes the most, and the person who is owed the most.
- One pays the other the smaller of their two amounts. Now at least one of them is settled.
- Repeat with whoever is left.
Every payment settles at least one person, so a group of n people needs at most n − 1 payments, however tangled the debts were. Ties are broken by name, so the suggestion is the same every time the screen opens. A rule like this, which always takes the biggest option in front of it, is called greedy.
Let’s run it on a small group. After the trip, the nets are: Ana −50, Ben −30, Cy +20, Dee +60. They add up to zero, as they always do.
- Ana owes the most (50), and Dee is owed the most (60). Ana pays Dee 50. Ana is settled; Dee is still owed 10.
- Now Ben owes the most (30), and Cy is owed the most (20). Ben pays Cy 20. Cy is settled; Ben still owes 10.
- Ben owes 10, and Dee is owed 10. Ben pays Dee 10. Everyone is settled.
Three payments for four people, which is n − 1, however many expenses the trip had.
Scroll or pinch to zoom, drag to pan
The suggestions are a view, not a change. Nothing is recorded until someone pays, and a payment is
recorded with settle, like any other. When Ana pays Cy, the ledger shows a debt between two people
who never shared an expense. That’s fine: every net moves toward zero, and once all the suggested
payments are made, every net is zero.
Scroll or pinch to zoom, drag to pan
- Color key
- Facade
- Entity
- Value object
- Enum
- Interface
- Implementation
- New in this step
// One payment the simplifier suggests: `from` pays `to` this amount.record Transfer(String from, String to, long amount) {}
// After a weekend away, the pairwise debts can form a tangle: Ana owes Ben, Ben owes Cy, Cy owes// Dee. Only each person's net matters: how much they are up or down overall. Matching the// biggest debtor with the biggest creditor, again and again, settles everyone. Each transfer// clears at least one person, so a group of n needs at most n - 1 transfers.class DebtSimplifier { static List<Transfer> simplify(Group g) { // Biggest amount first; ties broken by name so the answer is the same every time. Comparator<Map.Entry<String, Long>> biggest = Map.Entry.<String, Long>comparingByValue().reversed() .thenComparing(Map.Entry.comparingByKey()); PriorityQueue<Map.Entry<String, Long>> debtors = new PriorityQueue<>(biggest); PriorityQueue<Map.Entry<String, Long>> creditors = new PriorityQueue<>(biggest); for (String m : g.members()) { long net = g.net(m); if (net < 0) debtors.add(Map.entry(m, -net)); if (net > 0) creditors.add(Map.entry(m, net)); } List<Transfer> out = new ArrayList<>(); while (!debtors.isEmpty()) { var d = debtors.poll(); var c = creditors.poll(); long amount = Math.min(d.getValue(), c.getValue()); out.add(new Transfer(d.getKey(), c.getKey(), amount)); // Whoever isn't fully settled goes back in with what's left. if (d.getValue() > amount) debtors.add(Map.entry(d.getKey(), d.getValue() - amount)); if (c.getValue() > amount) creditors.add(Map.entry(c.getKey(), c.getValue() - amount)); } return out; }}import heapq
# One payment the simplifier suggests: from_ pays to this amount.@dataclass(frozen=True)class Transfer: from_: str to: str amount: int
# After a weekend away, the pairwise debts can form a tangle: Ana owes Ben, Ben owes Cy, Cy owes# Dee. Only each person's net matters: how much they are up or down overall. Matching the# biggest debtor with the biggest creditor, again and again, settles everyone. Each transfer# clears at least one person, so a group of n needs at most n - 1 transfers.def simplify(g: Group) -> list[Transfer]: # heapq is a min-heap, so amounts go in negated: the biggest comes out first, ties by name. debtors: list[tuple[int, str]] = [] creditors: list[tuple[int, str]] = [] for m in g.members: net = g.net(m) if net < 0: heapq.heappush(debtors, (net, m)) elif net > 0: heapq.heappush(creditors, (-net, m)) out = [] while debtors: d_neg, d = heapq.heappop(debtors) c_neg, c = heapq.heappop(creditors) amount = min(-d_neg, -c_neg) out.append(Transfer(d, c, amount)) # Whoever isn't fully settled goes back in with what's left. if -d_neg > amount: heapq.heappush(debtors, (d_neg + amount, d)) if -c_neg > amount: heapq.heappush(creditors, (c_neg + amount, c)) return out// One payment the simplifier suggests: From pays To this amount.public sealed record Transfer(string From, string To, long Amount);
// After a weekend away, the pairwise debts can form a tangle: Ana owes Ben, Ben owes Cy, Cy owes// Dee. Only each person's net matters: how much they are up or down overall. Matching the// biggest debtor with the biggest creditor, again and again, settles everyone. Each transfer// clears at least one person, so a group of n needs at most n - 1 transfers.public static class DebtSimplifier{ public static List<Transfer> Simplify(Group g) { // Biggest amount first; ties broken by name so the answer is the same every time. The // priority is (-amount, name) because PriorityQueue hands out the smallest first. var byBiggest = Comparer<(long, string)>.Create((a, b) => a.Item1 != b.Item1 ? a.Item1.CompareTo(b.Item1) : string.CompareOrdinal(a.Item2, b.Item2)); var debtors = new PriorityQueue<string, (long, string)>(byBiggest); var creditors = new PriorityQueue<string, (long, string)>(byBiggest); foreach (var m in g.Members) { var net = g.Net(m); if (net < 0) debtors.Enqueue(m, (net, m)); if (net > 0) creditors.Enqueue(m, (-net, m)); } var transfers = new List<Transfer>(); while (debtors.TryDequeue(out var d, out var dp)) { creditors.TryDequeue(out var c, out var cp); long owe = -dp.Item1, due = -cp.Item1, amount = Math.Min(owe, due); transfers.Add(new Transfer(d, c!, amount)); // Whoever isn't fully settled goes back in with what's left. if (owe > amount) debtors.Enqueue(d, (amount - owe, d)); if (due > amount) creditors.Enqueue(c!, (amount - due, c!)); } return transfers; }}// Transfer is one payment the simplifier suggests: From pays To this amount.type Transfer struct { From, To string Amount int64}
// Simplify untangles a group's debts. After a weekend away, pairwise debts can form a chain:// Ana owes Ben, Ben owes Cy, Cy owes Dee. Only each person's net matters: how much they are up// or down overall. Matching the biggest debtor with the biggest creditor, again and again,// settles everyone. Each transfer clears at least one person, so a group of n needs at most// n - 1 transfers.func Simplify(g *Group) []Transfer { type entry struct { who string amount int64 } var debtors, creditors []entry for _, m := range g.Members() { if net := g.Net(m); net < 0 { debtors = append(debtors, entry{m, -net}) } else if net > 0 { creditors = append(creditors, entry{m, net}) } } // Biggest amount first; ties broken by name so the answer is the same every time. A group // is a handful of people, so re-sorting each round is simpler than a heap and just as fast. biggest := func(a, b entry) int { return cmp.Or(cmp.Compare(b.amount, a.amount), cmp.Compare(a.who, b.who)) } var out []Transfer for len(debtors) > 0 { slices.SortFunc(debtors, biggest) slices.SortFunc(creditors, biggest) d, c := &debtors[0], &creditors[0] amount := min(d.amount, c.amount) out = append(out, Transfer{d.who, c.who, amount}) d.amount -= amount c.amount -= amount // Whoever is fully settled drops out; the other stays with what's left. if d.amount == 0 { debtors = debtors[1:] } if c.amount == 0 { creditors = creditors[1:] } } return out}// One payment the simplifier suggests: `from` pays `to` this amount.interface Transfer { readonly from: string; readonly to: string; readonly amount: number;}
// After a weekend away, the pairwise debts can form a tangle: Ana owes Ben, Ben owes Cy, Cy owes// Dee. Only each person's net matters: how much they are up or down overall. Matching the// biggest debtor with the biggest creditor, again and again, settles everyone. Each transfer// clears at least one person, so a group of n needs at most n - 1 transfers.function simplify(g: Group): Transfer[] { const debtors: { who: string; amount: number }[] = []; const creditors: { who: string; amount: number }[] = []; for (const m of g.members) { const net = g.net(m); if (net < 0) debtors.push({ who: m, amount: -net }); if (net > 0) creditors.push({ who: m, amount: net }); } // Biggest amount first; ties broken by name so the answer is the same every time. A group is // a handful of people, so re-sorting each round is simpler than a heap and just as fast. const biggest = (a: { who: string; amount: number }, b: { who: string; amount: number }) => b.amount - a.amount || a.who.localeCompare(b.who); const out: Transfer[] = []; while (debtors.length > 0) { debtors.sort(biggest); creditors.sort(biggest); const d = debtors[0]; const c = creditors[0]; const amount = Math.min(d.amount, c.amount); out.push({ from: d.who, to: c.who, amount }); d.amount -= amount; c.amount -= amount; // Whoever is fully settled drops out; the other stays with what's left. if (d.amount === 0) debtors.shift(); if (c.amount === 0) creditors.shift(); } return out;}What does greedy cost? It isn’t always the smallest number of payments. Here’s a case: Ana and Ben owe 3.00 each, and Cy owes 4.00. Dee is owed 6.00, and Eve 4.00. Greedy pairs Cy with Dee first and ends up needing four payments. But Cy paying Eve, and Ana and Ben each paying Dee, takes three. Finding the true minimum means splitting people into small groups whose nets add up to zero, and that’s a famously hard problem (computer scientists call it NP-hard). Real apps use greedy.
Go deeperFinding the true minimum, step by step2 min
Greedy needs at most n − 1 payments. When can we do better? Look at the counter-example again. Cy owes 4.00 and Eve is owed 4.00. Those two people form a small group of their own whose nets add up to zero: one payment settles them both. Ana, Ben and Dee form another: 3 + 3 = 6. Two payments settle those three.
That’s the whole idea. A group whose nets add up to zero can always be settled in “its size minus one” payments. So if the people can be split into k such groups, the total is n − k payments. More groups means fewer payments. Greedy found only one big group (n − 1 = 4 payments). The best split found two (5 − 2 = 3 payments).
To find the best split, a program would try every way of dividing the people into groups that each add up to zero, and keep the one with the most groups. Here’s why that’s slow: with 20 people, there are over a million subsets to check, and the number doubles with each person added. No one knows a fast way to do it for every case, which is what “NP-hard” means in practice.
For a group of a dozen friends, it can still be done in well under a second, by checking small subsets first and remembering which sets add up to zero. But it usually saves only one or two payments, and the suggestions can look strange. So most apps stay with greedy, and some offer the exact search only for small groups.
This is enough for a mid-level answer. Money is in cents, each split is a strategy that checks its inputs, the ledger is a running total, and debts are simplified with nets. The rest of the page is what makes it a senior answer.
The full design
Section titled “The full design”Here is everything together. Each class is here because a requirement needed it.
Scroll or pinch to zoom, drag to pan
- Color key
- Facade
- Entity
- Value object
- Enum
- Interface
- Implementation
AllInOne.java
AllInOne.java
// The complete design, built from every stage on this page.
import java.util.*;import java.util.concurrent.locks.*;import java.util.function.*;
// One bill, already split. It keeps the shares, not the split rule, so deleting it later undoes// exactly what it did.record Expense(String id, String description, String paidBy, long total, Map<String, Long> shares) {}
// The front door: who has an account, and which groups exist.class Splitwise { private final Set<String> users = new HashSet<>(); private final Map<String, Group> groups = new HashMap<>(); private final Supplier<String> ids;
Splitwise(Supplier<String> ids) { this.ids = ids; }
void addUser(String user) { users.add(user); }
Group createGroup(String name, Set<String> members) { if (!users.containsAll(members)) return null; Group g = new Group(name, new HashSet<>(members), ids); groups.put(name, g); return g; }}
// How an expense is divided. Each kind of split carries its own inputs (who shares equally, the// exact amounts, the percentages) and turns a total into a share per person that adds up to// the total exactly. An impossible split returns null.interface Split { Map<String, Long> shares(long total);}
// Everyone listed pays the same. A name listed twice is a mistake, so the split is refused.class EqualSplit implements Split { private final List<String> people;
EqualSplit(List<String> people) { this.people = people; }
public Map<String, Long> shares(long total) { if (people.isEmpty() || new HashSet<>(people).size() != people.size()) return null; return Shares.allocate(total, people, Collections.nCopies(people.size(), 1L)); }}
class ExactSplit implements Split { private final Map<String, Long> amounts; // insertion order kept by the caller's LinkedHashMap
ExactSplit(Map<String, Long> amounts) { this.amounts = amounts; }
// The amounts are the shares, as long as they add up to what was paid. public Map<String, Long> shares(long total) { long sum = amounts.values().stream().mapToLong(Long::longValue).sum(); boolean negative = amounts.values().stream().anyMatch(a -> a < 0); return sum == total && !negative ? new LinkedHashMap<>(amounts) : null; }}
// Each person pays a percentage. The percentages must add up to exactly 100.class PercentSplit implements Split { private final Map<String, Integer> percents;
PercentSplit(Map<String, Integer> percents) { this.percents = percents; }
public Map<String, Long> shares(long total) { int sum = percents.values().stream().mapToInt(Integer::intValue).sum(); if (sum != 100 || percents.values().stream().anyMatch(p -> p < 0)) return null; List<Long> weights = percents.values().stream().map(Integer::longValue).toList(); return Shares.allocate(total, new ArrayList<>(percents.keySet()), weights); }}
// Used by the equal and percent splits: it turns weights into cents that add up exactly.class Shares { // Divides the total by weight, rounding each share down, then hands the cents left over to // the first people listed, one each. Any rule works if it's deterministic and the shares add // up to the total: 100.00 three ways is 33.34, 33.33 and 33.33, and no cent disappears. static Map<String, Long> allocate(long total, List<String> people, List<Long> weights) { long weightSum = weights.stream().mapToLong(Long::longValue).sum(); Map<String, Long> out = new LinkedHashMap<>(); long given = 0; for (int i = 0; i < people.size(); i++) { long share = total * weights.get(i) / weightSum; out.put(people.get(i), share); given += share; } for (int i = 0; given < total; i++, given++) out.merge(people.get(i), 1L, Long::sum); return out; }}
// Who owes whom, kept up to date as expenses arrive, so a question is one lookup. The map is// two-sided: when Ben owes Ana 10, owed[ben][ana] is 10 and owed[ana][ben] is -10.class Balances { private final Map<String, Map<String, Long>> owed = new HashMap<>();
void record(String debtor, String creditor, long amount) { if (debtor.equals(creditor) || amount == 0) return; add(debtor, creditor, amount); add(creditor, debtor, -amount); }
long owes(String debtor, String creditor) { return owed.getOrDefault(debtor, Map.of()).getOrDefault(creditor, 0L); }
// What everyone else owes this user in total: positive gets money back, negative pays. long net(String user) { return -owed.getOrDefault(user, Map.of()).values().stream().mapToLong(Long::longValue).sum(); }
private void add(String a, String b, long amount) { owed.computeIfAbsent(a, k -> new HashMap<>()).merge(b, amount, (x, y) -> x + y == 0 ? null : x + y); }}
// What a request gets back, so the app can say what went wrong.enum Result { OK, NOT_A_MEMBER, INVALID_SPLIT, INVALID_AMOUNT, NO_SUCH_EXPENSE }
// The result, plus the new expense when it worked.record ExpenseResult(Result result, Expense expense) {}
// Money moving between two people outside of any expense: Ben pays Ana back.record Payment(String from, String to, long amount) {}
// A trip, a flat, a couple. Expenses and payments belong to one group, and so do the balances,// so the flat's electricity bill never mixes with the ski trip.class Group { private final String name; private final Set<String> members; private final Map<String, Expense> expenses = new LinkedHashMap<>(); private final List<Payment> payments = new ArrayList<>(); private final Balances balances = new Balances(); private final Supplier<String> ids;
Group(String name, Set<String> members, Supplier<String> ids) { this.name = name; this.members = members; this.ids = ids; }
// Check everything first, then change the balances. A bad expense changes nothing. ExpenseResult addExpense(String description, String paidBy, long total, Split split) { Map<String, Long> shares = split.shares(total); if (total <= 0 || shares == null) return new ExpenseResult(Result.INVALID_SPLIT, null); if (!members.contains(paidBy) || !members.containsAll(shares.keySet())) return new ExpenseResult(Result.NOT_A_MEMBER, null); Expense e = new Expense(ids.get(), description, paidBy, total, shares); expenses.put(e.id(), e); apply(e, 1); return new ExpenseResult(Result.OK, e); }
// A mistake is undone by applying the expense again with the sign flipped, so balances stay // a running sum and never need rebuilding from history. Deleting twice finds nothing. Result deleteExpense(String expenseId) { Expense e = expenses.remove(expenseId); if (e == null) return Result.NO_SUCH_EXPENSE; apply(e, -1); return Result.OK; }
// Paying someone back is recorded as money owed the other way. Any positive amount is // accepted: friends settle in round numbers, and paying a little too much just flips who // owes whom. Result settle(String from, String to, long amount) { if (!members.contains(from) || !members.contains(to)) return Result.NOT_A_MEMBER; if (amount <= 0 || from.equals(to)) return Result.INVALID_AMOUNT; payments.add(new Payment(from, to, amount)); balances.record(to, from, amount); return Result.OK; }
long owes(String debtor, String creditor) { return balances.owes(debtor, creditor); }
long net(String member) { return balances.net(member); }
Set<String> members() { return members; }
// Each person's share is money they owe the payer. sign is 1 to add the expense, -1 to undo it. private void apply(Expense e, int sign) { e.shares().forEach((person, share) -> balances.record(person, e.paidBy(), sign * share)); }}
// One payment the simplifier suggests: `from` pays `to` this amount.record Transfer(String from, String to, long amount) {}
// After a weekend away, the pairwise debts can form a tangle: Ana owes Ben, Ben owes Cy, Cy owes// Dee. Only each person's net matters: how much they are up or down overall. Matching the// biggest debtor with the biggest creditor, again and again, settles everyone. Each transfer// clears at least one person, so a group of n needs at most n - 1 transfers.class DebtSimplifier { static List<Transfer> simplify(Group g) { // Biggest amount first; ties broken by name so the answer is the same every time. Comparator<Map.Entry<String, Long>> biggest = Map.Entry.<String, Long>comparingByValue().reversed() .thenComparing(Map.Entry.comparingByKey()); PriorityQueue<Map.Entry<String, Long>> debtors = new PriorityQueue<>(biggest); PriorityQueue<Map.Entry<String, Long>> creditors = new PriorityQueue<>(biggest); for (String m : g.members()) { long net = g.net(m); if (net < 0) debtors.add(Map.entry(m, -net)); if (net > 0) creditors.add(Map.entry(m, net)); } List<Transfer> out = new ArrayList<>(); while (!debtors.isEmpty()) { var d = debtors.poll(); var c = creditors.poll(); long amount = Math.min(d.getValue(), c.getValue()); out.add(new Transfer(d.getKey(), c.getKey(), amount)); // Whoever isn't fully settled goes back in with what's left. if (d.getValue() > amount) debtors.add(Map.entry(d.getKey(), d.getValue() - amount)); if (c.getValue() > amount) creditors.add(Map.entry(c.getKey(), c.getValue() - amount)); } return out; }}
// Three friends add dinner, the taxi and the bar tab from their phones at the same moment. Each// expense reads a balance and writes it back, and two that interleave lose one update: the// group's balances no longer add up to its expenses, and nobody can say which is right. Every// operation on a group must run alone. A group sees a handful of writes a minute, so one lock// per group is plenty, and different groups never wait on each other.class SharedGroup { private final Group group; private final ReentrantLock lock = new ReentrantLock();
SharedGroup(Group group) { this.group = group; }
ExpenseResult addExpense(String description, String paidBy, long total, Split split) { return locked(() -> group.addExpense(description, paidBy, total, split)); } Result deleteExpense(String id) { return locked(() -> group.deleteExpense(id)); } Result settle(String from, String to, long amount) { return locked(() -> group.settle(from, to, amount)); } long owes(String debtor, String creditor) { return locked(() -> group.owes(debtor, creditor)); } List<Transfer> simplify() { return locked(() -> DebtSimplifier.simplify(group)); }
// Runs one operation with the lock held. finally releases it even if the operation throws. private <T> T locked(Supplier<T> op) { lock.lock(); try { return op.get(); } finally { lock.unlock(); } }}Read onlyJava 21Every file builds in CI16 files248 lines
all_in_one.py
all_in_one.py
# The complete design, built from every stage on this page.
from __future__ import annotations
import heapqimport threadingfrom dataclasses import dataclassfrom enum import Enum, autofrom typing import Callable, Protocol
# One bill, already split. It keeps the shares, not the split rule, so deleting it later undoes# exactly what it did.@dataclass(frozen=True)class Expense: id: str description: str paid_by: str total: int shares: dict[str, int]
# The front door: who has an account, and which groups exist.class Splitwise: def __init__(self, ids: Callable[[], str]): self._users: set[str] = set() self._groups: dict[str, Group] = {} self._ids = ids
def add_user(self, user: str) -> None: self._users.add(user)
def create_group(self, name: str, members: set[str]) -> Group | None: if not self._users.issuperset(members): return None g = Group(name, set(members), self._ids) self._groups[name] = g return g
# How an expense is divided. Each kind of split carries its own inputs (who shares equally, the# exact amounts, the percentages) and turns a total into a share per person that adds up to# the total exactly. An impossible split returns None.class Split(Protocol): def shares(self, total: int) -> dict[str, int] | None: ...
# Everyone listed pays the same. A name listed twice is a mistake, so the split is refused.class EqualSplit: def __init__(self, people: list[str]): self._people = people
def shares(self, total: int) -> dict[str, int] | None: if not self._people or len(set(self._people)) != len(self._people): return None return allocate(total, self._people, [1] * len(self._people))
class ExactSplit: def __init__(self, amounts: dict[str, int]): self._amounts = amounts
# The amounts are the shares, as long as they add up to what was paid. def shares(self, total: int) -> dict[str, int] | None: if sum(self._amounts.values()) != total or any(a < 0 for a in self._amounts.values()): return None return dict(self._amounts)
# Each person pays a percentage. The percentages must add up to exactly 100.class PercentSplit: def __init__(self, percents: dict[str, int]): self._percents = percents
def shares(self, total: int) -> dict[str, int] | None: if sum(self._percents.values()) != 100 or any(p < 0 for p in self._percents.values()): return None return allocate(total, list(self._percents), list(self._percents.values()))
# Divides the total by weight, rounding each share down, then hands the cents left over to the# first people listed, one each. Any rule works if it's deterministic and the shares add up to# the total: 100.00 three ways is 33.34, 33.33 and 33.33, and no cent disappears.def allocate(total: int, people: list[str], weights: list[int]) -> dict[str, int]: weight_sum = sum(weights) out = {p: total * w // weight_sum for p, w in zip(people, weights)} left = total - sum(out.values()) for p in people[:left]: out[p] += 1 return out
# Who owes whom, kept up to date as expenses arrive, so a question is one lookup. The map is# two-sided: when Ben owes Ana 10, owed[ben][ana] is 10 and owed[ana][ben] is -10.class Balances: def __init__(self): self._owed: dict[str, dict[str, int]] = {}
def record(self, debtor: str, creditor: str, amount: int) -> None: if debtor == creditor or amount == 0: return self._add(debtor, creditor, amount) self._add(creditor, debtor, -amount)
def owes(self, debtor: str, creditor: str) -> int: return self._owed.get(debtor, {}).get(creditor, 0)
# What everyone else owes this user in total: positive gets money back, negative pays. def net(self, user: str) -> int: return -sum(self._owed.get(user, {}).values())
def _add(self, a: str, b: str, amount: int) -> None: row = self._owed.setdefault(a, {}) row[b] = row.get(b, 0) + amount if row[b] == 0: del row[b]
# What a request gets back, so the app can say what went wrong.class Result(Enum): OK = auto() NOT_A_MEMBER = auto() INVALID_SPLIT = auto() INVALID_AMOUNT = auto() NO_SUCH_EXPENSE = auto()
# Money moving between two people outside of any expense: Ben pays Ana back.@dataclass(frozen=True)class Payment: from_: str to: str amount: int
# A trip, a flat, a couple. Expenses and payments belong to one group, and so do the balances,# so the flat's electricity bill never mixes with the ski trip.class Group: def __init__(self, name: str, members: set[str], ids: Callable[[], str]): self.name = name self.members = members self._expenses: dict[str, Expense] = {} self._payments: list[Payment] = [] self._balances = Balances() self._ids = ids
# Check everything first, then change the balances. A bad expense changes nothing. def add_expense(self, description: str, paid_by: str, total: int, split: Split) -> tuple[Result, Expense | None]: shares = split.shares(total) if total <= 0 or shares is None: return Result.INVALID_SPLIT, None if paid_by not in self.members or not self.members.issuperset(shares): return Result.NOT_A_MEMBER, None e = Expense(self._ids(), description, paid_by, total, shares) self._expenses[e.id] = e self._apply(e, 1) return Result.OK, e
# A mistake is undone by applying the expense again with the sign flipped, so balances stay # a running sum and never need rebuilding from history. Deleting twice finds nothing. def delete_expense(self, expense_id: str) -> Result: e = self._expenses.pop(expense_id, None) if e is None: return Result.NO_SUCH_EXPENSE self._apply(e, -1) return Result.OK
# Paying someone back is recorded as money owed the other way. Any positive amount is # accepted: friends settle in round numbers, and paying a little too much just flips who # owes whom. def settle(self, from_: str, to: str, amount: int) -> Result: if from_ not in self.members or to not in self.members: return Result.NOT_A_MEMBER if amount <= 0 or from_ == to: return Result.INVALID_AMOUNT self._payments.append(Payment(from_, to, amount)) self._balances.record(to, from_, amount) return Result.OK
def owes(self, debtor: str, creditor: str) -> int: return self._balances.owes(debtor, creditor)
def net(self, member: str) -> int: return self._balances.net(member)
# Each person's share is money they owe the payer. sign is 1 to add the expense, -1 to undo it. def _apply(self, e: Expense, sign: int) -> None: for person, share in e.shares.items(): self._balances.record(person, e.paid_by, sign * share)
# One payment the simplifier suggests: from_ pays to this amount.@dataclass(frozen=True)class Transfer: from_: str to: str amount: int
# After a weekend away, the pairwise debts can form a tangle: Ana owes Ben, Ben owes Cy, Cy owes# Dee. Only each person's net matters: how much they are up or down overall. Matching the# biggest debtor with the biggest creditor, again and again, settles everyone. Each transfer# clears at least one person, so a group of n needs at most n - 1 transfers.def simplify(g: Group) -> list[Transfer]: # heapq is a min-heap, so amounts go in negated: the biggest comes out first, ties by name. debtors: list[tuple[int, str]] = [] creditors: list[tuple[int, str]] = [] for m in g.members: net = g.net(m) if net < 0: heapq.heappush(debtors, (net, m)) elif net > 0: heapq.heappush(creditors, (-net, m)) out = [] while debtors: d_neg, d = heapq.heappop(debtors) c_neg, c = heapq.heappop(creditors) amount = min(-d_neg, -c_neg) out.append(Transfer(d, c, amount)) # Whoever isn't fully settled goes back in with what's left. if -d_neg > amount: heapq.heappush(debtors, (d_neg + amount, d)) if -c_neg > amount: heapq.heappush(creditors, (c_neg + amount, c)) return out
# Three friends add dinner, the taxi and the bar tab from their phones at the same moment. Each# expense reads a balance and writes it back, and two that interleave lose one update: the# group's balances no longer add up to its expenses, and nobody can say which is right. Every# operation on a group must run alone. A group sees a handful of writes a minute, so one lock# per group is plenty, and different groups never wait on each other.class SharedGroup: def __init__(self, group: Group): self._group = group self._lock = threading.Lock()
def add_expense(self, description: str, paid_by: str, total: int, split: Split) -> tuple[Result, Expense | None]: with self._lock: return self._group.add_expense(description, paid_by, total, split)
def delete_expense(self, expense_id: str) -> Result: with self._lock: return self._group.delete_expense(expense_id)
def settle(self, from_: str, to: str, amount: int) -> Result: with self._lock: return self._group.settle(from_, to, amount)
def owes(self, debtor: str, creditor: str) -> int: with self._lock: return self._group.owes(debtor, creditor)
def simplify(self) -> list[Transfer]: with self._lock: return simplify(self._group)Read onlyPython 3.12Every file builds in CI13 files256 lines
AllInOne.cs
AllInOne.cs
// The complete design, built from every stage on this page.
// One bill, already split. It keeps the shares, not the split rule, so deleting it later undoes// exactly what it did.public sealed record Expense(string Id, string Description, string PaidBy, long Total, List<(string Person, long Amount)> Shares);
// The front door: who has an account, and which groups exist.public sealed class Splitwise(Func<string> ids){ private readonly HashSet<string> _users = []; private readonly Dictionary<string, Group> _groups = [];
public void AddUser(string user) => _users.Add(user);
public Group? CreateGroup(string name, IEnumerable<string> members) { var set = members.ToHashSet(); if (!set.All(_users.Contains)) return null; var g = new Group(name, set, ids); _groups[name] = g; return g; }}
// How an expense is divided. Each kind of split carries its own inputs (who shares equally, the// exact amounts, the percentages) and turns a total into a share per person that adds up to// the total exactly. Shares are a list of pairs, so their order (who gets a leftover cent) is// the order the caller listed them. An impossible split returns null.public interface ISplit{ List<(string Person, long Amount)>? Shares(long total);}
// Everyone listed pays the same. A name listed twice is a mistake, so the split is refused.public sealed class EqualSplit(IReadOnlyList<string> people) : ISplit{ public List<(string Person, long Amount)>? Shares(long total) => people.Count == 0 || people.Distinct().Count() != people.Count ? null : Allocation.Allocate(total, people, people.Select(_ => 1L).ToList());}
public sealed class ExactSplit(IReadOnlyList<(string Person, long Amount)> amounts) : ISplit{ // The amounts are the shares, as long as they add up to what was paid. public List<(string Person, long Amount)>? Shares(long total) => amounts.Sum(a => a.Amount) == total && amounts.All(a => a.Amount >= 0) ? amounts.ToList() : null;}
// Each person pays a percentage. The percentages must add up to exactly 100.public sealed class PercentSplit(IReadOnlyList<(string Person, int Percent)> percents) : ISplit{ public List<(string Person, long Amount)>? Shares(long total) => percents.Sum(p => p.Percent) == 100 && percents.All(p => p.Percent >= 0) ? Allocation.Allocate(total, percents.Select(p => p.Person).ToList(), percents.Select(p => (long)p.Percent).ToList()) : null;}
// Used by the equal and percent splits: it turns weights into cents that add up exactly.public static class Allocation{ // Divides the total by weight, rounding each share down, then hands the cents left over to // the first people listed, one each. Any rule works if it's deterministic and the shares add // up to the total: 100.00 three ways is 33.34, 33.33 and 33.33, and no cent disappears. public static List<(string Person, long Amount)> Allocate(long total, IReadOnlyList<string> people, IReadOnlyList<long> weights) { var weightSum = weights.Sum(); var shares = people.Select((p, i) => (Person: p, Amount: total * weights[i] / weightSum)).ToList(); var left = total - shares.Sum(s => s.Amount); for (var i = 0; i < left; i++) shares[i] = (shares[i].Person, shares[i].Amount + 1); return shares; }}
// Who owes whom, kept up to date as expenses arrive, so a question is one lookup. The map is// two-sided: when Ben owes Ana 10, owed[ben][ana] is 10 and owed[ana][ben] is -10.public sealed class Balances{ private readonly Dictionary<string, Dictionary<string, long>> _owed = [];
public void Record(string debtor, string creditor, long amount) { if (debtor == creditor || amount == 0) return; Add(debtor, creditor, amount); Add(creditor, debtor, -amount); }
public long Owes(string debtor, string creditor) => _owed.TryGetValue(debtor, out var row) ? row.GetValueOrDefault(creditor) : 0;
// What everyone else owes this user in total: positive gets money back, negative pays. public long Net(string user) => _owed.TryGetValue(user, out var row) ? -row.Values.Sum() : 0;
private void Add(string a, string b, long amount) { if (!_owed.TryGetValue(a, out var row)) _owed[a] = row = []; var next = row.GetValueOrDefault(b) + amount; if (next == 0) row.Remove(b); else row[b] = next; }}
// What a request gets back, so the app can say what went wrong.public enum Result { Ok, NotAMember, InvalidSplit, InvalidAmount, NoSuchExpense }
// Money moving between two people outside of any expense: Ben pays Ana back.public sealed record Payment(string From, string To, long Amount);
// A trip, a flat, a couple. Expenses and payments belong to one group, and so do the balances,// so the flat's electricity bill never mixes with the ski trip.public sealed class Group(string name, IReadOnlySet<string> members, Func<string> ids){ private readonly Dictionary<string, Expense> _expenses = []; private readonly List<Payment> _payments = []; private readonly Balances _balances = new();
public string Name { get; } = name; public IReadOnlySet<string> Members { get; } = members;
// Check everything first, then change the balances. A bad expense changes nothing. public (Result, Expense?) AddExpense(string description, string paidBy, long total, ISplit split) { var shares = split.Shares(total); if (total <= 0 || shares is null) return (Result.InvalidSplit, null); if (!Members.Contains(paidBy) || !shares.All(s => Members.Contains(s.Person))) return (Result.NotAMember, null); var e = new Expense(ids(), description, paidBy, total, shares); _expenses[e.Id] = e; Apply(e, 1); return (Result.Ok, e); }
// A mistake is undone by applying the expense again with the sign flipped, so balances stay // a running sum and never need rebuilding from history. Deleting twice finds nothing. public Result DeleteExpense(string id) { if (!_expenses.Remove(id, out var e)) return Result.NoSuchExpense; Apply(e, -1); return Result.Ok; }
// Paying someone back is recorded as money owed the other way. Any positive amount is // accepted: friends settle in round numbers, and paying a little too much just flips who // owes whom. public Result Settle(string from, string to, long amount) { if (!Members.Contains(from) || !Members.Contains(to)) return Result.NotAMember; if (amount <= 0 || from == to) return Result.InvalidAmount; _payments.Add(new Payment(from, to, amount)); _balances.Record(to, from, amount); return Result.Ok; }
public long Owes(string debtor, string creditor) => _balances.Owes(debtor, creditor);
public long Net(string member) => _balances.Net(member);
// Each person's share is money they owe the payer. sign is 1 to add the expense, -1 to undo it. private void Apply(Expense e, int sign) { foreach (var (person, share) in e.Shares) _balances.Record(person, e.PaidBy, sign * share); }}
// One payment the simplifier suggests: From pays To this amount.public sealed record Transfer(string From, string To, long Amount);
// After a weekend away, the pairwise debts can form a tangle: Ana owes Ben, Ben owes Cy, Cy owes// Dee. Only each person's net matters: how much they are up or down overall. Matching the// biggest debtor with the biggest creditor, again and again, settles everyone. Each transfer// clears at least one person, so a group of n needs at most n - 1 transfers.public static class DebtSimplifier{ public static List<Transfer> Simplify(Group g) { // Biggest amount first; ties broken by name so the answer is the same every time. The // priority is (-amount, name) because PriorityQueue hands out the smallest first. var byBiggest = Comparer<(long, string)>.Create((a, b) => a.Item1 != b.Item1 ? a.Item1.CompareTo(b.Item1) : string.CompareOrdinal(a.Item2, b.Item2)); var debtors = new PriorityQueue<string, (long, string)>(byBiggest); var creditors = new PriorityQueue<string, (long, string)>(byBiggest); foreach (var m in g.Members) { var net = g.Net(m); if (net < 0) debtors.Enqueue(m, (net, m)); if (net > 0) creditors.Enqueue(m, (-net, m)); } var transfers = new List<Transfer>(); while (debtors.TryDequeue(out var d, out var dp)) { creditors.TryDequeue(out var c, out var cp); long owe = -dp.Item1, due = -cp.Item1, amount = Math.Min(owe, due); transfers.Add(new Transfer(d, c!, amount)); // Whoever isn't fully settled goes back in with what's left. if (owe > amount) debtors.Enqueue(d, (amount - owe, d)); if (due > amount) creditors.Enqueue(c!, (amount - due, c!)); } return transfers; }}
// Three friends add dinner, the taxi and the bar tab from their phones at the same moment. Each// expense reads a balance and writes it back, and two that interleave lose one update: the// group's balances no longer add up to its expenses, and nobody can say which is right. Every// operation on a group must run alone. A group sees a handful of writes a minute, so one lock// per group is plenty, and different groups never wait on each other.public sealed class SharedGroup(Group group){ private readonly Lock _gate = new();
public (Result, Expense?) AddExpense(string description, string paidBy, long total, ISplit split) { lock (_gate) return group.AddExpense(description, paidBy, total, split); }
public Result DeleteExpense(string id) { lock (_gate) return group.DeleteExpense(id); } public Result Settle(string from, string to, long amount) { lock (_gate) return group.Settle(from, to, amount); } public long Owes(string debtor, string creditor) { lock (_gate) return group.Owes(debtor, creditor); } public List<Transfer> Simplify() { lock (_gate) return DebtSimplifier.Simplify(group); }}Read onlyC# · .NET 10Every file builds in CI15 files219 lines
all_in_one.go
all_in_one.go
// The complete design, built from every stage on this page.
package splitwise
import ( "cmp" "maps" "slices" "sync")
// Share is one person's part of an expense. Shares are a slice, not a map, so their order (who// gets a leftover cent) is the order the caller listed them.type Share struct { Person string Amount int64}
// Split says how an expense is divided. Each kind carries its own inputs (who shares equally,// the exact amounts, the percentages) and turns a total into shares that add up to the total// exactly. An impossible split returns false.type Split interface { Shares(total int64) ([]Share, bool)}
// EqualSplit charges everyone listed the same. A name listed twice is a mistake, so the split// is refused.type EqualSplit struct{ People []string }
func (s EqualSplit) Shares(total int64) ([]Share, bool) { if len(s.People) == 0 { return nil, false } weights := make([]int64, len(s.People)) for i, p := range s.People { if slices.Contains(s.People[:i], p) { return nil, false // listed twice } weights[i] = 1 } return allocate(total, s.People, weights), true}
// ExactSplit's amounts are the shares, as long as they add up to what was paid.type ExactSplit struct{ Amounts []Share }
func (s ExactSplit) Shares(total int64) ([]Share, bool) { var sum int64 for _, a := range s.Amounts { if a.Amount < 0 { return nil, false } sum += a.Amount } return slices.Clone(s.Amounts), sum == total}
// Percent is one person's percentage in a PercentSplit.type Percent struct { Person string Percent int64}
// PercentSplit charges each person a percentage. The percentages must add up to exactly 100.type PercentSplit struct{ Percents []Percent }
func (s PercentSplit) Shares(total int64) ([]Share, bool) { var sum int64 people := make([]string, len(s.Percents)) weights := make([]int64, len(s.Percents)) for i, p := range s.Percents { if p.Percent < 0 { return nil, false } sum += p.Percent people[i], weights[i] = p.Person, p.Percent } if sum != 100 { return nil, false } return allocate(total, people, weights), true}
// allocate divides the total by weight, rounding each share down, then hands the cents left// over to the first people listed, one each. Any rule works if it's deterministic and the// shares add up to the total: 100.00 three ways is 33.34, 33.33 and 33.33, and no cent// disappears.func allocate(total int64, people []string, weights []int64) []Share { var weightSum, given int64 for _, w := range weights { weightSum += w } out := make([]Share, len(people)) for i, p := range people { out[i] = Share{p, total * weights[i] / weightSum} given += out[i].Amount } for i := 0; given < total; i, given = i+1, given+1 { out[i].Amount++ } return out}
// Balances keeps who owes whom up to date as expenses arrive, so a question is one lookup. The// map is two-sided: when Ben owes Ana 10, owed[ben][ana] is 10 and owed[ana][ben] is -10.type Balances struct { owed map[string]map[string]int64}
func NewBalances() *Balances { return &Balances{owed: map[string]map[string]int64{}} }
func (b *Balances) Record(debtor, creditor string, amount int64) { if debtor == creditor || amount == 0 { return } b.add(debtor, creditor, amount) b.add(creditor, debtor, -amount)}
func (b *Balances) Owes(debtor, creditor string) int64 { return b.owed[debtor][creditor] }
// Net is what everyone else owes this user in total: positive gets money back, negative pays.func (b *Balances) Net(user string) int64 { var sum int64 for _, v := range b.owed[user] { sum -= v } return sum}
func (b *Balances) add(x, y string, amount int64) { if b.owed[x] == nil { b.owed[x] = map[string]int64{} } if b.owed[x][y] += amount; b.owed[x][y] == 0 { delete(b.owed[x], y) }}
// Expense is one bill, already split. It keeps the shares, not the split rule, so deleting it// later undoes exactly what it did.type Expense struct { ID string Description string PaidBy string Total int64 Shares []Share}
// Result is what a request gets back, so the app can say what went wrong.type Result int
const ( OK Result = iota NotAMember InvalidSplit InvalidAmount NoSuchExpense)
// Payment is money moving between two people outside of any expense: Ben pays Ana back.type Payment struct { From, To string Amount int64}
// Group is a trip, a flat, a couple. Expenses and payments belong to one group, and so do the// balances, so the flat's electricity bill never mixes with the ski trip.type Group struct { Name string members map[string]bool expenses map[string]*Expense payments []Payment balances *Balances ids func() string}
// AddExpense checks everything first, then changes the balances. A bad expense changes nothing.func (g *Group) AddExpense(description, paidBy string, total int64, split Split) (Result, *Expense) { shares, ok := split.Shares(total) if total <= 0 || !ok { return InvalidSplit, nil } if !g.members[paidBy] || slices.ContainsFunc(shares, func(sh Share) bool { return !g.members[sh.Person] }) { return NotAMember, nil } e := &Expense{ID: g.ids(), Description: description, PaidBy: paidBy, Total: total, Shares: shares} g.expenses[e.ID] = e g.apply(e, 1) return OK, e}
// DeleteExpense undoes a mistake by applying the expense again with the sign flipped, so// balances stay a running sum and never need rebuilding from history. Deleting twice finds// nothing.func (g *Group) DeleteExpense(id string) Result { e := g.expenses[id] if e == nil { return NoSuchExpense } delete(g.expenses, id) g.apply(e, -1) return OK}
// Settle records paying someone back as money owed the other way. Any positive amount is// accepted: friends settle in round numbers, and paying a little too much just flips who owes// whom.func (g *Group) Settle(from, to string, amount int64) Result { if !g.members[from] || !g.members[to] { return NotAMember } if amount <= 0 || from == to { return InvalidAmount } g.payments = append(g.payments, Payment{from, to, amount}) g.balances.Record(to, from, amount) return OK}
func (g *Group) Owes(debtor, creditor string) int64 { return g.balances.Owes(debtor, creditor) }
func (g *Group) Net(member string) int64 { return g.balances.Net(member) }
func (g *Group) Members() []string { return slices.Sorted(maps.Keys(g.members)) }
// apply records each person's share as money they owe the payer. sign is 1 to add the expense,// -1 to undo it.func (g *Group) apply(e *Expense, sign int64) { for _, sh := range e.Shares { g.balances.Record(sh.Person, e.PaidBy, sign*sh.Amount) }}
// Splitwise is the front door: who has an account, and which groups exist.type Splitwise struct { users map[string]bool groups map[string]*Group ids func() string}
func NewSplitwise(ids func() string) *Splitwise { return &Splitwise{users: map[string]bool{}, groups: map[string]*Group{}, ids: ids}}
func (s *Splitwise) AddUser(user string) { s.users[user] = true }
func (s *Splitwise) CreateGroup(name string, members []string) *Group { g := &Group{Name: name, members: map[string]bool{}, expenses: map[string]*Expense{}, balances: NewBalances(), ids: s.ids} for _, m := range members { if !s.users[m] { return nil } g.members[m] = true } s.groups[name] = g return g}
// Transfer is one payment the simplifier suggests: From pays To this amount.type Transfer struct { From, To string Amount int64}
// Simplify untangles a group's debts. After a weekend away, pairwise debts can form a chain:// Ana owes Ben, Ben owes Cy, Cy owes Dee. Only each person's net matters: how much they are up// or down overall. Matching the biggest debtor with the biggest creditor, again and again,// settles everyone. Each transfer clears at least one person, so a group of n needs at most// n - 1 transfers.func Simplify(g *Group) []Transfer { type entry struct { who string amount int64 } var debtors, creditors []entry for _, m := range g.Members() { if net := g.Net(m); net < 0 { debtors = append(debtors, entry{m, -net}) } else if net > 0 { creditors = append(creditors, entry{m, net}) } } // Biggest amount first; ties broken by name so the answer is the same every time. A group // is a handful of people, so re-sorting each round is simpler than a heap and just as fast. biggest := func(a, b entry) int { return cmp.Or(cmp.Compare(b.amount, a.amount), cmp.Compare(a.who, b.who)) } var out []Transfer for len(debtors) > 0 { slices.SortFunc(debtors, biggest) slices.SortFunc(creditors, biggest) d, c := &debtors[0], &creditors[0] amount := min(d.amount, c.amount) out = append(out, Transfer{d.who, c.who, amount}) d.amount -= amount c.amount -= amount // Whoever is fully settled drops out; the other stays with what's left. if d.amount == 0 { debtors = debtors[1:] } if c.amount == 0 { creditors = creditors[1:] } } return out}
// SharedGroup exists because three friends add dinner, the taxi and the bar tab from their// phones at the same moment. Each expense reads a balance and writes it back, and two that// interleave lose one update: the group's balances no longer add up to its expenses, and// nobody can say which is right. Every operation on a group must run alone. A group sees a// handful of writes a minute, so one mutex per group is plenty, and different groups never// wait on each other.type SharedGroup struct { mu sync.Mutex group *Group}
func NewSharedGroup(g *Group) *SharedGroup { return &SharedGroup{group: g} }
func (s *SharedGroup) AddExpense(description, paidBy string, total int64, split Split) (Result, *Expense) { s.mu.Lock() defer s.mu.Unlock() return s.group.AddExpense(description, paidBy, total, split)}
func (s *SharedGroup) DeleteExpense(id string) Result { s.mu.Lock() defer s.mu.Unlock() return s.group.DeleteExpense(id)}
func (s *SharedGroup) Settle(from, to string, amount int64) Result { s.mu.Lock() defer s.mu.Unlock() return s.group.Settle(from, to, amount)}
func (s *SharedGroup) Owes(debtor, creditor string) int64 { s.mu.Lock() defer s.mu.Unlock() return s.group.Owes(debtor, creditor)}
func (s *SharedGroup) Simplify() []Transfer { s.mu.Lock() defer s.mu.Unlock() return Simplify(s.group)}Read onlyGo 1.24Every file builds in CI15 files350 lines
all-in-one.ts
all-in-one.ts
// The complete design, built from every stage on this page.
// One bill, already split. It keeps the shares, not the split rule, so deleting it later undoes// exactly what it did.interface Expense { readonly id: string; readonly description: string; readonly paidBy: string; readonly total: number; readonly shares: ReadonlyMap<string, number>;}
// The front door: who has an account, and which groups exist.class Splitwise { private readonly users = new Set<string>(); private readonly groups = new Map<string, Group>();
constructor(private readonly ids: () => string) {}
addUser(user: string): void { this.users.add(user); }
createGroup(name: string, members: string[]): Group | null { if (!members.every((m) => this.users.has(m))) return null; const g = new Group(name, new Set(members), this.ids); this.groups.set(name, g); return g; }}
// How an expense is divided. Each kind of split carries its own inputs (who shares equally, the// exact amounts, the percentages) and turns a total into a share per person that adds up to// the total exactly. A Map keeps the order people were listed in. An impossible split returns// null.interface Split { shares(total: number): Map<string, number> | null;}
// Everyone listed pays the same. A name listed twice is a mistake, so the split is refused.class EqualSplit implements Split { constructor(private readonly people: string[]) {}
shares(total: number): Map<string, number> | null { if (this.people.length === 0 || new Set(this.people).size !== this.people.length) return null; return allocate( total, this.people, this.people.map(() => 1), ); }}
class ExactSplit implements Split { constructor(private readonly amounts: Map<string, number>) {}
// The amounts are the shares, as long as they add up to what was paid. shares(total: number): Map<string, number> | null { const values = [...this.amounts.values()]; if (values.reduce((a, b) => a + b, 0) !== total || values.some((a) => a < 0)) return null; return new Map(this.amounts); }}
// Each person pays a percentage. The percentages must add up to exactly 100.class PercentSplit implements Split { constructor(private readonly percents: Map<string, number>) {}
shares(total: number): Map<string, number> | null { const values = [...this.percents.values()]; if (values.reduce((a, b) => a + b, 0) !== 100 || values.some((p) => p < 0)) return null; return allocate(total, [...this.percents.keys()], values); }}
// Divides the total by weight, rounding each share down, then hands the cents left over to the// first people listed, one each. Any rule works if it's deterministic and the shares add up to// the total: 100.00 three ways is 33.34, 33.33 and 33.33, and no cent disappears.function allocate(total: number, people: string[], weights: number[]): Map<string, number> { const weightSum = weights.reduce((a, b) => a + b, 0); const out = new Map(people.map((p, i) => [p, Math.floor((total * weights[i]) / weightSum)])); let left = total - [...out.values()].reduce((a, b) => a + b, 0); for (const p of people) { if (left-- <= 0) break; out.set(p, out.get(p)! + 1); } return out;}
// Who owes whom, kept up to date as expenses arrive, so a question is one lookup. The map is// two-sided: when Ben owes Ana 10, owed[ben][ana] is 10 and owed[ana][ben] is -10.class Balances { private readonly owed = new Map<string, Map<string, number>>();
record(debtor: string, creditor: string, amount: number): void { if (debtor === creditor || amount === 0) return; this.add(debtor, creditor, amount); this.add(creditor, debtor, -amount); }
owes(debtor: string, creditor: string): number { return this.owed.get(debtor)?.get(creditor) ?? 0; }
// What everyone else owes this user in total: positive gets money back, negative pays. net(user: string): number { let sum = 0; for (const v of this.owed.get(user)?.values() ?? []) sum -= v; return sum; }
private add(a: string, b: string, amount: number): void { let row = this.owed.get(a); if (!row) this.owed.set(a, (row = new Map())); const next = (row.get(b) ?? 0) + amount; if (next === 0) row.delete(b); else row.set(b, next); }}
// What a request gets back, so the app can say what went wrong.type Result = 'ok' | 'not-a-member' | 'invalid-split' | 'invalid-amount' | 'no-such-expense';
// Money moving between two people outside of any expense: Ben pays Ana back.interface Payment { readonly from: string; readonly to: string; readonly amount: number;}
// A trip, a flat, a couple. Expenses and payments belong to one group, and so do the balances,// so the flat's electricity bill never mixes with the ski trip.class Group { private readonly expenses = new Map<string, Expense>(); private readonly payments: Payment[] = []; private readonly balances = new Balances();
constructor( readonly name: string, readonly members: ReadonlySet<string>, private readonly ids: () => string, ) {}
// Check everything first, then change the balances. A bad expense changes nothing. addExpense(description: string, paidBy: string, total: number, split: Split): { result: Result; expense?: Expense } { const shares = split.shares(total); if (total <= 0 || !shares) return { result: 'invalid-split' }; if (!this.members.has(paidBy) || ![...shares.keys()].every((p) => this.members.has(p))) { return { result: 'not-a-member' }; } const e = { id: this.ids(), description, paidBy, total, shares }; this.expenses.set(e.id, e); this.apply(e, 1); return { result: 'ok', expense: e }; }
// A mistake is undone by applying the expense again with the sign flipped, so balances stay // a running sum and never need rebuilding from history. Deleting twice finds nothing. deleteExpense(id: string): Result { const e = this.expenses.get(id); if (!e) return 'no-such-expense'; this.expenses.delete(id); this.apply(e, -1); return 'ok'; }
// Paying someone back is recorded as money owed the other way. Any positive amount is // accepted: friends settle in round numbers, and paying a little too much just flips who // owes whom. settle(from: string, to: string, amount: number): Result { if (!this.members.has(from) || !this.members.has(to)) return 'not-a-member'; if (amount <= 0 || from === to) return 'invalid-amount'; this.payments.push({ from, to, amount }); this.balances.record(to, from, amount); return 'ok'; }
owes(debtor: string, creditor: string): number { return this.balances.owes(debtor, creditor); }
net(member: string): number { return this.balances.net(member); }
// Each person's share is money they owe the payer. sign is 1 to add the expense, -1 to undo it. private apply(e: Expense, sign: number): void { for (const [person, share] of e.shares) this.balances.record(person, e.paidBy, sign * share); }}
// One payment the simplifier suggests: `from` pays `to` this amount.interface Transfer { readonly from: string; readonly to: string; readonly amount: number;}
// After a weekend away, the pairwise debts can form a tangle: Ana owes Ben, Ben owes Cy, Cy owes// Dee. Only each person's net matters: how much they are up or down overall. Matching the// biggest debtor with the biggest creditor, again and again, settles everyone. Each transfer// clears at least one person, so a group of n needs at most n - 1 transfers.function simplify(g: Group): Transfer[] { const debtors: { who: string; amount: number }[] = []; const creditors: { who: string; amount: number }[] = []; for (const m of g.members) { const net = g.net(m); if (net < 0) debtors.push({ who: m, amount: -net }); if (net > 0) creditors.push({ who: m, amount: net }); } // Biggest amount first; ties broken by name so the answer is the same every time. A group is // a handful of people, so re-sorting each round is simpler than a heap and just as fast. const biggest = (a: { who: string; amount: number }, b: { who: string; amount: number }) => b.amount - a.amount || a.who.localeCompare(b.who); const out: Transfer[] = []; while (debtors.length > 0) { debtors.sort(biggest); creditors.sort(biggest); const d = debtors[0]; const c = creditors[0]; const amount = Math.min(d.amount, c.amount); out.push({ from: d.who, to: c.who, amount }); d.amount -= amount; c.amount -= amount; // Whoever is fully settled drops out; the other stays with what's left. if (d.amount === 0) debtors.shift(); if (c.amount === 0) creditors.shift(); } return out;}
// In one Node process Group needs no lock: addExpense updates every balance without an await// in between, so no other request can run in the middle. The race comes back when a group's// ledger lives in a database shared by many servers, and it brings a second problem: a phone// on a train sends "add dinner", the reply is lost, and it sends it again.interface Db { // Runs one statement and returns how many rows it changed. run(sql: string, ...args: unknown[]): Promise<number>; transaction<T>(work: (db: Db) => Promise<T>): Promise<T>;}
// expenses(id, group_id, request_id UNIQUE, paid_by, total), and one shares row per person:// shares(expense_id, person, amount). Balances aren't stored at all; "what does Ben owe Ana?"// is a SUM over the group's shares and payments, so there is no total to update and nothing// for two writers to overwrite.async function addExpenseInDb(db: Db, groupId: string, requestId: string, paidBy: string, total: number, split: Split): Promise<Result> { const shares = split.shares(total); if (total <= 0 || !shares) return 'invalid-split'; return db.transaction<Result>(async (tx) => { // The phone picks requestId once per expense, so a retry carries the same one. The // unique column turns the second insert into a no-op instead of a second dinner. const inserted = await tx.run( `INSERT INTO expenses (id, group_id, request_id, paid_by, total) VALUES ($1, $2, $3, $4, $5) ON CONFLICT (request_id) DO NOTHING`, requestId, groupId, requestId, paidBy, total, ); if (inserted === 0) return 'ok'; // already recorded by the first attempt // All shares commit with the expense, or none do, so no reader ever sees half of it. for (const [person, amount] of shares) { await tx.run(`INSERT INTO shares (expense_id, person, amount) VALUES ($1, $2, $3)`, requestId, person, amount); } return 'ok'; });}Read onlyTypeScript, strictEvery file builds in CI13 files268 lines
Three ideas hold it together:
- Every amount adds up. Shares add up to the expense, and the ledger’s entries for an expense add up to zero. So a group’s nets always add up to zero.
- The ledger only ever adds. Expenses, deletes and payments are all entries in the same running total. So any balance is correct without going back through history.
- Rules are strategies; views are worked out. Splits plug in (Strategy). Simplified payments
are worked out from nets when asked for, and never stored. And the app only calls
SplitwiseandGroup, simple front doors (a facade).
Stress it
Section titled “Stress it”So far, one phone adds expenses at a time. But at the end of a trip, everyone adds their last receipts at once.
Three phones, one group
Section titled “Three phones, one group”At the end of the trip, three people add the last expenses from their phones at the same moment. What can go wrong?
What they are testing
Whether you see the lost update on the ledger, choose a sensible thing to lock, and, for a database answer, think about a phone that retries after a lost reply and adds dinner twice.
Each expense reads a balance, adds a share, and writes it back. Two expenses that run at the same moment both read Ben’s debt to Ana as 20.00. Both add their share. Then one write overwrites the other. This is called a lost update. Ben’s balance is now wrong, the group’s nets no longer add up to zero, and the app can’t tell which number is right. With several shares per expense, someone reading balances can also see an expense that’s only half applied.
The fix, and the one we choose, is one lock per group. Every operation on a group runs alone. A
group sees a handful of changes a minute, so nobody waits in practice. And no expense spans two
groups, so different groups never wait for each other. SharedGroup adds the lock around Group,
so the group’s own code stays simple.
Scroll or pinch to zoom, drag to pan
- Color key
- Facade
| Option | How | Correct? | Cost |
|---|---|---|---|
| 1. One lock per group (our choice in memory) | Every SharedGroup method holds the lock |
Yes | One server owns each group |
| 2. Store entries, add up when reading | Insert expense and share rows in a transaction; balances are SUM queries |
Yes | Reads do more work; see the TypeScript tab |
| 3. Balance rows updated in place | UPDATE balances SET amount = amount + $1 per pair, in one transaction |
Yes | Two expenses touching the same pairs in opposite order can block each other forever |
| 4. A version number on the group | Write only if the group’s version is unchanged, else retry | Yes | Retries during a busy end-of-trip rush |
| 5. Read the balance, add, write it back | Two separate statements | No: lost updates | None, which is why it ships by mistake |
// Three friends add dinner, the taxi and the bar tab from their phones at the same moment. Each// expense reads a balance and writes it back, and two that interleave lose one update: the// group's balances no longer add up to its expenses, and nobody can say which is right. Every// operation on a group must run alone. A group sees a handful of writes a minute, so one lock// per group is plenty, and different groups never wait on each other.class SharedGroup { private final Group group; private final ReentrantLock lock = new ReentrantLock();
SharedGroup(Group group) { this.group = group; }
ExpenseResult addExpense(String description, String paidBy, long total, Split split) { return locked(() -> group.addExpense(description, paidBy, total, split)); } Result deleteExpense(String id) { return locked(() -> group.deleteExpense(id)); } Result settle(String from, String to, long amount) { return locked(() -> group.settle(from, to, amount)); } long owes(String debtor, String creditor) { return locked(() -> group.owes(debtor, creditor)); } List<Transfer> simplify() { return locked(() -> DebtSimplifier.simplify(group)); }
// Runs one operation with the lock held. finally releases it even if the operation throws. private <T> T locked(Supplier<T> op) { lock.lock(); try { return op.get(); } finally { lock.unlock(); } }}import threading
# Three friends add dinner, the taxi and the bar tab from their phones at the same moment. Each# expense reads a balance and writes it back, and two that interleave lose one update: the# group's balances no longer add up to its expenses, and nobody can say which is right. Every# operation on a group must run alone. A group sees a handful of writes a minute, so one lock# per group is plenty, and different groups never wait on each other.class SharedGroup: def __init__(self, group: Group): self._group = group self._lock = threading.Lock()
def add_expense(self, description: str, paid_by: str, total: int, split: Split) -> tuple[Result, Expense | None]: with self._lock: return self._group.add_expense(description, paid_by, total, split)
def delete_expense(self, expense_id: str) -> Result: with self._lock: return self._group.delete_expense(expense_id)
def settle(self, from_: str, to: str, amount: int) -> Result: with self._lock: return self._group.settle(from_, to, amount)
def owes(self, debtor: str, creditor: str) -> int: with self._lock: return self._group.owes(debtor, creditor)
def simplify(self) -> list[Transfer]: with self._lock: return simplify(self._group)// Three friends add dinner, the taxi and the bar tab from their phones at the same moment. Each// expense reads a balance and writes it back, and two that interleave lose one update: the// group's balances no longer add up to its expenses, and nobody can say which is right. Every// operation on a group must run alone. A group sees a handful of writes a minute, so one lock// per group is plenty, and different groups never wait on each other.public sealed class SharedGroup(Group group){ private readonly Lock _gate = new();
public (Result, Expense?) AddExpense(string description, string paidBy, long total, ISplit split) { lock (_gate) return group.AddExpense(description, paidBy, total, split); }
public Result DeleteExpense(string id) { lock (_gate) return group.DeleteExpense(id); } public Result Settle(string from, string to, long amount) { lock (_gate) return group.Settle(from, to, amount); } public long Owes(string debtor, string creditor) { lock (_gate) return group.Owes(debtor, creditor); } public List<Transfer> Simplify() { lock (_gate) return DebtSimplifier.Simplify(group); }}// SharedGroup exists because three friends add dinner, the taxi and the bar tab from their// phones at the same moment. Each expense reads a balance and writes it back, and two that// interleave lose one update: the group's balances no longer add up to its expenses, and// nobody can say which is right. Every operation on a group must run alone. A group sees a// handful of writes a minute, so one mutex per group is plenty, and different groups never// wait on each other.type SharedGroup struct { mu sync.Mutex group *Group}
func NewSharedGroup(g *Group) *SharedGroup { return &SharedGroup{group: g} }
func (s *SharedGroup) AddExpense(description, paidBy string, total int64, split Split) (Result, *Expense) { s.mu.Lock() defer s.mu.Unlock() return s.group.AddExpense(description, paidBy, total, split)}
func (s *SharedGroup) DeleteExpense(id string) Result { s.mu.Lock() defer s.mu.Unlock() return s.group.DeleteExpense(id)}
func (s *SharedGroup) Settle(from, to string, amount int64) Result { s.mu.Lock() defer s.mu.Unlock() return s.group.Settle(from, to, amount)}
func (s *SharedGroup) Owes(debtor, creditor string) int64 { s.mu.Lock() defer s.mu.Unlock() return s.group.Owes(debtor, creditor)}
func (s *SharedGroup) Simplify() []Transfer { s.mu.Lock() defer s.mu.Unlock() return Simplify(s.group)}// In one Node process Group needs no lock: addExpense updates every balance without an await// in between, so no other request can run in the middle. The race comes back when a group's// ledger lives in a database shared by many servers, and it brings a second problem: a phone// on a train sends "add dinner", the reply is lost, and it sends it again.interface Db { // Runs one statement and returns how many rows it changed. run(sql: string, ...args: unknown[]): Promise<number>; transaction<T>(work: (db: Db) => Promise<T>): Promise<T>;}
// expenses(id, group_id, request_id UNIQUE, paid_by, total), and one shares row per person:// shares(expense_id, person, amount). Balances aren't stored at all; "what does Ben owe Ana?"// is a SUM over the group's shares and payments, so there is no total to update and nothing// for two writers to overwrite.async function addExpenseInDb(db: Db, groupId: string, requestId: string, paidBy: string, total: number, split: Split): Promise<Result> { const shares = split.shares(total); if (total <= 0 || !shares) return 'invalid-split'; return db.transaction<Result>(async (tx) => { // The phone picks requestId once per expense, so a retry carries the same one. The // unique column turns the second insert into a no-op instead of a second dinner. const inserted = await tx.run( `INSERT INTO expenses (id, group_id, request_id, paid_by, total) VALUES ($1, $2, $3, $4, $5) ON CONFLICT (request_id) DO NOTHING`, requestId, groupId, requestId, paidBy, total, ); if (inserted === 0) return 'ok'; // already recorded by the first attempt // All shares commit with the expense, or none do, so no reader ever sees half of it. for (const [person, amount] of shares) { await tx.run(`INSERT INTO shares (expense_id, person, amount) VALUES ($1, $2, $3)`, requestId, person, amount); } return 'ok'; });}Why is this correct? Every change to a group holds the group’s lock from its first read to its last write. So no two expenses can read the same old balance, and nobody can read an expense that’s only half applied.
What does it cost? In-memory locks only work on one server, so each group must live on one server, or move to a database.
Go deeperThe database version, step by step1 min
In TypeScript, the in-memory Group needs no lock: addExpense updates every balance with no
await in between. So the TypeScript tab shows the database version instead.
It stores no balances at all, only expense rows and share rows. A balance is a sum over the share rows, worked out when someone asks. So there’s no total for two writers to overwrite: each expense just adds new rows.
It also handles the retry. The phone sends a request ID it chose once for this expense. The expense table has a rule that this column must be unique. So a second attempt with the same ID is refused by the database, instead of becoming a second dinner. The phone treats that refusal as “already saved”.
How you’d prove it works
Section titled “How you’d prove it works”Every test checks exact cents. The tests that matter:
- 100.00 split three ways gives 33.34, 33.33 and 33.33, and the balances match.
- Exact amounts that don’t add up, and percentages that aren’t 100, are refused.
- 99.99 split 50/30/20 gives 50.00, 30.00 and 19.99, with no cent lost.
- Debts in both directions net out to one number.
- Someone outside the group can’t be part of an expense.
- Settling up lowers the debt; a zero payment is refused.
- Deleting an expense restores the balances, and deleting twice is refused.
- A chain of debts simplifies to one payment, and a tangled group’s suggested payments leave every net at zero, in at most n − 1 payments.
- 160 expenses added from 16 threads are all counted.
Go deeperThe tests in five languages2 min
The simplification test checks a property, not a fixed answer. It applies whatever payments the simplifier suggests, then checks that everyone is at zero. So a better algorithm later passes the same test.
AtomicInteger nextId = new AtomicInteger();Group trip;
@BeforeEachvoid setUp() { Splitwise app = new Splitwise(() -> "e" + nextId.incrementAndGet()); for (String u : List.of("ana", "ben", "cy", "dee", "eve")) app.addUser(u); trip = app.createGroup("ski trip", Set.of("ana", "ben", "cy", "dee"));}
// An ordered map, so remainder cents go to the people in the order they were listed.static <V> Map<String, V> ordered(Object... kv) { Map<String, V> m = new LinkedHashMap<>(); for (int i = 0; i < kv.length; i += 2) m.put((String) kv[i], (V) kv[i + 1]); return m;}
Expense add(String paidBy, long total, Split split) { ExpenseResult r = trip.addExpense("x", paidBy, total, split); assertEquals(Result.OK, r.result()); return r.expense();}
@Testvoid anEqualSplitLosesNoCents() { Expense e = add("ana", 10000, new EqualSplit(List.of("ana", "ben", "cy"))); assertEquals(List.of(3334L, 3333L, 3333L), List.copyOf(e.shares().values())); assertEquals(3333, trip.owes("ben", "ana")); assertEquals(-3333, trip.owes("ana", "cy")); // negative: it's the other way round}
@Testvoid exactAmountsMustAddUpToWhatWasPaid() { ExpenseResult r = trip.addExpense("x", "ana", 5000, new ExactSplit(ordered("ben", 2000L, "cy", 2000L))); assertEquals(Result.INVALID_SPLIT, r.result()); add("ana", 5000, new ExactSplit(ordered("ben", 2000L, "cy", 3000L))); assertEquals(3000, trip.owes("cy", "ana"));}
@Testvoid percentagesRoundWithoutLosingTheTotal() { Expense e = add("ana", 9999, new PercentSplit(ordered("ana", 50, "ben", 30, "cy", 20))); assertEquals(List.of(5000L, 3000L, 1999L), List.copyOf(e.shares().values())); ExpenseResult bad = trip.addExpense("x", "ana", 100, new PercentSplit(ordered("ana", 50, "ben", 40))); assertEquals(Result.INVALID_SPLIT, bad.result());}
@Testvoid debtsInBothDirectionsNetOut() { add("ana", 3000, new EqualSplit(List.of("ana", "ben"))); add("ben", 1000, new EqualSplit(List.of("ana", "ben"))); assertEquals(1000, trip.owes("ben", "ana"));}
@Testvoid someoneOutsideTheGroupCantBeAdded() { ExpenseResult r = trip.addExpense("x", "ana", 1000, new EqualSplit(List.of("ana", "eve"))); assertEquals(Result.NOT_A_MEMBER, r.result());}
@Testvoid settlingUpRecordsAPayment() { add("ana", 4000, new EqualSplit(List.of("ana", "ben"))); assertEquals(Result.OK, trip.settle("ben", "ana", 1500)); assertEquals(500, trip.owes("ben", "ana")); assertEquals(Result.INVALID_AMOUNT, trip.settle("ben", "ana", 0));}
@Testvoid deletingAnExpenseUndoesItOnce() { Expense e = add("ana", 4000, new EqualSplit(List.of("ana", "ben"))); add("ben", 1000, new ExactSplit(ordered("ana", 1000L))); assertEquals(Result.OK, trip.deleteExpense(e.id())); assertEquals(1000, trip.owes("ana", "ben")); assertEquals(Result.NO_SUCH_EXPENSE, trip.deleteExpense(e.id()));}
@Testvoid aChainOfDebtsBecomesOneTransfer() { add("ben", 1000, new ExactSplit(ordered("ana", 1000L))); // ana owes ben add("cy", 1000, new ExactSplit(ordered("ben", 1000L))); // ben owes cy assertEquals(List.of(new Transfer("ana", "cy", 1000)), DebtSimplifier.simplify(trip));}
@Testvoid simplifiedTransfersSettleEveryone() { add("ana", 12000, new EqualSplit(List.of("ana", "ben", "cy", "dee"))); add("ben", 8000, new ExactSplit(ordered("cy", 5000L, "dee", 3000L))); add("cy", 2000, new EqualSplit(List.of("ana", "dee"))); List<Transfer> plan = DebtSimplifier.simplify(trip); assertTrue(plan.size() <= 3); for (Transfer t : plan) trip.settle(t.from(), t.to(), t.amount()); for (String m : trip.members()) assertEquals(0, trip.net(m));}
@Testvoid expensesAddedAtOnceAreAllCounted() throws Exception { SharedGroup shared = new SharedGroup(trip); ExecutorService pool = Executors.newFixedThreadPool(16); CountDownLatch start = new CountDownLatch(1); List<Future<?>> done = new ArrayList<>(); for (int i = 0; i < 160; i++) { done.add(pool.submit(() -> { start.await(); return shared.addExpense("coffee", "ana", 100, new EqualSplit(List.of("ana", "ben"))); })); } start.countDown(); for (Future<?> f : done) f.get(); pool.shutdown(); assertEquals(8000, shared.owes("ben", "ana"));}import itertoolsfrom concurrent.futures import ThreadPoolExecutor
import pytest
@pytest.fixturedef trip() -> Group: counter = itertools.count(1) app = Splitwise(lambda: f"e{next(counter)}") for u in ("ana", "ben", "cy", "dee", "eve"): app.add_user(u) return app.create_group("ski trip", {"ana", "ben", "cy", "dee"})
def add(trip: Group, paid_by: str, total: int, split: Split) -> Expense: result, e = trip.add_expense("x", paid_by, total, split) assert result is Result.OK return e
def test_an_equal_split_loses_no_cents(trip): e = add(trip, "ana", 10000, EqualSplit(["ana", "ben", "cy"])) assert list(e.shares.values()) == [3334, 3333, 3333] assert trip.owes("ben", "ana") == 3333 assert trip.owes("ana", "cy") == -3333 # negative: it's the other way round
def test_exact_amounts_must_add_up_to_what_was_paid(trip): assert trip.add_expense("x", "ana", 5000, ExactSplit({"ben": 2000, "cy": 2000}))[0] is Result.INVALID_SPLIT add(trip, "ana", 5000, ExactSplit({"ben": 2000, "cy": 3000})) assert trip.owes("cy", "ana") == 3000
def test_percentages_round_without_losing_the_total(trip): e = add(trip, "ana", 9999, PercentSplit({"ana": 50, "ben": 30, "cy": 20})) assert list(e.shares.values()) == [5000, 3000, 1999] assert trip.add_expense("x", "ana", 100, PercentSplit({"ana": 50, "ben": 40}))[0] is Result.INVALID_SPLIT
def test_debts_in_both_directions_net_out(trip): add(trip, "ana", 3000, EqualSplit(["ana", "ben"])) add(trip, "ben", 1000, EqualSplit(["ana", "ben"])) assert trip.owes("ben", "ana") == 1000
def test_someone_outside_the_group_cant_be_added(trip): assert trip.add_expense("x", "ana", 1000, EqualSplit(["ana", "eve"]))[0] is Result.NOT_A_MEMBER
def test_settling_up_records_a_payment(trip): add(trip, "ana", 4000, EqualSplit(["ana", "ben"])) assert trip.settle("ben", "ana", 1500) is Result.OK assert trip.owes("ben", "ana") == 500 assert trip.settle("ben", "ana", 0) is Result.INVALID_AMOUNT
def test_deleting_an_expense_undoes_it_once(trip): e = add(trip, "ana", 4000, EqualSplit(["ana", "ben"])) add(trip, "ben", 1000, ExactSplit({"ana": 1000})) assert trip.delete_expense(e.id) is Result.OK assert trip.owes("ana", "ben") == 1000 assert trip.delete_expense(e.id) is Result.NO_SUCH_EXPENSE
def test_a_chain_of_debts_becomes_one_transfer(trip): add(trip, "ben", 1000, ExactSplit({"ana": 1000})) # ana owes ben add(trip, "cy", 1000, ExactSplit({"ben": 1000})) # ben owes cy assert simplify(trip) == [Transfer("ana", "cy", 1000)]
def test_simplified_transfers_settle_everyone(trip): add(trip, "ana", 12000, EqualSplit(["ana", "ben", "cy", "dee"])) add(trip, "ben", 8000, ExactSplit({"cy": 5000, "dee": 3000})) add(trip, "cy", 2000, EqualSplit(["ana", "dee"])) plan = simplify(trip) assert len(plan) <= 3 for t in plan: trip.settle(t.from_, t.to, t.amount) assert all(trip.net(m) == 0 for m in trip.members)
def test_expenses_added_at_once_are_all_counted(trip): shared = SharedGroup(trip) with ThreadPoolExecutor(16) as pool: list(pool.map(lambda _: shared.add_expense("coffee", "ana", 100, EqualSplit(["ana", "ben"])), range(160))) assert shared.owes("ben", "ana") == 8000private readonly Group _trip;private int _nextId;
public SplitwiseTests(){ var app = new Splitwise(() => $"e{Interlocked.Increment(ref _nextId)}"); foreach (var u in new[] { "ana", "ben", "cy", "dee", "eve" }) app.AddUser(u); _trip = app.CreateGroup("ski trip", ["ana", "ben", "cy", "dee"])!;}
private Expense Add(string paidBy, long total, ISplit split){ var (result, e) = _trip.AddExpense("x", paidBy, total, split); Assert.Equal(Result.Ok, result); return e!;}
[Fact]public void AnEqualSplitLosesNoCents(){ var e = Add("ana", 10000, new EqualSplit(["ana", "ben", "cy"])); Assert.Equal(new long[] { 3334, 3333, 3333 }, e.Shares.Select(s => s.Amount)); Assert.Equal(3333, _trip.Owes("ben", "ana")); Assert.Equal(-3333, _trip.Owes("ana", "cy")); // negative: it's the other way round}
[Fact]public void ExactAmountsMustAddUpToWhatWasPaid(){ Assert.Equal(Result.InvalidSplit, _trip.AddExpense("x", "ana", 5000, new ExactSplit([("ben", 2000), ("cy", 2000)])).Item1); Add("ana", 5000, new ExactSplit([("ben", 2000), ("cy", 3000)])); Assert.Equal(3000, _trip.Owes("cy", "ana"));}
[Fact]public void PercentagesRoundWithoutLosingTheTotal(){ var e = Add("ana", 9999, new PercentSplit([("ana", 50), ("ben", 30), ("cy", 20)])); Assert.Equal(new long[] { 5000, 3000, 1999 }, e.Shares.Select(s => s.Amount)); Assert.Equal(Result.InvalidSplit, _trip.AddExpense("x", "ana", 100, new PercentSplit([("ana", 50), ("ben", 40)])).Item1);}
[Fact]public void DebtsInBothDirectionsNetOut(){ Add("ana", 3000, new EqualSplit(["ana", "ben"])); Add("ben", 1000, new EqualSplit(["ana", "ben"])); Assert.Equal(1000, _trip.Owes("ben", "ana"));}
[Fact]public void SomeoneOutsideTheGroupCantBeAdded(){ Assert.Equal(Result.NotAMember, _trip.AddExpense("x", "ana", 1000, new EqualSplit(["ana", "eve"])).Item1);}
[Fact]public void SettlingUpRecordsAPayment(){ Add("ana", 4000, new EqualSplit(["ana", "ben"])); Assert.Equal(Result.Ok, _trip.Settle("ben", "ana", 1500)); Assert.Equal(500, _trip.Owes("ben", "ana")); Assert.Equal(Result.InvalidAmount, _trip.Settle("ben", "ana", 0));}
[Fact]public void DeletingAnExpenseUndoesItOnce(){ var e = Add("ana", 4000, new EqualSplit(["ana", "ben"])); Add("ben", 1000, new ExactSplit([("ana", 1000)])); Assert.Equal(Result.Ok, _trip.DeleteExpense(e.Id)); Assert.Equal(1000, _trip.Owes("ana", "ben")); Assert.Equal(Result.NoSuchExpense, _trip.DeleteExpense(e.Id));}
[Fact]public void AChainOfDebtsBecomesOneTransfer(){ Add("ben", 1000, new ExactSplit([("ana", 1000)])); // ana owes ben Add("cy", 1000, new ExactSplit([("ben", 1000)])); // ben owes cy Assert.Equal(new[] { new Transfer("ana", "cy", 1000) }, DebtSimplifier.Simplify(_trip));}
[Fact]public void SimplifiedTransfersSettleEveryone(){ Add("ana", 12000, new EqualSplit(["ana", "ben", "cy", "dee"])); Add("ben", 8000, new ExactSplit([("cy", 5000), ("dee", 3000)])); Add("cy", 2000, new EqualSplit(["ana", "dee"])); var plan = DebtSimplifier.Simplify(_trip); Assert.True(plan.Count <= 3); foreach (var t in plan) _trip.Settle(t.From, t.To, t.Amount); Assert.All(_trip.Members, m => Assert.Equal(0, _trip.Net(m)));}
[Fact]public async Task ExpensesAddedAtOnceAreAllCounted(){ var shared = new SharedGroup(_trip); var start = new TaskCompletionSource(); var adds = Enumerable.Range(0, 160) .Select(_ => Task.Run(async () => { await start.Task; shared.AddExpense("coffee", "ana", 100, new EqualSplit(["ana", "ben"])); })) .ToArray(); start.SetResult(); await Task.WhenAll(adds); Assert.Equal(8000, shared.Owes("ben", "ana"));}func newTrip() *Group { var next atomic.Int64 app := NewSplitwise(func() string { return fmt.Sprintf("e%d", next.Add(1)) }) for _, u := range []string{"ana", "ben", "cy", "dee", "eve"} { app.AddUser(u) } return app.CreateGroup("ski trip", []string{"ana", "ben", "cy", "dee"})}
func add(t *testing.T, g *Group, paidBy string, total int64, split Split) *Expense { t.Helper() r, e := g.AddExpense("x", paidBy, total, split) if r != OK { t.Fatalf("add: %v", r) } return e}
func expect[T comparable](t *testing.T, want, got T) { t.Helper() if want != got { t.Fatalf("want %v, got %v", want, got) }}
func TestAnEqualSplitLosesNoCents(t *testing.T) { g := newTrip() e := add(t, g, "ana", 10000, EqualSplit{[]string{"ana", "ben", "cy"}}) expect(t, true, slices.Equal([]Share{{"ana", 3334}, {"ben", 3333}, {"cy", 3333}}, e.Shares)) expect(t, 3333, g.Owes("ben", "ana")) expect(t, -3333, g.Owes("ana", "cy")) // negative: it's the other way round}
func TestExactAmountsMustAddUpToWhatWasPaid(t *testing.T) { g := newTrip() r, _ := g.AddExpense("x", "ana", 5000, ExactSplit{[]Share{{"ben", 2000}, {"cy", 2000}}}) expect(t, InvalidSplit, r) add(t, g, "ana", 5000, ExactSplit{[]Share{{"ben", 2000}, {"cy", 3000}}}) expect(t, 3000, g.Owes("cy", "ana"))}
func TestPercentagesRoundWithoutLosingTheTotal(t *testing.T) { g := newTrip() e := add(t, g, "ana", 9999, PercentSplit{[]Percent{{"ana", 50}, {"ben", 30}, {"cy", 20}}}) expect(t, true, slices.Equal([]Share{{"ana", 5000}, {"ben", 3000}, {"cy", 1999}}, e.Shares)) r, _ := g.AddExpense("x", "ana", 100, PercentSplit{[]Percent{{"ana", 50}, {"ben", 40}}}) expect(t, InvalidSplit, r)}
func TestDebtsInBothDirectionsNetOut(t *testing.T) { g := newTrip() add(t, g, "ana", 3000, EqualSplit{[]string{"ana", "ben"}}) add(t, g, "ben", 1000, EqualSplit{[]string{"ana", "ben"}}) expect(t, 1000, g.Owes("ben", "ana"))}
func TestSomeoneOutsideTheGroupCantBeAdded(t *testing.T) { g := newTrip() r, _ := g.AddExpense("x", "ana", 1000, EqualSplit{[]string{"ana", "eve"}}) expect(t, NotAMember, r)}
func TestSettlingUpRecordsAPayment(t *testing.T) { g := newTrip() add(t, g, "ana", 4000, EqualSplit{[]string{"ana", "ben"}}) expect(t, OK, g.Settle("ben", "ana", 1500)) expect(t, 500, g.Owes("ben", "ana")) expect(t, InvalidAmount, g.Settle("ben", "ana", 0))}
func TestDeletingAnExpenseUndoesItOnce(t *testing.T) { g := newTrip() e := add(t, g, "ana", 4000, EqualSplit{[]string{"ana", "ben"}}) add(t, g, "ben", 1000, ExactSplit{[]Share{{"ana", 1000}}}) expect(t, OK, g.DeleteExpense(e.ID)) expect(t, 1000, g.Owes("ana", "ben")) expect(t, NoSuchExpense, g.DeleteExpense(e.ID))}
func TestAChainOfDebtsBecomesOneTransfer(t *testing.T) { g := newTrip() add(t, g, "ben", 1000, ExactSplit{[]Share{{"ana", 1000}}}) // ana owes ben add(t, g, "cy", 1000, ExactSplit{[]Share{{"ben", 1000}}}) // ben owes cy expect(t, true, slices.Equal([]Transfer{{"ana", "cy", 1000}}, Simplify(g)))}
func TestSimplifiedTransfersSettleEveryone(t *testing.T) { g := newTrip() add(t, g, "ana", 12000, EqualSplit{[]string{"ana", "ben", "cy", "dee"}}) add(t, g, "ben", 8000, ExactSplit{[]Share{{"cy", 5000}, {"dee", 3000}}}) add(t, g, "cy", 2000, EqualSplit{[]string{"ana", "dee"}}) plan := Simplify(g) expect(t, true, len(plan) <= 3) for _, tr := range plan { g.Settle(tr.From, tr.To, tr.Amount) } for _, m := range g.Members() { expect(t, 0, g.Net(m)) }}
func TestExpensesAddedAtOnceAreAllCounted(t *testing.T) { shared := NewSharedGroup(newTrip()) var wg sync.WaitGroup for range 160 { wg.Add(1) go func() { defer wg.Done() shared.AddExpense("coffee", "ana", 100, EqualSplit{[]string{"ana", "ben"}}) }() } wg.Wait() expect(t, 8000, shared.Owes("ben", "ana"))}import { test } from 'node:test';import assert from 'node:assert/strict';
function trip(): Group { let next = 0; const app = new Splitwise(() => `e${++next}`); for (const u of ['ana', 'ben', 'cy', 'dee', 'eve']) app.addUser(u); return app.createGroup('ski trip', ['ana', 'ben', 'cy', 'dee'])!;}
function add(g: Group, paidBy: string, total: number, split: Split): Expense { const { result, expense } = g.addExpense('x', paidBy, total, split); assert.equal(result, 'ok'); return expense!;}
test('an equal split loses no cents', () => { const g = trip(); const e = add(g, 'ana', 10000, new EqualSplit(['ana', 'ben', 'cy'])); assert.deepEqual([...e.shares.values()], [3334, 3333, 3333]); assert.equal(g.owes('ben', 'ana'), 3333); assert.equal(g.owes('ana', 'cy'), -3333); // negative: it's the other way round});
test('exact amounts must add up to what was paid', () => { const g = trip(); const bad = new ExactSplit( new Map([ ['ben', 2000], ['cy', 2000], ]), ); assert.equal(g.addExpense('x', 'ana', 5000, bad).result, 'invalid-split'); add( g, 'ana', 5000, new ExactSplit( new Map([ ['ben', 2000], ['cy', 3000], ]), ), ); assert.equal(g.owes('cy', 'ana'), 3000);});
test('percentages round without losing the total', () => { const g = trip(); const split = new PercentSplit( new Map([ ['ana', 50], ['ben', 30], ['cy', 20], ]), ); assert.deepEqual([...add(g, 'ana', 9999, split).shares.values()], [5000, 3000, 1999]); const bad = new PercentSplit( new Map([ ['ana', 50], ['ben', 40], ]), ); assert.equal(g.addExpense('x', 'ana', 100, bad).result, 'invalid-split');});
test('debts in both directions net out', () => { const g = trip(); add(g, 'ana', 3000, new EqualSplit(['ana', 'ben'])); add(g, 'ben', 1000, new EqualSplit(['ana', 'ben'])); assert.equal(g.owes('ben', 'ana'), 1000);});
test("someone outside the group can't be added", () => { const g = trip(); assert.equal(g.addExpense('x', 'ana', 1000, new EqualSplit(['ana', 'eve'])).result, 'not-a-member');});
test('settling up records a payment', () => { const g = trip(); add(g, 'ana', 4000, new EqualSplit(['ana', 'ben'])); assert.equal(g.settle('ben', 'ana', 1500), 'ok'); assert.equal(g.owes('ben', 'ana'), 500); assert.equal(g.settle('ben', 'ana', 0), 'invalid-amount');});
test('deleting an expense undoes it once', () => { const g = trip(); const e = add(g, 'ana', 4000, new EqualSplit(['ana', 'ben'])); add(g, 'ben', 1000, new ExactSplit(new Map([['ana', 1000]]))); assert.equal(g.deleteExpense(e.id), 'ok'); assert.equal(g.owes('ana', 'ben'), 1000); assert.equal(g.deleteExpense(e.id), 'no-such-expense');});
test('a chain of debts becomes one transfer', () => { const g = trip(); add(g, 'ben', 1000, new ExactSplit(new Map([['ana', 1000]]))); // ana owes ben add(g, 'cy', 1000, new ExactSplit(new Map([['ben', 1000]]))); // ben owes cy assert.deepEqual(simplify(g), [{ from: 'ana', to: 'cy', amount: 1000 }]);});
test('simplified transfers settle everyone', () => { const g = trip(); add(g, 'ana', 12000, new EqualSplit(['ana', 'ben', 'cy', 'dee'])); add( g, 'ben', 8000, new ExactSplit( new Map([ ['cy', 5000], ['dee', 3000], ]), ), ); add(g, 'cy', 2000, new EqualSplit(['ana', 'dee'])); const plan = simplify(g); assert.ok(plan.length <= 3); for (const t of plan) g.settle(t.from, t.to, t.amount); for (const m of g.members) assert.equal(g.net(m), 0);});Go deeperEvery edge case, and where it is handled2 min
| Case | What happens | Where |
|---|---|---|
| 100.00 three ways | 33.34, 33.33, 33.33 | allocate |
| Exact amounts don’t add up | INVALID_SPLIT, nothing recorded |
ExactSplit.shares |
| Percentages aren’t 100, or negative | INVALID_SPLIT |
PercentSplit.shares |
| Same person listed twice in an equal split | INVALID_SPLIT |
EqualSplit.shares |
| Zero or negative total | INVALID_SPLIT |
Group.addExpense |
| Someone outside the group | NOT_A_MEMBER |
Group.addExpense |
| Payer not among those who shared | Allowed: everyone else owes the payer their share | Group.addExpense |
| Delete twice | NO_SUCH_EXPENSE, reversed once |
Group.deleteExpense |
| Pay back more than owed | Allowed: the debt flips direction | Group.settle |
| Pay yourself, or pay zero | INVALID_AMOUNT |
Group.settle |
| Everyone already settled | simplify returns no payments |
DebtSimplifier |
| Phone retries an add | Recorded once, by request ID | the database version |
Wrap up
Section titled “Wrap up”The decisions, and what each one costs
Section titled “The decisions, and what each one costs”| Decision | We chose | We gave up |
|---|---|---|
| Money | Whole cents, leftovers given by a fixed rule | Fractions of a cent, which nobody can pay anyway |
| Kinds of split | A strategy per kind, checking its own inputs | One switch that’s quicker to write |
| Balances | A two-sided ledger per pair, updated as a running total | A replay that needs no extra data |
| Deleting | Apply the expense again, made negative | Nothing; it’s exact |
| Settling up | A payment in the same ledger | The app doesn’t move money |
| Fewer payments | Greedy on nets, at most n − 1 | The true minimum, which is NP-hard |
| Several phones | Lock per group; entries and a request ID in the database | Each group’s ledger lives in one place |
Go deeperGenuinely different designs, and when to pick them2 min
An event log as the source of truth. Store every expense, delete and payment as an event that never changes, and work out balances by going through them, saving the result. It gives a perfect history and makes edits easy to audit. It’s the database version taken further, and what larger apps do.
Nets only. Store only each person’s net per group. It’s smaller and makes simplifying trivial, but it can’t answer “what do I owe Ben?”. Apps that always show simplified debts can use it. Apps that show who owes whom, like Splitwise, can’t.
The exact minimum number of payments. For small groups, search for the largest number of sub-groups whose nets add up to zero (each settles in its size minus one payments). The search time grows very fast, so it only fits groups of about a dozen, and it usually saves just one or two payments over greedy.
How to spend 45 minutes
Section titled “How to spend 45 minutes”- 0 to 3. Kinds of split, cents, groups, and whether the app moves money.
- 3 to 5. The promises. Name “every split adds up” as the hard one.
- 5 to 23. One equal split, split strategies and the ledger, groups with delete and settle,
then simplifying. Code
allocate, the ledger’srecord, andsimplify. - 23 to 25. Walk through the full diagram: everything adds up, the ledger only adds.
- 25 to 32. Three phones at once: a lock per group, and the database version with a request ID.
- 32 to 45. Currencies or several payers, then your own questions.
If time is short, skip deleting and spend it on the split strategies and simplifying. Those are the two parts interviewers come back to.
Follow-up questions
Section titled “Follow-up questions”Half the trip was in euros and half in pounds. What changes?
What they are testing
Whether you keep balances per currency instead of converting when an expense is added, and see that the conversion question moves to settle-up time.
Most extensions fit into one place:
| Extension | What changes | Touches the ledger? |
|---|---|---|
| Several currencies | A balance per currency; simplify per currency | Yes, one more key |
| Split by shares or weights | A WeightedSplit using the same allocate |
No |
| Several payers on one expense | The payer side becomes a split too; each payer is owed their part | No |
| Repeating expenses (rent) | A schedule that adds the expense each month | No |
| Activity feed | Keep every add, delete and payment as an event | No |
| Reminders to settle | A job that reads nets and reminds whoever owes the most | No |
Go deeperAdding several currencies, step by step2 min
The tempting answer is to convert everything into one currency when the expense is added. But at what rate? The rate that day is one the group never agreed on, and next week’s rate will be different. Balances would slowly drift away from what people actually paid.
So instead, money keeps its currency until someone actually pays:
- Each expense keeps its currency. “Dinner, 84.00 EUR”. The split works in that currency’s smallest unit (cents), exactly as before.
- The ledger adds one more key. Instead of “what does Ben owe Ana?”, it records “what does Ben owe Ana, in euros?” and “in pounds?”. Each currency has its own running total, and each one still adds up to zero across the group.
- Simplify per currency. The greedy rule runs once for euros and once for pounds. Nothing about it changes.
- Convert only when paying, if the group wants. At settle-up, the app can show “Ben owes Ana 20 EUR and 15 GBP”, or offer to convert it all into one currency at today’s rate. That’s one choice, made once, at the moment money moves, and the payment is recorded in the currency it was made in.
Notice what didn’t change: the split strategies, allocate, deleting, and the lock. The ledger
grew one more key.
Go deeperAdding several payers, step by step2 min
Dinner was 90.00, and Ana paid 60.00 while Ben paid 30.00 because the card machine split the bill. Today, an expense has exactly one payer. Here’s how to allow several without touching the split strategies.
- The payer side becomes a list. An expense records who paid how much: Ana 6,000 cents, Ben 3,000 cents. These must add up to the total, checked like an exact split.
- Each person’s position is “paid minus owes”. The split still says what each person should pay: say 3,000 each for Ana, Ben and Cy. Then Ana is up 3,000 (paid 6,000, owes 3,000), Ben is at zero (paid 3,000, owes 3,000), and Cy is down 3,000.
- Turn the positions into ledger entries. Cy owes 3,000, and Ana is owed 3,000, so the ledger records Cy owing Ana 3,000. When several people are up and several are down, the same greedy matching from stage 4 turns positions into a few pairs.
- Deleting still works. The ledger entries for an expense still add up to zero, so applying them again with the signs flipped still undoes the expense exactly.
Notice that the split strategies didn’t change at all. They still answer “what should each person pay?”. The new part answers a different question, “what did each person pay?”, and the difference between the two is what goes in the ledger.
Go deeperFour more follow-up questions2 min
Interviewer asksWho should get the extra cent?
Any rule that always gives the same answer works, as long as the shares add up. Giving it to the first person listed is simple and easy to test. Giving it to the payer means nobody else ever pays more than an exact third, which some apps prefer. What’s wrong is a rule that depends on the order of a hash map, because the same expense could then split differently on different servers.
Interviewer asksHow would you show a user's total across all groups?
Add up their net in each group they belong to. It’s a few lookups per group, and can be cached per user and updated when any of their groups changes. Simplifying across groups is a different question. Most apps simplify within a group only, so payments stay with the trip they belong to.
Interviewer asksWhy not work out balances from all expenses on every read?
It’s correct and simple, which is why stage 1 did it. But the cost grows with history: a flat that has shared bills for five years would go through thousands of expenses to show one number. A running total makes reads quick, and a delete is a reversal, so nothing ever needs a replay.
Interviewer asksCan the simplifier suggest a payment between people who never met?
Yes, and that’s the point of it: Ana pays Cy because Ben was only passing money along. Some users dislike it, so apps make simplifying a group setting. With it off, the app shows the two-sided ledger instead. Both views come from the same data.
Further reading
Section titled “Further reading”- Strategy pattern, the shape of the split classes
- Design a hotel booking system, another ledger of counts kept as a running sum
- Design a library management system, fines as a small ledger settled at return
- Martin Fowler: Money, why amounts need a type and an allocation rule
- Stripe: idempotent requests, the client request id in practice
The designbeyondcode digest, every Saturday
New deep dives, interview tips and site news in one short email. Free. Leave with one click.
We never sell or share your email. We only use it to send this newsletter.