Splitwise: expense sharing

Design an expense-sharing app like Splitwise. Users add expenses split equally, by exact amounts or by percentage, see who owes whom, and settle with a short list of payments.

Friends share costs on a trip. Design an app like Splitwise where anyone can add an expense, choose how to split it, see balances, and get a short list of payments that settles everything.

Questions to ask first

  • Which split types do we need? Assume equal, exact amounts and percentages, and that more types will come later.
  • Are expenses always inside a group? Assume yes. A one-to-one expense is a group of two.
  • Does one person pay each expense? Assume yes for now. Many payers is an extension.
  • One currency or many? Assume one currency, Indian rupees, stored as paise in a `long`.
  • When an amount does not divide evenly, who pays the extra paisa? Assume the first participants pay one paisa more each, so the splits always add up to the total.
  • Should 'simplify debts' change who owes whom? Assume yes. Users want the fewest payments, even if A now pays C instead of B.

Requirements

  • Create a group and add users to it.
  • Add an expense: amount, payer, participants and a split type (equal, exact or percentage).
  • Reject a split that does not add up: exact amounts must sum to the total, percentages to 100.
  • Show each user's net balance in a group: how much they get back or owe.
  • Simplify debts: produce a short list of payments that settles the group.
  • Record a settlement payment and update balances.

Out of scope

  • Real payments through UPI or a bank.
  • Many currencies and exchange rates (see the extensions).
  • Login, profiles, receipts and photos.

Entities

  • User: id, name, phone
  • Group: members, expenses -> addMember(), addExpense()
  • Expense: amountPaise, paidBy, type, splits
  • Split: user, amountPaise (one share of one expense)
  • SplitType (EQUAL, EXACT, PERCENT) and SplitStrategy -> split(total, users, values)
  • BalanceSheet: net per user -> apply(expense), netBalances()
  • DebtSimplifier -> simplify(net) gives Settlement(from, to, amount)
  • ExpenseService: the entry point -> addExpense(), balances(), simplifyDebts()

Classes in the model design

  • User (class)
  • Group (class)
  • Expense (class)
  • Split (class)
  • SplitType (enum)
  • SplitStrategy (interface)
  • EqualSplitStrategy (class)
  • ExactSplitStrategy (class)
  • PercentSplitStrategy (class)
  • BalanceSheet (class)
  • ExpenseService (class)
  • DebtSimplifier (class)
  • Settlement (class)

The main use case, step by step

  1. Asha pays ₹1,000 for dinner with Ravi and Meena. The app calls `ExpenseService.addExpense` with 100000 paise, payer Asha, three participants and type EQUAL.
  2. The service looks up the `SplitStrategy` for EQUAL in its map. It does not use an `if` on the type, so a new split type needs no change here.
  3. `EqualSplitStrategy.split` divides 100000 by 3. Each person gets 33333 paise, and the one leftover paisa goes to the first person, so the splits add up to 100000.
  4. The service builds an immutable `Expense` with its three `Split` objects and adds it to the `Group`.
  5. `BalanceSheet.apply` adds 100000 to Asha's net balance and subtracts each share from its owner. Asha's net is now +66666 paise. Ravi and Meena are each at minus 33333.
  6. When the group asks to settle, `DebtSimplifier.simplify` matches the biggest debtor with the biggest creditor until every net balance is zero. It returns a list of `Settlement` objects.

Patterns used

  • Strategy: SplitStrategy with EqualSplitStrategy, ExactSplitStrategy and PercentSplitStrategy, picked from a map by SplitType.. Each split type has its own rule and its own validation. A new type, such as split by shares, is one new class. The service and the Expense do not change.
  • Value object: Split and Settlement are small immutable records that carry a user and an amount in paise.. Nobody can change a share after the expense is saved. That keeps the rule 'splits add up to the total' true for the life of the expense.

Key code

Split strategies with exact paise

public record Split(User user, long amountPaise) {}

public interface SplitStrategy {
    /** values: unused for EQUAL, paise for EXACT, basis points (1% = 100) for PERCENT. */
    List<Split> split(long totalPaise, List<User> users, List<Long> values);
}

public final class EqualSplitStrategy implements SplitStrategy {
    @Override
    public List<Split> split(long totalPaise, List<User> users, List<Long> values) {
        long base = totalPaise / users.size();
        long leftover = totalPaise % users.size();   // 0 to n-1 paise
        List<Split> out = new ArrayList<>();
        for (int i = 0; i < users.size(); i++) {
            out.add(new Split(users.get(i), base + (i < leftover ? 1 : 0)));
        }
        return out;
    }
}

public final class PercentSplitStrategy implements SplitStrategy {
    @Override
    public List<Split> split(long totalPaise, List<User> users, List<Long> basisPoints) {
        if (basisPoints.size() != users.size()
                || basisPoints.stream().mapToLong(Long::longValue).sum() != 10_000) {
            throw new IllegalArgumentException("Percentages must add up to 100");
        }
        List<Split> out = new ArrayList<>();
        long given = 0;
        for (int i = 0; i < users.size(); i++) {
            long share = Math.multiplyExact(totalPaise, basisPoints.get(i)) / 10_000; // rounds down
            out.add(new Split(users.get(i), share));
            given += share;
        }
        // Rounding down loses a few paise. Give them to the first person so the total is exact.
        Split first = out.get(0);
        out.set(0, new Split(first.user(), first.amountPaise() + (totalPaise - given)));
        return out;
    }
}

Net balances and simplifying debts

public record Settlement(User from, User to, long amountPaise) {}

public final class BalanceSheet {
    private final Map<User, Long> net = new HashMap<>(); // > 0 gets money back, < 0 owes

    public void apply(Expense e) {
        net.merge(e.paidBy(), e.amountPaise(), Long::sum);
        for (Split s : e.splits()) net.merge(s.user(), -s.amountPaise(), Long::sum);
    }

    public void applyPayment(Settlement s) {
        net.merge(s.from(), s.amountPaise(), Long::sum);
        net.merge(s.to(), -s.amountPaise(), Long::sum);
    }

    public Map<User, Long> netBalances() { return Map.copyOf(net); }
}

public final class DebtSimplifier {
    private record Entry(User user, long paise) {}

    /** Greedy: the biggest debtor pays the biggest creditor. At most n - 1 payments. */
    public List<Settlement> simplify(Map<User, Long> net) {
        Comparator<Entry> biggestFirst = Comparator.comparingLong((Entry e) -> Math.abs(e.paise())).reversed();
        PriorityQueue<Entry> creditors = new PriorityQueue<>(biggestFirst);
        PriorityQueue<Entry> debtors = new PriorityQueue<>(biggestFirst);
        net.forEach((u, p) -> {
            if (p > 0) creditors.add(new Entry(u, p));
            else if (p < 0) debtors.add(new Entry(u, p));
        });
        List<Settlement> out = new ArrayList<>();
        while (!creditors.isEmpty() && !debtors.isEmpty()) {
            Entry c = creditors.poll();
            Entry d = debtors.poll();
            long amount = Math.min(c.paise(), -d.paise());
            out.add(new Settlement(d.user(), c.user(), amount));
            if (c.paise() > amount) creditors.add(new Entry(c.user(), c.paise() - amount));
            if (-d.paise() > amount) debtors.add(new Entry(d.user(), d.paise() + amount));
        }
        return out;
    }
}

Deep dives

How to store balances

Weak: Keep only the list of expenses. Recompute every balance on each screen load by walking all expenses. It is correct, but slow for an old group with thousands of expenses, and the logic hides inside a read method.

Good: Keep a pairwise map: for each pair of users, how much one owes the other. Update it when an expense is added. The screen 'Ravi owes you ₹333' reads straight from it. The map grows with the square of the group size, which is fine for groups of friends.

Great: Keep one net balance per user per group in a BalanceSheet, updated by apply(expense). Net balance is all you need to simplify debts. Keep the expense list as the history and as the source of truth, so you can rebuild the sheet if a bug corrupts it. Add pairwise totals only if the product needs 'who owes me' per friend.

Trade-off: Net balances are small and fast, but they lose the answer to 'why do I owe Meena?'. Pairwise data keeps that answer and costs more memory. Many designs keep both: the expense log for history and the net sheet for settling.

Rounding money so splits add up

Weak: Store amounts as double and divide: 1000.0 / 3 gives 333.333... for each person. Floating point cannot store most decimal fractions exactly. Totals drift, and a balance of 0.0000001 rupees never becomes zero, so the group never shows 'settled up'.

Good: Use BigDecimal and round each share with RoundingMode.HALF_UP to two decimals. Each share is now a real amount, but three shares of 333.33 add up to 999.99. One paisa is missing, and some user sees a wrong balance.

Great: Store every amount as paise in a long. Divide with integers, then hand out the leftover paise one at a time to the first participants. The splits now add up to the total by construction. For percentages, round each share down and give the leftover to one person. Write a test that checks 'sum of splits equals total' for many random amounts.

Trade-off: Integer paise is fast and exact, but you must convert at the edges (input and display). It also does not fit currencies with three decimals, such as some Gulf currencies. Store the currency's minor-unit count if you need those.

Simplifying debts

Weak: Do not simplify. Every expense creates payments from each participant to the payer. After a trip of 40 expenses, the group sees dozens of small payments, many in both directions between the same two people.

Good: Net out each pair: if Ravi owes Asha ₹500 and Asha owes Ravi ₹200, show one payment of ₹300. This keeps who pays whom close to the real expenses, and it removes the back-and-forth.

Great: Compute each user's net balance across the group. Then use the greedy rule: the person who owes the most pays the person owed the most, as much as possible, and repeat. Two priority queues make each step O(log n). This gives at most n minus 1 payments for n people, but not always the fewest. Finding the true minimum number of payments is NP-hard (no known fast algorithm), so the greedy result is the usual answer in an interview.

Trade-off: The greedy rule may ask Meena to pay someone she never spent money with. Some users find that confusing. Offer simplification as a group setting, and keep pairwise netting as the default when the group turns it off.

Now add one more feature

  • Now add group expenses in different currencies. What changes? Each `Expense` stores its currency code with the minor-unit amount. The `BalanceSheet` keeps one net balance per user per currency. Simplify inside each currency, or convert at a stored rate when the user chooses to settle in one currency.
  • Now add 'split by shares' (Ravi 2 shares, Meena 1). What changes? Add a `ShareSplitStrategy` and a SHARES enum value, and register it in the service's map. No other class changes, which shows the strategy pattern working.
  • Now allow two people to pay for one expense. What changes? `paidBy` becomes a list of payer splits that must add up to the total. `BalanceSheet.apply` credits each payer with their part. The split strategies stay the same.
  • Now let a user edit or delete an expense. What changes? Keep expenses immutable. An edit becomes 'reverse the old expense, apply the new one' on the balance sheet, and the history keeps both versions for audit.

What each level is expected to show

SDE-1: Model User, Group, Expense and Split, with one class per split type behind an interface. Store money as paise in a long. Show net balances that add up to zero. A working main method with one dinner example is enough.

SDE-2: Everything at SDE-1, plus correct leftover-paisa handling for equal and percentage splits, validation that rejects bad splits, and the greedy debt simplification with priority queues. Explain why the exact minimum is hard, and how edits and many currencies change the balance sheet.

Common mistakes

  • Using `double` for money. Totals drift and balances never reach exactly zero.
  • Writing one `addExpense` method with an `if` on the split type. Each new type means editing the same method again.
  • Losing the leftover paisa when dividing, so three shares do not add up to the bill.
  • Recomputing all balances from every expense on each read, with no class that owns balances.
  • Skipping validation: accepting exact amounts that do not sum to the total, or percentages that sum to 99.
  • Letting code change a Split after the expense is saved, which breaks the totals silently in other screens.

Lessons behind this answer