LLD9 min read
Splitwise (Expense Sharing)
Track group expenses with arbitrary splits and minimise inter-user settlement transactions.
lldoopgraph
Intro
Splitwise tracks who owes whom across a group. The two non-trivial pieces are the expense data model (it must accept equal, exact and percentage splits cleanly) and the settle-up algorithm that minimises the number of transactions.
Functional
- Add a user and a group.
- Add an expense with EQUAL / EXACT / PERCENT splits.
- Show net balance for each user.
- Suggest minimum-transaction settlement.
Non-functional
- Floating-point safe — money in cents/paise, not doubles.
- Auditable expense history — never mutate, append.
Components
User
Identity. Holds name and contact.
Group
Bag of users with shared expenses.
Expense
Immutable. Holds payer, total, splits[] and metadata.
Split (interface)
EqualSplit, ExactSplit, PercentSplit — strategy for divvying up.
BalanceSheet
Maintains net[i][j] and exposes balances.
SettlementMinimizer
Greedy max-debtor / max-creditor algorithm.
Trade-offs
Live n×n matrix vs. per-user net balance
Pros
- Net balance is O(n) memory and matches what users actually see.
- n×n matrix preserves who-owes-whom for audit.
Cons
- Net balance loses pairwise history; n×n grows with users.
Code
Adding an expense + settlingjava
abstract class Split { final User user; long amount; Split(User u){ this.user = u; } }
class EqualSplit extends Split { EqualSplit(User u){ super(u); } }
class PercentSplit extends Split { final double pct; PercentSplit(User u, double p){ super(u); this.pct = p; } }
class Expense {
User payer; long total; List<Split> splits; ExpenseType type;
void validate() {
if (type == ExpenseType.EQUAL) {
long share = total / splits.size();
for (Split s : splits) s.amount = share;
} else if (type == ExpenseType.PERCENT) {
double sum = splits.stream().mapToDouble(s -> ((PercentSplit)s).pct).sum();
if (Math.abs(sum - 100.0) > 1e-6) throw new IllegalArgumentException();
for (Split s : splits) s.amount = Math.round(total * ((PercentSplit)s).pct / 100);
}
}
}
class BalanceSheet {
Map<String, Map<String, Long>> owes = new HashMap<>();
void apply(Expense e) {
for (Split s : e.splits) {
if (s.user.equals(e.payer)) continue;
owes.computeIfAbsent(s.user.id, x -> new HashMap<>())
.merge(e.payer.id, s.amount, Long::sum);
}
}
}Pitfalls
- Tracking money as doubles — rounding errors compound.
- Editing an expense in place — the audit trail is gone.
- Naive O(n²) settlement when a heap-based greedy gives O(n log n).