SyntaxPilot
Courses/Low-Level Design/Lesson 76
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Low-Level Design · Lesson 76 of 90

Design Splitwise

expense sharingUserGroupExpenseSplitsplit types equal exact percentageSplitStrategybalance sheetwho owes whomsettle updebt simplificationminimizing transactionsvalidation of splits

These are the notes for Low-Level Design (LLD) episode 76: designing an expense sharing app, the kind of app Splitwise is. We model users, groups, expenses and splits, find out (with real output) why money must never be an int division or a double, build equal, exact and percentage split types as one SplitStrategy per type with validation of splits, keep a balance sheet, work out who owes whom and settle up, and finish with debt simplification: minimizing transactions so that n friends need at most n − 1 payments.

How the code was run: every program was saved as Main.java in a fresh folder and run with javac Main.java && java -cp . Main on OpenJDK 21. Every output below is the real output, pasted exactly (Java also printed a Picked up JAVA_TOOL_OPTIONS line from the machine's settings; it is left out because it has nothing to do with the programs). The people (Asha, Ravi, Neha, Amit), the Goa trip and every amount are made up. Nothing here describes how the real Splitwise app is built or what it does.

The previous episode (75) made a movie booking app safe for many users at once. Here the hard part is not threads but arithmetic: every paisa must be accounted for.

1. The problem: the Goa trip notebook

Four friends, Asha, Ravi, Neha and Amit, go to Goa. Asha pays the hotel, Ravi the dinner, Neha a cab, Amit the tickets. Someone writes each bill in a notebook: "Hotel 4000, Asha. Dinner 1200, Ravi." At the end of the trip, someone asks: so who owes whom? Some bills were shared by all four, some by only three. Ten lines later, nobody is sure. What everyone wants is a short answer: "these three UPI payments and we're done", not twelve small payments back and forth.

Real life In the design
Friends on a trip, each paying for something Expense sharing
Each friend A User
"Goa trip", the set of friends sharing costs A Group
One line in the notebook: hotel, 4000, Asha An Expense
"Ravi's part of the hotel is 1000" A Split
"Equally", "you pay 500, I pay 300", "50% / 30% / 20%" Split types: equal, exact, percentage, each a SplitStrategy
"These numbers don't add up to the bill!" Validation of splits
"Asha should get 1700 back, Neha owes 1300" The balance sheet
"Ravi owes Asha 700" Who owes whom
Ravi sends Asha 700 on UPI Settle up
"Three payments, not six" Debt simplification / minimizing transactions

2. The words: users, groups, expenses, splits

  • Expense sharing: friends pay for things at different times, and later the app evens it out so everyone has paid their fair part. Example: one person pays the whole 4000 hotel bill; later the other three each give their share.
  • User: one person in the app, with an id, a name and maybe a phone number. Example: User("u1", "Asha").
  • Group: a set of users who share costs, with a name. Example: the group "Goa trip" with Asha, Ravi, Neha and Amit.
  • Expense: one bill: what it was for, who paid, how much, and how it is split. Example: hotel, 4000 rupees, paid by Asha, split four ways.
  • Split: one person's share of one expense. Example: in the hotel expense, Ravi's split is 1000.

A user is a member of groups; a group has many expenses; each expense has many splits. The payer can also share it: Asha paid 4000 and her own split is 1000.

3. Attempt 1: just divide

The dinner bill is 1000 rupees for three friends. The obvious code divides by three. Then, maybe a double is more exact. And one tiny test: 10 paise plus 20 paise, as a double.

public class Main { public static void main(String[] args) {
    int bill = 1000, friends = 3;                     // Goa dinner: 1000 rupees, 3 friends
    int share = bill / friends;                       // attempt: just divide
    System.out.println("Each pays " + share + ", collected " + share * friends + " of " + bill);
    double exact = 1000.0 / 3;                        // attempt 2: use a double
    System.out.println("With double each pays " + exact);
    double cab = 0.1 + 0.2;                           // two small UPI payments: 10 paise + 20 paise
    System.out.println("0.1 + 0.2 = " + cab + "  equal to 0.3? " + (cab == 0.3));
} }

Real output:

Each pays 333, collected 999 of 1000
With double each pays 333.3333333333333
0.1 + 0.2 = 0.30000000000000004  equal to 0.3? false

Three bugs: we collect 999 of 1000 (one rupee vanished), the double share 333.3333333333333 can't be paid by anyone, and 0.1 + 0.2 is not 0.3.

Why it failed

  • Integer division (int / int) throws the remainder away: 1000 / 3 = 333, remainder 1. The remainder is simply lost.
  • A double is a floating-point number stored in binary (base two). 0.1 has no exact binary form, just as 1/3 has no exact decimal form (0.3333...). Java stores the nearest binary number, and the tiny errors show up when you add or compare.

The fix: money in paise, in a long

  • Store money as whole paise in a long. 1000 rupees = 100000 paise. Whole numbers add, subtract and compare exactly.
  • When a bill does not divide evenly, hand out the leftover paise: 100000 / 3 = 33333 remainder 1, so the first person pays 33334 and the others 33333: 333.34 + 333.33 + 333.33 = 1000.00.
  • The rule: every split must add up to the bill, exactly, to the last paisa. Print paise as rupees with p / 100 + "." + String.format("%02d", p % 100): 33334 → 333.34.
  • Java's BigDecimal (an exact decimal number class) also works; see common mistakes for its trap with division. We use long paise: short and fast.

4. Split types and the SplitStrategy

Real bills are not always equal. Three split types:

Split type Meaning Example (Asha, Ravi, Neha)
Equal Everyone pays the same Dinner 1000 → 333.34, 333.33, 333.33
Exact Each amount is typed in 1000 → 500, 300, 200
Percentage Each share is a percent of the bill 1200 at 50 / 30 / 20 % → 600, 360, 240

Attempt 2: one big if-else

The obvious code is one method with a branch per type. (A sketch, not a full program.)

List<Long> split(String type, long total, List<String> users, List<Double> values) {
    if (type.equals("EQUAL")) { /* divide, hand out leftover paise */ }
    else if (type.equals("EXACT")) { /* copy the typed amounts */ }
    else if (type.equals("PERCENT")) { /* total * p / 100 */ }
    // a new type "by shares"? edit this method again, and re-test all the others
}

Why it fails

Every new split type (for example by shares: 2 shares for a couple, 1 for a single person) means editing and re-testing this one method. It breaks the open-closed principle: code should be open to new behaviour without editing what already works.

The fix: one SplitStrategy class per type

This is the Strategy pattern from episode 34: an interface for "how to split", and one class per way. Each strategy also does validation: checking the input before accepting it. Exact amounts must add up to the bill; percentages must add up to 100. If not, it refuses loudly with an IllegalArgumentException (Java's standard exception for "this argument is not acceptable").

import java.util.*;
record Split(String user, long paise) {                       // one person's share, in paise
    public String toString() { return user + " " + paise / 100 + "." + String.format("%02d", paise % 100); } }
interface SplitStrategy { List<Split> split(long total, List<String> users, List<Double> values); }
class EqualSplit implements SplitStrategy {
    public List<Split> split(long total, List<String> users, List<Double> values) {
        List<Split> out = new ArrayList<>();  long base = total / users.size(), extra = total % users.size();
        for (int i = 0; i < users.size(); i++) out.add(new Split(users.get(i), base + (i < extra ? 1 : 0)));
        return out; } }                                       // leftover paise go to the first people
class ExactSplit implements SplitStrategy {
    public List<Split> split(long total, List<String> users, List<Double> values) {
        long sum = 0;  List<Split> out = new ArrayList<>();
        for (int i = 0; i < users.size(); i++) { long p = Math.round(values.get(i) * 100);  sum += p;
            out.add(new Split(users.get(i), p)); }
        if (sum != total) throw new IllegalArgumentException("exact splits add up to " + sum / 100.0
                + ", but the bill is " + total / 100.0);
        return out; } }
class PercentSplit implements SplitStrategy {
    public List<Split> split(long total, List<String> users, List<Double> values) {
        if (Math.abs(values.stream().mapToDouble(d -> d).sum() - 100) > 1e-9)
            throw new IllegalArgumentException("percentages must add up to 100");
        return new ExactSplit().split(total, users, values.stream().map(p -> total * p / 10000).toList()); } }
public class Main { public static void main(String[] args) {
    List<String> trio = List.of("Asha", "Ravi", "Neha");
    System.out.println("equal   " + new EqualSplit().split(100000, trio, null));
    System.out.println("exact   " + new ExactSplit().split(100000, trio, List.of(500.0, 300.0, 200.0)));
    System.out.println("percent " + new PercentSplit().split(120000, trio, List.of(50.0, 30.0, 20.0)));
    System.out.println("bad     " + new ExactSplit().split(100000, trio, List.of(500.0, 300.0, 100.0)));
} }

Real output:

equal   [Asha 333.34, Ravi 333.33, Neha 333.33]
exact   [Asha 500.00, Ravi 300.00, Neha 200.00]
percent [Asha 600.00, Ravi 360.00, Neha 240.00]
Exception in thread "main" java.lang.IllegalArgumentException: exact splits add up to 900.0, but the bill is 1000.0
    at ExactSplit.split(Main.java:15)
    at Main.main(Main.java:28)

What to notice:

  • Equal: 333.34 + 333.33 + 333.33, not a paisa lost: base = total / n, extra = total % n, the first extra people pay one paisa more.
  • Exact: typed rupees become paise with Math.round(value * 100) (not a cast: see common mistakes), then are added up.
  • Percentage: PercentSplit checks the percentages sum to 100, turns each percent into an amount (total * p / 10000, because total is in paise and p is a percent), then reuses ExactSplit, so it gets the "must add up" check for free.
  • Bad: 500 + 300 + 100 = 900, not 1000, so the split is refused with a message that names both numbers. The bad line never prints, because the exception is thrown before println runs.
  • Adding a fourth type is one new class. (A record is a short class for plain data: record Split(String user, long paise) gets a constructor, user(), paise(), equals and hashCode for free.)

5. The balance sheet, who owes whom, and settle up

Splits give each share. Now: who owes whom?

  • Balance sheet: one number per user for the whole group. For every expense, the payer's balance goes up by each share they paid for, and each sharer's balance goes down by their share. Plus means "gets money back", minus means "owes". Example: Asha paid the 4000 hotel and her share is 1000, so the hotel makes her balance +3000; Ravi paid nothing for it and his share is 1000, so −1000.
  • The zero-sum check: add every balance in a group and you always get 0, because money only moves between friends. If the sum is not 0, there is a bug. This is an invariant: something that must always be true.
  • Who owes whom: the debt between each pair of friends, netted both ways. If Ravi owes Asha 1000 and Asha owes Ravi 300, the app shows one line: Ravi owes Asha 700.
  • Settle up: a real payment outside the app, like Ravi sending Asha 700 on UPI, recorded in the app so the balances change. It works like an expense in reverse: the person who paid goes up, the person who received goes down.
import java.util.*;
record Expense(String what, String paidBy, long amount, Map<String, Long> shares) {}  // rupees
class Group {
    final Map<String, Long> balance = new TreeMap<>();              // + gets money back, - owes
    final Map<String, Long> owes = new TreeMap<>();                 // "Ravi->Asha" -> 700
    void add(Expense e) {
        long sum = e.shares().values().stream().mapToLong(x -> x).sum();
        if (sum != e.amount()) throw new IllegalArgumentException(e.what() + ": shares add up to "
                + sum + ", but the bill is " + e.amount());
        e.shares().forEach((user, share) -> {
            balance.merge(e.paidBy(), share, Long::sum);  balance.merge(user, -share, Long::sum);
            if (!user.equals(e.paidBy())) owe(user, e.paidBy(), share); }); }
    void owe(String from, String to, long amt) {                    // net each pair both ways
        long back = owes.getOrDefault(to + "->" + from, 0L);  owes.remove(to + "->" + from);
        if (back > amt) owes.put(to + "->" + from, back - amt);
        else if (amt > back) owes.merge(from + "->" + to, amt - back, Long::sum); }
    void settleUp(String from, String to, long amt) {               // from pays to, in real life
        balance.merge(from, amt, Long::sum);  balance.merge(to, -amt, Long::sum);  owe(to, from, amt); } }
public class Main { public static void main(String[] args) {
    Group g = new Group();
    g.add(new Expense("hotel", "Asha", 4000, Map.of("Asha", 1000L, "Ravi", 1000L, "Neha", 1000L, "Amit", 1000L)));
    g.add(new Expense("dinner", "Ravi", 1200, Map.of("Asha", 300L, "Ravi", 300L, "Neha", 300L, "Amit", 300L)));
    g.add(new Expense("cab", "Neha", 800, Map.of("Asha", 200L, "Ravi", 200L, "Neha", 200L, "Amit", 200L)));
    g.add(new Expense("tickets", "Amit", 2000, Map.of("Asha", 800L, "Ravi", 600L, "Neha", 600L)));
    System.out.println("balance sheet: " + g.balance);
    System.out.println(g.owes.size() + " payments: " + g.owes);
    g.settleUp("Ravi", "Asha", 700);
    System.out.println("Ravi pays Asha 700 -> " + g.owes.size() + " payments left");
    g.add(new Expense("snacks", "Ravi", 500, Map.of("Asha", 200L, "Neha", 200L))); } }

Real output:

balance sheet: {Amit=500, Asha=1700, Neha=-1300, Ravi=-900}
6 payments: {Amit->Asha=200, Neha->Amit=400, Neha->Asha=800, Neha->Ravi=100, Ravi->Amit=300, Ravi->Asha=700}
Ravi pays Asha 700 -> 5 payments left
Exception in thread "main" java.lang.IllegalArgumentException: snacks: shares add up to 400, but the bill is 500
    at Group.add(Main.java:9)
    at Main.main(Main.java:29)

Reading it:

  • Balance sheet: Asha gets back 1700, Amit 500; Neha owes 1300, Ravi 900. 1700 + 500 − 1300 − 900 = 0. The invariant holds.
  • Check Asha: paid 4000, shares 1000 + 300 + 200 + 800 = 2300, so +1700.
  • Who owes whom needs 6 payments for 4 friends: every pair. Look at Ravi and Asha: Ravi owed Asha 1000 (hotel), Asha owed Ravi 300 (dinner), netted to Ravi->Asha=700.
  • After settleUp("Ravi", "Asha", 700), that pair is clear: 5 payments left.
  • The snacks bill is refused before it touches any balance: 200 + 200 = 400, not 500. A bad bill accepted here would quietly break every balance after it.
  • Amounts here are whole rupees to keep the screen short (the mini project uses paise). merge(key, value, Long::sum) adds to the stored value or stores it if new; TreeMap keeps keys sorted.

6. Debt simplification: minimizing transactions

The problem: too many payments

Pair by pair, 4 friends needed 6 payments. With n friends there can be one debt per pair: n × (n − 1) / 2 pairs, so 10 friends can need up to 45 payments. Nobody wants that.

The key observation: only the balances matter. Neha does not care whether her 1300 goes to Asha or to Amit, as long as at the end everyone's balance is 0.

The fix: biggest debtor pays biggest creditor

  • Debt simplification, also called minimizing transactions (or minimizing cash flow): replace all the pairwise debts with as few payments as possible that bring every balance to 0.
  • A debtor owes money (negative balance); a creditor is owed money (positive balance).
  • The greedy method (greedy: always take the best-looking step right now, never go back): take the person who owes the most and the person who is owed the most. The debtor pays the creditor the smaller of the two amounts. That clears at least one of them. Put whoever still has something left back, and repeat.
  • Every payment clears at least one person, and the last payment clears two, so n people need at most n − 1 payments.
  • Finding the true minimum number of payments in every case is a much harder problem (it means searching for groups of people whose balances cancel exactly). The greedy method is simple, fast, and usually close. In an interview, say both things.

To always get "the biggest" quickly we use a priority queue (PriorityQueue): a collection whose poll() always returns the top item by a comparator (a rule for ordering two items). Our comparator most puts the biggest amount on top.

import java.util.*;
public class Main {
    record Person(String name, long amt) {}
    static List<String> simplify(Map<String, Long> balance) {   // biggest debtor pays biggest creditor
        Comparator<Person> most = (a, b) -> Long.compare(b.amt(), a.amt());
        PriorityQueue<Person> give = new PriorityQueue<>(most), get = new PriorityQueue<>(most);
        balance.forEach((n, b) -> { if (b < 0) give.add(new Person(n, -b));
                                    else if (b > 0) get.add(new Person(n, b)); });
        List<String> pay = new ArrayList<>();
        while (!give.isEmpty()) {
            Person d = give.poll(), c = get.poll();  long x = Math.min(d.amt(), c.amt());
            pay.add(d.name() + "->" + c.name() + " " + x);
            if (d.amt() > x) give.add(new Person(d.name(), d.amt() - x));   // still owes some
            if (c.amt() > x) get.add(new Person(c.name(), c.amt() - x)); }  // still gets some
        return pay; }
    public static void main(String[] args) {
        Map<String, Long> goa = Map.of("Asha", 1700L, "Amit", 500L, "Neha", -1300L, "Ravi", -900L);
        System.out.println("Goa trip: " + simplify(goa));
        Random r = new Random(7);  Map<String, Long> bal = new TreeMap<>(), pair = new HashMap<>();
        for (int i = 0; i < 200; i++) {                          // 200 random expenses, 10 friends
            int payer = r.nextInt(10), other = r.nextInt(10);  long amt = 50 + r.nextInt(950);
            if (payer == other) continue;
            bal.merge("F" + payer, amt, Long::sum);  bal.merge("F" + other, -amt, Long::sum);
            String key = Math.min(payer, other) + "-" + Math.max(payer, other);   // one entry per pair
            pair.merge(key, payer < other ? amt : -amt, Long::sum); }
        pair.values().removeIf(v -> v == 0);
        System.out.println("10 friends: pairwise payments " + pair.size()
                           + ", simplified " + simplify(bal).size()); } }

Real output:

Goa trip: [Neha->Asha 1300, Ravi->Amit 500, Ravi->Asha 400]
10 friends: pairwise payments 45, simplified 9

Tracing the Goa trip:

Step Biggest debtor Biggest creditor Payment Left over
1 Neha 1300 Asha 1700 Neha → Asha 1300 Neha done; Asha still gets 400
2 Ravi 900 Amit 500 Ravi → Amit 500 Amit done; Ravi still owes 400
3 Ravi 400 Asha 400 Ravi → Asha 400 both done
  • Goa: 6 pairwise payments → 3 (n − 1 for 4 people). 10 friends, 200 random expenses: all 45 pairs had a debt; simplified, 9 (n − 1 again). Random(7) has a fixed seed, so the run is repeatable.
  • The loop trusts that the balances sum to 0; if not, it crashes (see common mistakes).

7. The class diagram

User ─ member of ─▶ Group ─ has many ─▶ Expense(what, paidBy, amount, splits)
Expense ─ has ─▶ Split(user, paise)     money in paise (long), never double
SplitStrategy ◁─ EqualSplit · ExactSplit · PercentSplit   (validates: sum = bill, % = 100)
Group: balance sheet  user → +gets back / −owes      owes: "Ravi->Asha" → 700 (netted per pair)
settleUp(from, to, amt): a real payment, recorded like an expense in reverse
simplify(balance): biggest debtor pays biggest creditor → at most n − 1 payments

◁─ means "implements". The Group owns the balances; the Expense only records what happened, so deleting an expense is just applying its splits again with the opposite sign. In a machine-coding round, an ExpenseService in front of the groups looks up users and groups by id.

8. Interview follow-ups

Question Answer
Many currencies? Store the currency with every amount (Money(long minorUnits, String currency)) and never add rupees to dollars. Keep one balance per currency, or convert at a recorded rate.
Edit or delete an expense? Reverse its effect on the balances (apply it with the opposite sign), then apply the new version. The mini project's deleteExpense does this.
Two people add bills to one group at the same moment? Synchronize per group (episode 75's idea: a lock per show, here a lock per group), so two updates never mix.
A new split type, like by shares? One new SplitStrategy class (the mini project's ShareSplit); nothing else changes.
Debts across groups? Add up balances per pair of friends across all their groups, then show or simplify that.
Who gets the leftover paise? Any fixed, fair rule: the first people in the list, the payer, or rotate. The only must: the total equals the bill exactly.

9. Common mistakes

Every "what you see" below is real output from programs run for these notes.

Mistake What you see (real) Fix
int division for shares Each pays 333, collected 999 of 1000 Paise, and hand out the leftover paise
Money as double 0.1 + 0.2 = 0.30000000000000004 equal to 0.3? false long paise, or BigDecimal
Putting a double into a long error: incompatible types: possible lossy conversion from double to long Math.round(rupees * 100)
Casting instead of rounding (long) (1.15 * 100) gives 114, not 115 Math.round, which gives 115
BigDecimal.divide with no rounding java.lang.ArithmeticException: Non-terminating decimal expansion; no exact representable decimal result. divide(x, 2, RoundingMode.DOWN), then hand out the rest
No split validation a 500 bill shared as 400 is accepted Throw: snacks: shares add up to 400, but the bill is 500
Rounding each percentage share separately exact splits add up to 0.99, but the bill is 1.0 Hand out leftover paise after the percentage split too
Simplifying balances that don't sum to 0 java.lang.NullPointerException: Cannot invoke "Main$Person.amt()" because "<local6>" is null Check the zero-sum invariant first; stop when either queue is empty
Debts kept pair by pair only 10 friends: pairwise payments 45 Simplify from the balances: simplified 9
One if-else for split types edit it for every new type One SplitStrategy class per type

The programs behind the new rows:

Lossy conversion (a compile error): double rupees = 333.34; followed by long paise = rupees * 100; gives

Main.java:3: error: incompatible types: possible lossy conversion from double to long
    long paise = rupees * 100;                 // mistake: double into a long
                        ^
1 error

Cast vs round, and BigDecimal division:

import java.math.*;
public class Main { public static void main(String[] args) {
    double typed = 1.15;                                         // Ravi types 1.15 rupees
    System.out.println("typed * 100 = " + typed * 100 + ", cast " + (long) (typed * 100) + ", round " + Math.round(typed * 100));
    BigDecimal bill = new BigDecimal("1000.00");
    System.out.println("BigDecimal rounded: " + bill.divide(BigDecimal.valueOf(3), 2, RoundingMode.DOWN));
    System.out.println("BigDecimal exact:   " + bill.divide(BigDecimal.valueOf(3)));
} }
typed * 100 = 114.99999999999999, cast 114, round 115
BigDecimal rounded: 333.33
Exception in thread "main" java.lang.ArithmeticException: Non-terminating decimal expansion; no exact representable decimal result.
    at java.base/java.math.BigDecimal.divide(BigDecimal.java:1783)
    at Main.main(Main.java:7)
  • A cast to long chops off the fraction, so 114.999... becomes 114 and a paisa is lost; Math.round goes to the nearest whole number. That is why ExactSplit uses Math.round.
  • BigDecimal refuses to guess: 1000 / 3 never ends in decimal, so you must give the number of places and a RoundingMode. Even then 3 × 333.33 = 999.99: you still hand out the leftover paisa yourself.

The percentage split's hidden rounding bug: the episode's PercentSplit (section 4) rounds each share on its own and then asks ExactSplit to check the sum. For 1000 rupees that works; for a tiny bill it does not. Same classes as section 4, with this main:

public class Main { public static void main(String[] args) {
    List<String> trio = List.of("Asha", "Ravi", "Neha");
    System.out.println("1000 rupees " + new PercentSplit().split(100000, trio, List.of(33.33, 33.33, 33.34)));
    System.out.println("1 rupee     " + new PercentSplit().split(100, trio, List.of(33.33, 33.33, 33.34)));
} }
1000 rupees [Asha 333.30, Ravi 333.30, Neha 333.40]
Exception in thread "main" java.lang.IllegalArgumentException: exact splits add up to 0.99, but the bill is 1.0
    at ExactSplit.split(Main.java:15)
    at PercentSplit.split(Main.java:22)
    at Main.main(Main.java:26)

100 paise × 33.33% = 33.33 paise, rounded to 33; three times gives 99, not 100. Validation caught it, which is good, but a valid input was refused. The mini project fixes it by sharing out by weight and handing the leftover paise to the first people, just like the equal split.

Simplifying a broken balance sheet: same simplify as section 6, with balances that sum to −100 (a lost 100 somewhere):

        Map<String, Long> typo = Map.of("Asha", 1700L, "Amit", 500L, "Neha", -1300L, "Ravi", -1000L);  // sums to -100: a lost 100
        System.out.println(simplify(typo)); } }
Exception in thread "main" java.lang.NullPointerException: Cannot invoke "Main$Person.amt()" because "<local6>" is null
    at Main.simplify(Main.java:11)
    at Main.main(Main.java:18)

The creditors run out first, so get.poll() returns null, and c.amt() crashes. (<local6> is how Java names a local variable when the class was compiled without debug names; it is c.) Fix: check that balances sum to 0 before simplifying, and loop while (!give.isEmpty() && !get.isEmpty()).

Mini project: a small Splitwise

One runnable program with everything from the episode, in paise:

  • User, Group, Expense, Split records and classes.
  • Four strategies: EqualSplit, ExactSplit, PercentSplit (percent in basis points, 5000 = 50.00%, so no double at all) and the homework's ShareSplit (2 shares for a couple, 1 for a single person).
  • One helper, Money.shareOut, splits by weight and hands out the leftover paise, so equal, percentage and share splits always add up exactly.
  • Validation: positive amount, payer and sharers must be group members, exact sums must match, percentages must sum to 100, shares must be positive.
  • deleteExpense reverses an expense, settleUp records a payment, simplify stops safely when either queue is empty; synchronized methods give one lock per group; a random test of 1000 expenses checks the balances still sum to 0.
import java.util.*;

record User(String id, String name) {}
record Split(User user, long paise) {}

interface SplitStrategy { List<Split> split(long total, List<User> users, List<Long> values); }  // one class per type

class Money {
    static String fmt(long p) { return (p < 0 ? "-" : "") + Math.abs(p) / 100 + "." + String.format("%02d", Math.abs(p) % 100); }
    static List<Long> shareOut(long total, List<Long> weights) {   // by weight, leftover paise to the first people
        long sum = weights.stream().mapToLong(w -> w).sum();
        List<Long> out = new ArrayList<>();  long given = 0;
        for (long w : weights) { long p = total * w / sum;  out.add(p);  given += p; }
        for (int i = 0; given < total; i++, given++) out.set(i, out.get(i) + 1);
        return out;
    }
}

class EqualSplit implements SplitStrategy {
    public List<Split> split(long total, List<User> users, List<Long> values) {
        return new ExactSplit().split(total, users, Money.shareOut(total, Collections.nCopies(users.size(), 1L)));
    }
}
class ExactSplit implements SplitStrategy {      // values: paise for each user
    public List<Split> split(long total, List<User> users, List<Long> values) {
        long sum = values.stream().mapToLong(v -> v).sum();
        if (sum != total) throw new IllegalArgumentException("exact splits add up to " + Money.fmt(sum) + ", bill is " + Money.fmt(total));
        List<Split> out = new ArrayList<>();
        for (int i = 0; i < users.size(); i++) out.add(new Split(users.get(i), values.get(i)));
        return out;
    }
}
class PercentSplit implements SplitStrategy {    // values: basis points, 5000 = 50.00%
    public List<Split> split(long total, List<User> users, List<Long> values) {
        if (values.stream().mapToLong(v -> v).sum() != 10000) throw new IllegalArgumentException("percentages must add up to 100");
        return new ExactSplit().split(total, users, Money.shareOut(total, values)); }
}
class ShareSplit implements SplitStrategy {      // values: shares, a couple = 2, a single person = 1
    public List<Split> split(long total, List<User> users, List<Long> values) {
        if (values.stream().anyMatch(v -> v <= 0)) throw new IllegalArgumentException("every share must be positive");
        return new ExactSplit().split(total, users, Money.shareOut(total, values));
    }
}

record Expense(int id, String what, User paidBy, long amount, List<Split> splits) {}

class Group {
    final String name;  final Set<User> members = new LinkedHashSet<>();
    final Map<Integer, Expense> expenses = new LinkedHashMap<>();
    final Map<User, Long> balance = new LinkedHashMap<>();        // + gets back, - owes
    private int nextId = 1;
    Group(String name, User... us) { this.name = name;  for (User u : us) { members.add(u);  balance.put(u, 0L); } }

    synchronized Expense addExpense(String what, User paidBy, long amount, List<User> users, SplitStrategy how, List<Long> values) {
        if (amount <= 0) throw new IllegalArgumentException(what + ": amount must be positive");
        if (!members.contains(paidBy) || !members.containsAll(users)) throw new IllegalArgumentException(what + ": not a group member");
        Expense e = new Expense(nextId++, what, paidBy, amount, how.split(amount, users, values));
        apply(e, +1);  expenses.put(e.id(), e);  return e; }
    synchronized void deleteExpense(int id) {                     // reverse its effect
        Expense e = expenses.remove(id);
        if (e == null) throw new IllegalArgumentException("no expense " + id);
        apply(e, -1); }
    synchronized void settleUp(User from, User to, long paise) {  // a real payment: an expense in reverse
        balance.merge(from, paise, Long::sum);  balance.merge(to, -paise, Long::sum); }
    private void apply(Expense e, int sign) {
        for (Split s : e.splits()) { balance.merge(e.paidBy(), sign * s.paise(), Long::sum);
                                     balance.merge(s.user(), -sign * s.paise(), Long::sum); } }
    long total() { return balance.values().stream().mapToLong(b -> b).sum(); }   // must always be 0

    List<String> simplify() {                                     // biggest debtor pays biggest creditor
        record P(User u, long amt) {}
        Comparator<P> most = (a, b) -> Long.compare(b.amt(), a.amt());
        PriorityQueue<P> give = new PriorityQueue<>(most), get = new PriorityQueue<>(most);
        balance.forEach((u, b) -> { if (b < 0) give.add(new P(u, -b)); else if (b > 0) get.add(new P(u, b)); });
        List<String> pay = new ArrayList<>();
        while (!give.isEmpty() && !get.isEmpty()) {
            P d = give.poll(), c = get.poll();  long x = Math.min(d.amt(), c.amt());
            pay.add(d.u().name() + " pays " + c.u().name() + " " + Money.fmt(x));
            if (d.amt() > x) give.add(new P(d.u(), d.amt() - x));
            if (c.amt() > x) get.add(new P(c.u(), c.amt() - x));
        }
        return pay;
    }
    String sheet() {
        StringBuilder sb = new StringBuilder();
        balance.forEach((u, b) -> sb.append(u.name()).append(" ").append(Money.fmt(b)).append("  "));
        return sb.toString().trim();
    }
}

public class Main {
    public static void main(String[] args) {
        User asha = new User("u1", "Asha"), ravi = new User("u2", "Ravi"), neha = new User("u3", "Neha"), amit = new User("u4", "Amit");
        List<User> all = List.of(asha, ravi, neha, amit);
        Group g = new Group("Goa trip", asha, ravi, neha, amit);

        g.addExpense("hotel", asha, 400000, all, new EqualSplit(), null);
        g.addExpense("dinner", ravi, 100000, List.of(asha, ravi, neha), new EqualSplit(), null);
        g.addExpense("cab", neha, 80000, all, new ExactSplit(), List.of(20000L, 20000L, 30000L, 10000L));
        g.addExpense("tickets", amit, 120000, List.of(asha, ravi, neha), new PercentSplit(), List.of(5000L, 3000L, 2000L));
        Expense villa = g.addExpense("villa", asha, 100000, all, new ShareSplit(), List.of(2L, 1L, 1L, 1L));
        System.out.println("villa splits: " + villa.splits().stream().map(s -> s.user().name() + " " + Money.fmt(s.paise())).toList());
        System.out.println("balance sheet: " + g.sheet() + "  | sum " + g.total());
        System.out.println("simplified:    " + g.simplify());

        g.settleUp(ravi, asha, 50000);
        System.out.println("after Ravi pays Asha 500.00: " + g.sheet());
        g.deleteExpense(villa.id());
        System.out.println("villa deleted: " + g.sheet() + "  | sum " + g.total());

        for (Runnable bad : List.<Runnable>of(
                () -> g.addExpense("snacks", ravi, 50000, List.of(asha, neha), new ExactSplit(), List.of(20000L, 20000L)),
                () -> g.addExpense("boat", neha, 90000, all, new PercentSplit(), List.of(2500L, 2500L, 2500L, 2000L)),
                () -> g.addExpense("fuel", new User("u9", "Kiran"), 30000, all, new EqualSplit(), null),
                () -> g.deleteExpense(42)))
            try { bad.run(); } catch (IllegalArgumentException e) { System.out.println("refused: " + e.getMessage()); }

        Random r = new Random(7);                                   // property test: balances always sum to 0
        Group big = new Group("big");  List<User> ten = new ArrayList<>();
        for (int i = 0; i < 10; i++) { User u = new User("f" + i, "F" + i);  ten.add(u);  big.members.add(u);  big.balance.put(u, 0L); }
        SplitStrategy[] kinds = { new EqualSplit(), new ShareSplit() };
        for (int i = 0; i < 1000; i++) {
            List<User> who = new ArrayList<>(ten);  Collections.shuffle(who, r);  who = who.subList(0, 2 + r.nextInt(9));
            int k = r.nextInt(2);
            List<Long> vals = k == 0 ? null : who.stream().map(u -> 1L + r.nextInt(3)).toList();
            big.addExpense("e" + i, ten.get(r.nextInt(10)), 1 + r.nextInt(500000), who, kinds[k], vals);
        }
        System.out.println("1000 random expenses: balances sum to " + big.total() + ", simplified payments " + big.simplify().size());
    }
}

Real output:

villa splits: [Asha 400.00, Ravi 200.00, Neha 200.00, Amit 200.00]
balance sheet: Asha 2466.66  Ravi -1093.33  Neha -1273.33  Amit -100.00  | sum 0
simplified:    [Neha pays Asha 1273.33, Ravi pays Asha 1093.33, Amit pays Asha 100.00]
after Ravi pays Asha 500.00: Asha 1966.66  Ravi -593.33  Neha -1273.33  Amit -100.00
villa deleted: Asha 1366.66  Ravi -393.33  Neha -1073.33  Amit 100.00  | sum 0
refused: exact splits add up to 400.00, bill is 500.00
refused: percentages must add up to 100
refused: fuel: not a group member
refused: no expense 42
1000 random expenses: balances sum to 0, simplified payments 9

Checking Asha by hand: hotel +3000.00 (paid 4000, share 1000), dinner −333.34 (she got the leftover paisa), cab −200.00, tickets −600.00 (50% of 1200), villa +600.00 (paid 1000, share 2 of 5 = 400): +2466.66.

  • The sheet sums to 0 after every step, even after a delete. Simplified: 3 payments, all to Asha, the only creditor.
  • Deleting the villa takes Asha down by exactly 600.00 and gives Amit back 200.00, so Amit flips from −100 to +100.
  • All four bad inputs are refused before any balance changes; 1000 random expenses still sum 0, with 9 payments for 10 people.

Practice

1. Split 100 rupees equally among 3 people in paise. What does each pay?

Answer

10000 paise / 3 = 3333 remainder 1. The first person pays 3334, the other two 3333: 33.34 + 33.33 + 33.33 = 100.00.

2. Add a ShareSplit to the episode's Split/SplitStrategy code (values are shares like 2, 1, 1).

Answer
class ShareSplit implements SplitStrategy {
    public List<Split> split(long total, List<String> users, List<Double> values) {
        double shares = values.stream().mapToDouble(d -> d).sum();
        if (shares <= 0) throw new IllegalArgumentException("shares must be positive");
        List<Split> out = new ArrayList<>();  long given = 0;
        for (int i = 0; i < users.size(); i++) { long p = (long) (total * values.get(i) / shares);
            out.add(new Split(users.get(i), p));  given += p; }
        for (int i = 0; given < total; i++, given++)          // leftover paise to the first people
            out.set(i, new Split(out.get(i).user(), out.get(i).paise() + 1));
        return out; } }

No other class changes: that is the point of the Strategy pattern. The mini project's ShareSplit does the same with whole-number weights through Money.shareOut.

3. Write deleteExpense for the episode's Group (section 5).

Answer

Do exactly what add did, with every sign flipped: for each share, balance.merge(paidBy, -share, Long::sum) and balance.merge(user, share, Long::sum), and for the pairwise debts call owe(paidBy, user, share) (the reverse direction), which nets it away. Store expenses by id so you can find the one to delete. The mini project keeps a map of expenses and calls apply(e, -1).

4. Print each user's own "you owe" list from the owes map.

Answer

Keys look like "Ravi->Asha". For a user u, keep the entries whose key starts with u + "->" (what u owes) and those that end with "->" + u (what u is owed). Split each key with k.split("->") to get the two names; for Ravi, with section 5's six debts (before settling up), that prints Neha owes Ravi 100, Ravi owes Amit 300 and Ravi owes Asha 700. A record Pair(String from, String to) as the key is cleaner than a string, and avoids bugs when a name contains ->.

5. Balances: P +900, Q −400, R −300, S −200. Run the greedy simplification by hand.

Answer

Q pays P 400 (P still +500). R pays P 300 (P +200). S pays P 200. 3 payments for 4 people (n − 1). With one creditor, everyone simply pays them.

Quick quiz

After a trip: Kiran +600, Meera +200, Dev −500, Tara −300. Using greedy (biggest debtor pays biggest creditor), how many payments? (a) 2 (b) 3 (c) 4 (d) 6

Answer

(b) 3. Dev pays Kiran 500 (Dev done, Kiran still +100). Tara pays Meera 200 (Meera done, Tara still −100). Tara pays Kiran 100 (both done). Three payments: at most n − 1 = 3 for four people. Pair by pair could have needed up to 6.

Interview questions

  1. What are the main classes of an expense sharing app? User, Group, Expense, Split, a SplitStrategy per split type, and the Group's balance sheet.
  2. How do you store money? As whole paise in a long (or BigDecimal), never as a double; integer division also loses the remainder unless you hand it out.
  3. Who gets the leftover paise? A fixed rule, such as the first people in the list; the splits must add up to the bill exactly.
  4. How do you support equal, exact and percentage splits? The Strategy pattern: one SplitStrategy class per type, each validating its own input.
  5. What validation do you do? Exact amounts sum to the bill, percentages sum to 100, amounts are positive, payer and sharers are group members; refuse before changing any balance.
  6. What is the balance sheet? One number per user: plus if they get money back, minus if they owe. It always sums to 0.
  7. How do you show who owes whom? Keep one debt per pair and net it both ways: 1000 one way and 300 back is 700.
  8. How does settle up work? A real payment recorded like an expense in reverse: the payer's balance goes up, the receiver's goes down.
  9. How do you minimize the number of transactions? Greedy from the balances: biggest debtor pays biggest creditor the smaller amount, repeat; at most n − 1 payments. The exact minimum is a much harder problem.
  10. How do you test it? Small hand-checked cases plus random expenses, checking that balances always sum to 0.

Glossary

Term Meaning, with an example
Expense sharing Friends pay for things at different times and later even it out: Asha pays the hotel, the others pay her back their part
User One person in the app: User("u1", "Asha")
Group A set of users (its members) who share costs: "Goa trip" with Asha, Ravi, Neha, Amit
Expense One bill: what, who paid, how much, how split: hotel, 4000, Asha, equal by 4
Split One person's share of one expense: Ravi's split of the hotel is 1000
Split types The ways to split a bill: equal, exact, percentage (and by shares)
Equal split Everyone pays the same, leftover paise to the first people: 333.34, 333.33, 333.33
Exact split Each amount is typed in and must sum to the bill: 500, 300, 200 of 1000
Percentage split Each share is a percent of the bill, summing to 100: 50 / 30 / 20 % of 1200 = 600, 360, 240
Share split Shares by weight: a couple 2, a single person 1: 1000 at 2 : 1 : 1 : 1 = 400, 200, 200, 200
SplitStrategy Our interface with one method, split(total, users, values); one class per split type
Strategy pattern Put each way of doing a job in its own class behind one interface (episode 34)
Open-closed principle Add new behaviour by adding code, not by editing code that works: a new split type is a new class
Validation of splits Checking a split before accepting it: exact amounts sum to the bill, percentages to 100
IllegalArgumentException Java's exception for an unacceptable argument: snacks: shares add up to 400, but the bill is 500
Paise 1/100 of a rupee; we store money as whole paise: 1000 rupees = 100000
long Java's 64-bit whole number type; exact for money in paise
Integer division int / int drops the remainder (% gives it): 1000 / 3 = 333, 1000 % 3 = 1
Leftover paise The remainder handed out one paisa at a time so the splits sum to the bill
double / floating point A number with a fraction stored in binary (base two); 0.1 can't be stored exactly: 0.1 + 0.2 = 0.30000000000000004
BigDecimal Java's exact decimal number class; division needs a scale and a RoundingMode
Rounding vs casting Math.round(114.999...) = 115; (long) 114.999... = 114
Basis point 1/100 of a percent: 50.00% = 5000
Lossy conversion Putting a double into a long can lose the fraction, so Java refuses without a cast or Math.round
record A short Java class for plain data: record Split(String user, long paise)
Balance sheet One number per user for the group: + gets money back, − owes: Asha +1700, Neha −1300
Zero-sum / invariant All balances always add up to 0, because money only moves between friends; a sum that isn't 0 means a bug
Debtor Someone with a negative balance, who owes: Neha −1300
Creditor Someone with a positive balance, who is owed: Asha +1700
Who owes whom The debt for each pair of friends: Ravi->Asha=700
Netting Cancelling debts in both directions: Ravi owes Asha 1000, Asha owes Ravi 300 → Ravi owes Asha 700
Settle up Recording a real payment, like an expense in reverse: Ravi pays Asha 700 on UPI
Debt simplification Replacing many pairwise debts with a few payments that bring every balance to 0: Goa 6 → 3
Minimizing transactions Another name for debt simplification: as few payments as possible
Greedy algorithm Always take the best-looking step now: biggest debtor pays biggest creditor
n − 1 bound Each greedy payment clears at least one person, so n people need at most n − 1 payments
Priority queue A collection whose poll() returns the top item by a rule: PriorityQueue<Person>
Comparator A rule for ordering two items: (a, b) -> Long.compare(b.amt(), a.amt()) puts the biggest first
Map.merge Add to a stored value, or store it if new: balance.merge("Asha", 1000L, Long::sum)
TreeMap A map that keeps its keys sorted: the balance sheet prints in alphabetical order
Seed The starting number of a random generator; new Random(7) gives the same numbers every run
Random / property test Many random inputs, checking an invariant each time: 1000 expenses, balances still sum to 0
synchronized Java keyword: only one thread at a time runs this method on this object (one lock per group)
NullPointerException Calling a method on null: get.poll() returned null when the balances didn't sum to 0
UPI India's instant phone-to-phone bank payment system; used here only as the example of paying a friend

Summary

  • An expense sharing app has users, groups, expenses and splits.
  • Integer division lost a rupee (collected 999 of 1000) and a double couldn't even add 0.1 and 0.2. Store money as paise in a long and hand out the leftover paise, so every split adds up to the bill exactly.
  • Equal, exact and percentage splits are one SplitStrategy class each, and each validates its input: exact splits add up to 900.0, but the bill is 1000.0.
  • The balance sheet always sums to 0; who owes whom is netted per pair; settle up is an expense in reverse.
  • Debt simplification (minimizing transactions) uses the balances only: biggest debtor pays biggest creditor, at most n − 1 payments. Goa: 6 → 3; ten friends: 45 → 9.
  • Next episode: design a hotel booking system: rooms, an availability calendar, and never giving one room to two guests on the same night.