Design Splitwise (Low Level Design)

Problem Statement

Four friends go on a trip. One person books the hotel, another pays for dinner, a third pays for the cab. Nobody wants to stop at every shop and settle the bill. So they write everything down and sort it out at the end.

Splitwise is the app that does the writing down. You add an expense, say who paid and how it should be shared, and the app keeps a running total of who owes whom. At the end it tells everyone what to pay.

In this note we build the core of it in plain Java: users, groups, expenses, three ways to split a bill, a balance sheet, and a step that cuts down the number of payments.

Questions to Ask First

In an interview, spend the first two minutes on questions. It shows you think before you type. These are the ones I would ask, with the answer I would assume if the interviewer shrugs.

Requirements

What the code must do:

• Add users and put them in a group.
• Add an expense: who paid, how much, who shares it, and how.
• Split three ways: equally, by exact amount for each person, or by percent.
• Keep a balance sheet: who owes whom, right now.
• Let someone pay a debt back (settle up).
• Reduce the list of payments, so the group makes few transfers.

What the code must not get wrong:

• Money is never a double. We store whole paise (100 paise is 1 rupee).
• The shares of an expense always add up to the total. Not one paise lost.
• Bad input is rejected loudly: percents that do not add to 100, people outside the group.

Core Classes

Eleven small classes and a Main. User, Expense and Transfer are Java records, which means they just hold data and Java writes the boring parts for us (constructor, getters, equals).

How the Design Works

Money is a whole number

Try this in any language: add 0.1 and 0.2 and you do not get exactly 0.3. Computers store decimals in a way that is slightly off. For a game score that is fine. For money it is how you end up with a bill that is short by one paisa and nobody can find it.

So every amount in this code is a long that counts paise. Rs 250.00 is 25000. The only place we turn it back into rupees is when we print:

public static String format(long paise) {
    String sign = paise < 0 ? "-" : "";
    long abs = Math.abs(paise);
    return String.format("%sRs %d.%02d", sign, abs / 100, abs % 100);
}

Integer division never gives you 0.333. It gives you a whole number and a remainder, and that remainder is the thing we have to handle on purpose.

The split types are one interface

A bill can be split in three ways today and maybe five ways next year. If Group had an if (type == EQUAL) ... else if (type == EXACT) inside it, every new way would mean opening Group and risking a break. Instead there is one small interface:

public interface SplitStrategy {

    /** Returns how many paise each person owes. The shares must add up to totalPaise. */
    Map<User, Long> split(long totalPaise);

Each split type knows its own people. EqualSplit gets a list of users. ExactSplit gets a map of user to paise. PercentSplit gets a map of user to percent. The group only calls split(total) and gets back the shares.

Equal split and the leftover paise

Split Rs 100.00 between three people. That is 10000 paise. 10000 / 3 is 3333 with 1 left over. If you give everyone 3333, the shares add up to 9999, and one paisa has vanished.

The fix is to hand out the leftover one paisa at a time, starting from the first person. Nobody pays more than one paisa extra.

@Override
public Map<User, Long> split(long totalPaise) {
    long each = totalPaise / participants.size();
    long leftover = totalPaise % participants.size();
    Map<User, Long> shares = new LinkedHashMap<>();
    for (User user : participants) {
        shares.put(user, each);
    }
    SplitStrategy.spreadLeftover(shares, leftover);
    return shares;
}

The helper that gives out the leftover sits in the interface, because percent split needs the same trick:

static void spreadLeftover(Map<User, Long> shares, long leftoverPaise) {
    long remaining = leftoverPaise;
    for (Map.Entry<User, Long> share : shares.entrySet()) {
        if (remaining == 0) {
            return;
        }
        share.setValue(share.getValue() + 1);
        remaining--;
    }
}

Giving the extra paisa to the first person is a little unfair if the same person is always first. Real apps often rotate it. Say that out loud and move on.

Exact and percent split

Exact split is the easy one. You are told the amounts. The only job is to check they add up to the bill. If they do not, throw an error instead of guessing.

long sum = amounts.values().stream().mapToLong(Long::longValue).sum();
if (sum != totalPaise) {
    throw new IllegalArgumentException("Exact amounts add up to " + Money.format(sum)
            + " but the expense is " + Money.format(totalPaise));
}

Percent split rounds each share down, then hands out what is left, just like equal split:

long share = totalPaise * entry.getValue() / 100; // rounds down
shares.put(entry.getKey(), share);
given += share;

The constructor refuses percents that do not add up to 100. Because every share loses less than one paisa when rounded down, the leftover is always smaller than the number of people, so one paisa each is enough.

The balance sheet remembers who owes whom

Say Ben owes Asha Rs 250 for the hotel. Later Asha owes Ben Rs 33.34 for dinner. Splitwise does not show both. It shows one line: Ben owes Asha Rs 216.66. The two debts cancel against each other.

BalanceSheet does exactly that. It keeps a map of "a owes b", and whenever a new debt arrives it works out the net result between those two people:

public void addDebt(User debtor, User creditor, long amountPaise) {
    if (debtor.equals(creditor) || amountPaise == 0) {
        return;
    }
    long net = owed(debtor, creditor) + amountPaise - owed(creditor, debtor);
    if (net >= 0) {
        set(debtor, creditor, net);
        set(creditor, debtor, 0);
    } else {
        set(debtor, creditor, 0);
        set(creditor, debtor, -net);
    }
}

The first if is there because when you pay for something that you also share, you do not owe yourself. Settling up uses the same method in reverse. If Ben pays Asha Rs 100, that is the same as Asha now owing Ben Rs 100, which cancels part of his debt:

/** Paying someone back is the same as them now owing you that amount. */
public void settle(User payer, User receiver, long amountPaise) {
    addDebt(receiver, payer, amountPaise);
}

Putting an expense in

Group.addExpense is the only place where all the pieces meet. It checks everyone is a member, asks the strategy for the shares, builds the Expense, and then records one debt per person.

public Expense addExpense(String description, User paidBy, long totalPaise, SplitStrategy strategy) {
    requireMember(paidBy);
    Map<User, Long> shares = strategy.split(totalPaise);
    shares.keySet().forEach(this::requireMember);

    Expense expense = new Expense(description, paidBy, totalPaise, shares);
    expenses.add(expense);
    shares.forEach((user, share) -> balanceSheet.addDebt(user, paidBy, share));
    return expense;
}

The Expense record has its own check that the shares add up to the total. So even if someone writes a buggy new split type later, the bad expense never reaches the balance sheet.

Simplifying debts

After a week, the balance sheet in our example has six lines. Six payments for four people feels silly. Can we do fewer?

Here is the idea. Forget who owed whom for which bill. Only look at where each person ends up. Add up everything: what others owe you, minus what you owe others. That is your net balance. Some people end up positive (they should receive money), some negative (they should pay), and the totals of both sides are equal.

Now do the simple thing. Take the person who is owed the most and the person who owes the most. Let the debtor pay the creditor as much as possible. One of them is now done (or both). Repeat until nobody is left.

while (!creditors.isEmpty() && !debtors.isEmpty()) {
    Balance creditor = creditors.poll();
    Balance debtor = debtors.poll();
    long amount = Math.min(creditor.paise(), debtor.paise());
    transfers.add(new Transfer(debtor.user(), creditor.user(), amount));
    if (creditor.paise() > amount) {
        creditors.add(new Balance(creditor.user(), creditor.paise() - amount));
    }
    if (debtor.paise() > amount) {
        debtors.add(new Balance(debtor.user(), debtor.paise() - amount));
    }
}

The two queues are priority queues, which means poll() always hands you the biggest amount first. Each round finishes at least one person, so with n people with a non-zero balance you get at most n minus 1 payments.

Now the honest part. This is greedy, and greedy is not always the best. Finding the true smallest number of payments is a hard problem (it is the same family as splitting a pile of numbers into groups that each add to zero).

Here is a case where greedy loses. Asha is owed Rs 10 and Ben is owed Rs 7. Chitra owes Rs 7, Dev owes Rs 6 and Esha owes Rs 4. Look closely and you can see two separate little groups: Ben and Chitra cancel each other exactly (1 payment), and Asha, Dev and Esha cancel as another group (2 payments). That is 3 payments in total. I ran the real DebtSimplifier on these numbers and it gives 4: Chitra pays Asha 7, Dev pays Ben 6, Esha pays Asha 3, Esha pays Ben 1. It always pairs the biggest with the biggest, and it cannot see the hidden groups.

For a study project and for most interviews, greedy is a fine answer as long as you say what it is. Do not claim it is optimal.

Patterns Used and Why

Only one pattern is really doing work here.

Strategy. The three split types are three classes behind one interface. Group never asks "which type is this?". Adding a fourth type, say "by shares" (you get 2 shares, I get 1), means one new class and zero changes to Group, BalanceSheet or Expense. That is the single best thing to say in this interview.

Two smaller choices are worth naming, but they are not patterns:

• DebtSimplifier is a plain class with one static method. It has no state, so there is nothing to build or inject.
• Expense, User and Transfer are immutable records. Once an expense is written, nobody can quietly change it.

I did not add a Factory for creating split strategies, because nothing here needs to choose a strategy from a string. If you later read the split type from a JSON request, that is when a small factory starts to pay for itself.

Walk Through One Full Example

Four friends, one group called "Goa trip": Asha, Ben, Chitra and Dev. This is the real output of Main.

== Adding expenses ==
Hotel paid by Asha (Rs 1000.00): Asha=Rs 250.00 Ben=Rs 250.00 Chitra=Rs 250.00 Dev=Rs 250.00
Dinner paid by Ben (Rs 100.00): Asha=Rs 33.34 Ben=Rs 33.33 Chitra=Rs 33.33
Cab paid by Chitra (Rs 600.00): Asha=Rs 150.00 Ben=Rs 150.00 Chitra=Rs 100.00 Dev=Rs 200.00
Snacks paid by Dev (Rs 400.01): Asha=Rs 200.01 Ben=Rs 80.00 Dev=Rs 120.00

Look at three things. In the dinner, Asha pays Rs 33.34 and the other two pay Rs 33.33, so the three add up to exactly Rs 100.00. In the cab, the amounts were typed by hand (exact split). In the snacks, the percents were 50, 20 and 30. Half of 40001 paise is 20000.5, which rounds down to 20000, so the one leftover paisa goes to Asha: Rs 200.01.

Now the balance sheet. Each line is one person owing another, after the debts from all four bills were netted.

== Who owes whom (before simplifying) ==
Ben pays Asha Rs 216.66
Ben pays Chitra Rs 116.67
Ben pays Dev Rs 80.00
Chitra pays Asha Rs 100.00
Dev pays Asha Rs 49.99
Dev pays Chitra Rs 200.00

Check one line by hand. The hotel made Ben owe Asha Rs 250.00. The dinner made Asha owe Ben Rs 33.34. Net: Ben owes Asha Rs 216.66. Matches.

Six payments. Now the net balance per person, positive meaning "gets money":

== Net balance per person ==
Ben: -Rs 413.33
Asha: Rs 366.65
Chitra: Rs 216.67
Dev: -Rs 169.99

The two people who owe add up to Rs 583.32 and the two people who are owed add up to Rs 583.32. That equal total is always true, and it is a nice sanity check to mention.

Greedy goes like this. Ben owes the most, Asha is owed the most. Ben pays Asha Rs 366.65, which finishes Asha. Ben still owes Rs 46.68. Next, Dev owes Rs 169.99 and Chitra is owed Rs 216.67. Dev pays Chitra Rs 169.99, which finishes Dev. Chitra is still owed Rs 46.68. Last, Ben pays Chitra Rs 46.68. Everyone is at zero.

== Simplified debts ==
Ben pays Asha Rs 366.65
Dev pays Chitra Rs 169.99
Ben pays Chitra Rs 46.68

Six payments became three. Then Ben pays Asha Rs 100.00 in cash, and we look again:

== Ben pays Asha Rs 100.00, then we look again ==
Ben pays Asha Rs 266.65
Dev pays Chitra Rs 169.99
Ben pays Chitra Rs 46.68

Finally the code rejects bad input instead of guessing:

== Bad input is rejected ==
Rejected: Exact amounts add up to Rs 9.00 but the expense is Rs 10.00
Rejected: Stranger is not in the group Goa trip

Edge Cases

• Total does not divide evenly. Handled: leftover paise are handed out one by one.
• Exact amounts do not add up to the bill. Rejected with a clear message.
• Percents do not add up to 100. Rejected in the PercentSplit constructor.
• The payer is also in the split. Their own share is skipped in the balance sheet, so nobody owes themselves.
• The payer is not in the split at all (Dev paying for a dinner he did not eat). Allowed, and it works naturally.
• Someone outside the group appears in the split. Rejected.
• Someone settles more than they owe. The direction flips and the other person now owes them the difference. Real Splitwise does the same, but in an interview you may want to say it out loud, because some people expect an error here.

Follow Up Questions an Interviewer May Ask

"How would you edit or delete an expense?"

Right now the group keeps the list of expenses, but the balance sheet is only updated, never rebuilt. To support edits, I would replay all expenses (and settlements) from the list into a fresh balance sheet. It is slower but simple and impossible to get out of sync. Optimise only if groups get huge.

"Can you get the true minimum number of payments?"

Not cheaply. You would search for the biggest number of sub-groups whose balances add up to zero. Each such group of k people needs k minus 1 payments, so more groups means fewer payments. That search is exponential. For a small group (say up to 15 people) a bitmask dynamic programming solution works. Beyond that, greedy is what people use.

"How do you support decimals in percent, like 33.33 percent?"

Store percents in hundredths, so 33.33 percent is the integer 3333 and the total must be 10000. The rest of the code stays the same.

"Is it thread safe?"

No. Two people adding expenses at the same moment could break the balance sheet. The easy fix is one lock per group, since groups do not touch each other. In a real app, the database would do this job with transactions.

"How would you store this?"

Tables for users, groups, group members, expenses and expense shares. The balance sheet is not stored. It is derived from the expense and settlement rows.

Common Mistakes

Using double for money. The most common one, and an instant red flag for the interviewer.

Dividing and forgetting the remainder. Rs 100 split three ways as 100 / 3 * 3 gives 99. Someone must pay the missing paisa.

Putting a big switch on the split type inside Group or Expense. It works on day one and hurts on day thirty.

Letting a person owe themselves. If the payer is part of the split, skip their own share.

Calling the greedy simplifier "optimal". Say it is a good, quick approach and not always the minimum.

Skipping validation. A split that does not add up to the total is the bug you will meet first in real life.

Where This Is Simplified

Being honest about the gaps:

• Everything is in memory. Nothing is saved.
• No thread safety.
• Users are plain objects with an id and a name. There is no sign up, no check that ids are unique.
• One currency, one payer per expense, whole percents only.
• Expenses cannot be edited or deleted.
• Group does a bit of everything. In a bigger system I would split it into a group service and a repository.
• The leftover paisa always goes to the first person in the list.

How to Run

From the repo root (Java 17 or newer):

javac --release 17 -d /tmp/splitwise-out $(find src/LLD/Splitwise/src -name '*.java')
java -cp /tmp/splitwise-out com.blueprint.lld.splitwise.Main

The code lives under src/LLD/Splitwise/src/com/blueprint/lld/splitwise/.