Splitwise

Expense Sharing

Design an expense-sharing service: one person pays, the bill is split by a rule, balances are tracked in whole cents, and the group settles up with as few transfers as the greedy method finds.

Overview

A group of friends pays for things on each other's behalf: one buys dinner, another the train tickets. The service records each expense, splits it among the people who shared it, keeps a running balance of who owes whom, and at the end proposes a short list of payments that clears everything. Splitwise is the app that made this popular; its own description of debt simplification lists three rules: everyone owes the same net amount afterward, no one owes a person they did not owe before, and no one owes more in total than before.

The problem has two halves. The object model half is about splitting one expense correctly: equal, exact amounts or percentages, with every cent accounted for. The algorithm half is about settling: turning a tangle of pairwise debts into a few transfers. Interviewers use the first half to check that you model money without floats and use a strategy object for the split rule, and the second half to see whether you know the greedy method, its guarantee of at most N minus 1 transfers, and why finding the true minimum is hard.

A strong answer stores amounts as integer cents, validates each split before touching any balance, keeps both the expense log and a net balance per user, and can explain the greedy settlement with a small trace.

Scoping the problem

Which split rules are needed? — Each rule is a strategy class; ask before writing the base class — Equal, exact amounts, percentages
One currency or many? — Mixed currencies need exchange rates and a currency per balance — One currency, whole cents
Do we need groups? — A group scopes expenses and settlement to its members — Yes, but the ledger logic is the same
Is the payer always one person? — Several payers make an expense a list of (payer, amount) pairs — One payer
Should settlement be per pair or simplified? — Simplification changes who pays whom, not how much anyone owes in total — Offer both; simplification is the interesting part
Many users adding at once? — Two writes to the same balance must not race — A lock per group in memory; a transaction in a database

Adding an expense

The ledger asks the strategy for the shares, checks that they add up to the total, and only then updates balances. The payer is credited the whole amount and each participant, the payer included, is debited their share.

Money in whole cents

Floating point cannot hold most decimal fractions exactly. Python's own tutorial shows that 0.1 + 0.1 + 0.1 == 0.3 is False. A ledger built on floats drifts by a cent and then its settlement never reaches exactly zero. Store cents as integers, split with integer division, and hand out the remainder one cent at a time.

$100.00 — 3 — 3333 — 1 — 3334, 3333, 3333
$90.00 — 4 — 2250 — 0 — 2250 each
$10.01 — 2 — 500 — 1 — 501, 500

The rule for the remainder must be deterministic so that the same expense always produces the same shares. The code gives the extra cents to the first participants in the order passed in. Percentages work the same way: compute each share as total * percent // 100 and give the leftover cents out in order.

Pairwise debts versus net balances

There are two ways to keep the state. A pairwise table answers 'how much does B owe A?' exactly as the expenses happened. A net balance per user is a single number: positive means the group owes that person, negative means they owe the group. Settlement only needs the net numbers.

Expense log — What was bought, by whom, split how — One row per expense — Audit, editing or deleting an expense
Pairwise balances — B owes A this much — Up to one entry per pair — The 'you owe Alice $12' screen
Net balance per user — Group owes A, B owes group — One number per user — Settlement

Keep the log always; it is the source of truth and the other two can be rebuilt from it. The code below keeps the log and the net balances, and derives the pairwise view from the log when asked.

Settling with the greedy method

Sort the people who are owed money (creditors) and the people who owe (debtors) by amount. Match the largest debtor with the largest creditor, transfer the smaller of the two amounts, and drop whichever side reached zero. Each transfer zeroes at least one person, so there are at most N minus 1 transfers for N people with nonzero balances.

A trace on four people. Alice paid $90.00 for a dinner shared by all four, and Carol paid $30.00 for something shared by Carol and Dave. Carol is credited 3000 and debited 2250 for the dinner and 1500 for her own bill, so she still owes 750.

start — A +6750, B -2250, C -750, D -3750 — sum is 0
1 — D (-3750), A (+6750) — D pays A 3750 — A +3000, D 0
2 — B (-2250), A (+3000) — B pays A 2250 — A +750, B 0
3 — C (-750), A (+750) — C pays A 750 — everyone 0

Three transfers for four people, which is the N minus 1 bound. Greedy works on net balances only, so in other cases it can ask someone to pay a person they never owed; keeping Splitwise's second rule means limiting transfers to pairs that already owed each other. The demo in the implementation runs this exact case and then applies the transfers to a copy of the raw nets to prove they all reach zero.

Why the greedy result is good but not always minimal

Tom Verhoeff's paper on settling debts shows both facts an interviewer wants to hear. Any set of balances can be settled in at most N minus 1 transfers. Finding the smallest possible number of transfers is NP-hard: even with only two people in debt, deciding whether N minus 2 transfers suffice amounts to finding a subset of the positive balances that sums exactly to one debtor's balance, which is the subset-sum problem.

A +30, B -10, C -20 — 2 — 2 — N minus 1, and each debtor needs at least one transfer
A -60, B -50, C +10, D +50, E +50 — 4 — 3 — A can pay D 50 and C 10, B can pay E 50; greedy pairs A with one of the 50s first and then has to split the rest
A +50, B +50, C -50, D -50 — 2 — 2 — Two independent pairs; greedy finds them because the amounts tie

For a group of friends the greedy answer is fine and runs in O(N log N). Say that the optimal version is a partition problem and would need exponential search, and that products do not do it.

What you will be able to do

Model an expense with a payer, a total in cents and a split strategy, and add a new split rule without touching the others.
Split any amount so the shares sum exactly to the total, and explain why floats are wrong for money.
Keep an expense log plus net balances, and derive who-owes-whom from the log.
Settle a group with the greedy method, trace it by hand, and state the N minus 1 bound and the NP-hardness of the minimum.
Protect the ledger from concurrent writers with one lock, and describe the database version.

Functional requirements

Record an expense: who paid, the total in cents, the participants and the split rule
Split equally, by exact amounts or by percentages, with every cent assigned and shares summing to the total
Reject a split that does not add up before any balance changes
Keep a net balance per user and the full expense log; answer how much one user owes another
Produce a settlement: a list of transfers that brings every net balance to zero
Record a payment between two users as a settlement transfer

Non-functional requirements

Amounts are integers (cents); no floating point anywhere in the ledger
The net balances always sum to zero; the code asserts it after every change
Settlement runs in O(N log N) and returns at most N minus 1 transfers
Concurrent add_expense calls on one ledger are serialized by a lock
The expense log is never lost; balances can be rebuilt from it

Interview questions

Why integer cents instead of floats or Decimal?
Should the system store every expense, or just the balances?
Is the greedy settlement optimal? What would optimal cost?
How do you add a new split rule, for example splitting by shares?
Two people add expenses to the same group at the same time. What breaks, and how do you stop it?