9.7.29 — Expense Sharing

"Design Splitwise: a group of friends record who paid for what, and the app works out who owes whom."

Three friends split a ₹100 dinner. Each owes ₹33.33. Three times ₹33.33 is ₹99.99, so the app has just decided that one paisa does not exist. Nobody notices, because a paisa is nothing.

Run that group for two years and a few hundred expenses, and the balances stop adding up to zero. Now one friend is owed ₹4 that nobody owes, the settle-up screen suggests a transfer that leaves a residue, and a support engineer is asked to explain a number that no arithmetic in the system produces. A rounding decision that was never made is a rounding decision that is wrong, and this problem is built around that fact.

The rule this design has to hold: every split adds up to exactly what was paid, and every balance in the group adds up to exactly zero. Both are checkable at every step, and once you have them, the rest of the problem is bookkeeping you can prove.

1. Money is an integer, and that decision comes before anything else

class Money {                                            // (1)
  private constructor(readonly paise: number) {}         // (2)

  static rupees(r: number): Money { return new Money(Math.round(r * 100)); }
  static paise(p: number): Money { return new Money(p); }
  static zero(): Money { return new Money(0); }

  plus(o: Money): Money  { return new Money(this.paise + o.paise); }   // (3)
  minus(o: Money): Money { return new Money(this.paise - o.paise); }
  times(n: number): Money { return new Money(this.paise * n); }        // (4)

  isZero(): boolean { return this.paise === 0; }
  isNegative(): boolean { return this.paise < 0; }
}

(1) A class rather than a number, so that a rupee amount cannot be accidentally added to a count of people or a percentage. The type is doing work here beyond documentation.

(2) The stored value is paise, a whole number of the smallest unit. This is the decision the whole page rests on. 0.1 + 0.2 in JavaScript is 0.30000000000000004, because binary floating point cannot represent a tenth exactly, in the same way decimal cannot represent a third exactly. Add a few hundred of those errors together and balances drift by amounts nobody can trace. 10 + 20 = 30 has no such problem. The full explanation of why lives in 1.4; the rule here is that money never touches a floating-point number after it is parsed.

(3) Every operation returns a new Money rather than changing this one. That matters more than it looks: a Money sitting inside a recorded expense must not be modifiable by anyone who got a reference to it, because a recorded expense is a historical fact.

(4) Notice what is missing. There is no dividedBy. Division is where money is destroyed, so it is not an operation on the value; it is a decision made by the thing doing the splitting, which is the next section.

One thing to say before an interviewer asks it. Integer paise is right for rupees, dollars and euros, and the general form is "integer number of the smallest unit this currency has". Some currencies have no subunit at all (the Japanese yen), and some financial contexts need four decimal places rather than two. The rule that survives all of them is: store an integer, and store what unit it counts. A design that hard-codes "multiply by 100" works until the first yen amount arrives.

2. Splitting: four ways to divide, one rule they all obey

interface SplitStrategy {                                          // (1)
  split(total: Money, participants: MemberId[], spec: SplitSpec): Map<MemberId, Money>;
}

(1) Every strategy takes what was paid and who is involved, and returns what each person owes. And every one of them has the same postcondition: the returned amounts add up to exactly total. Not approximately. Exactly. That is the assertion worth writing once and calling from every strategy, because it turns a silent money leak into a loud failure at the moment it happens.

Equal split, done properly:

class EqualSplit implements SplitStrategy {
  split(total: Money, participants: MemberId[], spec: SplitSpec): Map<MemberId, Money> {
    const n = participants.length;
    const base = Math.floor(total.paise / n);                      // (1)
    let remainder = total.paise - base * n;                        // (2)

    const order = pickExtraOrder(participants, spec.expenseId);    // (3)
    const shares = new Map(participants.map(p => [p, Money.paise(base)]));

    for (const p of order) {                                       // (4)
      if (remainder === 0) break;
      shares.set(p, shares.get(p)!.plus(Money.paise(1)));
      remainder -= 1;
    }
    return assertSumsTo(shares, total);                            // (5)
  }
}

(1) Integer division, rounding down. ₹100 among three people is 10,000 paise divided by 3, which is 3,333 paise each with something left over.

(2) That something is the remainder: 10,000 minus 3,333 times 3 is 1 paisa. This is the paisa the naive version threw away. It is computed rather than ignored, and now it has to go somewhere.

(3) Somewhere means one specific person, chosen by a rule rather than by luck. Two properties are needed and they pull against each other. The choice must be deterministic, so that re-running the split on the same expense gives the same answer forever, including when a support engineer recomputes it two years later. And it must not always be the same person, because if it is sorted alphabetically then Asha pays one extra paisa on every expense in every group for the rest of her life. Deriving the order from the expense's own identifier gives both: fixed for a given expense, spread across people over many expenses.

(4) Hand out one extra paisa each, in that order, until the remainder is gone. The remainder is always smaller than the number of participants, so at most one extra paisa lands on any person. ₹100 among three becomes ₹33.34, ₹33.33, ₹33.33, which adds up to ₹100.00 exactly.

(5) The assertion runs on the way out. It costs a loop over a handful of numbers and it is the reason this class of bug cannot escape.

The other three strategies are the same discipline with a different starting point.

Exact amounts. Someone types what each person owes. There is nothing to compute and everything to check: if the amounts do not add to the total, the expense is rejected, not adjusted. Silently fixing up a mismatch is how a typo becomes a permanent wrong balance.

Percentages. Check the percentages add to exactly 100 first, then convert. The conversion has the same remainder problem as equal split and takes the same treatment.

Shares. "Two of us shared a room, one had a single" is weights of 2:1:1. This one hides a real arithmetic trap:

// wrong: divide first, then multiply — the remainder is lost n times over
const perShare = Math.floor(total.paise / totalWeight);
const owed = perShare * weight;                          

// right: multiply first, then divide
const owed = Math.floor(total.paise * weight / totalWeight);   

Take ₹1,000 split 3:2:2. Total weight is 7. Dividing first gives 100,000 ÷ 7 = 14,285 paise per share, so the three people get 42,855, 28,570 and 28,570, which adds to 99,995. Five paise gone, from a single expense. Multiplying first gives 42,857, 28,571 and 28,571, which adds to 99,999, so the remainder is one paisa and the loop above handles it. The rule is general: when you scale and divide, do the multiplication before the division, because every division rounds down and doing it once loses less than doing it three times.

3. The ledger: nothing is ever edited

This is the structural decision that makes the rest of the design work, and it is worth arguing for rather than asserting.

type Entry =                                                   // (1)
  | { kind: "expense"; id: EntryId; at: Date; by: MemberId;
      description: string; paidBy: Map<MemberId, Money>;       // (2)
      owedBy: Map<MemberId, Money> }
  | { kind: "settlement"; id: EntryId; at: Date;               // (3)
      from: MemberId; to: MemberId; amount: Money }
  | { kind: "reversal"; id: EntryId; at: Date; by: MemberId;   // (4)
      reverses: EntryId; reason: string };

class Group {
  #entries: Entry[] = [];                                      // (5)

  record(e: Entry): void { this.#entries.push(e); }            // (6)
}

(1) Three kinds of entry, and they are the only things that ever happen in a group. Everything a user sees is computed from this list.

(2) An expense records who paid and who owes, as two separate maps. Two maps rather than one payer, because real dinners are paid by two people putting cards in, and a design that assumes a single payer needs restructuring the first time that happens. The invariant on an expense is that the paid map and the owed map add to the same total.

(3) A settlement is somebody actually handing over money, and it is an entry in the same list rather than a separate concept. That is deliberate, and section 5 shows what it buys.

(4) A reversal is how a mistake is fixed. Not a delete, not an edit. A new entry that says "entry X is cancelled, here is who did it and why", followed by a fresh corrected expense if one is needed.

(5) and (6) One list, append-only. There is no method that changes an entry, because there is no situation in which changing one is the right thing to do.

Why not just let people edit an expense? Three things break, and each one is a real support ticket.

The history goes. A member asks why they owe ₹417. With an editable expense, the honest answer is "because of the current values of some rows", and if last month's ₹600 dinner was quietly edited to ₹900 by whoever typed it in, nothing in the system records that it changed, when, or who did it. With a ledger, the answer is a list of entries with dates and authors, and the number is the sum of them.

Two people editing at once lose one another's work. Both load the expense, both change something, both save, and the second save silently wins. That is the lost update from 9.6.3, landing on money. Appends do not have this problem at all: two people adding two entries produce two entries, in some order, and both survive. Appending is safe under concurrency in a way that editing can never be, and that alone is worth the design.

Disputes need the sequence, not the summary. "I already paid you back in March" is settled by finding the March settlement entry, which only exists if settlements are recorded rather than subtracted.

The cost, stated honestly. Every read folds the whole list. A group with 4,000 entries recomputes 4,000 entries to show a balance, which is fine, and a group that has been running for ten years is not. The repair is a periodic snapshot: store the balances as of entry 3,500 and fold only what came after. That is the same checkpoint idea that databases use to avoid replaying their entire write log at startup, and it is worth naming as the plan rather than pretending the fold is free.

4. Balances are computed, not stored

function balances(entries: Entry[]): Map<MemberId, Money> {      // (1)
  const net = new Map<MemberId, Money>();
  const add = (m: MemberId, amt: Money) =>
    net.set(m, (net.get(m) ?? Money.zero()).plus(amt));

  const reversed = new Set(entries.filter(isReversal).map(e => e.reverses));  // (2)

  for (const e of entries) {
    if (reversed.has(e.id)) continue;                            // (3)
    switch (e.kind) {
      case "expense":
        for (const [m, amt] of e.paidBy) add(m, amt);            // (4)
        for (const [m, amt] of e.owedBy) add(m, Money.zero().minus(amt));
        break;
      case "settlement":
        add(e.from, e.amount);                                   // (5)
        add(e.to, Money.zero().minus(e.amount));
        break;
      case "reversal": break;                                    // (6)
    }
  }
  return net;
}

(1) A balance is a positive number if you are owed money and negative if you owe it. One number per person, folded from the list.

(2) Reversed entries are collected first, so the fold can skip them in one pass rather than looking backwards as it goes.

(3) A reversed expense contributes nothing. Its reversal is a record that it happened and was cancelled, which is exactly what an audit needs and exactly what the arithmetic must ignore.

(4) Paying money moves your balance up; owing money moves it down. Someone who paid ₹1,200 for a dinner they were part of gets ₹1,200 up and their own ₹300 share down, netting ₹900 owed to them, which is right.

(5) A settlement moves money in the real world, so it moves the balances in the opposite direction from the debt. Paying somebody ₹900 raises the payer's balance by ₹900 and lowers the receiver's by the same amount, which cancels the debt exactly.

(6) The reversal entry itself adds nothing to the arithmetic. It is a marker.

The invariant that makes this checkable: every balance in the group adds to exactly zero. It has to, because every rupee that enters the fold enters twice with opposite signs. A group whose balances sum to anything other than zero has a bug, and since the fold is one function, the check is one line at the end of it. This is the same double-entry principle that accountants have used for six hundred years, which is not a coincidence. It is the only known way to make money arithmetic self-checking.

Worked, with four people on a trip.

Entry	Paid by	Split among	Each owes
Dinner ₹1,200	Asha	all four	₹300
Cab ₹500	Bilal	all four	₹125
Hotel ₹4,000	Chen	all four	₹1,000

Everyone owes ₹1,425 in total. Asha paid ₹1,200, Bilal paid ₹500, Chen paid ₹4,000, Dee paid nothing. So the balances are Asha −225, Bilal −925, Chen +2,575, Dee −1,425, and those add to zero. Chen is owed ₹2,575 and the other three owe it between them.

5. Settling up: nine transfers or three

Pay every debt as it was incurred and the trip above needs nine transfers. Three people pay Asha for dinner, three pay Bilal for the cab, three pay Chen for the hotel. Everybody sends money to everybody, several times, for amounts like ₹125.

But only the net position matters. Nobody cares which dinner produced which part of Dee's ₹1,425. So collapse the debts to one number per person and match debtors to creditors directly:

function settleUp(balances: Map<MemberId, Money>): Transfer[] {
  const debtors   = [...balances].filter(([, b]) => b.isNegative())
                                 .map(([m, b]) => ({ m, left: -b.paise }))
                                 .sort((a, b) => b.left - a.left);       // (1)
  const creditors = [...balances].filter(([, b]) => b.paise > 0)
                                 .map(([m, b]) => ({ m, left: b.paise }))
                                 .sort((a, b) => b.left - a.left);

  const transfers: Transfer[] = [];
  let d = 0, c = 0;
  while (d < debtors.length && c < creditors.length) {
    const amount = Math.min(debtors[d].left, creditors[c].left);         // (2)
    transfers.push({ from: debtors[d].m, to: creditors[c].m, amount: Money.paise(amount) });
    debtors[d].left -= amount;                                           // (3)
    creditors[c].left -= amount;
    if (debtors[d].left === 0) d++;                                      // (4)
    if (creditors[c].left === 0) c++;
  }
  return transfers;
}

(1) Two lists, biggest first. Sorting is not required for correctness, and it produces sensible-looking transfers where the person who owes most pays the person who is owed most, rather than a scatter of small payments.

(2) Transfer whichever is smaller, the debt or the credit. That is the largest payment that does not overshoot either side.

(3) Both sides shrink by the amount actually transferred.

(4) At least one of the two is now zero, because the amount was the smaller of them. That is what bounds the whole thing: every transfer removes at least one person from the problem, and the last transfer removes two. With n people that is at most n − 1 transfers, and the trip above goes from nine to three.

Watch it run on the trip. Chen is the only creditor at +2,575. Debtors sorted biggest first are Dee 1,425, Bilal 925, Asha 225.

Dee pays Chen ₹1,425. Dee is settled, Chen is down to ₹1,150 owed. Bilal pays Chen ₹925. Bilal is settled, Chen is down to ₹225. Asha pays Chen ₹225. Both settled, and the loop ends.

Three transfers for four people, which is the n − 1 bound hit exactly.

Now the boundary you should name before being asked. Three transfers is not always the theoretical minimum. If two people owe ₹500 each and two are owed ₹500 each, the ideal answer is two transfers, and this greedy method may produce three by matching the biggest debtor against the biggest creditor and leaving a residue. Finding the true minimum means finding subsets of debtors whose amounts exactly match subsets of creditors, which is the subset-sum problem, and it is NP-hard. There is no fast algorithm for it, and for a group of six friends the difference is one extra transfer.

So the products in this category ship the greedy version. Saying which problem you are not solving, and why it does not matter here, is worth more than solving it, because it shows you know where the boundary is rather than either ignoring it or spending the interview on it.

And a settlement is recorded as an entry, which is the payoff for section 3. When Dee actually sends the ₹1,425, that becomes a settlement entry in the same list. The next time balances are folded, Dee's ₹1,425 owed and the settlement cancel exactly and Dee comes out at zero. Nothing had to be marked as paid, no debt had to be found and updated, and there is no second place where "who has settled" is recorded that could disagree with the first. There is one list, and everything is a view of it.

6. The awkward cases, which are the interview

Somebody leaves the group owing money. The balance does not disappear because a membership row was deleted. Either they settle first, or the group records who absorbs the debt as a real entry, or the member stays in the group as a non-participating account with a balance. Deleting the person and letting the sum stop being zero breaks the one invariant the design is built on, and it will be noticed by the settle-up screen the same afternoon.

Two people add the same expense. Both were at the restaurant, both opened the app. Nothing in the system can tell that these are duplicates, because they legitimately might not be. The honest design does not try to detect it automatically; it surfaces likely duplicates (same amount, same day, same group, within a few minutes) and lets a human reverse one. The reversal machinery is already there, which is why this costs nothing to support.

Multi-currency. A group where one dinner was paid in euros and one in rupees cannot have a single balance number without an exchange rate, and the rate changes daily. The rule that survives is: an expense records the amount in the currency it was actually paid in, and never changes. Conversion happens when balances are displayed or when a settlement is made, using a dated rate, and the rate used is recorded on the settlement entry. Converting at entry time and storing rupees means that a rate revision retroactively rewrites what a dinner in Rome cost, which is both wrong and impossible to explain.

Somebody paid for someone who is not in the group. This is the case that reveals whether the model is right. The owedBy map is a map of member identifiers, so a guest who is not a member cannot appear in it. Real apps solve this by letting a group have members who have no account, which costs nothing here because a member is an identifier and a display name, not a login.

7. What the interviewer will push on

"Split ₹100 three ways. Show me the code." They are checking one thing before anything else: whether money is a float. The good answer uses integer paise, computes the remainder explicitly, and hands it out one paisa at a time in a deterministic order. The tell that separates a memorised answer is whether you say why the order must be deterministic and must not always be the same person — reproducible for support, and not always Asha. The common wrong answer is total / n with a comment about rounding, which loses a paisa and never notices.

"Why can't an expense be edited?" They are checking whether you can argue for a constraint rather than recite it. Three concrete losses: the history that answers "why do I owe ₹417", the second editor's work when two people edit at once, and the March settlement that proves a dispute. The strongest version adds that appends commute and edits do not, which is why an append-only list is the shape that survives concurrency without any locking.

"So a user taps delete. What happens?" A reversal entry naming the cancelled entry, its author and its reason, and the fold skips the reversed one. The user sees the expense disappear, which is what they asked for, and the record of it happening survives, which is what the group needs six months later. Candidates who answer "soft delete with a flag" are close, and the difference worth stating is that a flag records that something was cancelled while a reversal entry records who and when and why.

"Explain settle-up and prove your bound." The proof is the interesting part and most answers skip it. Each transfer moves the smaller of the debt and the credit, so at least one of the two parties reaches zero, so each transfer removes at least one person and the final one removes two. That gives n − 1. Then name the boundary: the true minimum needs exact subset matching, which is NP-hard, and for groups of human size the greedy result is at most a transfer or two off.

"Your balance screen is slow for a group with 20,000 entries." They are checking whether you understood the cost you accepted. Folding the ledger is linear in its length, and the fix is a stored snapshot of the balances as of some entry plus a fold of everything after it. What must not change is where the truth lives: the snapshot is a cache that can be thrown away and rebuilt, and the ledger stays the only source. A "fix" that starts writing balances directly reintroduces every problem section 3 removed.

"Add multi-currency." They are checking whether you convert at the wrong time. The expense keeps the currency it was paid in, permanently. Conversion happens at display or at settlement, with a dated rate, and the rate is recorded on the settlement. The common wrong answer converts everything to a base currency on entry, which means a rate correction silently rewrites what a dinner cost last March.

The thing to volunteer that nobody asks for: the group's balances must sum to exactly zero, and that is a one-line assertion at the end of the fold. It catches a broken split, a bad reversal, a member removed while owing, and an arithmetic mistake anywhere in the system, all with the same check. Most candidates describe the balance calculation; noticing that the calculation has a property that makes it self-checking is what shows you have thought about money as something that must be provable rather than merely computed.

Recall

• Money is an integer count of the smallest unit. Never a float. Store the unit alongside it, because not every currency has hundredths.
• Money has no dividedBy. Division destroys money, so splitting is a decision made by a strategy, not an operation on the value.
• Every split adds to exactly the total, asserted on the way out. The remainder is computed and handed out one unit at a time.
• The extra paisa goes to a deterministic person derived from the expense id, so it is reproducible for support and not always the same person.
• Multiply before you divide when splitting by weights. Dividing first loses the remainder once per participant.
• Exact-amount splits that do not add up are rejected, never adjusted.
• The ledger is append-only: expenses, settlements, reversals. Nothing is edited, nothing is deleted.
• Appends commute; edits do not. That is why two people recording expenses at once is safe and two people editing one expense is a lost update.
• A correction is a reversal entry naming what it cancels, who did it and why, plus a fresh entry if needed.
• Balances are folded from the ledger, never stored as truth. A snapshot is a cache you can delete and rebuild.
• All balances sum to exactly zero. One assertion catches broken splits, bad reversals and removed members.
• Settle-up nets first, then matches biggest debtor to biggest creditor. Each transfer zeroes at least one side, so n − 1 transfers at most. The four-person trip goes from nine transfers to three.
• The true minimum is subset-sum, NP-hard. Ship the greedy and name the boundary.
• A settlement is another entry, so the debt cancels in the fold. There is no second place recording who has paid.
• Multi-currency: the expense keeps the currency it was paid in. Convert at display or settlement with a dated rate, recorded on the settlement.

Self-test: Walk ₹100 among three, paise by paise. Why must the extra-paisa order be deterministic and rotating? Why does dividing before multiplying lose more? Name the three things that break when an expense is editable. Prove the n − 1 bound. What is the one-line check that catches almost every money bug here?

Quiz Bank

FoundationalSplit ₹100 equally among three people, exactly, and explain every decision in the arithmetic.

Start before the division, because that is where this is won or lost. ₹100 is stored as 10,000 paise, a whole number. It is not stored as 100.0, because binary floating point cannot represent a tenth any more than decimal can represent a third, so 0.1 + 0.2 comes out as 0.30000000000000004. One such error is invisible. A few hundred of them, folded into a balance, produce a number nobody can trace to any expense.

The division:

const base = Math.floor(10000 / 3);        // 3333 paise = ₹33.33
let remainder = 10000 - base * 3;          // 10000 - 9999 = 1 paisa

One paisa is left over, and it exists. The naive total / n never sees it, which is precisely the bug: nothing errors, nothing logs, and the group's balances quietly stop adding to zero.

Where the paisa goes is a design decision with two requirements that pull against each other.

It must be deterministic. Re-running the split on this expense next year must give the same three numbers. If the extra paisa lands on a random person, a support engineer recomputing a two-year-old dinner gets a different answer from the one in the app, and there is no way to tell which is right.

It must not always be the same person. Sort the members alphabetically and Asha pays one extra paisa on every expense she is ever part of. It is a trivial amount and it is still a systematic unfairness that somebody will eventually notice and write about.

Both are satisfied by deriving the order from something fixed about the expense itself, such as its identifier. Fixed for a given expense, and spread across people over hundreds of expenses.

const order = pickExtraOrder(participants, spec.expenseId);
for (const p of order) {
  if (remainder === 0) break;
  shares.set(p, shares.get(p)!.plus(Money.paise(1)));
  remainder -= 1;
}

The result is ₹33.34, ₹33.33, ₹33.33, which adds to exactly ₹100.00. The remainder is always smaller than the number of participants, so nobody receives more than one extra paisa.

Then the line that makes the whole class of bug impossible to ship:

return assertSumsTo(shares, total);

It costs a loop over a handful of numbers, and it converts a silent money leak into a failure at the moment it happens. Every strategy calls it.

The same discipline, three more ways. Exact amounts are validated and rejected if they do not add up, never quietly adjusted, because adjusting turns a typo into a permanent wrong balance. Percentages are checked to add to exactly 100, then converted with the same remainder handling. Shares carry one extra trap worth showing:

const owed = Math.floor(total.paise / totalWeight) * weight;      
const owed = Math.floor(total.paise * weight / totalWeight);      

₹1,000 split 3:2:2 has total weight 7. Dividing first gives 14,285 paise per share, so the shares are 42,855 + 28,570 + 28,570 = 99,995, and five paise vanish from one expense. Multiplying first gives 42,857 + 28,571 + 28,571 = 99,999, so the remainder is one paisa and the loop above places it. The general rule is that every division rounds down, so do the division once at the end rather than once per participant.

AppliedExplain settle-up: the problem it solves, the algorithm, the proof of its bound, and the limit you should name.

The problem, with real numbers. Four friends on a trip: Asha pays ₹1,200 for dinner, Bilal pays ₹500 for a cab, Chen pays ₹4,000 for the hotel, all split four ways.

Paying each debt as it was incurred means three people pay Asha, three pay Bilal, and three pay Chen: nine transfers, several of them for amounts like ₹125, and everybody has to remember which ones they have done.

The insight: only the net position matters. Nobody cares which dinner produced which part of what they owe. Fold the ledger into one number per person:

Everyone owes ₹1,425 in total. Asha paid ₹1,200 so she is at −225. Bilal paid ₹500 so he is at −925. Chen paid ₹4,000 so he is at +2,575. Dee paid nothing so she is at −1,425. Those add to zero, which they must.

The algorithm: put debtors and creditors in two lists, biggest first, and repeatedly transfer the smaller of the two amounts at the heads of the lists.

const amount = Math.min(debtors[d].left, creditors[c].left);
transfers.push({ from: debtors[d].m, to: creditors[c].m, amount: Money.paise(amount) });
debtors[d].left -= amount;
creditors[c].left -= amount;
if (debtors[d].left === 0) d++;
if (creditors[c].left === 0) c++;

Running it on the trip. Chen is the only creditor at ₹2,575.

Dee pays Chen ₹1,425 — Dee is settled, Chen is down to ₹1,150. Bilal pays Chen ₹925 — Bilal is settled, Chen is down to ₹225. Asha pays Chen ₹225 — both hit zero and the loop ends.

Nine transfers became three.

The proof of the bound, which is what the question is really asking for. The transferred amount is the smaller of the debt and the credit, so after the transfer at least one of the two is exactly zero and that person leaves the problem. Every transfer therefore removes at least one person, and the very last transfer removes two at once, because the last debtor and the last creditor must settle against each other. Starting with n people, that gives at most n − 1 transfers. Four people, three transfers, which is the bound hit exactly.

The limit, named before being asked. This is not always the theoretical minimum. Two people owing ₹500 each and two owed ₹500 each should be settled in two transfers by pairing them off; the greedy method can produce three if the sorted heads do not match exactly. Finding the true minimum means finding subsets of debtors whose totals exactly match subsets of creditors, which is subset-sum, which is NP-hard. There is no fast general algorithm, and for a group of six friends the cost of being wrong is one extra bank transfer.

Products in this category ship the greedy version for exactly that reason, and saying which problem you are choosing not to solve is worth more than solving it.

The last piece, which is where the ledger earns its keep. When Dee actually sends the ₹1,425, that is recorded as a settlement entry in the same list as the expenses. Next time balances are folded, Dee's ₹1,425 of debt and the ₹1,425 settlement cancel and she comes out at zero. Nothing was marked as paid, no debt row was found and updated, and there is no separate record of who has settled that could ever disagree with the expenses. One list, and every screen is a view of it.

InterviewA member says the app deleted their expense but the balance did not change. Walk through how your design handles deletion, and why editing is refused everywhere.

Deletion in this design is an entry, not an absence.

{ kind: "reversal", id, at, by: whoDidIt, reverses: originalEntryId, reason }

The fold collects reversed identifiers first and skips those entries, so the expense contributes nothing to any balance. The user sees it gone from the list, which is what they asked for. What survives is the record that it existed, who cancelled it, when, and why.

So the symptom in the question is a real bug and the design tells you where to look: either the reversal was written but the fold was reading a stale snapshot, or the reversal names an identifier that does not match the entry. Both are visible by reading the entries, which is itself the argument for this shape. In a system that deletes rows, the same symptom has no evidence left to examine.

Now why editing is refused. Three concrete failures, not a principle.

The history is the product. "Why do I owe ₹417" is the most common support question in an app like this. With a ledger, the answer is a list of entries with dates and authors that sums to ₹417. With editable expenses, last month's ₹600 dinner might now say ₹900, with nothing recording that it changed, when, or who changed it, and the balance is simply a consequence of whatever the rows currently say.

Two editors lose each other's work. Both people open the expense, one fixes the amount, the other fixes the participant list, both save. The second save overwrites the first completely and nothing warns anyone. That is the lost update from 9.6.3, and here it happens on money.

Appends do not have this problem at all, and that is the deeper reason for the shape. Two people recording two entries at the same time produce two entries in some order, and both survive. There is no interleaving that loses information, so there is nothing to lock and no version to compare. Appends commute; edits do not.

Disputes need the sequence. "I paid you back in March" is answered by finding the March settlement entry. That entry only exists if settling is recorded rather than subtracted from a stored balance.

What it costs, said plainly. Every read folds the whole list. Four thousand entries is nothing; a decade-old group is a problem. The repair is a stored snapshot of balances as of some entry, with only later entries folded on top. The important discipline is that the snapshot is a cache: it can be deleted and rebuilt from the ledger at any time, and the ledger stays the only source of truth. A version that starts writing balances directly, and treats the ledger as a log beside them, has reintroduced every problem this design removed while keeping all of its costs.

One extra thing the ledger gives away for free, worth mentioning unprompted. Because a correction is a new entry rather than a change to an old one, the system can show a member exactly what changed in their group since they last looked, as a list. Apps that mutate rows have to build a separate change feed to do the same thing, and it will drift from the data it describes.

StaffThis becomes a product with millions of groups, multiple currencies, payment integration so people can settle inside the app, and a requirement that a user can export everything they have ever been part of. What survives, what changes, and where does the model actually strain?

What survives is everything structural. Integer money, the split strategies with their exact-sum assertion, the append-only ledger, folded balances, the zero-sum invariant, and the greedy settle-up. Millions of groups is millions of independent small ledgers, and the group is the natural boundary — no operation in one group needs anything from another, so the data partitions by group identifier with no coordination anywhere. That property was not designed for scale; it came free from putting every fact in one per-group list.

Currencies are where the model genuinely strains, and it is worth being precise about why. The rule stays that an expense records the currency it was actually paid in and never changes. The strain is that a balance in more than one currency is not a single number, so "Dee owes ₹1,425" becomes "Dee owes ₹900 and €35", and the settle-up algorithm needs a common unit to compare positions.

Three options, and they trade different things:

Settle per currency. Run the whole netting separately for each currency. Perfectly honest, never needs a rate, and produces more transfers than people expect.

Convert at settlement time. Pick a group currency, convert positions using a dated rate at the moment of settling, and record the rate on the settlement entry. The recording is the important half: without it, nobody can ever reproduce why the transfer was ₹3,412 rather than ₹3,398.

Convert at entry time. Store everything in one currency as it arrives. This is the tempting one and it is wrong, because a rate correction retroactively rewrites what a dinner in Rome cost. Reject it explicitly rather than by omission.

I would ship per-currency positions with conversion offered at settlement, rate recorded.

Payment integration is where the design meets something it does not control. Recording a settlement is instant and free; actually moving money is neither, and it can fail after being started. So a settlement gains states rather than being a single entry: initiated, confirmed, failed. The entry that affects balances is written when the payment provider confirms, not when the user taps pay, because a balance that clears on a payment that later bounces is worse than one that clears a few seconds late.

Two consequences follow and both need saying. The provider will occasionally tell you about the same payment twice, so the settlement carries the provider's reference and a repeated confirmation is ignored rather than recorded again — the idempotency-key idea from 9.6.3. And a payment that fails after being initiated needs a visible state in the app, because "I paid and it still says I owe" with nothing on screen explaining it is the worst possible version of this feature.

Export is easy, and that is the receipt for the whole design. A user's history is the set of entries in the groups they belong to, in order, which is exactly the data structure the system already has. There is no assembly step, no reconciliation between a summary table and a detail table, and no question about which of two representations is right. Most systems find export hard because the truth is scattered across mutable rows and derived tables that disagree; here the export is the model.

Where I would actually be careful. The snapshot layer. Once balances are cached at an entry offset, there are two representations of the same fact and they can disagree, which is the thing the ledger was chosen to avoid. The rules that keep it safe: the snapshot is always rebuildable and is rebuilt on a schedule, the entry offset it was taken at is stored with it so a stale snapshot is detectable rather than silently trusted, and the zero-sum assertion runs against the snapshot as well as against the fold. A cache that is checked against its source is a cache. One that is not is a second source of truth wearing a disguise.

What I would monitor. Groups whose balances do not sum to zero, which should be exactly none and each of which is a real bug. Reversal rate per group, because a spike means a confusing feature rather than careless users. Settlements initiated but never confirmed, each of which is a person who thinks they have paid. And the age of the oldest snapshot, because a rebuild job that has quietly stopped shows up here long before it shows up as a wrong balance.

Flashcards

FlashWhy money is an integer

Binary floating point cannot represent a tenth exactly, so 0.1 + 0.2 is 0.30000000000000004. Store a whole count of the smallest unit, and store which unit it counts, because not every currency has hundredths.

FlashThe remainder rule

₹100 among three is 3,333 paise each with 1 paisa left. Hand it out one unit at a time in an order derived from the expense id: deterministic so support can reproduce it, rotating so the same person is not always charged extra.

FlashMultiply before dividing

For weighted splits use floor(total * weight / totalWeight), not floor(total / totalWeight) * weight. The second rounds down once per participant, so ₹1,000 split 3:2:2 loses five paise instead of one.

FlashWhy appends beat edits

Two appends produce two entries and both survive. Two edits mean the second save silently overwrites the first. Appending is safe under concurrency without any locking; editing needs versions and comparison.

FlashThe zero-sum check

Every balance in a group sums to exactly zero, because every amount enters the fold twice with opposite signs. One assertion catches broken splits, bad reversals, and members removed while owing.

FlashSettle-up's bound

Each transfer moves the smaller of the debt and the credit, so at least one side hits zero and leaves. That is n − 1 transfers at most. The true minimum needs exact subset matching, which is NP-hard, so ship the greedy and say so.

Next: 9.7.5 — the rate limiter, where the resource being handed out is permission to make a request, and the whole design is a decision that has to be made in microseconds.