DSA & System Design
BackendMedium35 min

Design Splitwise (LLD)

Split bills four ways in integer cents with a fixed leftover rule, net the debts per pair, simplify them greedily, and keep settle-up race-free.

Related:Design a Parking Lot (LLD)Design an ATM (LLD) Explain it back
Say it in 30 seconds
  • 1001 = 334+334+333equal split of 1001 cents among three
  • n - 1most payments the greedy simplify needs
  • 1 lockper group, around check and subtract
Show what to say

“I'd keep money in integer cents and make each split type a strategy that turns an amount into one share per person, with the leftover cents handed out in a fixed order. Shares become debts to the payer in a ledger that nets each pair. Simplify matches the biggest debtor to the biggest creditor, and settle-up checks and subtracts under one group lock.”

Trade-offs

  • Strategy per split vs one function: open to new split types, at the cost of an interface for a few lines.
  • Greedy simplify vs the minimum: fast and repeatable, but the true fewest payments is NP-hard.
  • Pair debts vs net balances only: pairs show who owes whom, at the cost of two numbers to keep in step.

Bring it up before they ask

Two people tapping settle-up on the same debt must not both pay, so the check and the subtract happen in one locked step.

0 of 0 sections ticked
30-second answer

Turn each bill into one share per person with a swappable split strategy, record each share as a debt to the payer in a ledger that nets opposite debts, and keep all money in integer cents with a fixed rule for the leftover cent. Simplifying debts is a greedy match of the biggest debtor to the biggest creditor.

Functional

  • Groups of members add expenses paid by one member
  • Split a bill equally, by exact amounts, by percent, or by shares
  • Show who owes whom, and each member's net balance
  • Settle up a debt, partly or fully
  • Simplify debts into fewer payments
  • Notify members of new expenses and settlements

Non-functional

  • Shares always add up to the bill, to the cent
  • The same input always gives the same split
  • A rejected expense changes nothing
  • Two settle-ups cannot both pay the same debt
  • New split types need no change to the group or the ledger

Out of scope

  • Currencies and exchange rates (a follow-up)
  • Accounts, login and payments
  • Recurring expenses

A low-level design (LLD) question where the classes are easy and the money is not. The test is whether you handle the stray cent and the races.

New to this? Read Swap behaviour first.

Scope and interface

Read more · 156 words
  • Which split types: equal only, or exact, percent and shares too?
  • Is money in one currency? Who rounds, and how?
  • May the payer be outside the participants?
  • Is a debt tracked per pair, or only as a net balance per person?
  • Do we only show balances, or also suggest fewer payments?

The public interface:

CallReturnsNotes
addExpense(payer, amount, type, users, data)Shares, or a reasonValidated before anything is written
settleUp(from, to, cents)ok, or a reasonNever more than is owed
owes(from, to)CentsNetted per pair
balances()Net cents per memberSums to 0
simplify()Transfers [from, to, cents]At most n - 1
on(listener)Hears expense and settled

What it remembers:

  • members and the list of expenses.
  • owed: for each ordered pair, cents one member owes the other. At most one direction per pair is non-zero.
  • Nothing else: balances and the simplified plan are computed from owed when asked.

Build the design in stages

Step through: the group and its expenses, then the ledger, then the split strategy, then new splits, then observers. Green marks what the latest stage added.

Stage 1 of 5

A group and its expenses

A group knows who belongs to it and keeps a list of expenses. Each expense has one payer, an amount in cents, and a share for every participant.

Splitwise class diagramA Group owns its members, its expenses and a Ledger. When an expense arrives, the Group picks a SplitStrategy by type (equal, exact, percent or shares) to turn one amount into one share per person, then records each share in the Ledger as a debt to the payer. Listeners observe expenses and settlements.Groupmembers: Setexpenses: Expense[]lock: one per groupaddExpense(payer, amount, type, users, data)settleUp(from, to, cents)on(listener)Expensepayeramount: centstypeshares: cents per user0..*

A Group owns its members, its expenses and a Ledger. When an expense arrives, the Group picks a SplitStrategy by type (equal, exact, percent or shares) to turn one amount into one share per person, then records each share in the Ledger as a debt to the payer. Listeners observe expenses and settlements.

  • ◆ composition (owns)
  • ◇ aggregation
  • △ inheritance / implements (dashed)
  • → association · ⇢ dependency

Splitting the bill

Each split type has one job: turn an amount and a list of people into one share each, or say the data is invalid.

Read more · 105 words

That is a Strategy. The group looks the type up by name, so it has no if (type === ...) ladder.

The cent problem is the real test. Split 1001 cents three ways: each floor is 333, leaving 2. Hand the leftover out one cent each to the first people, in the order given. Shares are now 334, 334, 333 and always add to 1001.

Play the add-expense diagram to see one expense flow through the strategy and the ledger.

When this is over-engineering. If the interviewer only asked for equal splits, a plain function is enough. Add the interface when the second split type shows up.

const shares = weights.map(w => Math.floor((amount * w) / total));
for (let i = 0, left = amount - sum(shares); left > 0; i++, left--) shares[i]++;

Press Play to watch it run · 7 steps

The group validates the participants, asks the split strategy for shares, and only then writes to the ledger. A bad expense is rejected before anything changes. After the lock is released, listeners are told.

Ana pays 1001 for a dinner of threeThe group validates the participants, asks the split strategy for shares, and only then writes to the ledger. A bad expense is rejected before anything changes. After the lock is released, listeners are told.addExpense(ana, 1001, equal, [ana, ben, cam])group lock taken; members checkedalt [valid]split(1001, users, [])[334, 334, 333]add(ben, ana, 334)add(cam, ana, 333)lock releasedexpense recordedok, shares
  • Client
  • Service
  • Worker
  • Database
  • Pub/Sub
Text description
  1. Ana → Group: addExpense(ana, 1001, equal, [ana, ben, cam])
  2. Group → SplitStrategy: split(1001, users, [])
  3. SplitStrategy replies to Group: [334, 334, 333]
  4. Group → Ledger: add(ben, ana, 334)
  5. Group → Ledger: add(cam, ana, 333)
  6. Group sends (async) to Listener: expense recorded
  7. Group replies to Ana: ok, shares

Simplifying debts

First net everyone: add up what they are owed and subtract what they owe. Nets always sum to 0.

Read more · 95 words

Then repeat: take the biggest debtor and the biggest creditor, move the smaller of the two amounts, and drop whoever reaches 0. Break ties by name so the answer repeats.

Each transfer clears at least one person, so n people need at most n - 1 transfers. The true minimum is NP-hard in general, so say so and keep the greedy answer.

Example: Ana owes Ben 10 and Ben owes Cam 10. The pairs show two debts, but the nets show Ana owing 10 and Cam owed 10, so one payment Ana to Cam settles both.

Threads and races

Put one lock on each group. Every method that reads or changes the ledger takes it.

Read more · 59 words

The dangerous one is settleUp. If it reads the debt and subtracts in two steps, two taps both see 100 and both pay. Do the check and the subtract in one locked step.

Run listeners after the lock is released, so a slow notification cannot block the group.

Open the settle-up branches to see the second racer lose cleanly.

Press Play to watch it run · 4 steps

Settling checks the debt and subtracts from it in one locked step. Two people who both try to pay the same 100 cannot both succeed: the second finds the debt already gone. Pick a branch to see each outcome.

Settling up while someone else does tooSettling checks the debt and subtracts from it in one locked step. Two people who both try to pay the same 100 cannot both succeed: the second finds the debt already gone. Pick a branch to see each outcome.Ben owes Ana 100settleUp(ben, ana, 100)group lock takensettle(ben, ana, 100)alt [debt is there]true, now 0ok
  • Client
  • Service
  • Database
Text description
  1. Ben → Group: settleUp(ben, ana, 100)
  2. Group → Ledger: settle(ben, ana, 100)
  3. Ledger replies to Group: true, now 0
  4. Group replies to Ben: ok

Step-by-step answer

In one line each:

Read more · 196 words

  1. Clarify

    Split types, rounding, currency, simplify.

  2. Pick the money type

    Integer cents, never floats.

  3. Model expense and ledger

    One payer, many shares, netted pairs.

  4. Split as a strategy

    Validate first, fixed leftover rule.

  5. Break it

    Stray cent, bad data, double settle.

In full:

  1. Entities

    Group, Expense, Ledger, SplitStrategy. A debt is a ledger entry, not an object.

  2. Money is integer cents

    0.1 + 0.2 is 0.30000000000000004. A dinner costs 1001, not 10.01.

  3. Validate before you write

    Check members, amount and split data first. Then add every share to the ledger. A bad expense never half-applies.

  4. Net each pair

    Adding a debt also cancels any debt the other way, so each pair holds one number.

    const net = this.owes(debtor, creditor) + cents - this.owes(creditor, debtor);
this.owed.set(`${debtor}>${creditor}`, Math.max(0, net));
this.owed.set(`${creditor}>${debtor}`, Math.max(0, -net));

  5. Balances and simplify come from the ledger

    Compute both when asked. Nothing is stored twice, so nothing can disagree.

  6. Tests

    Random bills must always sum to the amount. Add the stray cent, a repeated pair, an overpay, a thread race on settle-up, and a messy trip that simplifies to zero.

Implementation

The same design in JavaScript, Java or Python.

Read more · 68 words

Java and Python add a real lock per group and run listeners after releasing it.

  • spread is the only place that rounds. Every strategy except exact goes through it.
  • The ledger is not thread-safe by itself. The group's lock is what makes it safe.

Then code it yourself. Try the Expense Splitter exercise: four split types, a fixed leftover rule, settle-up limits and a simplify with exact tie-breaks.

// Strategy: each split type turns (amount in cents, participants) into one share per participant, in order,
// or null when the input makes no sense. Money is integer cents, so 10.00 is 1000 and nothing is a float.
const sum = xs => xs.reduce((a, b) => a + b, 0);
const whole = xs => xs.every(Number.isInteger);

// Proportional split. Floors lose under one cent per person, so the leftover is fewer cents than people: hand them
// out one each to the first participants in the order given. The rule is fixed so the same input always gives the same bill.
function spread(amount, weights) {
  const total = sum(weights);
  const shares = weights.map(w => Math.floor((amount * w) / total));
  for (let i = 0, left = amount - sum(shares); left > 0; i++, left--) shares[i]++;
  return shares;
}

export const SPLITS = {
  equal: (amount, users) => spread(amount, users.map(() => 1)),
  shares: (amount, users, data) => (data.length === users.length && whole(data) && data.every(w => w > 0) ? spread(amount, data) : null),
  percent: (amount, users, data) =>
    data.length === users.length && whole(data) && data.every(p => p > 0) && sum(data) === 100 ? spread(amount, data) : null,
  exact: (amount, users, data) => (data.length === users.length && whole(data) && data.every(c => c >= 0) && sum(data) === amount ? data : null),
};

Failure modes and trade-offs

Read more · 185 words
What breaksEffectMitigation
Floats for moneyCents drift and books do not balanceInteger cents everywhere
Leftover cent droppedShares sum to less than the billHand the cents out in a fixed order
Overpaid settle-upA debt flips direction by accidentReject more than is owed
Read-then-write settleTwo payments for one debtCheck and subtract under the lock
Percent not summing to 100Part of the bill is nobody'sReject the expense
Plan from stale balancesWrong payments suggestedCompute simplify from the live ledger

Trade-offs.

ChoiceProsCons
Per-pair debts vs net balances onlyShows who owes whomTwo numbers to keep in step
Strategy per split vs one functionOpen to new splitsAn interface for a few lines
Greedy simplify vs the minimumFast, repeatableNot always the fewest payments
One lock per groupSimple and correctBusy groups serialize

Follow-up questions

How would you support several currencies?

Keep one ledger per currency and convert only when the user asks. Never mix them in one number.

How would you add a tax or tip on top?

Wrap a strategy in a decorator that adds the extra amount first and splits the total. The group does not change.

How would you let people undo an expense?

Store each expense with its shares, then reverse them in the ledger. Do it as a new entry, so the history stays honest.

How do you scale this to millions of groups?

A group is the unit of locking and of . by group id, and the locks never cross machines.

How would you test the simplify step?

Check that nets reach zero after applying the plan, that it has at most n - 1 transfers, and that ties give a fixed order.

Check yourself

Question 1 of 3

Score 2 out of 3 or better to mark this page complete.

1. A bill of 1000 cents is split equally among 3 people. What should the shares be?