More interview problems · Chapter 28

Splitwise

Design Splitwise: users, groups, expenses split equally, by exact amounts or by percentage (Strategy), balances in integer cents, and debt simplification.

IntermediateInterview priority: High50 min
On this page
  1. The problem: shared expenses that never add up
  2. 1. Clarify the requirements
  3. 2. Entities and the class design
  4. 3. Money: integer cents, and where the leftover cent goes
  5. 4. The code
  6. 5. Simplifying debts
  7. 6. Concurrency: two phones, one group
  8. 7. Extensions the interviewer will ask for
  9. When not to over-design
  10. In the interview
  11. Quiz

The problem: shared expenses that never add up

Four friends on a trip pay for dinner, a taxi, a hotel and groceries, each split differently. Splitwise is an app that records who paid what and tells everyone who owes whom. It is a popular machine-coding question because it mixes three things interviewers like: a clean Strategy for the split types, money arithmetic that must be exact, and a small algorithm (simplifying debts).

The usual first attempt:

class Splitwise {
    Map<String, Map<String, Double>> owes = new HashMap<>();   // owes[a][b] = what a owes b

    void addExpense(String payer, double amount, List<String> people, String type, List<Double> values) {
        for (int i = 0; i < people.size(); i++) {
            double share;
            if (type.equals("EQUAL")) share = amount / people.size();
            else if (type.equals("EXACT")) share = values.get(i);
            else share = amount * values.get(i) / 100;          // PERCENT
            owes.computeIfAbsent(people.get(i), k -> new HashMap<>()).merge(payer, share, Double::sum);
        }
    }
}

What is wrong:

  • Money as double. 100 / 3 is 33.333333333333336. Three shares add up to 100.00000000000001, and after a few hundred expenses balances show "you owe 0.0000001".
  • No validation. Exact amounts that don't add up to the total, or percentages that add up to 90, are silently accepted, and money appears from nowhere.
  • The split type is a string with an if chain; a new type ("by shares", "by nights stayed") edits this method.
  • A person owes themselves their own share, and the pairwise map grows into a tangle of debts that nobody can settle in fewer than a dozen transfers.

1. Clarify the requirements

Your turn: scope it

The interviewer says "Design Splitwise." Write 5 questions and the requirements you would agree on.

Compare with our answer

Questions worth asking: Which split types: equal, exact, percentage, shares? Groups, or also expenses between two friends? One currency or many? Do we need "simplify debts"? Can expenses be edited or deleted? Do we record settle-up payments? Is it a library, or an app with many users at once?

A strong answer mentions: the split types and their validation rules · groups with members · balances per person · settle-up payments · money representation and rounding · debt simplification · out of scope: multiple currencies, notifications, receipts.

The agreed list:

RequirementDetail
Users and groupsA group has members; expenses belong to a group
ExpensePaid by one member, for an amount, split among some members
Split typesEqual; exact amounts (must add up to the total); percentage (must add up to 100%)
BalancesEach member's net position: positive = is owed, negative = owes
Settle upRecord a payment from one member to another
SimplifySuggest a small set of transfers that clears every balance
MoneyExact: no rounding drift, no cent lost or created

Out of scope: multiple currencies, editing history, notifications and the user interface. Each appears as an extension below.

2. Entities and the class design

Nouns: user, group, expense, payer, share, split type, balance, payment, transfer. Payer is a field of an expense. Share is a number per person, stored in the expense. Balance is a number per person in the group. Split type is behaviour that varies, so it becomes an interface.

Group, Expense, and the SplitStrategy family

Class / typeKindResponsibility
Uservalue objectId and name; equality by value
SplitStrategyinterfacesplit(amountCents, people) → a share per person that adds up to the amount exactly; validates its own inputs
EqualSplit, ExactSplit, PercentSplitstrategiesThe three split rules
Expensevalue objectDescription, payer, amount, the computed shares. Immutable once recorded
Transfervalue object"A pays B this much": the output of simplification
GroupclassMembers, expenses, net balances; adds expenses and payments; simplifies debts

Why these choices:

  • Strategy for the split. Each split type has its own inputs and its own validation, and new ones arrive ("by shares": 2 shares for a couple, 1 for a single person). Each is a class with one method; Group only calls split. See the Strategy pattern.
  • Shares are computed once and stored in the expense. If balances ever need recomputing (after a bug fix, or an edit), the expenses are the source of truth.
  • Net balance per person, not a pairwise "A owes B" matrix. For simplification only the net matters, and it is n numbers instead of n².

3. Money: integer cents, and where the leftover cent goes

Floating-point numbers are binary fractions, so most decimal amounts (0.10, 33.33) cannot be stored exactly; 0.1 + 0.2 is 0.30000000000000004. Two exact representations:

RepresentationHowGood atWatch out for
Integer minor units (cents) in a long / int100.00 is 10000Fast, simple, exact; easy to store in a database BIGINTCurrencies differ: JPY has 0 decimal places, KWD has 3, so store the currency with the amount
Decimal type: Java BigDecimal, Python decimal.Decimalnew BigDecimal("100.00")Exact decimal fractions; handy for rates and percentagesDivision needs an explicit scale and rounding mode; new BigDecimal(0.1) (from a double) is inexact; slower

This page uses integer cents. The remaining question is what happens when an amount does not divide evenly.

Splitting 100.00 three ways with integer cents

Each strategy gives everyone the rounded-down share and then hands out the leftover cents one at a time, so the shares always add up to the exact amount. Who gets the extra cent is a product rule: the first people in the list (as here), the payer, or a random person. Pick one, make it deterministic, and say it out loud.

4. The code

The complete model: three split strategies with validation, a group with net balances, settle-up payments, greedy simplification, and a demo that replays the trip, rejects a bad split, settles everything, and then adds 4,000 expenses from four threads.

import java.util.*;
import java.util.concurrent.*;

record User(String id, String name) {}

/** How an expense is divided. Every strategy returns shares in cents that add up to the amount exactly. */
interface SplitStrategy {
    Map<User, Long> split(long amountCents, List<User> people);
}

final class EqualSplit implements SplitStrategy {
    public Map<User, Long> split(long amount, List<User> people) {
        long base = amount / people.size(), extra = amount % people.size();
        Map<User, Long> out = new LinkedHashMap<>();
        for (int i = 0; i < people.size(); i++) out.put(people.get(i), base + (i < extra ? 1 : 0)); // leftover cents go to the first few
        return out;
    }
}

final class ExactSplit implements SplitStrategy {
    private final List<Long> amounts;
    ExactSplit(Long... amounts) { this.amounts = List.of(amounts); }
    public Map<User, Long> split(long amount, List<User> people) {
        if (amounts.size() != people.size()) throw new IllegalArgumentException("one amount per person");
        if (amounts.stream().mapToLong(Long::longValue).sum() != amount)
            throw new IllegalArgumentException("exact amounts must add up to " + amount);
        Map<User, Long> out = new LinkedHashMap<>();
        for (int i = 0; i < people.size(); i++) out.put(people.get(i), amounts.get(i));
        return out;
    }
}

/** Percentages in basis points: 4000 = 40.00%. Integers, so 33.33% is exact. */
final class PercentSplit implements SplitStrategy {
    private final List<Integer> basisPoints;
    PercentSplit(Integer... basisPoints) { this.basisPoints = List.of(basisPoints); }
    public Map<User, Long> split(long amount, List<User> people) {
        if (basisPoints.size() != people.size()) throw new IllegalArgumentException("one percentage per person");
        if (basisPoints.stream().mapToInt(Integer::intValue).sum() != 10_000)
            throw new IllegalArgumentException("percentages must add up to 100%");
        Map<User, Long> out = new LinkedHashMap<>();
        long given = 0;
        for (int i = 0; i < people.size(); i++) {
            long share = amount * basisPoints.get(i) / 10_000;     // rounds down
            out.put(people.get(i), share); given += share;
        }
        for (int i = 0; given < amount; i++, given++)                // hand out the rounding cents one by one
            out.merge(people.get(i % people.size()), 1L, Long::sum);
        return out;
    }
}

record Expense(String id, String description, User paidBy, long amountCents, Map<User, Long> shares) {}

record Transfer(User from, User to, long cents) {
    public String toString() { return from.name() + " pays " + to.name() + " " + Money.fmt(cents); }
}

final class Money {
    static String fmt(long cents) { return String.format("%s%d.%02d", cents < 0 ? "-" : "", Math.abs(cents) / 100, Math.abs(cents) % 100); }
}

final class Group {
    final String name;
    private final Set<User> members = new LinkedHashSet<>();
    private final List<Expense> expenses = new ArrayList<>();
    private final Map<User, Long> net = new LinkedHashMap<>();      // + is owed money, - owes money
    private int seq;

    Group(String name, User... users) { this.name = name; for (User u : users) addMember(u); }

    synchronized void addMember(User u) { members.add(u); net.putIfAbsent(u, 0L); }

    synchronized Expense addExpense(String desc, User paidBy, long amountCents, List<User> people, SplitStrategy how) {
        if (amountCents <= 0) throw new IllegalArgumentException("amount must be positive");
        if (!members.contains(paidBy) || !members.containsAll(people)) throw new IllegalArgumentException("not a group member");
        Map<User, Long> shares = how.split(amountCents, people);  // validate before changing anything
        Expense e = new Expense("E" + (++seq), desc, paidBy, amountCents, Collections.unmodifiableMap(new LinkedHashMap<>(shares)));
        expenses.add(e);
        net.merge(paidBy, amountCents, Long::sum);
        shares.forEach((u, s) -> net.merge(u, -s, Long::sum));
        return e;
    }

    /** A real payment between two members ("settle up"). */
    synchronized void recordPayment(User from, User to, long cents) {
        net.merge(from, cents, Long::sum);
        net.merge(to, -cents, Long::sum);
    }

    synchronized Map<User, Long> balances() { return new LinkedHashMap<>(net); }

    /** Greedy: the biggest debtor pays the biggest creditor. At most n - 1 transfers. */
    synchronized List<Transfer> simplify() {
        Comparator<Map.Entry<User, Long>> byAmount = (a, b) -> Long.compare(Math.abs(b.getValue()), Math.abs(a.getValue()));
        PriorityQueue<Map.Entry<User, Long>> owed = new PriorityQueue<>(byAmount), owes = new PriorityQueue<>(byAmount);
        for (Map.Entry<User, Long> e : net.entrySet()) {
            if (e.getValue() > 0) owed.add(new AbstractMap.SimpleEntry<>(e));
            else if (e.getValue() < 0) owes.add(new AbstractMap.SimpleEntry<>(e));
        }
        List<Transfer> out = new ArrayList<>();
        while (!owed.isEmpty() && !owes.isEmpty()) {
            var c = owed.poll(); var d = owes.poll();
            long x = Math.min(c.getValue(), -d.getValue());
            out.add(new Transfer(d.getKey(), c.getKey(), x));
            if (c.getValue() - x > 0) { c.setValue(c.getValue() - x); owed.add(c); }
            if (d.getValue() + x < 0) { d.setValue(d.getValue() + x); owes.add(d); }
        }
        return out;
    }
}

public class SplitwiseDemo {
    public static void main(String[] args) throws Exception {
        User alice = new User("u1", "alice"), bob = new User("u2", "bob"), carol = new User("u3", "carol"), dan = new User("u4", "dan");
        Group trip = new Group("Goa trip", alice, bob, carol, dan);

        Expense dinner = trip.addExpense("dinner", alice, 10_000, List.of(alice, bob, carol), new EqualSplit());
        System.out.println("dinner shares: " + fmt(dinner.shares()));
        trip.addExpense("taxi", bob, 6_000, List.of(alice, bob, dan), new ExactSplit(1_000L, 2_000L, 3_000L));
        trip.addExpense("hotel", carol, 20_000, List.of(alice, bob, carol, dan), new PercentSplit(4000, 3000, 2000, 1000));
        trip.addExpense("groceries", dan, 9_000, List.of(alice, bob, carol, dan), new EqualSplit());
        try { trip.addExpense("bad", bob, 5_000, List.of(alice, bob), new ExactSplit(1_000L, 2_000L)); }
        catch (IllegalArgumentException e) { System.out.println("rejected: " + e.getMessage()); }

        Map<User, Long> b = trip.balances();
        System.out.println("balances: " + fmt(b) + "  (sum " + b.values().stream().mapToLong(Long::longValue).sum() + ")");
        List<Transfer> plan = trip.simplify();
        plan.forEach(t -> System.out.println("  " + t));

        for (Transfer t : plan) trip.recordPayment(t.from(), t.to(), t.cents());
        System.out.println("after settling: " + fmt(trip.balances()));

        // Concurrency: 4 threads add 1,000 expenses each; the balances must still sum to zero
        Group g = new Group("flat", alice, bob, carol);
        ExecutorService pool = Executors.newFixedThreadPool(4);
        List<Future<?>> fs = new ArrayList<>();
        for (int t = 0; t < 4; t++) fs.add(pool.submit(() -> {
            for (int i = 0; i < 1_000; i++) g.addExpense("x", bob, 1_001, List.of(alice, bob, carol), new EqualSplit());
        }));
        for (Future<?> f : fs) f.get();
        pool.shutdown();
        long sum = g.balances().values().stream().mapToLong(Long::longValue).sum();
        System.out.println("4,000 concurrent expenses: bob is owed " + Money.fmt(g.balances().get(bob)) + ", sum " + sum);
    }

    static String fmt(Map<User, Long> m) {
        StringJoiner j = new StringJoiner(", ");
        m.forEach((u, c) -> j.add(u.name() + " " + Money.fmt(c)));
        return j.toString();
    }
}

Running either version prints:

dinner shares: alice 33.34, bob 33.33, carol 33.33
rejected: exact amounts must add up to 5000
balances: alice -45.84, bob -75.83, carol 104.17, dan 17.50  (sum 0)
  bob pays carol 75.83
  alice pays carol 28.34
  alice pays dan 17.50
after settling: alice 0.00, bob 0.00, carol 0.00, dan 0.00
4,000 concurrent expenses: bob is owed 26680.00, sum 0

Check one balance by hand. Alice paid 100.00 for dinner. Her shares are 33.34 (dinner) + 10.00 (taxi) + 80.00 (40% of the hotel) + 22.50 (a quarter of the groceries) = 145.84. Net: 100.00 − 145.84 = −45.84, she owes 45.84. The sum of all balances is zero, which is the invariant to test after every operation: money is only moved, never created.

Note how the payer's own share is handled. Alice paid 100.00 and her share is 33.34; adding +100.00 and −33.34 to her balance leaves +66.66, which is what the others owe her for dinner. No special case for "a person owes themselves" is needed.

5. Simplifying debts

Without simplification, every expense creates debts between the payer and each participant. Four people quickly need six transfers.

From six debts to three transfers

The greedy algorithm in the code:

  1. Split the members into creditors (balance > 0) and debtors (balance < 0), each in a priority queue by size.
  2. Take the largest creditor and the largest debtor. The debtor pays min(credit, debt).
  3. Whoever is not fully settled goes back into their queue. Repeat until both are empty.

Each round settles at least one person, so it produces at most n − 1 transfers for n people with a non-zero balance, in O(n log n) time.

Is the greedy answer the minimum?

Not always. The true minimum is n − k, where k is the largest number of separate subgroups whose balances each sum to zero (each such subgroup can settle internally with size − 1 transfers). Example: balances +5, +4, +2, −5, −6. The minimum is 3 transfers: the +5 and −5 settle each other, and the −6 pays the +4 and the +2. Greedy starts with the largest pair (+5 and −6), which breaks the perfect +5/−5 match, and needs 4. Finding the largest zero-sum partition is NP-hard (it contains the subset-sum problem), so real apps use the greedy method or a search for small groups. In the interview: describe greedy, state the n − 1 bound, and mention that exact minimisation is NP-hard.

6. Concurrency: two phones, one group

Several members add expenses from their phones at the same moment.

RaceWhat goes wrongFix
Two expenses update the same balanceRead-modify-write on net[bob]: one update is lost, and the balances no longer sum to zeroAll changes to a group happen under one lock per group (synchronized, with self._lock); in a database, one transaction per expense
Half-applied expensePayer credited, then a share fails validation: balances are off by the amountValidate and compute all shares before changing anything, then apply in one critical section or transaction
Simplify while an expense is addedThe suggested transfers are computed from a mix of old and new balancesCopy the balances under the lock, then compute from the snapshot
Double submit (a retry after a timeout)The same dinner is recorded twiceThe client sends an idempotency key (a unique id per expense); the server ignores a key it has already seen

The demo's 4,000 concurrent expenses end with a sum of exactly 0. The lock is per group, so different groups never wait for each other.

7. Extensions the interviewer will ask for

  • Split by shares (2 shares for a couple, 1 for a single): a new ShareSplit strategy using the same remainder trick. Nothing else changes.
  • Edit or delete an expense: apply the old shares in reverse, then the new ones; keep the old version for history.
  • Multiple currencies: store (amount, currency); keep balances per currency and only convert when settling, at a rate recorded with the conversion. Never add amounts in different currencies.
  • Expenses between two friends with no group: model it as a two-person group, so the code path is the same.
  • Notifications ("alice added dinner"): the group publishes events and notifiers subscribe (Observer).
  • Pairwise view ("you owe bob 23.33"): derive it from the expenses on demand, or keep a pairwise map next to the net balances.

When not to over-design

  • Only equal splits: an EqualSplit function is enough; add the interface when the second type appears.
  • A one-off trip calculator: no persistence, no locks, no idempotency. A list of expenses and a function that computes balances will do.
  • No simplification needed: skip the heaps; showing net balances may be all users want.

In the interview

Your turn: spot the bug

This percentage split passes the interviewer's test (40/30/20/10 of 200.00) but fails in production. Find two bugs and fix them.

public Map<User, Long> split(long amount, List<User> people) {
    Map<User, Long> out = new LinkedHashMap<>();
    for (int i = 0; i < people.size(); i++)
        out.put(people.get(i), Math.round(amount * percents.get(i) / 100.0));
    return out;
}
Compare with our answer

The bugs: (1) no check that the percentages add up to 100, so 40 + 30 + 20 shares out only 90% and the payer silently absorbs the rest. (2) Each share is rounded on its own, so the total can be off by a cent or more: 10 cents split 33.33/33.33/33.34% gives 3 + 3 + 3 = 9. (3) Percentages as double cannot express 33.33% exactly; basis points (integers) can.

public Map<User, Long> split(long amount, List<User> people) {
    if (basisPoints.size() != people.size()) throw new IllegalArgumentException("one percentage per person");
    if (basisPoints.stream().mapToInt(Integer::intValue).sum() != 10_000)
        throw new IllegalArgumentException("percentages must add up to 100%");
    Map<User, Long> out = new LinkedHashMap<>();
    long given = 0;
    for (int i = 0; i < people.size(); i++) {
        long share = amount * basisPoints.get(i) / 10_000;   // round down
        out.put(people.get(i), share); given += share;
    }
    for (int i = 0; given < amount; i++, given++)            // leftover cents, one each
        out.merge(people.get(i % people.size()), 1L, Long::sum);
    return out;
}

A strong answer mentions: validating that percentages sum to 100 · rounding down and distributing the remainder · shares that sum exactly to the amount · integer basis points instead of floating-point percentages · a test with an amount that does not divide evenly.

Your turn: the requirement changes

The trip is in Thailand. Some expenses are in THB, some in EUR, and members want to see what they owe in their home currency. How does the design change, and what must you not do?

Compare with our answer

A strong answer mentions:

  • Every amount becomes a Money(amountMinorUnits, currency) value object; the minor-unit scale comes from the currency (THB 2, JPY 0).
  • Balances are kept per currency (Map<Currency, Map<User, Long>>); EUR and THB are never added together.
  • Conversion happens only when displaying or settling, using a rate fetched at that moment and stored with the settlement, so history stays reproducible.
  • Simplification runs per currency, or after converting everything at one recorded rate if the group agrees.
  • Split strategies do not change: they still split an integer amount; the currency travels alongside.
Splitwise on one page
  • Classes: User, Group (members, expenses, net balances), Expense (payer, amount, shares), Transfer, SplitStrategy with EqualSplit, ExactSplit, PercentSplit.
  • Strategy: each split validates its inputs (exact sums to the total, percentages to 100%) and returns exact shares.
  • Money: integer minor units (cents) or BigDecimal/Decimal; never double. Round down, then hand out leftover cents deterministically.
  • Balance: payer +amount, each participant −share. Invariant: balances sum to zero.
  • Simplify: greedy max debtor → max creditor with two heaps; ≤ n − 1 transfers, O(n log n); exact minimum is NP-hard.
  • Concurrency: one lock or transaction per group; validate before mutating; snapshot for simplify; idempotency key per expense.
  • Durability: append-only ledger of expenses and payments; balances updated in the same transaction; reconciliation job.
  • Extensions: share-based split, edits as reverse + re-add, per-currency balances, notifications (Observer).
Check what stuck

1. A group splits a 100.00 bill equally among three people. The code computes each share as Math.round(10000 / 3.0) cents. What happens over many such bills?

2. Why is the split type modelled as a SplitStrategy interface instead of an enum and a switch in Group?

3. Balances are alice −30, bob −20, carol +50. How many transfers does greedy simplification suggest?

4. An interviewer asks whether greedy simplification always gives the fewest possible transfers. What is the most accurate answer?

5. Two members add expenses to the same group at the same moment. Afterwards the balances sum to 12.50 instead of zero. What is the most likely cause?

6. addExpense credits the payer, then calls the split strategy, which throws because the exact amounts don't add up. What is the state afterwards, and the fix?

7. A mobile app retries "add expense" after a timeout, and the dinner now appears twice. What prevents this?

Score 60% or more and the lesson is marked complete.

Passing the quiz also marks it complete. Progress is saved in this browser only.