Skip to main content

Low-Level Design: Splitwise (Expense Sharing) in Java: Split Strategies, Exact Money and Debt Simplification

Design Splitwise in Java from scratch: four split strategies, exact paise arithmetic with largest-remainder rounding, a ledger derived from an event log, debt simplification where greedy is not always minimal, and concurrency. Every number is quoted from a committed transcript.

Four friends go to Goa. Asha books the hotel, Bala pays for dinner, Chitra pays for the cab, Dev pays for the scuba trip. Three days later nobody remembers who paid what, and everybody owes everybody a slightly different amount. Splitwise is the app that remembers — and “design Splitwise” is a favourite low-level design interview question, because it looks like bookkeeping and hides three real problems: how do you divide Rs 100.00 between three people, how do you keep the books so they can never disagree with themselves, and how do you turn a tangle of debts into the fewest payments. This post builds the core of a Splitwise-style system in Java. It is written so that someone meeting the problem for the first time can read it straight through; the collapsible “going deeper” panels hold the intermediate and reference-level material, so open them on a second read. Every number and console line is quoted from a file in the companion module (regenerate them all with ./scripts/run-all.sh, script here), and every code block and output block links to the file it came from. If you want the same style of walk-through for other classic questions, see Parking Lot System and BookMyShow Seat Booking.
Versions this was built and run against. JDK 25.0.5+8 (Temurin, LTS; the java -version banner reads 2026-10-20), JUnit 6.1.3 (the latest GA on Maven Central, taken from maven-metadata.xml for junit-bom; 6.2.0-M1 is a milestone, and both the <latest> and <release> elements in that file point at it) and Maven 3.9.11. No frameworks and no runtime dependencies: everything in src/main is plain Java.

Splitwise is a ledger that never lets money appear from nowhere

Before any code, the rules. A group of friends records expenses. Each expense has one person who paid, an amount, and a way of dividing it among the people who benefited. From the list of expenses the app must answer two questions: how much is each person up or down overall? and who should pay whom to settle up? It must also let people record real payments, reject nonsense input, and stay correct when several people add expenses at the same moment. The idea that makes everything else simple is the net balance. If you paid more than your share you are owed money (a positive number); if you paid less you owe money (negative). Because every rupee somebody paid is a rupee somebody else owes, all the net balances in a group add up to exactly zero. That one fact is the invariant the whole design protects, and most of the tests in the companion module are, one way or another, checking it. Here is the shape of the solution before the details.
SplitwiseServiceusers and groupsGroupthe only place state changesLedgernet balance + pair viewSplitStrategy (interface)participants(), split(total)DebtSimplifier (interface)simplify(net balances)EqualSplitExactSplitPercentSplitShareSplitGreedyDebtSimplifierOptimalDebtSimplifierStrategies and simplifiers hold no state: numbers in, numbers out. Only Group changes anything.
A Group owns a Ledger and is the only place where anything changes. When you add an expense you hand the group a SplitStrategy, which knows how to divide the amount; when you want a settle-up plan you hand it a DebtSimplifier, which knows how to shorten the list of payments. Both are interfaces with two implementations each, so the group does not care which one it gets. An expense itself is a small immutable value, in Expense.java:
public record Expense(long id, String description, String paidBy, long totalPaise, Map<String, Long> shares) {

    public Expense {
        if (totalPaise <= 0) {
            throw new IllegalArgumentException("an expense must be positive, got " + Money.format(totalPaise));
        }
        shares = Collections.unmodifiableMap(new LinkedHashMap<>(shares));
        long sum = shares.values().stream().mapToLong(Long::longValue).sum();
        if (sum != totalPaise) {
            throw new IllegalArgumentException("shares add up to " + Money.format(sum) + " but the expense is " + Money.format(totalPaise));
        }
    }
The compact constructor refuses to build an Expense whose shares do not add up to its total, so an inconsistent expense cannot exist anywhere in the program.
Going deeper: what this module leaves out, and how to present it in 45 minutes Left out on purpose: multiple currencies and conversion, recurring expenses, editing or deleting an expense after the fact, people who belong to several groups with a combined “friends” view, permissions, notifications, and persistence. Section 9 says what editing, deleting and other currencies would change. In an interview, a good order is: requirements and the net-balance idea (five minutes), the class diagram above (five), the split strategies and rounding (ten), the ledger (five), debt simplification with the greedy algorithm (ten), then concurrency and what you would change for a database (ten). Interviewers tend to push on exactly three places: what happens with Rs 100.00 between three people, why you store money the way you do, and whether your simplification is really minimal. Sections 2, 3 and 7 are those three answers.
Going deeper

Money is a whole number of paise, never a double

The first instinct is to store 12000.50 in a double. Do not. Computers store a double in binary, and most decimal fractions have no exact binary form, so tiny errors creep in and then accumulate. This is not an exotic bug; two lines are enough to see it, and they are the first lines of 02-rounding.txt:
double: 0.1 + 0.2 = 0.30000000000000004
double: ten times 0.10 = 0.9999999999999999
Adding 0.1 and 0.2 does not give 0.3, and adding 0.10 ten times does not give 1.00. In a ledger whose whole job is to add up to zero, that is fatal. The fix is to count in the smallest unit instead: paise, so Rs 100.00 is the integer 10000, held in a long. Integer arithmetic is exact. The only place text enters or leaves is the tiny class Money.java:
    /** "100.00" becomes 10000. Text with more than two decimal places is rejected rather than rounded. */
    public static long ofRupees(String text) {
        try {
            return new BigDecimal(text).setScale(2, RoundingMode.UNNECESSARY).movePointRight(2).longValueExact();
        } catch (ArithmeticException e) {
            throw new IllegalArgumentException("not a whole number of paise: " + text, e);
        }
    }

    /** 3334 becomes "Rs 33.34"; negative amounts keep the sign in front. */
    public static String format(long paise) {
        long abs = Math.abs(paise);
        return String.format(Locale.ROOT, "%sRs %d.%02d", paise < 0 ? "-" : "", abs / 100, abs % 100);
    }
ofRupees uses BigDecimal only to parse the text, and RoundingMode.UNNECESSARY makes it throw if you pass three decimal places instead of silently rounding. format turns 3334 back into “Rs 33.34”. Everything between those two calls is integer maths.
Going deeper: why long and not BigDecimal, and what changes for other currencies BigDecimal is also exact, and it is the right choice when you must handle arbitrary scales or apply rounding modes to interest or tax. For splitting a bill, a long of the smallest unit is simpler, faster, and impossible to misuse: there is no rounding mode to forget. The trade-off is that the module bakes in two decimal places. That assumption is true for rupees and false for some other currencies. This is read from the JDK, not from memory, in 07-pitfalls.txt: Currency.getDefaultFractionDigits() returns 2 for INR, 0 for JPY and 3 for KWD.
4. default fraction digits: INR 2, JPY 0, KWD 3
A multi-currency version would carry the fraction digits with the amount instead of hard-coding two, and would never add amounts of different currencies together.
Going deeper

Splitting Rs 100.00 between three people has no exact answer

Now the first real design question. Rs 100.00 is 10000 paise, and 10000 does not divide by 3. The obvious code, total / 3, gives 3333 each, which makes 9999. One paisa has vanished, and the ledger no longer balances. The transcript shows it:
long, plain division: 10000 paise / 3 = 3333 each; three of them make 9999 paise
one paisa has vanished: 1
The fix is to give everybody the rounded-down share first, count what is left over, and hand those leftover paise out one at a time. Who gets them? The people whose exact share had the biggest fractional part. This is the largest remainder method, also called the Hamilton method after Alexander Hamilton, who proposed it in 1792 for dividing seats between states. Here it is for our case:
Rs 100.00 is 10000 paise, divided between three peopleasha: 33343333 + the leftover paisabala: 333310000 / 3 rounded downchitra: 333310000 / 3 rounded down1 paisa left over10000 – 3 x 3333 = 1All three remainders are equal, so the tie goes to the first person listed. 3334 + 3333 + 3333 = 10000: nothing vanishes.
Because the three remainders are equal, the tie goes to the first person in the list. The same routine divides by weights, not just equally, so one routine serves all four split types. The core, from Apportion.java:
        int n = weights.length;
        long[] parts = new long[n];
        long[] remainder = new long[n];
        long given = 0;
        for (int i = 0; i < n; i++) {
            long scaled = Math.multiplyExact(total, weights[i]);
            parts[i] = scaled / weightSum;
            remainder[i] = scaled % weightSum;
            given += parts[i];
        }
        int leftover = (int) (total - given);
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) {
            order[i] = i;
        }
        Arrays.sort(order, Comparator
                .comparingLong((Integer i) -> remainder[i]).reversed()
                .thenComparingInt(i -> Math.floorMod(i - tieOffset, n)));
        for (int k = 0; k < leftover; k++) {
            parts[order[k]]++;
        }
        return parts;
    }
Real output for five different divisions, quoted from the transcript:
largest remainder, Rs 100.00 in 3 equal parts: [3334, 3333, 3333] sum 10000
largest remainder, 10 paise in 3 equal parts:  [4, 3, 3] sum 10
largest remainder, 33.33% / 33.33% / 33.34%:   [3333, 3333, 3334] sum 10000
largest remainder, shares 2:1:1 of Rs 1000.00: [50000, 25000, 25000] sum 100000
largest remainder, Rs 100.00 in 7 equal parts: [1429, 1429, 1429, 1429, 1428, 1428, 1428] sum 10000
Each line adds up to its total exactly, including the awkward Rs 100.00 in 7 parts, where four paise are left over and the first four people get one each.
The extra paisa always goes to the same person. With a fixed listing order, the first person pays one paisa more on every uneven expense. It looks like nothing until you add up 3000 dinners of Rs 100.00: 07-pitfalls.txt shows the first person at Rs 100020.00 and the other two at Rs 99990.00, while a rotating tie offset (the tieOffset parameter above) brings all three to exactly Rs 100000.00.
2. 3000 dinners of Rs 100.00 between asha, bala and chitra
   always the same order:  asha Rs 100020.00, bala Rs 99990.00, chitra Rs 99990.00
   rotating tie offset:    asha Rs 100000.00, bala Rs 100000.00, chitra Rs 100000.00
Going deeper: how sure are we that the shares are fair? Two properties matter and both are checked mechanically. First, the shares always add up to the total. Second, no share is ever more than one paisa away from the exact amount: every share is either the exact amount rounded down, or one paisa more. RoundingTest.java runs 200,000 seeded random divisions (up to 12 people, weights up to 10,000) and asserts both on every one:
trials: 200000
every trial: shares add up to the total exactly
every share: equal to the exact amount rounded down, or one paisa more
largest gap above the rounded-down amount: 1 paisa
As a way of allocating seats the method is known to be susceptible to apportionment paradoxes, which is why many social choice theorists prefer divisor methods for elections; for splitting a bill, where the only goal is that the parts add up and stay within a paisa of exact, it is a good fit. The Wikipedia article on the largest remainders method covers the history and the trade-offs.
Going deeper

A split is a strategy: four ways to divide the same bill

People split bills in different ways. The hotel is split equally. The cab fare is split by exact amounts because the airport pickup was Dev’s. The scuba trip is split by percentage because two people did the deep dive. The groceries are split by shares because Asha is staying twice as long as the others. All four do the same job — turn one total into one share per person — so they sit behind one interface. This is the Strategy pattern, and the whole interface, from SplitStrategy.java, is two methods:
/** One way of dividing an expense. Implementations are small immutable values, so a group can accept any of them. */
public interface SplitStrategy {

    /** Everyone who owes a share, in the order the shares are reported. */
    Set<String> participants();

    /** Returns user id to share in paise. The shares add up to exactly {@code totalPaise}. */
    Map<String, Long> split(long totalPaise);
}
The group asks participants() to check everyone is a member, then calls split(total) and receives the shares. Adding a fifth way of splitting means writing one new class; Group does not change. The table shows what each strategy needs and how it divides.
StrategyYou provideRuleGoa example
EqualSplitthe list of peoplesame share, extra paise by largest remainderHotel Rs 12000.00 → Rs 3000.00 each
ExactSplitan amount per personamounts must add up to the total exactlyCab: 300, 200, 100, 300
PercentSplita percentage per personpercentages add up to exactly 100, at most two decimalsScuba: 40 / 10 / 10 / 40
ShareSplita number of shares per personproportional to sharesGroceries 2 : 1 : 1
Here are the five Goa expenses as the code builds them (from Fixtures.java), and what each one produced (from 01-happy-path.txt):
        SplitwiseService service = new SplitwiseService();
        FRIENDS.forEach(id -> service.registerUser(id, id));
        Group trip = service.createGroup("goa", "Goa trip", FRIENDS);

        trip.addExpense("Hotel (equal)", "asha", Money.ofRupees("12000.00"), new EqualSplit(FRIENDS));
        trip.addExpense("Dinner (equal, 3 people)", "bala", Money.ofRupees("100.00"), new EqualSplit(List.of("asha", "bala", "chitra")));
        Map<String, Long> cab = new LinkedHashMap<>();
        cab.put("asha", Money.ofRupees("300.00"));
        cab.put("bala", Money.ofRupees("200.00"));
        cab.put("chitra", Money.ofRupees("100.00"));
        cab.put("dev", Money.ofRupees("300.00"));
        trip.addExpense("Cab (exact)", "chitra", Money.ofRupees("900.00"), new ExactSplit(cab));
        trip.addExpense("Scuba (percent)", "dev", Money.ofRupees("4000.00"), new PercentSplit(percents(
                "asha", "40", "bala", "10", "chitra", "10", "dev", "40")));
        trip.addExpense("Groceries (shares 2:1:1)", "asha", Money.ofRupees("1000.00"), new ShareSplit(shares(
                "asha", 2, "bala", 1, "chitra", 1)));
        return trip;
Expenses (shares in paise-exact rupees)
#1 Hotel (equal)              paid by asha    Rs 12000.00   asha=Rs 3000.00  bala=Rs 3000.00  chitra=Rs 3000.00  dev=Rs 3000.00
#2 Dinner (equal, 3 people)   paid by bala      Rs 100.00   asha=Rs 33.34  bala=Rs 33.33  chitra=Rs 33.33
#3 Cab (exact)                paid by chitra    Rs 900.00   asha=Rs 300.00  bala=Rs 200.00  chitra=Rs 100.00  dev=Rs 300.00
#4 Scuba (percent)            paid by dev      Rs 4000.00   asha=Rs 1600.00  bala=Rs 400.00  chitra=Rs 400.00  dev=Rs 1600.00
#5 Groceries (shares 2:1:1)   paid by asha     Rs 1000.00   asha=Rs 500.00  bala=Rs 250.00  chitra=Rs 250.00
Look at expense #2: Rs 100.00 between three people gives 33.34, 33.33, 33.33, the largest-remainder answer from the last section. Now the part that makes the design trustworthy: it refuses bad input. The diagram shows where the checks sit when an expense is added.
addExpensepayer, total, strategycheck memberspayer and sharersstrategy.splitshares in paisenew Expenseshares must add to totalledger.applyonly now do balances moverejectnothing was changedEvery check happens before the ledger is touched, so a rejected request leaves no half-applied state behind.
Read the diagram left to right. The group first confirms that everyone named is a member, then the strategy divides the amount, then an Expense is built (which re-checks that the shares add up), and only the last step, applying it to the ledger, changes any balance. Anything that fails on the way, shown by the dashed red arrows, stops at the reject box with nothing changed. The code, from Group.java:
    public synchronized Expense addExpense(String description, String paidBy, long totalPaise, SplitStrategy strategy) {
        requireMember(paidBy);
        strategy.participants().forEach(this::requireMember);
        Map<String, Long> shares = strategy.split(totalPaise);
        Expense expense = new Expense(nextExpenseId, description, paidBy, totalPaise, shares);
        nextExpenseId++;
        ledger.apply(expense);
        expenses.add(expense);
        return expense;
    }
This is addExpense again, from Group.java. Membership is checked first, then the split, then the Expense is built (which re-checks the sum), and only then does the ledger move. Eleven different bad requests are rejected this way in 03-validation.txt, and the last line of that file proves the group was untouched afterwards:
exact amounts too small            -> InvalidSplitException: exact amounts add up to Rs 90.00 but the expense is Rs 100.00
percentages add up to 99.99        -> InvalidSplitException: percentages add up to 99.99 but must add up to 100
percentage with 3 decimal places   -> InvalidSplitException: percent for asha has more than 2 decimal places: 33.333
zero shares                        -> InvalidSplitException: shares for bala must be positive
same person listed twice           -> InvalidSplitException: duplicate participant in [asha, asha]
nobody to split with               -> InvalidSplitException: an equal split needs at least one participant
participant outside the group      -> IllegalArgumentException: esha is not a member of group Goa trip
payer outside the group            -> IllegalArgumentException: esha is not a member of group Goa trip
zero-rupee expense                 -> IllegalArgumentException: an expense must be positive, got Rs 0.00
paying yourself                    -> IllegalArgumentException: asha cannot pay themselves
amount with three decimals         -> IllegalArgumentException: not a whole number of paise: 10.005

After eleven rejected requests: 5 expenses, balances unchanged = true
Going deeper: where each check lives, and the percent trap Each strategy validates what it can in its own constructor (no duplicate people, no negative amounts, percentages that add to 100), and what depends on the total in split(total) (exact amounts that must equal the expense). Shares are checked once more inside Expense, so even a buggy strategy written later cannot corrupt the ledger. Percentages are stored as basis points (hundredths of a percent) so the apportion routine can work with whole numbers. This is where a classic trap sits: new BigDecimal(33.33) does not give 33.33, because the double is converted exactly. The transcript (07-pitfalls.txt) shows both, and shows the strategy refusing the value built from a double:
1. new BigDecimal(33.33)   = 33.3299999999999982946974341757595539093017578125
   new BigDecimal("33.33") = 33.33
   the split rejects the double-built value: percent for asha has more than 2 decimal places: 33.3299999999999982946974341757595539093017578125
    @Override
    public Map<String, Long> split(long totalPaise) {
        String[] users = percents.keySet().toArray(new String[0]);
        long[] basisPoints = new long[users.length];
        for (int i = 0; i < users.length; i++) {
            basisPoints[i] = percents.get(users[i]).setScale(2, RoundingMode.UNNECESSARY).movePointRight(2).longValueExact();
        }
        long[] parts = Apportion.split(totalPaise, basisPoints);
        Map<String, Long> shares = new LinkedHashMap<>();
        for (int i = 0; i < users.length; i++) {
            shares.put(users[i], parts[i]);
        }
        return shares;
    }
The code above is PercentSplit.split from PercentSplit.java. It converts each percentage with setScale(2, RoundingMode.UNNECESSARY), which would throw rather than round if a third decimal place ever slipped through.
Going deeper

The ledger: store what happened, derive who owes what

Every expense changes balances. The tempting design keeps a table of “Bala owes Asha” numbers and edits them in place. The more robust design keeps the log of events (expenses and payments) and derives the balances by applying the events one at a time. The ledger holds two views of the same facts: the net balance per person, and a signed balance per pair of people. Applying an expense is only a few lines, from Ledger.java:
    public void apply(Expense e) {
        net.merge(e.paidBy(), e.totalPaise(), Long::sum);
        e.shares().forEach((user, share) -> {
            net.merge(user, -share, Long::sum);
            if (!user.equals(e.paidBy()) && share > 0) {
                owes(user, e.paidBy(), share);
            }
        });
    }
The payer is credited the whole amount; every person, the payer included, is debited their own share; and each non-payer additionally owes the payer that share in the pair view. After the five Goa expenses the net balances look like this, and the diagram shows why they must balance:
Net balance after the five Goa expensesis owed moneyowes moneyasha+Rs 7566.66bala-Rs 3783.33chitra-Rs 2883.33dev-Rs 900.00Rs 7566.66 owed to asha = Rs 3783.33 + Rs 2883.33 + Rs 900.00 owed by the others. The bars always balance.
Each bar is one person’s net balance: green to the right for money they are owed, red to the left for money they owe. The two sides have equal total length, which is the zero-sum invariant made visible. The same numbers, from 01-happy-path.txt:
Net balance per person (positive = the group owes them)
asha      Rs 7566.66
bala     -Rs 3783.33
chitra   -Rs 2883.33
dev       -Rs 900.00
Asha is owed Rs 7566.66 because she paid the hotel and the groceries; the other three owe a total of exactly the same amount. The invariant from section 1 can be checked directly, and the tests check it after the trip, after the rejected requests, after settlements and after the concurrent run:
    /** The invariant everything rests on: money is only moved, never created, so the net balances add up to zero. */
    public boolean isBalanced() {
        return net.values().stream().mapToLong(Long::longValue).sum() == 0;
    }
Because the ledger is only ever derived from the log, you can throw it away and rebuild it. SettleUpTest.java does exactly that after an expense list and one payment, and asserts the rebuilt balances and pair view equal the live ones:
expenses replayed:   5
settlements replayed: 1
net balances equal:      true
pairwise debts equal:    true
Going deeper: why two views, and what happens when someone settles The net view answers “how much am I up or down overall?” and is what simplification needs. The pair view answers “who owes me what, specifically?” and is what a detailed screen shows. In the Goa trip the pair view lists 6 payments:
Detailed debts, netted pair by pair: 6 payments
  bala pays asha Rs 3216.66
  chitra pays asha Rs 2950.00
  dev pays asha Rs 1400.00
  bala pays chitra Rs 166.67
  bala pays dev Rs 400.00
  chitra pays dev Rs 100.00
Recording a real payment moves both views. But they can drift apart in a useful way: when Bala pays Asha his net amount of Rs 3783.33 instead of the Rs 3216.66 he owes her directly, the asha-bala pair flips direction (Asha now owes Bala Rs 566.67) while his net balance goes to zero. After a few payments like these and then the simplified plan, every net balance is zero but the pair view still lists debts that cancel around the cycle:
After bala pays asha Rs 3783.33
asha      Rs 3783.33
bala         Rs 0.00
chitra   -Rs 2883.33
dev       -Rs 900.00
pair view after paying the net amount (asha-bala flips direction, because bala paid more than he owed asha directly):
  asha pays bala Rs 566.67
  chitra pays asha Rs 2950.00
  dev pays asha Rs 1400.00
  bala pays chitra Rs 166.67
  bala pays dev Rs 400.00
  chitra pays dev Rs 100.00
After the plan
asha         Rs 0.00
bala         Rs 0.00
chitra       Rs 0.00
dev          Rs 0.00
net balances all zero: true
pair view still lists 5 debts, because the plan paid net amounts, not the original pairs:
  asha pays bala Rs 566.67
  chitra pays asha Rs 166.67
  dev pays asha Rs 400.00
  bala pays chitra Rs 166.67
  bala pays dev Rs 400.00
each person's pair debts add up to their net balance: true
What never drifts is the link between them: SettleUpTest.java asserts that each person’s pair debts add up to their net balance, and the last line above is that assertion’s result. This is also why Splitwise shows both a detailed and a simplified view.
Going deeper

Settling up: from six payments to three

The pair view of the Goa trip says six separate payments are needed. But nobody cares about the pairs; they care that everyone ends at zero. If you only look at the net balances, you can do much better: Asha is owed Rs 7566.66 and the other three owe exactly that between them, so each of them can simply pay Asha once.
Detailed: 6 paymentsSimplified: 3 payments3216.662950.001400.00166.67400.00100.00ashabalachitradev3783.332883.33900.00ashabalachitradevSame final balances for everyone: arrows point from payer to receiver, amounts in rupees.
The left diagram is the pair view, the right is the simplified plan, and every friend ends with the same balance in both. The algorithm that finds the right-hand plan is short and works for any group. List the people who are owed money (creditors) and the people who owe money (debtors). Take the biggest creditor and the biggest debtor. Let the debtor pay the creditor as much as the smaller of the two amounts. At least one of them is now settled; put the other back if anything remains. Repeat until nobody is left. The loop, from GreedyDebtSimplifier.java:
        List<Transfer> transfers = new ArrayList<>();
        while (!creditors.isEmpty() && !debtors.isEmpty()) {
            Balance creditor = creditors.poll();
            Balance debtor = debtors.poll();
            long pay = Math.min(creditor.paise(), debtor.paise());
            transfers.add(new Transfer(debtor.user(), creditor.user(), pay));
            if (creditor.paise() > pay) {
                creditors.add(new Balance(creditor.user(), creditor.paise() - pay));
            }
            if (debtor.paise() > pay) {
                debtors.add(new Balance(debtor.user(), debtor.paise() - pay));
            }
        }
        return transfers;
The two PriorityQueues give the biggest creditor and debtor in O(log n). Each trip round the loop settles at least one person, and the last trip settles two, so n people with non-zero balances need at most n – 1 payments — a property asserted on every case in 04b-simplify-random.txt. The result for the Goa trip:
Simplified debts (greedy): 3 payments
  bala pays asha Rs 3783.33
  chitra pays asha Rs 2883.33
  dev pays asha Rs 900.00
Going deeper: tie-breaking, and what the plan does not preserve When two people owe the same amount, the comparator breaks the tie by name, so the same balances always give the same plan; without that, the plan could change between runs, which is a nuisance for tests and for users. The module’s comparator is Comparator.comparingLong(Balance::paise).reversed().thenComparing(Balance::user). The simplified plan does not preserve who originally paid for what. Chitra never owed Asha Rs 2883.33 for any single expense; the plan merely settles her net position. That is the right trade for paying back quickly and the wrong one if people want to see exactly what they are paying for, which is why the detailed view should stay available. Splitwise’s own help article describes it as a setting, not something that always applies.
Going deeper

The greedy plan is good, but it is not always the minimum

Most interview answers stop at the greedy algorithm and say it gives “the minimum number of transactions”. It does not always, and a good interviewer will find out. Here is a small case where it loses. Five people have balances of +4, +3, +3, -4 and -6 rupees. Look closely: Person a (+4) and person d (-4) cancel each other exactly, and so do {b, c, e}, since 3 + 3 – 6 = 0. Two independent groups.
Five balances, two hidden groups that each add up to zeroa +4d -4sums to 0: 1 paymentb +3c +3e -6sums to 0: 2 paymentsExact: 1 + 2 = 3 paymentsd pays a 4, e pays b 3, e pays c 3Greedy: 4 paymentse pays a 4 (mixes the groups),then d pays b 3, e pays c 2, d pays c 1Greedy looks only at the biggesttwo balances. It cannot see the groups.
A group that adds up to zero can settle internally with one payment fewer than its size, so the minimum for the whole is the number of people minus the number of such groups: 5 – 2 = 3. Greedy does not look for groups. It pairs the biggest debtor (e, owing 6) with the biggest creditor (a, owed 4), which mixes the groups and costs an extra payment. The real output, from 04-simplify.txt:
Balances (Rs): a +4, b +3, c +3, d -4, e -6
greedy: 4 payments
  e pays a Rs 4.00
  d pays b Rs 3.00
  e pays c Rs 2.00
  d pays c Rs 1.00
exact:  3 payments
  e pays b Rs 3.00
  e pays c Rs 3.00
  d pays a Rs 4.00
why: {a, d} cancel exactly (+4 -4) and {b, c, e} cancel exactly (+3 +3 -6), so two separate groups need 1 + 2 = 3 payments
That is one hand-picked case. How common is it? SimplifyTest.java generates 1500 seeded random balance sets of up to 9 people made of two or three hidden groups, and asserts, for every one, that both methods leave everyone at zero, that greedy uses at most n – 1 payments, and that the exact count equals an independent backtracking search:
cases: 1500
every case: both simplifiers leave every balance at exactly zero
every case: greedy uses at most (people with a balance) - 1 payments
every case: the exact simplifier's count equals an independent backtracking search
cases where greedy used more payments than exact: 448 of 1500
largest difference: 2 payment(s)
In this seeded run greedy was beaten in 448 of 1500 cases, by at most two payments. Because these balances were built from groups on purpose, that proportion says how the method behaves when groups exist, not how often real friend groups contain them. Finding the true minimum is done by OptimalDebtSimplifier.java, using a dynamic program over every subset of people to find the most zero-sum groups. The heart of it:
        int full = (1 << n) - 1;
        long[] sum = new long[full + 1];
        int[] zeroGroups = new int[full + 1];
        byte[] last = new byte[full + 1];
        for (int mask = 1; mask <= full; mask++) {
            int low = Integer.numberOfTrailingZeros(mask);
            sum[mask] = sum[mask & (mask - 1)] + net.get(users.get(low));
            int best = -1;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0 && zeroGroups[mask ^ (1 << i)] > best) {
                    best = zeroGroups[mask ^ (1 << i)];
                    last[mask] = (byte) i;
                }
            }
            zeroGroups[mask] = best + (sum[mask] == 0 ? 1 : 0);
        }
For each subset of people it records the best number of zero-sum groups that can be formed with one ordering, then walks back to recover the ordering and cuts it wherever the running total returns to zero. Each group is then settled with the greedy routine, which is minimal inside a group that cannot be split further.
The exact search costs O(2n · n), so the module caps it at 20 people. That is not laziness: finding the minimum number of payments is known to be NP-hard, which means no fast general algorithm is known. A reduction from subset sum is shown in these lecture slides, and a paper on the debts’ clearing problem states it is NP-hard in the strong sense. The committed timing transcript (04c-simplify-cost.txt, figures differ from run to run) shows the growth:
people 10: exact 9 payments in about 4 ms, greedy 9 payments in about 32 microseconds
people 14: exact 12 payments in about 18 ms, greedy 13 payments in about 29 microseconds
people 18: exact 15 payments in about 46 ms, greedy 17 payments in about 141 microseconds
people 20: exact 17 payments in about 97 ms, greedy 18 payments in about 44 microseconds
Going deeper: how the subset dynamic program works Number the people with non-zero balances 0 to n-1 and treat each subset as a bitmask. sum[mask] is the total balance of that subset. zeroGroups[mask] is the largest number of times the running total can return to zero while adding the members of mask in the best possible order. Adding person i to a smaller subset can create one more zero, exactly when the new subset sums to zero, so: zeroGroups[mask] = max over i in mask of zeroGroups[mask without i] + (sum[mask] == 0 ? 1 : 0) For the full set (which sums to zero), zeroGroups is the maximum number of groups, and the answer is n minus that. The code stores which person was added last so it can rebuild the order. A group found this way cannot be split further, otherwise the count would have been higher, and a zero-sum group that cannot be split needs exactly size – 1 payments, which is what the greedy routine produces inside it. To be sure the bitmask version is right, the test does not trust it. It compares the count with a completely different method, the classic backtracking search over who pays whom, from SimplifyTest.java:
    private static int backtrack(long[] debts, int start) {
        while (start < debts.length && debts[start] == 0) {
            start++;
        }
        if (start == debts.length) {
            return 0;
        }
        int best = Integer.MAX_VALUE;
        for (int i = start + 1; i < debts.length; i++) {
            if (debts[i] * debts[start] < 0) {
                debts[i] += debts[start];
                best = Math.min(best, 1 + backtrack(debts, start + 1));
                debts[i] -= debts[start];
            }
        }
        return best;
    }
Going deeper

Many people at once: one lock around one invariant

Two friends add an expense at the same instant. Each call reads the balances, adds its changes and writes them back. If those steps interleave, one update overwrites the other, and money appears or disappears. The invariant from section 1 is exactly what breaks first. The fix in the module is the simplest possible one: every public method on Group is synchronized, so an expense is checked, divided, applied and logged as one uninterruptible step, as you saw in addExpense earlier. To see it work, ConcurrencyTest.java starts eight threads that add 5000 expenses each to one group, all released at the same moment. Afterwards it checks that every expense was recorded once, the ids are unique, the net balances still add up to zero, and replaying the log gives the same balances:
expenses added: 40000 (expected 40000)
distinct expense ids: 40000, highest id: 40000
net balances add up to zero: true
replaying the log gives the same balances: true
To make sure the test would notice a problem, there is also a control with no lock: eight threads incrementing one counter in a plain HashMap. This file says in its first line that the figure changes every run; the numbers below are from the committed run.
expected total: 1600000
actual total:   740725
updates lost:   859275 (always zero or more, and usually well above zero)
Going deeper: why a lock per group, and what a database changes One lock per Group means two different groups never wait for each other, and nothing in the module ever needs two group locks at once, so there is no lock-ordering problem to solve. Within a group the work done under the lock is a few map updates, so contention is short. If a group were huge and busy you would shard by group anyway. As soon as the ledger lives in a database the JVM lock stops mattering, because two servers can serve the same group. The usual answer is a transaction around the whole check, split, insert, update balances sequence, with either a row lock on the group or a version column checked on write (optimistic locking). Retried requests need an idempotency key so a double-tapped “Save” does not add two expenses. The same trade-offs between locking styles, built and measured, are in the BookMyShow seat-booking post.
Going deeper

Mistakes that look fine until they are not

Each of these was reproduced in PitfallsTest.java rather than described from memory.
  • Using double for money. Section 2: 0.1 + 0.2 is not 0.3.
  • Dropping the paisa. Section 3: total / 3 loses one paisa on Rs 100.00 and the ledger stops adding up.
  • Always charging the extra paisa to the same person. Over 3000 dinners that person pays Rs 30.00 more than each of the others. Rotate the tie offset.
  • Building a percentage from a double. new BigDecimal(33.33) is 33.3299999…; use the String constructor.
  • Assuming the payer is in the split. A friend can pay for a gift they are not sharing; the module handles it, as the transcript below shows.
  • Simplifying balances that do not add up. The simplifier refuses them with a message instead of producing payments that leave someone out of pocket.
3. asha pays Rs 600.00 for a gift but is not in the split
   asha       Rs 600.00
   bala      -Rs 300.00
   chitra    -Rs 300.00
6. simplifying balances that do not add up to zero: balances do not add up to zero: the sum is Rs 0.01
Going deeper: what you would change to support editing, deleting and other currencies Editing or deleting an expense. Because the ledger is derived from the log, deleting an expense is not a special case: mark it deleted in the log and rebuild. Editing is delete plus add. What you must decide is what happens to settlements already recorded against the old numbers, and whether to keep an audit trail of the change (you should). Other currencies. Carry the currency and its fraction digits with every amount, keep one ledger per currency, and do not net across currencies. Simplifying across currencies silently re-trades people, which is a product decision, not a detail. Rounding and fairness. Rotate the tie offset using something stable, such as the expense id, so extra paise spread evenly over time. The module exposes the parameter; wiring it to the id is a one-line change in the strategy construction.
Going deeper

Should you build it this way?

For learning and for interviews, yes; for a product, only as the core. The in-JVM Group is the right thing to draw on a whiteboard and to unit-test the rules against: split strategies, rounding, balances and simplification. It is the wrong thing to run on two servers. A real service adds a database with transactions, per-currency ledgers, an audit log, idempotent retries, notifications, and a decision about whether to simplify by default. If your groups have fewer than a dozen people, the greedy simplifier is almost certainly all you need; reach for the exact search only when you can prove you need the last payment saved.

Further reading

No Comments yet!

This site uses Akismet to reduce spam. Learn how your comment data is processed.