PHASE 4Intermediate ~7 min· topic 6 of 18Level 2

Problem 4.6 — Splitwise

In one line

Expense splitting with strategies and settlement math — exactly one map of balances and a strategy per split rule.

0/18 · 0%

Think of it like this

Splitting a dinner bill among friends. Instead of everyone paying everyone back individually, the app works out the smallest number of payments needed so everyone ends up even.

Key ideas

01
Entities: User, Expense, Split(s), Group; Ledger = Map<UserId, netBalance>.
02
Split strategies: EQUAL, EXACT, PERCENT — the Strategy pattern in its purest form (see Phase 2 code).
03
Core invariant: sum of splits = expense amount; validate per strategy.
04
Settlement minimization: repeatedly take maxDebtor and maxCreditor, transfer min — produces ≤ n−1 transactions.
05
Rounding drift (percent splits summing to 99.99) handled by assigning the remainder to the last member.
06
Groups: expenses scoped per group, balances computed per group; simplify endpoint returns the optimized transfers.
07
Extensibility: split type, currency (FX conversion port), group privacy — each a seam.

Java / Spring map

→
ExpenseService.appendSplit(Expense, SplitStrategy); SettlementCalculator.minimize(Ledger) — pure functions, easy tests.

Code & diagrams

SettlementCalculator.javajava

Greedy balance-settlement producing minimal transfers.

public class SettlementCalculator {
  // netBalances: user → total owed if negative, total due if positive
  public static List<Transfer> minimize(Map<String, Double> net) {
    // heap-based: O(n log n), result ≤ n-1 transfers
    PriorityQueue<Map.Entry<String, Double>> debtors =
        new PriorityQueue<>((a, b) -> Double.compare(a.getValue(), b.getValue()));
    PriorityQueue<Map.Entry<String, Double>> creditors =
        new PriorityQueue<>((a, b) -> Double.compare(b.getValue(), a.getValue()));
    for (var e : net.entrySet()) {
      if (e.getValue() < -1e-9) debtors.add(e);       // owes money
      else if (e.getValue() > 1e-9) creditors.add(e); // to be paid
    }
    List<Transfer> out = new ArrayList<>();
    while (!debtors.isEmpty() && !creditors.isEmpty()) {
      Map.Entry<String, Double> d = debtors.poll();
      Map.Entry<String, Double> c = creditors.poll();
      double amount = Math.min(-d.getValue(), c.getValue());
      out.add(new Transfer(d.getKey(), c.getKey(), Math.round(amount * 100) / 100.0));
      // push back the remainder
      d.setValue(d.getValue() + amount);
      c.setValue(c.getValue() - amount);
      if (d.getValue() < -1e-9) debtors.add(d);
      if (c.getValue() > 1e-9) creditors.add(c);
    }
    return out;
  }
  public record Transfer(String from, String to, double amount) {}
}

// Demo: Map.of("a", -200.0, "b", 50.0, "c", 150.0)
//   → a→b 50, a→c 150  (2 transfers, minimal)

Explain without notes

Prove the greedy minimizer produces at most n−1 transfers.

Practice

Add the RoundingRule strategy that gives the leftover paise to the last split member.

Trade-offs

↔
Minimized transfers confuse accounting audit; some apps choose traceability over minimality.

Completion checklist

I can implement split strategies + settle in a map and explain the invariant.

Back to phase

Command Palette