What Splitwise teaches
Splitwise is an app that tracks shared expenses: you pay for dinner, a friend pays for the cab, and the app tells everyone who owes whom. As an interview problem it is popular because it mixes three things in a small space:
- Clean object modelling: users, groups, expenses and splits.
- Validation and money handling: shares must add up exactly, percentages must total 100, and rupees must not drift through floating-point rounding.
- An algorithm: "simplify debts", which reduces the number of payments a group must make. Interviewers expect you to know the greedy approach, work an example and admit when it is not optimal.
This lesson designs and codes all three in Java. It runs a four-person trip with every split type, checks the balance sheet by hand to the paisa, simplifies six pairwise debts down to three payments, settles up to zero, shows a case where greedy simplification is beaten by an exact algorithm, and finally hammers the group with 8,000 concurrent expenses. Splits use the Strategy pattern; see Behavioural patterns if you need a refresher.
Problem statement
Design an expense-sharing application. Users can form groups. Any member can add an expense paid by one member and shared among some members, split equally, by exact amounts or by percentages. The app shows each user's balance, who owes whom, and a simplified plan with fewer payments. Users record settle-up payments that reduce what they owe.
Clarifying questions and assumed requirements
| Question | Assumed answer | Effect on the design |
|---|---|---|
| Expenses only inside groups? | Yes for the code; non-group expenses discussed as an extension | Group owns expenses |
| Who pays? | Exactly one payer per expense | paidBy field; multiple payers is an extension |
| Split types? | Equal, exact amounts, percentages | Three strategies |
| Must the payer be a participant? | No: you can pay for others without sharing | Payer and participants are separate |
| Currency? | Single currency, rupees with paise | Store paise as long |
| How is the leftover paisa handled in equal splits? | Give the extra paise to the first participants | Deterministic rounding rule |
| Simplify debts? | On request, as a plan; users still choose when to pay | DebtSimplifier returns a list of transfers |
| Edit or delete expenses? | Discuss | Append-only history makes this easier |
| Concurrent edits? | Several members add expenses at once | Locking per group |
Functional requirements
- Create users and groups.
- Add an expense with a payer, an amount, participants and a split type; reject invalid splits.
- Show net balances: how much each member is owed (positive) or owes (negative).
- Show pairwise debts: who owes whom without simplification.
- Produce a simplified payment plan with few transfers.
- Record settle-ups and reject overpayments.
Non-functional requirements
- Exactness: balances in a group always sum to zero, to the paisa.
- Extensibility: a new split type (shares, adjustments) is a new class.
- Auditability: every change is a record you can list, not a silent overwrite of totals.
- Thread safety: concurrent additions must not lose updates.
Why paise in a long
0.1 + 0.2 in double is 0.30000000000000004. Over thousands of expenses such errors make balances fail to sum to zero, and users notice a stray paisa. Store whole paise in a long (Rs 33.34 is 3334) and decide rounding explicitly. BigDecimal is the other correct choice; it is slower and more verbose.
Core use cases
- Asha pays Rs 3,000 for dinner shared equally by four.
- Bharat pays Rs 1,200 for a cab with exact shares because people travelled different distances.
- Chitra pays Rs 2,000 for boat tickets split by percentage.
- Dev pays Rs 100 for snacks shared equally by three (not Chitra).
- Anyone views balances, pairwise debts and a simplified plan.
- Dev and Bharat settle up; balances return to zero.
Entities and relationships
+--------+ * * +-------------+ 1 * +-------------------+
| User |------------| Group |------------| Expense |
|--------| member of |-------------| history |-------------------|
| id | | members | | id, description |
| name | | net: User-> | | paidBy: User |
+--------+ | paise | | amount (paise) |
| addExpense()| | shares: User->paise|
| settleUp() | | splitType |
| pairwise() | +-------------------+
+-------------+
| |
uses | | balances go to
v v
+---------------+ +------------------+
| SplitStrategy | | DebtSimplifier |
+---------------+ +------------------+
^ ^ ^ ^ ^
Equal Exact Percent Greedy Optimal
| Class | Responsibility |
|---|---|
Money | Helpers to create and format paise amounts |
User | Identity |
SplitStrategy (+3) | Turn a total and participants into exact shares; validate |
Expense | Immutable record of one expense or settle-up |
Group | Members, append-only expense history, net balances, read/write lock |
Transfer | "A pays B amount": the unit of a payment plan |
DebtSimplifier, GreedySimplifier, OptimalSimplifier | Turn net balances into a payment plan |
Net balance: the one number per user
For each member, define:
net(user) = total the user paid - total of the user's shares
Positive means the group owes the user; negative means the user owes the group. Because every expense adds its amount to one person's "paid" and the same total across "shares", the sum of all net balances is always zero. That is the invariant every test should check.
Why store net balances and the history, but not a pairwise matrix
A tempting design keeps a matrix owes[a][b] and updates it on every expense. It works until you simplify debts. After simplification, Dev might pay Asha more than he "owed her" pairwise, because he is also paying on behalf of debts that were routed through others. The pairwise matrix then has no meaning, and settle-up checks against it wrongly refuse valid payments. A first version of this lesson's demo hit exactly this: a pairwise-validated settle-up rejected the simplified plan.
The design therefore keeps:
- Net balances, updated on each expense; enough to simplify and validate settle-ups.
- An append-only list of expenses, including settle-ups, from which pairwise debts are computed on demand for display.
Storing the history and deriving views from it is the core idea of event sourcing. It also makes editing and deleting expenses easy to reason about, since you can recompute.
Design decisions and patterns
Strategy for splits, with validation inside each strategy
interface SplitStrategy {
Map<User, Long> shares(long total, List<User> participants);
}
Each strategy both computes shares and validates its own inputs, because the rules differ:
- Equal: no extra input. Rounding: Rs 100 among three is 10,000 paise ÷ 3 = 3,333 remainder 1. The first participant gets 3,334, the others 3,333. Shares sum to 10,000 exactly.
- Exact: amounts per participant. They must cover exactly the participants, be non-negative and sum to the total, or the expense is rejected.
- Percent: integer percentages that must sum to 100. Each share is
total * pct / 100, rounded down, and any leftover paise go to the first participant.
Adding a new split type, such as "by shares" (Asha 2 shares, Bharat 1 share), is one new class. Group does not change. This is the Open/Closed principle in SOLID principles.
Interview tip
Mention the rounding rule before the interviewer asks. "Equal splits leave remainder paise; I give them to the first participants so the shares sum exactly to the total" shows you have thought about money, which many candidates skip.
Why not subclasses of Expense?
Some designs create EqualExpense, ExactExpense and PercentExpense. The split rule is only needed when the expense is created; afterwards every expense is just "payer, amount, shares". Keeping one Expense record with computed shares and a label is simpler, and the history stays uniform. Strategy is the right tool because the variation is in an algorithm, not in the stored data.
Settle-up as an expense
A settle-up "Dev pays Asha Rs 500" is recorded as an expense paid by Dev with Asha's share equal to Rs 500. The net effect: Dev's net rises by 500, Asha's falls by 500. No special-case code is needed in balances or history. Settle-ups are validated against net balances: the amount may not exceed min(-net(from), net(to)), so nobody pays more than they owe or receives more than they are owed.
Simplifier as a strategy
DebtSimplifier is an interface with a fast greedy implementation and an exact but exponential one. The app uses greedy by default; a small group could use the exact one.
Simplifying debts
The problem
Given net balances, find a list of transfers that brings everyone to zero. Any such list works; we want few transfers. Two facts make this tractable:
- Only net balances matter. Who paid for what originally is irrelevant to the final plan.
- With n people who have non-zero balances, n − 1 transfers are always enough: each transfer can bring at least one person to zero, and the last transfer brings the final two to zero together.
The greedy min-cash-flow algorithm
- Split users into creditors (positive net) and debtors (negative net).
- Take the largest creditor C and the largest debtor D.
- D pays C the smaller of
net(C)and-net(D). - At least one of them reaches zero. Put the other back with its reduced balance.
- Repeat until everyone is zero.
With two priority queues (heaps) ordered by absolute balance, each step costs O(log n), and there are at most n − 1 steps, so the total is O(n log n).
Worked example
First compute every share, then net balances, by hand.
E1 Dinner, Asha paid 3000, equal among 4
Asha 750, Bharat 750, Chitra 750, Dev 750
E2 Cab, Bharat paid 1200, exact
Asha 200, Bharat 400, Chitra 300, Dev 300 sum 1200
E3 Boat, Chitra paid 2000, percent 10/40/25/25
Asha 200, Bharat 800, Chitra 500, Dev 500 sum 2000
E4 Snacks, Dev paid 100, equal among Asha, Bharat, Dev
10000 paise / 3 = 3333 r 1
Asha 33.34, Bharat 33.33, Dev 33.33 sum 100.00
Now net = paid − shares:
| User | Paid | Shares | Net |
|---|---|---|---|
| Asha | 3,000.00 | 750 + 200 + 200 + 33.34 = 1,183.34 | +1,816.66 |
| Bharat | 1,200.00 | 750 + 400 + 800 + 33.33 = 1,983.33 | −783.33 |
| Chitra | 2,000.00 | 750 + 300 + 500 = 1,550.00 | +450.00 |
| Dev | 100.00 | 750 + 300 + 500 + 33.33 = 1,583.33 | −1,483.33 |
Check the invariant: 1,816.66 + 450.00 = 2,266.66, and 783.33 + 1,483.33 = 2,266.66. The sum is zero.
Without simplification, each participant owes each payer their share, netted per pair:
Asha-Bharat : Bharat owes 750, Asha owes 200 -> Bharat pays Asha 550.00
Asha-Chitra : Chitra owes 750, Asha owes 200 -> Chitra pays Asha 550.00
Asha-Dev : Dev owes 750, Asha owes 33.34 -> Dev pays Asha 716.66
Bharat-Chitra: Bharat owes 800, Chitra owes 300 -> Bharat pays Chitra 500.00
Bharat-Dev : Dev owes 300, Bharat owes 33.33 -> Dev pays Bharat 266.67
Chitra-Dev : Dev owes 500 -> Dev pays Chitra 500.00
Total: 6 transfers
Greedy simplification:
Creditors: Asha +1816.66, Chitra +450.00
Debtors: Dev -1483.33, Bharat -783.33
Step 1: largest creditor Asha, largest debtor Dev
Dev pays Asha min(1816.66, 1483.33) = 1483.33
Asha +333.33, Dev 0
Step 2: creditors Chitra +450.00, Asha +333.33 -> Chitra
debtor Bharat -783.33
Bharat pays Chitra min(450.00, 783.33) = 450.00
Chitra 0, Bharat -333.33
Step 3: Bharat pays Asha 333.33. Everyone is 0.
Total: 3 transfers (= n - 1 for n = 4)
Verify: Asha receives 1,483.33 + 333.33 = 1,816.66, her net. Chitra receives 450.00, her net. Dev pays 1,483.33 and Bharat pays 450.00 + 333.33 = 783.33, their debts. Six payments became three.
When greedy is not optimal
Greedy always uses at most n − 1 transfers, but sometimes fewer are possible. The minimum equals n minus the largest number of groups you can split people into such that each group's balances sum to zero, because a zero-sum group of k people needs exactly k − 1 transfers among themselves. Finding that partition is NP-hard in general (it is closely related to the subset-sum problem), so production apps use heuristics.
A small counterexample, in rupees: A −600, B −500, C +200, D +400, E +500.
Greedy:
largest debtor A (-600), largest creditor E (+500): A pays E 500
A -100. Next: debtor B (-500), creditor D (+400): B pays D 400
B -100. Remaining: C +200, A -100, B -100
A pays C 100, B pays C 100
-> 4 transfers
Optimal: notice {B, E} sums to zero, and {A, C, D} sums to zero
B pays E 500
A pays D 400, A pays C 200
-> 3 transfers
Greedy paired A with E because they were the biggest, which broke the natural pair B and E. The OptimalSimplifier in the code finds the best partition using dynamic programming over subsets: O(3ⁿ) time, fine up to about 15 to 20 people, impossible for large groups. A brute-force search over small five-person balance sets turns up cases like this quickly, and the program confirms both results.
Common mistake
Claiming greedy min-cash-flow gives the minimum number of transactions. It guarantees at most n − 1 and is usually very good, but it is not always optimal. Say so, give the zero-sum-subset idea, and mention it is NP-hard in general. Interviewers often ask exactly this.
Should simplification change who owes whom?
Simplification may tell Dev to pay Asha even though, pairwise, Dev's biggest debt was to Chitra. Some users dislike paying someone they never shared an expense with. Real apps make simplification an opt-in group setting. The design handles both: pairwise debts are always computable from history, and the plan is only a suggestion until settle-ups are recorded.
Complete Java implementation
Save as SplitwiseDemo.java, compile with javac SplitwiseDemo.java, and run java SplitwiseDemo. Java 17 or later.
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.ReentrantReadWriteLock;
// ---------- Money ----------
/** Amounts are whole paise in a long: no floating point anywhere. */
final class Money {
private Money() {}
static long rupees(long r) { return r * 100; }
static long parse(String s) { // "33.34" -> 3334
String[] p = s.split("\\.");
long paise = p.length > 1 ? Long.parseLong((p[1] + "0").substring(0, 2)) : 0;
return Long.parseLong(p[0]) * 100 + paise;
}
static String fmt(long paise) {
String sign = paise < 0 ? "-" : "";
long a = Math.abs(paise);
return sign + "Rs " + (a / 100) + "." + String.format("%02d", a % 100);
}
}
record User(String id, String name) {}
// ---------- Split strategies ----------
interface SplitStrategy {
/** Shares per participant; must add up to exactly the total. Throws on invalid input. */
Map<User, Long> shares(long total, List<User> participants);
String name();
}
final class EqualSplit implements SplitStrategy {
public String name() { return "equal"; }
public Map<User, Long> shares(long total, List<User> ps) {
long base = total / ps.size(), remainder = total % ps.size();
Map<User, Long> out = new LinkedHashMap<>();
for (int i = 0; i < ps.size(); i++) out.put(ps.get(i), base + (i < remainder ? 1 : 0)); // spread leftover paise
return out;
}
}
final class ExactSplit implements SplitStrategy {
private final Map<User, Long> amounts;
ExactSplit(Map<User, Long> amounts) { this.amounts = Map.copyOf(amounts); }
public String name() { return "exact"; }
public Map<User, Long> shares(long total, List<User> ps) {
if (!amounts.keySet().equals(new HashSet<>(ps))) throw new IllegalArgumentException("exact amounts must cover exactly the participants");
long sum = 0;
for (long a : amounts.values()) {
if (a < 0) throw new IllegalArgumentException("negative share");
sum += a;
}
if (sum != total) throw new IllegalArgumentException("exact shares add to " + Money.fmt(sum) + ", expected " + Money.fmt(total));
Map<User, Long> out = new LinkedHashMap<>();
for (User u : ps) out.put(u, amounts.get(u));
return out;
}
}
final class PercentSplit implements SplitStrategy {
private final Map<User, Integer> percent;
PercentSplit(Map<User, Integer> percent) { this.percent = Map.copyOf(percent); }
public String name() { return "percent"; }
public Map<User, Long> shares(long total, List<User> ps) {
if (!percent.keySet().equals(new HashSet<>(ps))) throw new IllegalArgumentException("percentages must cover exactly the participants");
int sum = percent.values().stream().mapToInt(Integer::intValue).sum();
if (sum != 100) throw new IllegalArgumentException("percentages add to " + sum + ", expected 100");
Map<User, Long> out = new LinkedHashMap<>();
long given = 0;
for (User u : ps) {
long share = total * percent.get(u) / 100; // floor
out.put(u, share);
given += share;
}
out.merge(ps.get(0), total - given, Long::sum); // rounding leftover goes to the first participant
return out;
}
}
// ---------- Expenses and the group ledger ----------
record Expense(String id, String description, User paidBy, long amount, Map<User, Long> shares, String splitType) {}
record Transfer(User from, User to, long amount) {
public String toString() { return from.name() + " pays " + to.name() + " " + Money.fmt(amount); }
}
final class Group {
private final String name;
private final Set<User> members = new LinkedHashSet<>();
private final List<Expense> expenses = new ArrayList<>(); // append-only history
private final Map<User, Long> net = new LinkedHashMap<>(); // + means is owed, - means owes
private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
private long seq = 0;
Group(String name, List<User> members) {
this.name = name;
for (User u : members) { this.members.add(u); net.put(u, 0L); }
}
Expense addExpense(String description, User paidBy, long amount, List<User> participants, SplitStrategy split) {
if (amount <= 0) throw new IllegalArgumentException("amount must be positive");
if (participants.isEmpty()) throw new IllegalArgumentException("no participants");
if (new HashSet<>(participants).size() != participants.size()) throw new IllegalArgumentException("duplicate participant");
Map<User, Long> shares = split.shares(amount, participants); // validates; no lock needed yet
lock.writeLock().lock();
try {
requireMember(paidBy);
participants.forEach(this::requireMember);
Expense e = new Expense("E" + (++seq), description, paidBy, amount, Map.copyOf(shares), split.name());
expenses.add(e);
net.merge(paidBy, amount, Long::sum);
for (Map.Entry<User, Long> s : shares.entrySet()) net.merge(s.getKey(), -s.getValue(), Long::sum);
return e;
} finally { lock.writeLock().unlock(); }
}
/**
* A settle-up is recorded like an expense: `from` pays, and the whole amount is `to`'s share.
* It is checked against net balances, so it works whether or not debts were simplified.
*/
void settleUp(User from, User to, long amount) {
if (amount <= 0 || from.equals(to)) throw new IllegalArgumentException("invalid settle-up");
lock.writeLock().lock();
try {
requireMember(from); requireMember(to);
long canPay = Math.min(-net.get(from), net.get(to));
if (amount > canPay) throw new IllegalArgumentException("at most " + Money.fmt(Math.max(0, canPay)) + " is due");
expenses.add(new Expense("S" + (++seq), "Settle-up", from, amount, Map.of(to, amount), "settlement"));
net.merge(from, amount, Long::sum);
net.merge(to, -amount, Long::sum);
} finally { lock.writeLock().unlock(); }
}
private void requireMember(User u) {
if (!members.contains(u)) throw new IllegalArgumentException(u.name() + " is not in " + name);
}
Map<User, Long> netBalances() {
lock.readLock().lock();
try { return new LinkedHashMap<>(net); } finally { lock.readLock().unlock(); }
}
/** Who owes whom without simplification: every share is owed to the payer, netted per pair. */
List<Transfer> pairwiseDebts() {
lock.readLock().lock();
try {
Map<User, Map<User, Long>> owes = new HashMap<>(); // owes[a][b]: a owes b
for (Expense e : expenses)
for (Map.Entry<User, Long> s : e.shares().entrySet())
if (!s.getKey().equals(e.paidBy()))
owes.computeIfAbsent(s.getKey(), k -> new HashMap<>()).merge(e.paidBy(), s.getValue(), Long::sum);
List<Transfer> out = new ArrayList<>();
List<User> list = new ArrayList<>(members);
for (int i = 0; i < list.size(); i++)
for (int j = i + 1; j < list.size(); j++) {
User a = list.get(i), b = list.get(j);
long ab = owes.getOrDefault(a, Map.of()).getOrDefault(b, 0L);
long ba = owes.getOrDefault(b, Map.of()).getOrDefault(a, 0L);
if (ab > ba) out.add(new Transfer(a, b, ab - ba));
if (ba > ab) out.add(new Transfer(b, a, ba - ab));
}
return out;
} finally { lock.readLock().unlock(); }
}
List<Expense> expenses() {
lock.readLock().lock();
try { return List.copyOf(expenses); } finally { lock.readLock().unlock(); }
}
}
// ---------- Simplifying debts ----------
interface DebtSimplifier { List<Transfer> simplify(Map<User, Long> net); }
/** Greedy min cash flow: repeatedly let the biggest debtor pay the biggest creditor. At most n - 1 transfers. */
final class GreedySimplifier implements DebtSimplifier {
public List<Transfer> simplify(Map<User, Long> net) {
Comparator<Map.Entry<User, Long>> bigFirst =
Comparator.<Map.Entry<User, Long>>comparingLong(e -> -Math.abs(e.getValue()))
.thenComparing(e -> e.getKey().id());
PriorityQueue<Map.Entry<User, Long>> creditors = new PriorityQueue<>(bigFirst);
PriorityQueue<Map.Entry<User, Long>> debtors = new PriorityQueue<>(bigFirst);
for (Map.Entry<User, Long> e : net.entrySet()) {
if (e.getValue() > 0) creditors.add(new AbstractMap.SimpleEntry<>(e));
if (e.getValue() < 0) debtors.add(new AbstractMap.SimpleEntry<>(e));
}
List<Transfer> out = new ArrayList<>();
while (!creditors.isEmpty() && !debtors.isEmpty()) {
Map.Entry<User, Long> c = creditors.poll(), d = debtors.poll();
long amount = Math.min(c.getValue(), -d.getValue());
out.add(new Transfer(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 out;
}
}
/**
* Exact minimum number of transfers. Equals n minus the largest number of disjoint zero-sum groups;
* found with a DP over subsets, so it is exponential and only for small groups (n up to about 20).
*/
final class OptimalSimplifier implements DebtSimplifier {
public List<Transfer> simplify(Map<User, Long> net) {
List<User> users = new ArrayList<>();
List<Long> bal = new ArrayList<>();
net.forEach((u, v) -> { if (v != 0) { users.add(u); bal.add(v); } });
int n = users.size(), full = (1 << n) - 1;
long[] sum = new long[1 << n];
for (int m = 1; m <= full; m++) {
int low = Integer.numberOfTrailingZeros(m);
sum[m] = sum[m & (m - 1)] + bal.get(low);
}
int[] groups = new int[1 << n]; // max zero-sum groups that a mask can be split into
for (int m = 1; m <= full; m++) {
groups[m] = Integer.MIN_VALUE;
if (sum[m] != 0) continue;
int low = m & -m;
for (int sub = m; sub > 0; sub = (sub - 1) & m)
if ((sub & low) != 0 && sum[sub] == 0 && groups[m ^ sub] >= 0)
groups[m] = Math.max(groups[m], groups[m ^ sub] + 1);
}
// Rebuild the groups and settle each one greedily (a zero-sum group of k people needs k - 1 transfers).
List<Transfer> out = new ArrayList<>();
int m = full;
while (m != 0) {
int low = m & -m, chosen = -1;
for (int sub = m; sub > 0; sub = (sub - 1) & m)
if ((sub & low) != 0 && sum[sub] == 0 && groups[m ^ sub] >= 0 && groups[m] == groups[m ^ sub] + 1) { chosen = sub; break; }
Map<User, Long> part = new LinkedHashMap<>();
for (int i = 0; i < n; i++) if ((chosen >> i & 1) == 1) part.put(users.get(i), bal.get(i));
out.addAll(new GreedySimplifier().simplify(part));
m ^= chosen;
}
return out;
}
}
public class SplitwiseDemo {
static void printBalances(Group g) {
g.netBalances().forEach((u, v) -> System.out.printf(" %-7s %s%n", u.name(), Money.fmt(v)));
}
public static void main(String[] args) throws Exception {
User asha = new User("u1", "Asha"), bharat = new User("u2", "Bharat"),
chitra = new User("u3", "Chitra"), dev = new User("u4", "Dev");
Group goa = new Group("Goa trip", List.of(asha, bharat, chitra, dev));
List<User> all = List.of(asha, bharat, chitra, dev);
System.out.println("== 1. Expenses ==");
goa.addExpense("Dinner", asha, Money.rupees(3000), all, new EqualSplit());
goa.addExpense("Cab", bharat, Money.rupees(1200), all, new ExactSplit(Map.of(
asha, Money.rupees(200), bharat, Money.rupees(400), chitra, Money.rupees(300), dev, Money.rupees(300))));
goa.addExpense("Boat tickets", chitra, Money.rupees(2000), all, new PercentSplit(Map.of(
asha, 10, bharat, 40, chitra, 25, dev, 25)));
goa.addExpense("Snacks", dev, Money.rupees(100), List.of(asha, bharat, dev), new EqualSplit());
for (Expense e : goa.expenses()) {
StringBuilder sb = new StringBuilder();
for (User u : all) if (e.shares().containsKey(u)) sb.append(u.name()).append('=').append(Money.fmt(e.shares().get(u))).append(' ');
System.out.println(e.id() + " " + e.description() + " paid by " + e.paidBy().name() + " "
+ Money.fmt(e.amount()) + " (" + e.splitType() + "): " + sb.toString().trim());
}
System.out.println("== 2. Validation ==");
try { goa.addExpense("Bad", asha, Money.rupees(500), List.of(asha, bharat),
new ExactSplit(Map.of(asha, Money.rupees(200), bharat, Money.rupees(200)))); }
catch (IllegalArgumentException e) { System.out.println("rejected: " + e.getMessage()); }
try { goa.addExpense("Bad", asha, Money.rupees(500), List.of(asha, bharat),
new PercentSplit(Map.of(asha, 60, bharat, 50))); }
catch (IllegalArgumentException e) { System.out.println("rejected: " + e.getMessage()); }
System.out.println("== 3. Net balances (+ is owed, - owes) ==");
printBalances(goa);
long total = goa.netBalances().values().stream().mapToLong(Long::longValue).sum();
System.out.println(" sum of balances = " + total);
System.out.println("== 4. Pairwise debts before simplifying ==");
List<Transfer> pairwise = goa.pairwiseDebts();
pairwise.forEach(t -> System.out.println(" " + t));
System.out.println(" transfers: " + pairwise.size());
System.out.println("== 5. Simplified (greedy) ==");
List<Transfer> plan = new GreedySimplifier().simplify(goa.netBalances());
plan.forEach(t -> System.out.println(" " + t));
System.out.println(" transfers: " + plan.size());
System.out.println("== 6. Settle up following the plan ==");
try { goa.settleUp(bharat, chitra, Money.rupees(800)); }
catch (IllegalArgumentException ex) { System.out.println(" refused Bharat pays Chitra Rs 800.00: " + ex.getMessage()); }
for (Transfer t : plan) {
goa.settleUp(t.from(), t.to(), t.amount());
System.out.println(" recorded: " + t);
}
printBalances(goa);
System.out.println("== 7. Where greedy is not optimal ==");
User a = new User("a", "A"), b = new User("b", "B"), c = new User("c", "C"), d = new User("d", "D"), e = new User("e", "E");
Map<User, Long> tricky = new LinkedHashMap<>();
tricky.put(a, -Money.rupees(600)); tricky.put(b, -Money.rupees(500));
tricky.put(c, Money.rupees(200)); tricky.put(d, Money.rupees(400)); tricky.put(e, Money.rupees(500));
List<Transfer> g = new GreedySimplifier().simplify(tricky), o = new OptimalSimplifier().simplify(tricky);
System.out.println(" greedy (" + g.size() + "): " + g);
System.out.println(" optimal (" + o.size() + "): " + o);
System.out.println("== 8. 8 threads add 1,000 expenses each ==");
Group office = new Group("Office lunch", all);
ExecutorService pool = Executors.newFixedThreadPool(8);
List<Future<?>> fs = new ArrayList<>();
for (int t = 0; t < 8; t++) {
final User payer = all.get(t % 3); // Asha, Bharat, Chitra, Asha, ...; Dev never pays
fs.add(pool.submit(() -> {
for (int i = 0; i < 1000; i++) office.addExpense("Tea", payer, 1000, all, new EqualSplit()); // Rs 10.00
}));
}
for (Future<?> f : fs) f.get();
pool.shutdown();
System.out.println(" expenses recorded: " + office.expenses().size());
System.out.println(" sum of balances = " + office.netBalances().values().stream().mapToLong(Long::longValue).sum());
printBalances(office);
}
}
Real output
This is the actual output from Temurin JDK 21:
== 1. Expenses ==
E1 Dinner paid by Asha Rs 3000.00 (equal): Asha=Rs 750.00 Bharat=Rs 750.00 Chitra=Rs 750.00 Dev=Rs 750.00
E2 Cab paid by Bharat Rs 1200.00 (exact): Asha=Rs 200.00 Bharat=Rs 400.00 Chitra=Rs 300.00 Dev=Rs 300.00
E3 Boat tickets paid by Chitra Rs 2000.00 (percent): Asha=Rs 200.00 Bharat=Rs 800.00 Chitra=Rs 500.00 Dev=Rs 500.00
E4 Snacks paid by Dev Rs 100.00 (equal): Asha=Rs 33.34 Bharat=Rs 33.33 Dev=Rs 33.33
== 2. Validation ==
rejected: exact shares add to Rs 400.00, expected Rs 500.00
rejected: percentages add to 110, expected 100
== 3. Net balances (+ is owed, - owes) ==
Asha Rs 1816.66
Bharat -Rs 783.33
Chitra Rs 450.00
Dev -Rs 1483.33
sum of balances = 0
== 4. Pairwise debts before simplifying ==
Bharat pays Asha Rs 550.00
Chitra pays Asha Rs 550.00
Dev pays Asha Rs 716.66
Bharat pays Chitra Rs 500.00
Dev pays Bharat Rs 266.67
Dev pays Chitra Rs 500.00
transfers: 6
== 5. Simplified (greedy) ==
Dev pays Asha Rs 1483.33
Bharat pays Chitra Rs 450.00
Bharat pays Asha Rs 333.33
transfers: 3
== 6. Settle up following the plan ==
refused Bharat pays Chitra Rs 800.00: at most Rs 450.00 is due
recorded: Dev pays Asha Rs 1483.33
recorded: Bharat pays Chitra Rs 450.00
recorded: Bharat pays Asha Rs 333.33
Asha Rs 0.00
Bharat Rs 0.00
Chitra Rs 0.00
Dev Rs 0.00
== 7. Where greedy is not optimal ==
greedy (4): [A pays E Rs 500.00, B pays D Rs 400.00, A pays C Rs 100.00, B pays C Rs 100.00]
optimal (3): [A pays D Rs 400.00, A pays C Rs 200.00, B pays E Rs 500.00]
== 8. 8 threads add 1,000 expenses each ==
expenses recorded: 8000
sum of balances = 0
Asha Rs 10000.00
Bharat Rs 10000.00
Chitra Rs 0.00
Dev -Rs 20000.00
Compare with the hand calculations:
- Section 1 shows every share exactly as computed, including the 33.34 / 33.33 / 33.33 snack split.
- Section 2: the exact split that adds to 400 for a 500 expense, and percentages totalling 110, are both rejected before any state changes.
- Section 3: net balances match the table, and they sum to 0 paise.
- Section 4: the six pairwise transfers match the hand list.
- Section 5: greedy gives the same three transfers as the worked steps.
- Section 6: an attempt by Bharat to pay Chitra Rs 800 is refused because only Rs 450 is due under net balances; the three planned payments then bring everyone to exactly zero.
- Section 7: greedy uses four transfers on the counterexample and the exact simplifier three, as derived.
- Section 8: eight threads each add 1,000 "Rs 10 tea, equal among four" expenses. The payers rotate Asha, Bharat, Chitra, so Asha and Bharat each pay for 3,000 teas and Chitra for 2,000. Each tea costs each person Rs 2.50, so everyone's share total is 8,000 × 2.50 = Rs 20,000. Asha: 30,000 − 20,000 = +10,000. Bharat: +10,000. Chitra: 20,000 − 20,000 = 0. Dev: 0 − 20,000 = −20,000. No update was lost.
Concurrency considerations
What can go wrong
net.merge(user, delta, Long::sum) on a plain HashMap is a read-modify-write. Two threads adding expenses at the same time can both read Asha's balance as 1,000, both add their delta, and one write overwrites the other: a lost update. Worse, a single expense touches several users' balances; a reader in the middle could see some updated and some not, and the sum would not be zero.
The approach used: one read/write lock per group
Each Group has a ReentrantReadWriteLock:
addExpenseandsettleUptake the write lock, so one expense's changes to all balances and the history happen as a unit.netBalances,pairwiseDebtsandexpensestake the read lock and return copies. Many readers can proceed together; they never see a half-applied expense.
Split computation and validation happen before taking the lock, since they only read the inputs. That keeps the critical section tiny.
Why the group is the right granularity
| Granularity | Problem |
|---|---|
| One global lock | All groups in the app wait for each other |
| Per user | One expense touches several users; you must lock several in a fixed order and readers can see partial updates |
| Per group | Expenses only touch one group; independent groups run in parallel; simple |
A user who belongs to many groups has a separate balance in each, so per-group locking does not need to coordinate across groups. A cross-group "total I owe" view simply reads each group under its read lock; it may be a moment out of date, which is fine for display.
Across servers
In a database, put the expense insert and the balance updates in one transaction. Better still, store only the expense and share rows, and compute balances with SUM queries or a maintained summary table updated in the same transaction. Use optimistic version numbers on the group if concurrent edits to the same expense are possible. See Transactions and ACID.
Extensions interviewers ask, and how the design absorbs them
1. Split by shares (2 : 1 : 1). New ShareSplit strategy, computing total * share / totalShares with the same leftover rule.
2. Multiple payers (Asha paid 2,000 and Bharat 1,000 of a 3,000 bill). Replace paidBy with a Map<User, Long> paid that must sum to the amount. Net update becomes "add each payer's part". The simplifier is unchanged because it only sees nets.
3. Edit or delete an expense. Append a reversing record (the negative of the old shares) and a new record, or mark the old one deleted and recompute. The append-only history makes undo straightforward and auditable.
4. Non-group expenses between two friends. Model them as an implicit two-person group, so all code paths stay the same.
5. Multiple currencies. Store each expense in its original currency with the exchange rate at that time, keep balances per currency, and convert only for display or settle-up at a chosen rate.
6. Notifications ("Asha added Dinner, you owe Rs 750"). Observers on the expense-added event.
7. Recurring expenses (monthly rent). A scheduler creates the expense each period from a template.
8. Itemised bills. Each item has its own participants; the expense's shares are the sum over items. A new strategy that composes per-item equal splits.
9. Large groups simplification. Use greedy with heaps; offer the exact algorithm only for small groups or as a background optimisation.
Common mistakes
doublefor money, leading to balances that do not sum to zero.- Not handling remainder paise, so an equal split of Rs 100 among three becomes 33.33 × 3 = 99.99.
- Validation in the wrong place, for example in
Groupwith anifper split type, which defeats the Strategy pattern. - Keeping only a pairwise matrix and then simplifying, which makes settle-up validation inconsistent.
- Claiming greedy is optimal.
- Forgetting that the payer may not be a participant.
- Mutating totals without history, making edits, audits and bug investigations impossible.
- Locking per user without an ordering, risking deadlocks when one expense touches several users.
Interview questions
Q1. How do you represent money?
As whole paise in a long, or BigDecimal, never double. Rounding is explicit: equal splits give leftover paise to the first participants, and percentage splits round down and assign the leftover, so shares always sum to the exact total.
Q2. Why use the Strategy pattern for splits?
The split types differ only in how they compute and validate shares. A strategy per type keeps that logic in one place, and adding a new type such as split by shares needs no change to Group or Expense. It also makes each rule easy to unit-test.
Q3. What is a net balance and why does it matter?
It is the amount a user paid minus the total of their shares. Positive means they are owed, negative means they owe. Net balances always sum to zero within a group, and they are all the simplification algorithm needs.
Q4. Explain the debt simplification algorithm.
Separate creditors and debtors. Repeatedly let the largest debtor pay the largest creditor the smaller of the two amounts; one of them reaches zero each time. With heaps this is O(n log n) and produces at most n − 1 transfers.
Q5. Is greedy simplification optimal?
Not always. The true minimum is n minus the maximum number of disjoint zero-sum subgroups, and finding that is NP-hard in general. For example, balances −600, −500, +200, +400, +500 take four greedy transfers but three optimal ones, because {-500, +500} is a zero-sum pair.
Q6. How do you validate an exact split?
The amounts must cover exactly the participants, be non-negative and sum to the expense total. If any check fails, the expense is rejected before any balance changes.
Q7. How do you record a settle-up?
As an expense paid by the debtor with the whole amount as the creditor's share. It moves both nets toward zero and appears in history. It is validated so that the amount does not exceed what the payer owes or what the receiver is owed.
Q8. How do you keep balances correct under concurrent updates?
Each group has a read/write lock. Adding an expense takes the write lock and updates history and all affected balances together; reads take the read lock and return copies. Validation and share computation happen before locking to keep the critical section small.
Q9. How would you support editing an expense?
Keep history append-only. An edit adds a reversing entry and a new entry, or marks the old one superseded, and balances are adjusted by the difference. You can always rebuild balances from history to verify them.
Q10. How would you support multiple payers?
Replace the single payer with a map of payer to amount paid that must sum to the total. Net balances then add each payer's part. Nothing else changes, because simplification only uses nets.
Q11. What is the time complexity of computing balances and the plan?
Adding an expense with k participants is O(k). The greedy plan is O(n log n) for n users with non-zero balances. The exact plan is exponential, O(3ⁿ) with subset dynamic programming, so only for small groups.
Q12. Why compute pairwise debts from history instead of storing them?
Once simplification is used, a stored pairwise matrix no longer describes the actual obligations, so checks against it become wrong. Deriving pairwise views from the history keeps one source of truth, the history and the nets, and any view can be recomputed.
Key takeaways
- Model splits as strategies that both compute and validate shares; keep one
Expensetype. - Use integer paise and an explicit remainder rule so shares always sum to the total.
- Net balance per user is the key quantity, and all nets sum to zero.
- Greedy min-cash-flow gives at most n − 1 transfers in O(n log n); it is not always optimal, and the exact problem is NP-hard.
- Record settle-ups as expenses and validate them against net balances.
- Keep an append-only history and derive views; it makes edits, audits and simplification consistent.
- Lock per group with a read/write lock; validate outside the lock.
Next lesson
Continue with Design an LRU cache and a rate limiter.