Splitwise / Expense Sharing System

Core classes

class User { String id; String name; }
class Expense { User paidBy; double amount; List<Split> splits; }
class Split { User user; double amountOwed; }
class Ledger { Map<Pair<User,User>, Double> balances; } // balances.get(A,B) = how much A owes B, net

Split strategies via Strategy pattern

interface SplitStrategy { List<Split> calculateSplits(double amount, List<User> participants, Map<User, Double> inputs); }

class EqualSplitStrategy implements SplitStrategy {
    public List<Split> calculateSplits(double amount, List<User> participants, Map<User, Double> inputs) {
        double share = amount / participants.size();
        return participants.stream().map(u -> new Split(u, share)).toList();
    }
}

class PercentageSplitStrategy implements SplitStrategy {
    public List<Split> calculateSplits(double amount, List<User> participants, Map<User, Double> percentages) {
        return participants.stream()
            .map(u -> new Split(u, amount * percentages.get(u) / 100.0))
            .toList(); // caller must ensure percentages sum to 100 — worth validating explicitly
    }
}

class ExactAmountSplitStrategy implements SplitStrategy {
    public List<Split> calculateSplits(double amount, List<User> participants, Map<User, Double> exactAmounts) {
        // caller-supplied amounts must sum to `amount` — validate, don't silently accept a mismatch
        double sum = exactAmounts.values().stream().mapToDouble(Double::doubleValue).sum();
        if (Math.abs(sum - amount) > 0.01) throw new IllegalArgumentException("Split amounts don't sum to total");
        return participants.stream().map(u -> new Split(u, exactAmounts.get(u))).toList();
    }
}

Same Strategy shape as every other pluggable-algorithm design in this course — Expense creation takes a SplitStrategy, never branches on split type internally, and a new split type (e.g. "by shares/weights") means one new class.

Balance simplification: minimizing settling transactions

If A owes B $10 and B owes C $10, the ledger technically has two debts — but they simplify to "A owes C $10" (B nets to zero and drops out entirely). Naively settling every individual expense's debts separately produces far more transactions than necessary; a good design simplifies the net balances before suggesting who should pay whom.

class BalanceSimplifier {
    List<Settlement> simplify(Map<User, Double> netBalances) { // positive = owed money, negative = owes money
        PriorityQueue<Map.Entry<User, Double>> creditors = new PriorityQueue<>((a, b) -> Double.compare(b.getValue(), a.getValue()));
        PriorityQueue<Map.Entry<User, Double>> debtors = new PriorityQueue<>((a, b) -> Double.compare(a.getValue(), b.getValue()));
        netBalances.forEach((user, balance) -> {
            if (balance > 0.01) creditors.offer(Map.entry(user, balance));
            else if (balance < -0.01) debtors.offer(Map.entry(user, balance));
        });

        List<Settlement> settlements = new ArrayList<>();
        while (!creditors.isEmpty() && !debtors.isEmpty()) {
            var creditor = creditors.poll();
            var debtor = debtors.poll();
            double amount = Math.min(creditor.getValue(), -debtor.getValue());
            settlements.add(new Settlement(debtor.getKey(), creditor.getKey(), amount));
            double remainingCredit = creditor.getValue() - amount;
            double remainingDebt = debtor.getValue() + amount;
            if (remainingCredit > 0.01) creditors.offer(Map.entry(creditor.getKey(), remainingCredit));
            if (remainingDebt < -0.01) debtors.offer(Map.entry(debtor.getKey(), remainingDebt));
        }
        return settlements;
    }
}

The greedy approach — always match the largest creditor against the largest debtor — is a well-known heuristic for this problem (a variant of the general debt-simplification / minimum-cashflow problem): it doesn't always find the mathematically absolute minimum number of transactions in every case, but it performs well in practice and is far simpler to implement correctly than an optimal solution, which is worth naming explicitly as a deliberate simplicity-vs-optimality tradeoff rather than presenting it as provably optimal.

Follow-up questions this topic invites — and their answers

Q: Why use two separate priority queues (creditors, debtors) instead of one sorted structure? A: Creditors and debtors need to be matched against each other specifically (largest-to-largest), not against members of their own group — keeping them separate makes each poll() operation directly meaningful ("the biggest remaining creditor" and "the biggest remaining debtor") without needing to filter a mixed structure by sign on every iteration.

Q: How would you handle floating-point precision issues in balance tracking? A: Represent money as integer cents (or a fixed-point/BigDecimal type) rather than double throughout — the 0.01 epsilon comparisons shown above are a common workaround for double's imprecision, but the more robust fix is avoiding floating-point currency arithmetic entirely, which is also standard practice in real payment systems (see Payment — Core Flow).

Q: Does the greedy simplification algorithm always produce the mathematically minimum number of transactions? A: No — finding the true minimum is a harder combinatorial problem in the general case; the greedy largest-vs-largest matching is a good practical heuristic that performs well, and naming this distinction (heuristic vs provably optimal) explicitly is itself a strong interview signal, since claiming optimality for a greedy approach without justification is a common overreach.

Q: How would you extend this design to support group-specific balances (e.g., a 'trip' with its own separate ledger from other shared expenses)? A: Scope the Ledger (and the balance simplification) to a Group entity rather than tracking one global balance per user pair — each Group would maintain its own independent set of net balances, letting a 'Japan trip' settle separately from ongoing roommate expenses between the same two users.