!This gives away every stage. For a clean attempt, practise it first, then come back.

How this walkthrough is built

Same eleven steps as the other problems in this section. What’s new in this one: modelling money so it can never be wrong by a paisa, a sealed type for things that differ in their data, and an algorithm question hiding inside a design question.

Step 1Understand the problem

Picture the real thing first

Four friends go to Goa. Aarav books the hotel. Bhavna pays for a dinner where everyone ate different amounts. Chetan pays for scuba diving that only three of them did, and Divya pays for a cab. By the end, nobody knows who owes whom. The app’s job: record each expense, keep a running tally, and at the end say “Divya, pay Aarav ₹4,966.66” in as few payments as possible.

Hints: group, expense, paid by, split, everyone ate different amounts, only three of them, who owes whom, as few payments as possible.

Ask before you design

Group the questions: people and groups, kinds of split, money, settling up, and how it’s used.

Functional requirements

1. FR1. A group has members. Any member can add an expense: who paid, how much, a description, and how it’s split.
2. FR2. Splits can be equal, exact amounts, percentages, or shares (weights).
3. FR3. The system keeps, for every pair of members, how much one owes the other.
4. FR4. Each member can see their net balance: how much they’re owed overall, or owe.
5. FR5. A member can record a payment to another (settling up).
6. FR6. “Simplify debts” suggests a small set of payments that settles everyone.
7. FR7. Members are told when an expense is added.

Non-functional requirements

1. NFR1: Money is exact. Shares add up to the bill to the paisa, and the group’s balances always add up to zero.
2. NFR2: Correct under concurrency. Expenses added at the same time from many phones never lose an update.
3. NFR3: Retries are safe. A request sent twice records the expense once.
4. NFR4: Easy to extend. New split types and new simplification methods are added, not edited in.

NFR1’s second half is worth saying out loud: every rupee someone is owed, someone else owes. If the balances in a group ever add up to anything other than zero, money has been created or destroyed. That one check catches almost every bug in this problem, and we’ll use it in step 10.

Assumptions we’ll write down

Step 2Break it into entities

Pull out the nouns

User, member, friend, group, expense, bill, payer, amount, description, split, share, percentage, balance, debt, payment, settlement, notification, currency, paisa.

Three questions that decide if a noun is a class

The trap: one split method with flags

The first design most people write puts everything in one method:

enum SplitType { EQUAL, EXACT, PERCENT, SHARES }

void addExpense(User paidBy, double amount, SplitType type,
                List users, List values) {
    if (type == SplitType.EQUAL) { ... ignore values ... }
    else if (type == SplitType.EXACT) { ... values are rupees ... }
    else if (type == SplitType.PERCENT) { ... values are percentages ... }
    else { ... values are weights ... }
}

Three problems hide in it.

First, double. 0.1 + 0.2 is 0.30000000000000004 in Java, because most decimal fractions can’t be stored exactly in binary. Add a few thousand expenses and the balances drift by paise. The interviewer said people get upset over one paisa. Money is a whole number of paise, in a long.

Second, values means something different for each type. For an equal split it’s ignored; for exact splits it’s rupees; for percentages it’s percent; for shares it’s weights. Nothing stops a caller passing percentages with EXACT. The type of the input should say what it is.

Third, the if chain. A new kind of split means editing this method, and every other method with the same chain.

The fix: each kind of split is its own small record that holds exactly the data it needs and knows how to split:

sealed interface Split permits EqualSplit, ExactSplit, PercentSplit, ShareSplit {
    Map amounts(long total);
}

record EqualSplit(List users) implements Split { ... }
record ExactSplit(Map exact) implements Split { ... }
record PercentSplit(Map basisPoints) implements Split { ... }
record ShareSplit(Map shares) implements Split { ... }

Now an equal split can’t be given percentages by mistake: it doesn’t have anywhere to put them. And the group never asks what kind of split it has; it just calls amounts(total).

sealed means only these four types can implement Split. That’s a deliberate choice, discussed in step 7.

The second trap: one amount, three people

Split ₹100 equally between three people. ₹33.33 each makes ₹99.99. One paisa has vanished. Round up to ₹33.34 each and ₹100.02 has been charged for a ₹100 bill.

There’s no way around it: someone pays one paisa more. The design question is who, and the answer must be the same every time. Our rule: work out each person’s exact share as a fraction, give everyone the whole-paise part, then hand the leftover paise one at a time to the people with the biggest leftover fractions (earlier in the list wins a tie). For ₹100 three ways, everyone’s fraction is the same, so the first person gets the extra paisa: ₹33.34, ₹33.33, ₹33.33.

The same rule works for percentages and shares, so all three use one helper. This method of sharing out the remainder is old and well known: it’s called the largest remainder method, and it’s how some countries share out parliament seats.

Pull out the verbs

Add an expense, split it, check the shares, update balances, record a payment, see balances, simplify, notify, recognise a retry.

Give each job to the class that knows the most

CRC cards

Find what will change

Step 3Top-down or bottom-up?

Top-down: a phone calls addExpense(id, description, paidBy, amount, split). That needs a split that can produce amounts (Split.amounts), a ledger that can record a debt (Ledger.record), and a way to recognise a repeated id. “Simplify” needs Ledger.net and a DebtSimplifier.

Bottom-up: first the money rule (Shares.byWeight, tested on awkward amounts until it never loses a paisa), then the four splits, then the ledger, then the group.

Design from the phone inward; code from the paisa outward.

Step 4Design each class

Group: the shared space

Job: hold members, record expenses and payments exactly once, and keep balances right.

The expense id comes from the phone, not the server. That’s the key to safe retries: if the same id arrives twice, the second is the same request again, and the group returns the expense it already recorded. Step 10 explains why the server can’t make this id.

Why keep expenses at all, when the ledger already has their effect? Because people edit and delete expenses (a follow-up), and you can’t undo an expense you no longer have. The expenses are the record of what happened; the ledger is a running summary of them. If the summary is ever in doubt, it can be rebuilt from the record.

Split and its four records: how a bill is shared

Job: given a total, return what each person owes, adding up exactly to the total.

Three of the four use the same helper, Shares.byWeight, which applies the largest remainder rule. Only ExactSplit doesn’t, because there’s nothing to divide: it just checks the sum.

Ledger: who owes whom

Job: keep, for every pair, how much one owes the other, and never let the two sides disagree.

Every change writes both sides: if Bhavna owes Aarav ₹2,300 more, then owes[Bhavna][Aarav] goes up by 2,300 and owes[Aarav][Bhavna] goes down by 2,300. That pair of writes is what keeps the group’s total at zero. It only ever happens inside record, so no other code can get it half right.

Debts between two people also cancel. On the Goa trip, Aarav owes Chetan ₹3,000 for scuba and Chetan owes Aarav ₹3,000 for the hotel, so their balance is simply zero. Storing one signed number per pair does that automatically.

DebtSimplifier: few payments to settle everyone

Job: given each person’s net balance, suggest payments that bring everyone to zero.

An interface with one method, settle(net) → list of transfers. GreedySimplifier is the standard answer; OptimalSimplifier (step 11) finds the true minimum for small groups. Step 8 explains both.

Expense, Transfer, User, Money: the vocabulary

Expense is a record: id, description, payer, amount, and the exact amount each person owes. Transfer is a suggested payment. User is an id and a name. Money.format turns paise into “₹2,633.33” for display; everywhere else, money is just a long.

GroupListener: who hears about it

One method, expenseAdded(group, expense). Notifications, an activity feed, and emails are all listeners.

Step 5How the classes relate

That last row is a small, deliberate choice. The expense stores the resulting amounts, not the split object. If the rules for percentage splits ever change, old expenses don’t change with them.

Step 6The class diagram, built up

Version 1: groups, expenses, balances

Version 2: the four splits

Three of the four (equal, percent, shares) hand their work to the Shares helper, which version 3 shows. ExactSplit doesn’t need it: there’s nothing to divide, only a sum to check. It’s a small detail, but interviewers notice when your diagram and your code agree.

Version 3: the whole picture

ExactSplit, ShareSplit, Expense, Transfer and User are left off to keep it readable.

Check it against the requirements

Step 7The patterns, and why each one is here

Sealed or open?

Split is sealed: only our four records can implement it. Why close it?

Because a split has a promise to keep: the amounts add up to the total. With an open interface, anyone could add a split that breaks that promise, and the ledger would quietly drift. Sealing it means every split in the system is one we wrote and tested. Adding a fifth kind is still easy (a new record, plus one word in the permits list), but it’s a deliberate change by us.

DebtSimplifier, on the other hand, is open. A bad simplifier only produces bad suggestions; it can’t corrupt balances, because the suggestions only take effect when people record real payments. Different risk, different choice. Saying this in the interview shows you didn’t just pick a keyword.

Why not a Singleton

“One expense service” sounds natural, but the state lives in groups, and there are millions of them. Each group is its own object with its own lock. Nothing global is needed.

Patterns we deliberately didn’t use

• Factory for splits. The records’ constructors already say exactly what each needs.
• Command for expenses. Expenses are already kept as records; editing them is a follow-up, and the record is enough to undo one.
• Decorator. Nothing wraps anything here.

Step 8Walk the flows

Adding an expense

1. The lock is taken before checking the id. If two copies of the same request arrive together, only one can be inside at a time, so the second always sees the first’s expense.
2. Every check happens before anything is stored.
3. The split works out amounts that add up to exactly ₹1,000.00.
4. The payer’s own share is recorded as nothing: you can’t owe yourself.
5. Listeners are told after the lock is released. A slow notification service should never stop other expenses being added to the group.

Settling up

Bhavna pays Aarav ₹2,300. That’s recorded as a debt in the other direction: “Aarav owes Bhavna ₹2,300”, which cancels her existing ₹2,300 debt to him. One method, Ledger.record, handles expenses and payments alike, so there’s only one place where balances change.

Simplifying debts

After the four Goa expenses, five pairs of people owe each other something:

Bhavna owes Aarav ₹2300
Divya owes Aarav ₹2666.66
Divya owes Chetan ₹3000
Chetan owes Bhavna ₹900
Bhavna owes Divya ₹33.33

Settling those one by one takes five payments. But what matters to each person is only their net: how much they’re owed overall, minus how much they owe.

net: Aarav ₹4966.66, Bhavna -₹1433.33, Chetan ₹2100, Divya -₹5633.33
net adds up to 0

Aarav and Chetan are owed money; Bhavna and Divya owe it. The net adds up to exactly zero, as NFR1 promises.

Bad solutionSettle every pair separately

Five payments here, and in a big group, up to one for every pair of people: 45 for ten friends.

Good solutionGreedy matching

Take the person owed the most and the person who owes the most. The debtor pays the creditor as much as possible, the smaller of the two amounts. One of them is now settled. Repeat.

Divya pays Aarav ₹4966.66
Bhavna pays Chetan ₹1433.33
Divya pays Chetan ₹666.67

Three payments. Each payment settles at least one person, so for n people with non-zero balances it never needs more than n − 1 payments.

Great solutionGreedy, and know when it’s wrong

Greedy is not always the minimum. Here’s a five-person group (in rupees: Aarav −300, Bhavna +300, Chetan −200, Divya +400, Esha −200) where it isn’t, from a real run:

Greedy grabbed the biggest numbers first (Divya +400 and Aarav −300) and missed that Aarav and Bhavna exactly cancel each other. The true minimum comes from splitting the group into as many subgroups that add up to zero on their own as possible. Each subgroup of k people needs k − 1 payments, so more subgroups means fewer payments. Finding the best split into subgroups is a hard search problem (no fast method is known for large groups), which is why real apps use greedy.

How often does it matter? We built 2,000 random groups at each size, each with twice as many random expenses as people, and compared:

So the honest answer is: greedy, because it’s simple, fast and almost always optimal; and I know it can be off by a payment or so, and how I’d get the exact answer for a small group if the product needed it. That’s the “Great” answer: the algorithm plus a clear sense of its limits.

What walking the flows taught us

When things go wrong

Step 9Write the code, bottom-up

Each class only uses those before it. Complete Java; every output on this page comes from running it.

9.1 Users and money

record User(String id, String name) {
    @Override public String toString() { return name; }
}

final class Money {
    private Money() { }
    static String format(long paise) {
        String sign = paise < 0 ? "-" : "";
        long p = Math.abs(paise);
        String rupees = sign + "₹" + (p / 100);
        return p % 100 == 0 ? rupees : rupees + String.format(".%02d", p % 100);
    }
}

9.2 Sharing out paise fairly

final class Shares {
    private Shares() { }

    // Splits total in proportion to the weights, in whole paise, adding up exactly.
    static Map byWeight(long total, Map weights) {
        long sum = 0;
        for (long w : weights.values()) {
            if (w < 0) throw new IllegalArgumentException("negative weight");
            sum += w;
        }
        if (sum == 0) throw new IllegalArgumentException("nobody to split between");
        Map out = new LinkedHashMap<>();
        List order = new ArrayList<>(weights.keySet());
        Map rest = new HashMap<>();
        long given = 0;
        for (User u : order) {
            long exact = total * weights.get(u);                  // (1)
            out.put(u, exact / sum);
            rest.put(u, exact % sum);
            given += exact / sum;
        }
        order.sort((a, b) -> Long.compare(rest.get(b), rest.get(a)));   // (2)
        for (int i = 0; i < total - given; i++) out.merge(order.get(i), 1L, Long::sum);
        return out;
    }
}

1. Each person’s exact share is total × weight ÷ sum. Integer division gives the whole-paise part; the remainder says how much of a paisa they’re “missing”.
2. Biggest remainders first. Java’s list sort keeps equal items in their original order, so ties go to whoever was listed first. The loop then hands out exactly the missing paise, one each.

From real runs:

₹100 three ways: {Aarav=3334, Bhavna=3333, Chetan=3333}
₹10 by 33.33/33.33/33.34%: {Aarav=333, Bhavna=333, Chetan=334}

9.3 The four splits

sealed interface Split permits EqualSplit, ExactSplit, PercentSplit, ShareSplit {
    Map amounts(long total); 1
}

record EqualSplit(List users) implements Split {
    public Map amounts(long total) {
        Map w = new LinkedHashMap<>();
        for (User u : users) w.put(u, 1L);
        return Shares.byWeight(total, w);
    }
}

record ExactSplit(Map exact) implements Split {
    public Map amounts(long total) {
        long sum = exact.values().stream().mapToLong(Long::longValue).sum();
        if (sum != total)
            throw new IllegalArgumentException("exact amounts add up to "
                + Money.format(sum) + ", not " + Money.format(total));
        return new LinkedHashMap<>(exact);
    }
}

record PercentSplit(Map basisPoints) implements Split { 2
    public Map amounts(long total) {
        long sum = basisPoints.values().stream().mapToLong(Long::longValue).sum();
        if (sum != 10_000)
            throw new IllegalArgumentException("percentages must add to 100");
        return Shares.byWeight(total, basisPoints);
    }
}

record ShareSplit(Map shares) implements Split {
    public Map amounts(long total) {
        return Shares.byWeight(total, shares);
    }
}

1. The promise every split keeps, written on the interface.
2. Hundredths of a percent, so 33.33% is 3333. Exact, with no decimals.

Callers should pass a LinkedHashMap (or List) so the order, and therefore who gets a spare paisa, is the same every time.

9.4 The ledger

final class Ledger {
    private final Map> owes = new HashMap<>(); 1

    void record(User debtor, User creditor, long amount) {
        if (debtor.equals(creditor) || amount == 0) return;
        add(debtor, creditor, amount);
        add(creditor, debtor, -amount);                                // (2)
    }

    private void add(User a, User b, long amount) {
        Map row = owes.computeIfAbsent(a, x -> new HashMap<>());
        long v = row.getOrDefault(b, 0L) + amount;
        if (v == 0) row.remove(b); else row.put(b, v);
    }

    long owes(User a, User b) {
        return owes.getOrDefault(a, Map.of()).getOrDefault(b, 0L);
    }

    Map net() {                                           // (3)
        Map net = new HashMap<>();
        owes.forEach((a, row) -> row.forEach((b, v) -> net.merge(a, -v, Long::sum)));
        net.values().removeIf(v -> v == 0);
        return net;
    }
}

1. owes[a][b] is how much a owes b. Negative means b owes a.
2. Both sides, in the same method, every time. This is what keeps the group’s total at zero.
3. Positive net means the person is owed money overall.

9.5 Expenses, transfers and simplifying

record Expense(String id, String description, User paidBy, long amount,
               Map owed) { }

record Transfer(User from, User to, long amount) {
    @Override public String toString() {
        return from + " pays " + to + " " + Money.format(amount);
    }
}

interface DebtSimplifier {
    List settle(Map net);
}

final class GreedySimplifier implements DebtSimplifier {
    public List settle(Map net) {
        Comparator> big = (x, y) -> {
            int c = Long.compare(Math.abs(y.getValue()), Math.abs(x.getValue()));
            return c != 0 ? c : x.getKey().id().compareTo(y.getKey().id());   // (1)
        };
        PriorityQueue> owed = new PriorityQueue<>(big);
        PriorityQueue> owing = new PriorityQueue<>(big);
        net.forEach((u, v) -> {
            if (v > 0) owed.add(Map.entry(u, v));
            else if (v < 0) owing.add(Map.entry(u, v));
        });
        List out = new ArrayList<>();
        while (!owed.isEmpty() && !owing.isEmpty()) {
            var c = owed.poll();
            var d = owing.poll();
            long amount = Math.min(c.getValue(), -d.getValue());       // (2)
            out.add(new Transfer(d.getKey(), c.getKey(), amount));
            if (c.getValue() > amount)
                owed.add(Map.entry(c.getKey(), c.getValue() - amount));
            if (-d.getValue() > amount)
                owing.add(Map.entry(d.getKey(), d.getValue() + amount));
        }
        return out;
    }
}

1. Ties are broken by user id, so the same balances always give the same suggestions. Without this, two phones could show different advice for the same group.
2. Pay the smaller of the two amounts, so at least one person is fully settled each time.

Two priority queues keep the biggest creditor and biggest debtor at the front, so each step costs O(log n).

9.6 The group

interface GroupListener {
    void expenseAdded(Group group, Expense expense);
}

final class Group {
    private final String name;
    private final Set members;
    private final Map expenses = new LinkedHashMap<>();
    private final Ledger ledger = new Ledger();
    private final List listeners = new CopyOnWriteArrayList<>();

    Group(String name, Collection members) {
        this.name = name;
        this.members = Set.copyOf(members);
    }

    void subscribe(GroupListener l) { listeners.add(l); }

    Expense addExpense(String id, String description, User paidBy, long amount,
                       Split split) {
        Expense e;
        synchronized (this) {
            Expense seen = expenses.get(id);
            if (seen != null) {                                        // (1)
                if (seen.amount() != amount || !seen.paidBy().equals(paidBy))
                    throw new IllegalStateException("expense id reused: " + id);
                return seen;
            }
            if (amount <= 0)
                throw new IllegalArgumentException("amount must be positive");
            check(paidBy);
            Map owed = split.amounts(amount);
            owed.keySet().forEach(this::check);
            e = new Expense(id, description, paidBy, amount,
                            Collections.unmodifiableMap(owed));             // (3)
            expenses.put(id, e);
            owed.forEach((u, share) -> ledger.record(u, paidBy, share));
        }
        for (GroupListener l : listeners) l.expenseAdded(this, e);    // (2)
        return e;
    }

    synchronized void settle(User from, User to, long amount) {
        check(from);
        check(to);
        if (amount <= 0) throw new IllegalArgumentException("amount must be positive");
        ledger.record(to, from, amount);                               // (4)
    }

    synchronized long owes(User a, User b) { return ledger.owes(a, b); }
    synchronized Map net() { return ledger.net(); }
    synchronized int expenseCount() { return expenses.size(); }
    String name() { return name; }

    List simplify(DebtSimplifier s) { return s.settle(net()); }

    private void check(User u) {
        if (!members.contains(u))
            throw new IllegalArgumentException(u + " is not in " + name);
    }
}

1. A retry gets the expense it already created. If the same id comes back with a different payer or amount, that’s not a retry; it’s a bug in the client, so refuse it loudly.
2. Listeners are called outside the synchronized block.
3. The split returns a fresh, ordered map; wrapping it read-only keeps the expense unchangeable and keeps the order people were listed in.
4. “From paid to” means to now owes from that much, which cancels what from owed.

9.7 Putting it together

The Goa trip:

public class Demo {
    public static void main(String[] args) {
        User aarav = new User("u1", "Aarav"), bhavna = new User("u2", "Bhavna"),
             chetan = new User("u3", "Chetan"), divya = new User("u4", "Divya");
        List all = List.of(aarav, bhavna, chetan, divya);
        Group goa = new Group("Goa trip", all);

        goa.addExpense("e1", "Hotel", aarav, 12_000_00, new EqualSplit(all));
        Map dinner = new LinkedHashMap<>();
        dinner.put(aarav, 700_00L);
        dinner.put(bhavna, 600_00L);
        dinner.put(chetan, 900_00L);
        dinner.put(divya, 300_00L);
        goa.addExpense("e2", "Dinner", bhavna, 2_500_00, new ExactSplit(dinner));
        Map scuba = new LinkedHashMap<>();
        scuba.put(chetan, 40_00L);                                     // 40.00%
        scuba.put(divya, 30_00L);
        scuba.put(aarav, 30_00L);
        goa.addExpense("e3", "Scuba", chetan, 10_000_00, new PercentSplit(scuba));
        EqualSplit three = new EqualSplit(List.of(aarav, bhavna, divya));
        Expense cab = goa.addExpense("e4", "Cab", divya, 1_000_00, three);
        Expense again = goa.addExpense("e4", "Cab", divya, 1_000_00, three);

        System.out.println("cab: " + cab.owed());
        System.out.println("retry is the same expense: " + (again == cab)
            + ", expenses: " + goa.expenseCount());
        for (User x : all)
            for (User y : all) {
                long v = goa.owes(x, y);
                if (v > 0) System.out.println(x + " owes " + y + " " + Money.format(v));
            }
        System.out.println("greedy:");
        goa.simplify(new GreedySimplifier()).forEach(t -> System.out.println("  " + t));
        goa.settle(bhavna, aarav, 2_300_00);
        System.out.println("Bhavna owes Aarav after paying: "
            + Money.format(goa.owes(bhavna, aarav)));
    }
}

cab: {Aarav=33334, Bhavna=33333, Divya=33333}
retry is the same expense: true, expenses: 4
Bhavna owes Aarav ₹2300
Bhavna owes Divya ₹33.33
Chetan owes Bhavna ₹900
Divya owes Aarav ₹2666.66
Divya owes Chetan ₹3000
greedy:
  Divya pays Aarav ₹4966.66
  Bhavna pays Chetan ₹1433.33
  Divya pays Chetan ₹666.67
Bhavna owes Aarav after paying: ₹0

Notice what isn’t there: nothing between Aarav and Chetan. The hotel and the scuba diving cancelled out exactly.

Step 10Make it safe

Why a retry is a different problem

A phone sends “add ₹1,000 cab”. The server records it, but the reply is lost in a tunnel. The phone can’t tell “never arrived” from “arrived, reply lost”, so it sends the request again. Without protection, the cab is now in the group twice and Aarav owes for it twice.

Locks don’t fix this: the two copies might arrive a minute apart. What fixes it is recognising the second copy. So the phone makes a unique id for the expense when the user taps “save”, and sends the same id on every retry. The server only has to remember which ids it has seen.

Why can’t the server make the id? Because the server only makes an id when the request reaches it, and each copy of the request would get a new one. Only the phone knows that two requests are the same tap.

This is called making the operation idempotent: doing it twice has the same effect as doing it once. The same idea protects payments in lesson 7.3.

Why the check must be inside the lock

If the check ran first and the lock came later:

Both copies pass the check, and the cab is recorded twice. The check and the write must be one step, so they share one lock.

Prove it

We sent 10,000 expenses from 8 threads, every one of them twice (shuffled, so copies of the same request often ran at the same moment), to two versions of the group: one with the lock, and one without:

Without the lock, a few retries slipped through as duplicates, and the group’s balances stopped adding up to zero: thousands of rupees created or destroyed by lost updates, a different amount each run. With the lock, exactly 10,000 expenses, and balances identical to adding them one at a time on a single thread.

That “adds up to zero” check is worth putting in real code too: run it after tests, and alert if a live group ever fails it.

Why one lock per group

Expenses in different groups never touch the same balances, so they don’t need to wait for each other. One lock per group means a million groups can be updated in parallel, while expenses inside one group, which is a handful of friends, take turns. That’s never a bottleneck: a group doesn’t get thousands of expenses a second.

Step 11Follow-ups, extended without editing

The exact minimum number of payments

For small groups, yes. The idea from step 8: split the people into as many subgroups as possible whose balances add up to zero, then settle each subgroup with greedy (k − 1 payments for k people). To find the most subgroups, look at every subset of people, using a bitmask, and remember the best answer for each:

final class OptimalSimplifier implements DebtSimplifier {
    private final DebtSimplifier inside = new GreedySimplifier();

    public List settle(Map net) {
        List people = new ArrayList<>(net.keySet());
        int n = people.size();
        if (n > 20)
            throw new IllegalArgumentException("too many people for an exact answer");
        int full = (1 << n) - 1;
        long[] sum = new long[full + 1];
        int[] groups = new int[full + 1];                     // (1)
        for (int mask = 1; mask <= full; mask++) {
            int low = Integer.numberOfTrailingZeros(mask);
            sum[mask] = sum[mask & (mask - 1)] + net.get(people.get(low));
            int best = 0;
            for (int i = 0; i < n; i++)
                if ((mask & (1 << i)) != 0)
                    best = Math.max(best, groups[mask ^ (1 << i)]);
            groups[mask] = best + (sum[mask] == 0 ? 1 : 0);
        }
        List order = new ArrayList<>();             // (2)
        for (int mask = full; mask != 0; ) {
            int need = groups[mask] - (sum[mask] == 0 ? 1 : 0);
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0 && groups[mask ^ (1 << i)] == need) {
                    order.add(i);
                    mask ^= 1 << i;
                    break;
                }
            }
        }
        Collections.reverse(order);
        List out = new ArrayList<>();
        Map group = new LinkedHashMap<>();
        long running = 0;
        for (int i : order) {
            User u = people.get(i);
            group.put(u, net.get(u));
            running += net.get(u);
            if (running == 0) {                                  // (3)
                out.addAll(inside.settle(group));
                group.clear();
            }
        }
        return out;
    }
}

1. groups[mask] is the most zero-sum subgroups the people in mask can be split into. Build it from smaller masks: take the best answer with one person removed, and add one if this whole set adds up to zero.
2. Walk back from “everyone” to find an order of people in which the zero-sum subgroups appear one after another.
3. Each time the running total returns to zero, a subgroup is complete; settle it on its own.

It’s a new DebtSimplifier; nothing else changes. The cost grows as 2ⁿ × n, so it’s for small groups only. From real runs: 12 people took under a millisecond, 16 people 2 ms, 20 people 54 ms, and each extra person roughly doubles it. Fine for a friends’ trip; not for a 200-person office group, which is why the class refuses more than 20 and the app falls back to greedy.

Editing and deleting an expense

Because the group keeps every expense, editing is “undo the old, apply the new”, inside the lock: for each person in the old expense, record the reverse of their share; then add the new version. Deleting is just the first half. A cleaner version stores every change as an event (added, edited, deleted) and treats the ledger as a summary that can always be rebuilt from the events. That also gives you the activity feed for free.

Several people paid

“Aarav paid ₹8,000 and Bhavna ₹4,000 for the hotel.” Make paidBy a map of payer to amount, which must add up to the total. Then the ledger records each person’s share as owed to the payers in proportion to what they paid, using the same Shares.byWeight helper. One expense becomes a few more ledger records; nothing else changes.

More than one currency

Money then needs a currency next to the amount: a small Money(long minorUnits, Currency currency) record instead of a bare long. Keep separate balances per currency (owing someone ₹500 and $10 is not one number), and only convert when someone chooses to settle in a different currency, at that day’s rate. Converting every expense the moment it’s added makes old balances change whenever rates move, which confuses everyone.

Recurring expenses

Rent every month: a scheduled job that calls addExpense with an id made from the rule and the month (rent-2026-11). If the job runs twice, the id is the same, and the group ignores the second. The idempotency we built for flaky phones protects the scheduler for free.

Mistakes people make on this one

• *Using double for money,* and balances that drift by paise.
• Splitting ₹100 three ways into ₹33.33 each, and losing a paisa every time.
• *One addExpense with a type flag and a list of numbers* that mean different things for each type.
• Updating one side of a balance and forgetting the other, so the group stops adding up to zero.
• Storing only balances, so expenses can’t be edited or deleted.
• Claiming greedy simplification is always optimal.
• Ignoring retries, or checking for a duplicate outside the lock.
• Calling listeners while holding the group’s lock.

How this answer gets scored

The whole design on one page

1. Money: whole paise in a long. Shares.byWeight splits any total by weights and hands out leftover paise by largest remainder, so shares always add up.
2. Splits: a sealed Split with four records (equal, exact, percent, shares), each holding its own input and returning exact amounts.
3. Balances: a Ledger of pairwise amounts, both sides always written together; net per person derived from it. Payments go through the same method.
4. Group: members, expenses by client-made id, a ledger, listeners. addExpense checks the id, splits, stores and records under one lock, then notifies.
5. Simplify: greedy matching of biggest creditor and debtor (at most n − 1 payments, almost always optimal); an exact subset search for groups up to about twenty.
6. Safety: one lock per group for races; idempotent ids for retries; “balances add up to zero” as the check that catches everything else.