Splitwise: who owes whom, to the paisa
Part of the free Low-Level Design course on LogicWiz, in the chapter: Case studies, step by step. The class-diagram exercises run in the app.
Splitwise: who owes whom, to the paisa
"Three friends split Rs 1,000 and the screen says 333.33 each. Add the three shares and tell me where the paisa went."
Priya, reviewing ExpenseTracker.java
The prompt, the first questions and the first classes
The prompt: friends share costs on a trip. Anyone can add an expense, choose how to split it, see balances, and get a short list of payments that settles everything.
Arjun asks first, and writes down each assumption.
- Which split types? Equal, exact amounts and percentages, and more will come later. "More will come" is a hint that the split rule must be easy to add.
- Are expenses always inside a group? Yes. A one-to-one expense is a group of two.
- Who pays? One person per expense. Many payers is an extension.
- Which money type? One currency, rupees, stored as paise (100 paise make one rupee) in a
long. Alongholds whole numbers exactly. - Who pays the odd paisa when a bill does not divide evenly? The first participants pay one paisa more each, so the shares always add up to the bill.
- Does "simplify debts" change who owes whom? Yes. Users want the fewest payments, even if Asha now pays Meena instead of Ravi.
Now the nouns. User, Group, Expense and Split (one person's share of one expense) are easy. The verbs "split", "keep balances" and "simplify" each need an owner. Priya asks, "Who owns each verb?" Arjun answers with SplitStrategy for splitting, BalanceSheet for balances, DebtSimplifier for simplifying, and ExpenseService as the entry point. A Settlement is one payment: from, to and an amount.
He leaves out login, receipts and photos, because the prompt never asks for them.
The first draft, and where it breaks
Here is the first draft. It is short, and every line looks reasonable.
class Tracker {
final Map<String, Double> net = new HashMap<>();
void addExpense(String payer, double amount, List<String> people, String type) {
net.merge(payer, amount, Double::sum);
if (type.equals("EQUAL")) {
for (String p : people) net.merge(p, -amount / people.size(), Double::sum);
} else if (type.equals("PERCENT")) {
// every new split type means another branch here
throw new UnsupportedOperationException(type);
}
}
}
Arjun adds three small expenses between Asha, Ravi and Meena, then checks that the balances add up to zero. Every rupee paid is a rupee owed, so the sum must be exactly zero. He also tries BigDecimal, which many candidates reach for.
Sum of balances with double: 5.551115123125783E-17
Three shares of Rs 1000.00: 333.33 each, together 999.99
Two problems. A double cannot store most decimal fractions exactly, so the sum is a tiny number and not zero. The group never shows "settled up". And BigDecimal with rounding avoids the tiny error, but three shares of 333.33 make 999.99, so one paisa belongs to nobody.
"But BigDecimal is the correct type for money," Arjun says. It is a good type. Rounding each share on its own is the real mistake, because nothing forces the shares to add up to the bill.
The third problem is the if on the type. Each new split type edits addExpense, and each one has its own validation. This is the shape the Strategy lesson fixed.
The decision: whole paise, and one class per split rule
Two decisions, both small.
First, count money in whole paise. Divide with whole-number arithmetic, then hand out the remainder one paisa at a time. The shares now add up to the bill by construction, not by luck.
Second, give each split rule its own class. Equal, exact and percentage splits differ in how they work and in what they check. One interface, one class each. ExpenseService picks the class from a map keyed by an enum, so it has no if on the type.
interface SplitStrategy {
/** values: unused for EQUAL, paise for EXACT, basis points (1% = 100) for PERCENT. */
List<Split> split(long totalPaise, List<User> users, List<Long> values);
}
final class EqualSplitStrategy implements SplitStrategy {
@Override
public List<Split> split(long totalPaise, List<User> users, List<Long> values) {
long base = totalPaise / users.size();
long leftover = totalPaise % users.size(); // 0 to n-1 paise
List<Split> out = new ArrayList<>();
for (int i = 0; i < users.size(); i++) {
out.add(new Split(users.get(i), base + (i < leftover ? 1 : 0)));
}
return out;
}
}
The service holds a map from the enum to the strategy. It looks the rule up, runs it, and builds the expense. There is no if on the type anywhere. The strategies hold no fields, so one object of each kind can serve every expense, even from two threads at the same time.
Expense addExpense(String groupId, ExpenseRequest req) {
SplitStrategy strategy = strategies.get(req.type());
List<Split> splits = strategy.split(req.amountPaise(), req.users(), req.values());
Expense expense = new Expense(req.description(), req.amountPaise(), req.paidBy(), req.type(), splits);
sheets.computeIfAbsent(groupId, g -> new BalanceSheet()).apply(expense);
return expense;
}
A basis point is one hundredth of a percent, so 50% is 5,000 basis points. Whole numbers keep percentages exact too. PercentSplitStrategy rounds each share down and gives the lost paise to the first person. The exact-amount rule only checks that the amounts add up to the total.
The last guard sits in Expense itself. It is a record, so it is immutable, and its constructor refuses splits that do not add up.
/** Immutable once created. Its splits always add up to amountPaise. */
record Expense(String description, long amountPaise, User paidBy, SplitType type, List<Split> splits) {
Expense {
long sum = splits.stream().mapToLong(Split::amountPaise).sum();
if (sum != amountPaise) throw new IllegalArgumentException("Splits add up to " + sum + ", not " + amountPaise);
splits = List.copyOf(splits);
}
}
Run it on Rs 1,000.00 between three people, and on Rs 10.01 split 50 and 50.
1000.00 equal: Asha 33334 paise
1000.00 equal: Ravi 33333 paise
1000.00 equal: Meena 33333 paise
10.01 at 50/50: Asha 501 paise
10.01 at 50/50: Ravi 500 paise
The shares add up to 100,000 and to 1,001. Nothing is lost.
The key method: balances as a graph, then simplify
Think of the group as a graph: a set of dots joined by arrows. Each person is a dot, and each debt is an arrow from the person who owes to the person owed. Asha, Ravi, Meena and Arjun go on a trip. Asha pays Rs 2,000 for the hotel, shared equally by all four. Ravi pays Rs 900 for a cab, shared by Ravi, Meena and Arjun. Meena pays Rs 1,000 for dinner, split exactly as Asha 400, Ravi 100, Meena 300 and Arjun 200.
Read as arrows, that is eight payments: three for the hotel, two for the cab and three for the dinner. Some go in opposite directions between the same people. Nobody wants to make eight transfers.
The key idea: only each person's net balance matters. That is what they are owed minus what they owe. A positive net means they get money back. BalanceSheet keeps one number per person and updates it on every expense. It loses one thing: the answer to "why do I owe Meena?". So the list of expenses stays as the history, and the sheet is a fast summary that can be rebuilt from it.
final class BalanceSheet {
private final Map<User, Long> net = new HashMap<>(); // > 0 gets money back, < 0 owes
public synchronized void apply(Expense e) {
net.merge(e.paidBy(), e.amountPaise(), Long::sum);
for (Split s : e.splits()) net.merge(s.user(), -s.amountPaise(), Long::sum);
}
// ... applyPayment and netBalances follow the same pattern
}
For the trip, the nets are Asha +1,100, Ravi 0, Meena -100 and Arjun -1,000 (in rupees). They add up to zero, as they must. Now the greedy algorithm: at each step, take the best-looking choice right now and never go back. Here the choice is the person who owes most paying the person owed most, as much as possible.
- Biggest debtor: Arjun owes 1,000. Biggest creditor: Asha is owed 1,100. Arjun pays Asha 1,000. Asha is still owed 100, and Arjun is done.
- Biggest debtor: Meena owes 100. Biggest creditor: Asha is owed 100. Meena pays Asha 100. Everyone is at zero.
final class DebtSimplifier {
private record Entry(User user, long paise) {}
/** Greedy: the biggest debtor pays the biggest creditor. At most n - 1 payments. */
public List<Settlement> simplify(Map<User, Long> net) {
Comparator<Entry> biggestFirst = Comparator.comparingLong((Entry e) -> Math.abs(e.paise())).reversed();
PriorityQueue<Entry> creditors = new PriorityQueue<>(biggestFirst);
PriorityQueue<Entry> debtors = new PriorityQueue<>(biggestFirst);
net.forEach((u, p) -> {
if (p > 0) creditors.add(new Entry(u, p));
else if (p < 0) debtors.add(new Entry(u, p));
});
List<Settlement> out = new ArrayList<>();
while (!creditors.isEmpty() && !debtors.isEmpty()) {
Entry c = creditors.poll();
Entry d = debtors.poll();
long amount = Math.min(c.paise(), -d.paise());
out.add(new Settlement(d.user(), c.user(), amount));
if (c.paise() > amount) creditors.add(new Entry(c.user(), c.paise() - amount));
if (-d.paise() > amount) debtors.add(new Entry(d.user(), d.paise() + amount));
}
return out;
}
}
A priority queue hands back the largest entry in O(log n) time. Each step settles at least one person, so n people need at most n minus 1 payments. The program agrees with the hand trace:
net Arjun: -1000.00
net Asha: 1100.00
net Meena: -100.00
net Ravi: 0.00
Arjun pays Asha 1000.00
Meena pays Asha 100.00
Eight arrows became two. One example is not proof, so Arjun writes a check. It builds 10,000 random groups, then asserts three facts: the nets sum to zero, paying the plan settles everyone, and the plan has at most n minus 1 payments.
Map<User, Long> net = svc.balances("g");
if (net.values().stream().mapToLong(Long::longValue).sum() != 0) throw new AssertionError("nets do not sum to zero");
List<Settlement> plan = svc.simplifyDebts("g");
for (Settlement s : plan) svc.settle("g", s);
if (svc.balances("g").values().stream().anyMatch(p -> p != 0)) throw new AssertionError("not settled");
if (plan.size() > users.size() - 1) throw new AssertionError("too many payments");
10000 random groups: nets sum to 0, everyone settled, at most 4 payments
Greedy is not always the fewest. Take five friends with nets of +400, +300, -300, -200 and -200. Greedy makes four payments, but the best plan has three: one group of the +400 and the two -200s, and one group of +300 and -300. Finding the true minimum has no known fast method, so greedy is the standard answer in an interview. It also has a user-facing cost: Meena may be asked to pay someone she never spent money with. Offer simplification as a group setting that people can switch off.
Extend it, then try to break it
Extension: split by shares. Ravi has two shares of the rent and Meena has one. This is a new rule, so it is one new class, one enum value and one line in the service map. ExpenseService.addExpense does not change.
final class ShareSplitStrategy implements SplitStrategy {
@Override
public List<Split> split(long totalPaise, List<User> users, List<Long> shares) {
long all = shares.stream().mapToLong(Long::longValue).sum();
List<Split> out = new ArrayList<>();
long given = 0;
for (int i = 0; i < users.size(); i++) {
long part = totalPaise * shares.get(i) / all; // rounds down
out.add(new Split(users.get(i), part));
given += part;
}
Split first = out.get(0); // leftover paise go to the first person
out.set(0, new Split(first.user(), first.amountPaise() + (totalPaise - given)));
return out;
}
}
Ravi 666668 paise
Meena 333333 paise
splits add up to 1000001
Break it: two threads. Two people add expenses to the same group at the same moment. HashMap.merge is not safe for two threads, so one update can be lost and the nets no longer add up to zero. The synchronized methods on BalanceSheet make each apply run alone. The expense list stays the source of truth, so a corrupted sheet can be rebuilt by replaying it.
⚠️ Warning: Do not let anyone change a saved
Split. If a user edits an expense, keep the old one, apply a reversing entry and apply the new one.
Your turn
Draw the core of the design in the class designer. The starter is the draft with one if on the split type and a double amount. Replace it with strategies, give the expense its splits, and add a class that owns the balances.
Then open the Splitwise problem in the problem library. Design it again without the model answer, compare, and follow its "Build it on your machine" kit to write the working version in your IDE.
📌 Summary: Store money as whole paise and hand out the leftover so shares add up. Put each split rule behind a strategy. Keep net balances, then simplify greedily: biggest debtor pays biggest creditor.
What Arjun learns next
Money is exact now. Next, Priya shows him a harder kind of bug: two people tap the same seat at the same second, and both get a ticket.
Check your understanding
- A Rs 100.00 bill is split equally among three people. Which approach makes the three shares add up to the bill?
- Next week the product team asks for a split by shares, such as Ravi 2 and Meena 1. What is the smallest change?
- Why does DebtSimplifier work on net balances, and not on the list of expenses?
- Greedy simplification gives a group 4 payments, and a friend finds a plan with 3. What is the best reply in an interview?