Design Splitwise

Learning Objectives#

• Model an expense as the record of who paid and who owes, with the splitting rule as a strategy, not a branch inside the expense class.
• Compute the net balance per user from a group's expenses, and learn why netting is the step every naive design forgets.
• See the debt-simplification problem for what it is, a graph problem, and know when to offer the greedy solution and what it guarantees.

Introduction#

Splitwise is the case study where the domain rules are social and the arithmetic is subtle. Friends go out, someone pays, the rest chip in, and the app's job is to decide who owes whom how much. The surface looks simple enough: record an expense, split it, show balances. The depth is in what "how much" means. A group of four people with ten expenses can owe each other in a tangle that takes twenty manual transactions to unwind, or in three, and the difference is not in the expenses, it is in the algorithm that collapses the tangle. Interviewers ask this because it is a rare case study with a real graph-theoretic question hiding in a friendly domain, and because it tests whether you can model money flowing between people without losing a cent to rounding or bias.

Requirements Gathering#

Functional requirements:

• A group has members; an expense records the payer, the total amount, and how it splits among the participants.
• Splits can be equal, exact amounts, or percentages.
• The system computes, for each member, their net balance with the group: what they are owed or owe overall.
• The system can produce the minimal or near-minimal set of settlement transactions that clears everyone's balance.

Non-functional requirements:

• Money math must be exact for the currency's smallest unit; no floating point drift, and rounding must be decided, not accidental.
• Balance computation over a group's expenses must be fast enough to run on every group view.

Assumptions to state out loud: no partial settlements outside the simplified output, no recurring expenses, no group debt to outside parties, no interest or lending, and the currency is single (no multi-currency conversion). Cut recurring expenses and cut currency. The interviewer wants the split model and the simplification, and both are clean only with those cuts.

Identifying Core Entities#

The entity list is short, and the split rules are a family, not a single class.

The class that beginners skip is SplitStrategy, and skipping it is how the expense class ends up with a switch on split type and a hundred lines of conditionals.

Class Design#

Start with the split rule. An expense says "I paid 300, and it splits three ways." The three ways are the strategy. An interface with three implementations keeps the rule out of the expense and makes adding a fourth rule, say "split by weight," a new class instead of an edit to the switch.

public interface SplitStrategy {
    List<Long> shares(long totalInCents, int participantCount);
}

public class EqualSplit implements SplitStrategy {
    public List<Long> shares(long totalInCents, int participantCount) {
        long base = totalInCents / participantCount;
        long remainder = totalInCents % participantCount;
        List<Long> result = new ArrayList<>();
        for (int i = 0; i < participantCount; i++) {
            result.add(base + (i < remainder ? 1 : 0));
        }
        return result;
    }
}

public class ExactSplit implements SplitStrategy {
    private final List<Long> exactAmounts;

    public ExactSplit(List<Long> exactAmounts) { this.exactAmounts = exactAmounts; }

    public List<Long> shares(long totalInCents, int participantCount) {
        if (exactAmounts.stream().mapToLong(Long::longValue).sum() != totalInCents) {
            throw new IllegalArgumentException("Exact split does not sum to total");
        }
        return exactAmounts;
    }
}

public class PercentSplit implements SplitStrategy {
    private final List<Integer> percents;

    public PercentSplit(List<Integer> percents) { this.percents = percents; }

    public List<Long> shares(long totalInCents, int participantCount) {
        List<Long> result = new ArrayList<>();
        long assigned = 0;
        for (int i = 0; i < participantCount; i++) {
            long share = i == participantCount - 1
                    ? totalInCents - assigned
                    : totalInCents * percents.get(i) / 100;
            assigned += share;
            result.add(share);
        }
        return result;
    }
}

The rounding handling is deliberate and visible. The equal split hands the remainder out one cent at a time to the first members; the percent split gives the last participant whatever is left so the shares always sum exactly to the total. Either way, the invariant is that the sum of shares equals the expense total, to the cent, always. That invariant is the whole reason to write strategies at all: rounding is a property of the strategy, not a surprise in the expense.

Expense is the record that joins a payer, an amount, a set of participants, and a strategy. Its one interesting method is distribute, which returns the per-participant shares as a map, so the group can apply them.

public class Expense {
    private final String id;
    private final String payerId;
    private final long totalInCents;
    private final List<String> participantIds;
    private final SplitStrategy strategy;

    public Expense(String id, String payerId, long totalInCents,
                   List<String> participantIds, SplitStrategy strategy) {
        this.id = id;
        this.payerId = payerId;
        this.totalInCents = totalInCents;
        this.participantIds = participantIds;
        this.strategy = strategy;
    }

    public Map<String, Long> distribute() {
        List<Long> shares = strategy.shares(totalInCents, participantIds.size());
        Map<String, Long> result = new HashMap<>();
        for (int i = 0; i < participantIds.size(); i++) {
            result.put(participantIds.get(i), shares.get(i));
        }
        return result;
    }

    public String getPayerId() { return payerId; }
    public long getTotalInCents() { return totalInCents; }
}

Group computes the balances. The computation is two passes: for each expense, the payer is credited the full total, and every participant, including the payer, is debited their share. That is the step most candidates get subtly wrong: the payer participates in the split too, so a single expense both credits and debits the payer. The net is the sum of all credits minus all debits.

public class Group {
    private final List<User> members;
    private final List<Expense> expenses = new ArrayList<>();

    public Group(List<User> members) { this.members = members; }

    public void addExpense(Expense expense) { expenses.add(expense); }

    public Map<String, Long> netBalances() {
        Map<String, Long> balances = new HashMap<>();
        for (Expense expense : expenses) {
            balances.merge(expense.getPayerId(), expense.getTotalInCents(), Long::sum);
            for (Map.Entry<String, Long> share : expense.distribute().entrySet()) {
                balances.merge(share.getKey(), -share.getValue(), Long::sum);
            }
        }
        return balances;
    }
}

The settlement computation is the graph problem. The net balances are the input: some positive, some negative, some zero. The output is a list of transfers. The greedy approach pairs the biggest creditor with the biggest debtor and cancels as much as possible, which produces a correct set of settlements and is not always the true minimum, but it is simple, fast, and what most real apps do. The candidate who can say that sentence, with the "greedy is not minimal" caveat, has the interview's deepest moment.

public class SettlementCalculator {
    public List<Settlement> simplify(Map<String, Long> balances) {
        PriorityQueue<Map.Entry<String, Long>> creditors = new PriorityQueue<>(
                (a, b) -> Long.compare(b.getValue(), a.getValue()));
        PriorityQueue<Map.Entry<String, Long>> debtors = new PriorityQueue<>(
                (a, b) -> Long.compare(a.getValue(), b.getValue()));
        balances.entrySet().stream().filter(e -> e.getValue() > 0).forEach(creditors::add);
        balances.entrySet().stream().filter(e -> e.getValue() < 0).forEach(debtors::add);

        List<Settlement> settlements = new ArrayList<>();
        while (!creditors.isEmpty() && !debtors.isEmpty()) {
            Map.Entry<String, Long> creditor = creditors.poll();
            Map.Entry<String, Long> debtor = debtors.poll();
            long amount = Math.min(creditor.getValue(), -debtor.getValue());
            settlements.add(new Settlement(debtor.getKey(), creditor.getKey(), amount));
            if (creditor.getValue() - amount > 0) {
                creditor.setValue(creditor.getValue() - amount);
                creditors.add(creditor);
            }
            if (debtor.getValue() + amount < 0) {
                debtor.setValue(debtor.getValue() + amount);
                debtors.add(debtor);
            }
        }
        return settlements;
    }
}