Design Splitwise

Low-level design for a Splitwise-style expense-sharing app: split-type strategies (equal, exact, percentage, ratio), balance tracking, and the debt-simplification algorithm that minimizes settlement transactions.

August 11, 2026

lldsplitwisedebt-simplificationbalancesplit-typesgraph

Design Splitwise

Splitwise is the LLD interview's algorithm problem wearing an OOP costume. The class model — Group, Expense, User, Split — is the easy half. The half that actually separates candidates is the debt-simplification algorithm: given a tangle of pairwise debts (Alice owes Bob $10, Bob owes Carol $10, Carol owes Alice $5), compute the minimum number of transactions that settles everyone up. That's a real graph/greedy algorithm, not a design pattern, and interviewers expect you to derive it, not recite it.

1. Requirements

Functional requirements

Users can create groups and add members (e.g., "Goa Trip").
Any member can add an expense: one person paid, the amount is split among some subset of members.
Splits support four types: equal, exact share (explicit amounts that must sum to the total), percentage (must sum to 100), and ratio (e.g., 2:1:1).
The system tracks balances — who owes whom, and how much — both within a group and across all of a user's activity (personal, non-group expenses too).
Users can settle up, recording a payment that reduces or clears a balance.
The system can simplify debts: given all pairwise balances in a group, compute the minimum set of transactions that settles everyone to zero.

Non-functional requirements

Currency precision: money math must not silently lose or fabricate cents through floating-point rounding.
Consistency: a group's total balances must always net to zero (money isn't created or destroyed by an expense split).
Extensible split types: adding a new split type should not require editing existing split-type code.
Debt simplification should be efficient for realistic group sizes (tens of members, not designed for thousands).

✅

Say explicitly that debt simplification is a greedy, not globally-minimum-guaranteed algorithm unless you're prepared to justify an exact minimum-transaction solution (which is NP-hard in general, related to the min-cost-flow / subset-partition family). The greedy max-creditor/max-debtor approach is the standard, interview-expected answer — know its actual guarantee, not just its name.

2. Actors & Use Cases

Actor	Description
User	Member of one or more groups; pays for and participates in expenses.
Group	A named collection of users sharing expenses (trip, household, project).
Expense	A single spend event: who paid, total amount, how it's split.

Primary use cases

Create group, add members — straightforward collection management.
Add expense — one payer, N participants, a SplitType determining each participant's share; balances update immediately.
View balances — "you owe Bob $30," "Carol owes you $15," aggregated per user-pair and per group.
Settle up — record a direct payment between two users, zeroing or reducing their pairwise balance.
Simplify group debts — collapse a group's full balance graph into the minimum number of payments needed to zero everyone out.

3. Class Diagram

4. Core Class Design

Money as integer cents, not `double`

java

// All amounts stored as long cents internally to avoid floating-point drift
// across thousands of expense splits. Convert to/from double only at the UI boundary.
final class Money {
    private final long cents;
 
    private Money(long cents) { this.cents = cents; }
 
    static Money ofDollars(double dollars) { return new Money(Math.round(dollars * 100)); }
    static Money ofCents(long cents) { return new Money(cents); }
 
    Money plus(Money other) { return new Money(this.cents + other.cents); }
    Money minus(Money other) { return new Money(this.cents - other.cents); }
    long cents() { return cents; }
    double toDollars() { return cents / 100.0; }
}

User, Split, Expense

java

final class User {
    private final String id;
    private final String name;
 
    User(String id, String name) { this.id = id; this.name = name; }
    String getId() { return id; }
    String getName() { return name; }
 
    @Override public boolean equals(Object o) { return o instanceof User u && u.id.equals(id); }
    @Override public int hashCode() { return id.hashCode(); }
}
 
record Split(User user, Money amount) {}
 
enum SplitType { EQUAL, EXACT, PERCENTAGE, RATIO }
 
final class Expense {
    private final String id;
    private final User paidBy;
    private final Money amount;
    private final SplitType splitType;
    private final List<Split> splits;
 
    Expense(String id, User paidBy, Money amount, SplitType splitType, List<Split> splits) {
        this.id = id;
        this.paidBy = paidBy;
        this.amount = amount;
        this.splitType = splitType;
        this.splits = splits;
    }
 
    User getPaidBy() { return paidBy; }
    List<Split> getSplits() { return splits; }
    Money getAmount() { return amount; }
}

SplitStrategy — one interface, four implementations

java

interface SplitStrategy {
    List<Split> computeSplits(Money total, List<User> participants, Map<User, Double> inputs);
}
 
/** EQUAL: divide evenly; remainder cents distributed to the first N participants so the sum is exact. */
class EqualSplitStrategy implements SplitStrategy {
    public List<Split> computeSplits(Money total, List<User> participants, Map<User, Double> inputs) {
        long totalCents = total.cents();
        int n = participants.size();
        long baseShare = totalCents / n;
        long remainder = totalCents % n; // must be distributed, never silently dropped
 
        List<Split> splits = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            long share = baseShare + (i < remainder ? 1 : 0); // spread remainder cents 1-by-1
            splits.add(new Split(participants.get(i), Money.ofCents(share)));
        }
        return splits;
    }
}
 
/** EXACT: caller-provided amounts; must sum to the expense total exactly. */
class ExactSplitStrategy implements SplitStrategy {
    public List<Split> computeSplits(Money total, List<User> participants, Map<User, Double> inputs) {
        long sum = 0;
        List<Split> splits = new ArrayList<>();
        for (User u : participants) {
            long cents = Math.round(inputs.get(u) * 100);
            sum += cents;
            splits.add(new Split(u, Money.ofCents(cents)));
        }
        if (sum != total.cents()) {
            throw new IllegalArgumentException("Exact splits (" + sum + ") must sum to total (" + total.cents() + ")");
        }
        return splits;
    }
}
 
/** PERCENTAGE: caller-provided percentages; must sum to 100. */
class PercentageSplitStrategy implements SplitStrategy {
    public List<Split> computeSplits(Money total, List<User> participants, Map<User, Double> inputs) {
        double percentSum = inputs.values().stream().mapToDouble(Double::doubleValue).sum();
        if (Math.abs(percentSum - 100.0) > 0.01) {
            throw new IllegalArgumentException("Percentages must sum to 100, got " + percentSum);
        }
        List<Split> splits = new ArrayList<>();
        long allocated = 0;
        for (int i = 0; i < participants.size(); i++) {
            User u = participants.get(i);
            long cents = (i == participants.size() - 1)
                    ? total.cents() - allocated // last participant absorbs rounding remainder
                    : Math.round(total.cents() * (inputs.get(u) / 100.0));
            allocated += cents;
            splits.add(new Split(u, Money.ofCents(cents)));
        }
        return splits;
    }
}
 
/** RATIO: e.g. 2:1:1 — normalize ratios to weights of the total, same remainder-absorption trick. */
class RatioSplitStrategy implements SplitStrategy {
    public List<Split> computeSplits(Money total, List<User> participants, Map<User, Double> inputs) {
        double ratioSum = inputs.values().stream().mapToDouble(Double::doubleValue).sum();
        List<Split> splits = new ArrayList<>();
        long allocated = 0;
        for (int i = 0; i < participants.size(); i++) {
            User u = participants.get(i);
            long cents = (i == participants.size() - 1)
                    ? total.cents() - allocated
                    : Math.round(total.cents() * (inputs.get(u) / ratioSum));
            allocated += cents;
            splits.add(new Split(u, Money.ofCents(cents)));
        }
        return splits;
    }
}

⚠️

Every strategy above uses the "last participant absorbs the rounding remainder" trick (or explicit remainder distribution in EqualSplitStrategy). Without it, splitting $10.00 three ways as $3.33 + $3.33 + $3.33 = $9.99 loses a cent — multiplied across thousands of expenses, that's real, auditable money going missing. This is the single most common correctness bug in Splitwise-style implementations.

BalanceSheet — pairwise net balances

java

// Canonical ordering so (Alice, Bob) and (Bob, Alice) map to the same key.
record UserPair(User a, User b) {
    static UserPair of(User x, User y) {
        return x.getId().compareTo(y.getId()) < 0 ? new UserPair(x, y) : new UserPair(y, x);
    }
}
 
class BalanceSheet {
    // Positive value = pair.a() is owed money BY pair.b(); negative = the reverse.
    private final Map<UserPair, Long> netBalanceCents = new ConcurrentHashMap<>();
 
    void applyExpense(Expense expense) {
        User payer = expense.getPaidBy();
        for (Split split : expense.getSplits()) {
            if (split.user().equals(payer)) continue; // payer doesn't owe themself
            adjust(payer, split.user(), split.amount().cents()); // split.user() owes payer
        }
    }
 
    void applySettlement(User from, User to, Money amount) {
        adjust(to, from, -amount.cents()); // 'from' paid 'to' back, reducing what 'from' owed
    }
 
    private void adjust(User creditor, User debtor, long cents) {
        UserPair pair = UserPair.of(creditor, debtor);
        long sign = pair.a().equals(creditor) ? 1 : -1;
        netBalanceCents.merge(pair, sign * cents, Long::sum);
    }
 
    /** Net balance across ALL user pairs, collapsed to one number per user — input to debt simplification. */
    Map<User, Long> perUserNetBalance(List<User> members) {
        Map<User, Long> net = new HashMap<>();
        members.forEach(u -> net.put(u, 0L));
        netBalanceCents.forEach((pair, amount) -> {
            net.merge(pair.a(), amount, Long::sum);
            net.merge(pair.b(), -amount, Long::sum);
        });
        return net;
    }
}

5. Design Patterns Applied

Pattern	Where used	Why
Strategy	`SplitStrategy` (`Equal`, `Exact`, `Percentage`, `Ratio`)	Each split type is a self-contained computation with its own validation rule — adding a new type (e.g., "shares by weight/consumption") means adding a class, not editing an `if/switch` chain.
Facade	`Group.addExpense()` orchestrating split computation + balance update in one call	Callers interact with one simple method; the split-strategy dispatch and balance-sheet mutation stay internal.
Observer (extension point)	Balance-sheet changes triggering push notifications ("Bob added an expense, you owe $12")	Decouples "a balance changed" from "who gets notified" — same seam as the display board in Parking Lot.
Value Object	`Money`, `UserPair`	Immutable, equality-by-value types that make balance arithmetic safe to reason about and prevent the "which order were these two users in" bug class entirely.

6. Key Algorithms, Concurrency & Edge Cases

Debt simplification: greedy max-creditor/max-debtor

Problem: given each user's net balance (positive = owed money overall, negative = owes money overall) in a group, produce the minimum number of transactions that zeroes every balance out.

Key insight: once you've collapsed all pairwise debts into one net number per user, the specific pairwise history (who originally owed whom) is irrelevant — only the net matters. If Alice's net is +$20 and Bob's net is -$20, one $20 transaction settles both regardless of how many separate expenses produced that $20 gap.

Algorithm (greedy, using two heaps): repeatedly match the person owed the most against the person who owes the most, settle the smaller of the two amounts between them, and repeat until everyone nets to zero.

java

class DebtSimplifier {
    List<Transaction> simplify(Map<User, Long> netBalanceCents) {
        // Max-heap of creditors (owed money, net > 0), max-heap of debtors (owe money, net < 0).
        PriorityQueue<Map.Entry<User, Long>> creditors =
                new PriorityQueue<>((a, b) -> Long.compare(b.getValue(), a.getValue()));
        PriorityQueue<Map.Entry<User, Long>> debtors =
                new PriorityQueue<>((a, b) -> Long.compare(a.getValue(), b.getValue())); // most negative first
 
        for (Map.Entry<User, Long> e : netBalanceCents.entrySet()) {
            if (e.getValue() > 0) creditors.add(e);
            else if (e.getValue() < 0) debtors.add(e);
        }
 
        List<Transaction> transactions = new ArrayList<>();
        while (!creditors.isEmpty() && !debtors.isEmpty()) {
            var creditor = creditors.poll();
            var debtor = debtors.poll();
 
            long settleAmount = Math.min(creditor.getValue(), -debtor.getValue());
            transactions.add(new Transaction(debtor.getKey(), creditor.getKey(), Money.ofCents(settleAmount)));
 
            long creditorRemaining = creditor.getValue() - settleAmount;
            long debtorRemaining = debtor.getValue() + settleAmount;
 
            if (creditorRemaining > 0) creditors.add(Map.entry(creditor.getKey(), creditorRemaining));
            if (debtorRemaining < 0) debtors.add(Map.entry(debtor.getKey(), debtorRemaining));
        }
        return transactions;
    }
}
 
record Transaction(User from, User to, Money amount) {}

Complexity: O(n log n) for n users — each of the (at most n-1) settlement rounds does O(log n) heap work.

✅

This greedy approach minimizes transactions well in practice and is what real Splitwise-style systems use, but it is not proven to always find the mathematically absolute minimum for every possible balance configuration — the exact minimum-transaction problem is equivalent to a partition/flow problem that's NP-hard in general. In an interview, deriving the greedy heap approach and stating its complexity is the expected bar; claiming it's "provably optimal" without qualification is a common overreach worth avoiding.

Worked example

User	Net balance
Alice	+$25 (owed)
Bob	-$15 (owes)
Carol	-$10 (owes)

Naive pairwise settlement (without simplification) could require 3+ transactions across the original expenses. The greedy algorithm produces exactly 2:

Bob owes Alice → settle min($25, $15) = $15 → Alice now +$10, Bob settled.
Carol owes Alice → settle min($10, $10) = $10 → both settled.

Concurrency: two expenses added simultaneously

BalanceSheet.adjust() uses ConcurrentHashMap.merge(), which is atomic per key — two threads adding expenses that both touch the Alice/Bob pair won't lose an update, since merge performs an atomic read-modify-write per key rather than a separate get-then-put. Group-wide operations like simplifyDebts() should still snapshot the balance map (e.g., via new HashMap<>(netBalanceCents)) before running the greedy algorithm, so a concurrent expense addition mid-simplification doesn't produce a settlement plan based on a half-updated state.

Other edge cases worth naming

Floating-point currency: solved structurally by storing Money as integer cents (§4) rather than double — never reintroduce double for amounts anywhere in the balance path.
Rounding remainder distribution: every split strategy must guarantee sum(splits) == total exactly; the "last participant absorbs the remainder" pattern (or explicit cent-by-cent distribution for equal splits) is mandatory, not optional polish.
Self-split / payer included in participants: applyExpense explicitly skips split.user().equals(payer) so the payer never ends up owing themselves.
Group vs. personal expenses: a "personal" expense between two friends outside any group is just a Group of size 2 conceptually, or a separate non-grouped BalanceSheet entry keyed the same way — the model doesn't need a special case if BalanceSheet is keyed by UserPair rather than by group membership alone.
Settling more than is owed / partial settlement: applySettlement should clamp or reject an amount exceeding the current net balance, depending on whether overpayment (creating a reverse debt) is an allowed product behavior.

7. Trade-offs & Extensions

Decision	Trade-off
Greedy heap-based debt simplification	O(n log n), simple to implement and explain, minimizes transactions well in practice; not guaranteed globally minimal in every edge case — acceptable for a consumer app, not for a settlement system with legal/audit minimality requirements.
Integer cents (`Money`) instead of `double`/`BigDecimal`	Fast and simple arithmetic with no floating-point drift; `BigDecimal` would handle sub-cent precision and multiple currencies more robustly at some performance/verbosity cost.
Per-pair `BalanceSheet` instead of a full transaction ledger	Cheap balance queries (`netBalanceOf(a, b)` is O(1)); loses the ability to show "which specific expense" contributed to a balance without also keeping the raw expense history (which the design does retain via `Group.expenses`, so this is additive, not a real loss).
Debt simplification computed on-demand vs. maintained incrementally	On-demand (recompute from `BalanceSheet` snapshot each time `simplifyDebts()` is called) is simpler and always correct; incremental maintenance would be faster for very large groups but adds real complexity for a use case where group sizes are typically small.

Natural extensions an interviewer may probe:

Multi-currency groups: Money would need a currency field and either force same-currency expenses per group or route through an exchange-rate service — a meaningfully bigger design change worth flagging rather than hand-waving.
Partial settlements / IOUs with due dates: extends Transaction/settlement recording with a status and due date, closer to the Hotel Booking guide's BookingStatus state machine.
Recurring expenses (monthly rent split): a RecurringExpense template that generates Expense instances on a schedule — Factory Method territory.
"Simplify debts" opt-out per group: some group members may prefer to see the original pairwise debts rather than simplified ones (e.g., "I want Bob to pay me directly, not Carol on his behalf") — the design already supports this since BalanceSheet's pairwise map and DebtSimplifier's output are separate, queryable views.

Interview Questions

Walk through the greedy debt-simplification algorithm on a 4-person example with mixed positive/negative balances, and state its time complexity.
Why is the greedy approach not guaranteed to find the mathematically absolute minimum number of transactions? What's the actual guarantee it provides?
How does EqualSplitStrategy avoid losing a cent when splitting $10 three ways?
Why store money as integer cents instead of double? What specific bug does this prevent?
How does ConcurrentHashMap.merge() make BalanceSheet.adjust() safe under concurrent expense additions without an explicit lock?
How would you extend SplitStrategy to support a new split type (e.g., "by item consumed") without touching the existing four implementations?
If you needed to support multiple currencies per group, what would have to change in Money and BalanceSheet?

Design a Hotel Booking System

Design a Movie Ticket Booking System

Design Splitwise

Design Splitwise

1. Requirements

2. Actors & Use Cases

3. Class Diagram

4. Core Class Design

Money as integer cents, not double

User, Split, Expense

SplitStrategy — one interface, four implementations

BalanceSheet — pairwise net balances

5. Design Patterns Applied

6. Key Algorithms, Concurrency & Edge Cases

Debt simplification: greedy max-creditor/max-debtor

Worked example

Concurrency: two expenses added simultaneously

Other edge cases worth naming

7. Trade-offs & Extensions

Interview Questions

Money as integer cents, not `double`