Overview
Design an expense-sharing app like Splitwise. Requirements: users create groups; anyone can add an expense paid by one user and split among participants equally, by exact amounts, or by percentages; the app tracks who owes whom; users can see balances and settle up; and optionally debts are simplified to minimize the number of transactions.
Key design elements: a Split strategy per split type (EqualSplit, ExactSplit, PercentSplit) that validates and computes shares with correct rounding; a balance sheet (net balance per user, or pairwise map) updated on each expense; money as integer cents; and a debt simplification algorithm that greedily matches the largest creditor with the largest debtor.
Every time someone pays, they write it down with who shared it. At the end, you add up what each person paid versus what they used, and settle the difference with as few payments as possible.
When to use it
- Very common LLD interview problem.
- Practicing Strategy for calculations and value objects for money.
- Graph-like balance problems.
Where it shows up in interviews
Recognize it when: several ways to compute the same result.
- Design Splitwise
- Design a tax calculator
- Design a parking fee calculator
Recognize it when: minimize transactions to settle debts.
- Optimal Account Balancing (LeetCode 465)
- Design Splitwise simplify debts
Where it is used in real software
Supports equal, exact, percentage, and share-based splits plus 'simplify debts' within groups.
Venmo and PayPal groups and bill splitting use similar balance models.
Double-entry bookkeeping ensures total debits equal total credits, like balances summing to zero.
Key terms
- Expense
- Payer, amount, participants, split type.
- Split strategy
- Computes each participant's share.
- Net balance
- Paid minus owed per user; all balances sum to zero.
- Rounding remainder
- Leftover cents distributed deterministically.
- Debt simplification
- Reduce the number of settlement payments.
How it works, step by step
- 1Clarify
Split types, groups, currencies, settle-up, simplification.
- 2Entities
User, Group, Expense, Split strategies, BalanceSheet, Transaction.
- 3Add expense
Strategy validates and computes shares; balances updated.
- 4Show balances
Per user net and pairwise 'who owes whom'.
- 5Simplify
Greedy match largest creditor and largest debtor.
Adding an expense and simplifying
Ana pays 90.00 dinner split equally among Ana, Bo, Cy; Bo pays 30.00 taxi split equally among Bo, Cy
| User | Paid | Owes (share) | Net |
|---|---|---|---|
| Ana | 90.00 | 30.00 | +60.00 |
| Bo | 30.00 | 30.00 + 15.00 | -15.00 |
| Cy | 0.00 | 30.00 + 15.00 | -45.00 |
| Simplified | - | - | Cy pays Ana 45.00; Bo pays Ana 15.00 |
NOWUser: Ana | Paid: 90.00 | Owes (share): 30.00 | Net: +60.00
Net balances sum to zero; greedy matching settles everything in 2 payments.
Implementation
import java.util.*; interface SplitStrategy { /** Returns share in cents per participant; must sum to total. */ Map<String, Long> shares(long totalCents, List<String> participants, Map<String, Long> params);} final class EqualSplit implements SplitStrategy { public Map<String, Long> shares(long total, List<String> people, Map<String, Long> params) { long base = total / people.size(), remainder = total % people.size(); Map<String, Long> out = new LinkedHashMap<>(); for (int i = 0; i < people.size(); i++) out.put(people.get(i), base + (i < remainder ? 1 : 0)); return out; }} final class ExactSplit implements SplitStrategy { public Map<String, Long> shares(long total, List<String> people, Map<String, Long> exact) { long sum = people.stream().mapToLong(p -> exact.getOrDefault(p, 0L)).sum(); if (sum != total) throw new IllegalArgumentException("Exact amounts must sum to total"); Map<String, Long> out = new LinkedHashMap<>(); people.forEach(p -> out.put(p, exact.get(p))); return out; }} final class PercentSplit implements SplitStrategy { public Map<String, Long> shares(long total, List<String> people, Map<String, Long> percents) { if (people.stream().mapToLong(percents::get).sum() != 100) throw new IllegalArgumentException("Percents must sum to 100"); Map<String, Long> out = new LinkedHashMap<>(); long assigned = 0; for (int i = 0; i < people.size(); i++) { long share = i == people.size() - 1 ? total - assigned : total * percents.get(people.get(i)) / 100; out.put(people.get(i), share); assigned += share; } return out; }} record Settlement(String from, String to, long cents) {} final class ExpenseManager { private final Map<String, Long> net = new HashMap<>(); // + means others owe this user void addExpense(String payer, long totalCents, List<String> participants, SplitStrategy split, Map<String, Long> params) { if (totalCents <= 0 || participants.isEmpty()) throw new IllegalArgumentException("Invalid expense"); Map<String, Long> shares = split.shares(totalCents, participants, params); net.merge(payer, totalCents, Long::sum); shares.forEach((user, share) -> net.merge(user, -share, Long::sum)); } long balance(String user) { return net.getOrDefault(user, 0L); } List<Settlement> simplify() { PriorityQueue<Map.Entry<String, Long>> creditors = new PriorityQueue<>((a, b) -> Long.compare(b.getValue(), a.getValue())); PriorityQueue<Map.Entry<String, Long>> debtors = new PriorityQueue<>(Comparator.comparingLong(Map.Entry::getValue)); net.forEach((u, v) -> { if (v > 0) creditors.add(new AbstractMap.SimpleEntry<>(u, v)); if (v < 0) debtors.add(new AbstractMap.SimpleEntry<>(u, v)); }); List<Settlement> result = new ArrayList<>(); while (!creditors.isEmpty() && !debtors.isEmpty()) { var c = creditors.poll(); var d = debtors.poll(); long amount = Math.min(c.getValue(), -d.getValue()); result.add(new Settlement(d.getKey(), c.getKey(), amount)); if (c.getValue() - amount > 0) creditors.add(new AbstractMap.SimpleEntry<>(c.getKey(), c.getValue() - amount)); if (d.getValue() + amount < 0) debtors.add(new AbstractMap.SimpleEntry<>(d.getKey(), d.getValue() + amount)); } return result; }} // ExpenseManager m = new ExpenseManager();// m.addExpense("ana", 9000, List.of("ana", "bo", "cy"), new EqualSplit(), Map.of());// m.addExpense("bo", 3000, List.of("bo", "cy"), new EqualSplit(), Map.of());// m.simplify() -> [cy pays ana 4500, bo pays ana 1500]Complexity and performance
Update net balances.
At most n - 1 payments.
Greedy is the practical choice.
Trade-offs
Net balances are compact and enable simplification; pairwise ledgers preserve 'who owes whom for what' history for display.
Simplified debts may ask users to pay people they never shared an expense with; make it optional per group.
Variants and related techniques
Weights like 2:1:1 for adults and children.
Store currency per expense; convert at settle time with a rates provider.
Common mistakes
- Using floating point.
Fix: Integer cents with explicit remainder handling.
- Shares not summing to the total.
Fix: Validate in each strategy; assign remainders deterministically.
- Split logic in a switch inside ExpenseManager.
Fix: Strategy per split type.
Interview questions
How do you handle 100 split three ways?
Work in cents: 10000 / 3 = 3333 remainder 1, so shares are 3334, 3333, 3333, assigning remainder cents deterministically (for example to the first participants or the payer).
How does debt simplification work?
Compute each user's net balance, then repeatedly match the largest creditor with the largest debtor and settle the smaller of the two amounts. This yields at most n - 1 payments; the true minimum is NP-hard.
Practice problems
| Problem | Difficulty | What it trains |
|---|---|---|
| Splitwise with three split types | Medium | Strategy + validation. |
| Groups, history, and simplify debts | Hard | Balances and greedy. |