Design Splitwise (Expense Sharing)
Splitwise is the capstone of the case-study module because it looks like a weekend project and hides four separate hard problems. The first is money: three people splitting ₹100 can't each pay ₹33.333…, and whoever gets the extra paisa has to be decided by a rule, not by floating-point luck. The second is modelling: an expense, a settlement and an undo all change balances, and you want one mechanism for all three rather than three. The third is an algorithm question dressed up as a feature. "Simplify debts" is a graph problem whose exact version is NP-hard, and the interviewer wants to know whether you know that. The fourth is concurrency: several people in one group add expenses from their phones at the same moment, and money must never appear or vanish.
The Machine Coding Rounds page already builds a small expense-sharing ledger as its worked example: users, three split modes, a netted balance sheet and a command-line driver, in a 90-minute format. This page doesn't repeat that. It starts where the ledger stops, adding groups, a fourth split mode, a fairer and fully deterministic remainder rule, debt simplification with a proof of where greedy goes wrong, settle-up rules, an append-only activity log with undo, multi-currency, multiple payers, and thread-safe group balances. If you haven't read the ledger yet, read it first. It shows how to deliver a design like this under time pressure, and this page shows how far the design can go.
As with every case study here, the structure follows the LLD interview framework, and every code sample was compiled and run.
1. Clarifying questions and requirements
| Question | Answer we assume | Why it matters |
|---|---|---|
| Are expenses always inside a group? | Yes. Every expense belongs to a group, and two friends with no group get a two-person group. | One ledger per group. Balances never mix groups. |
| How many payers per expense? | One in the core design. Several payers is Extension C. | Decides whether an expense has a paidBy or a paid map. |
| Which split modes? | Equal, exact amounts, percentages, and shares ("2 : 1 : 1"). | Four strategies, each with its own validation. |
| Does the payer have to be a participant? | No. "I bought concert tickets for you two" is common. | The payer may have no share at all. |
| What precision? | Integer minor units (paise, cents). Percentages to two decimal places, such as 33.33%. | No floats anywhere. Percentages stored as basis points. |
| Who gets the leftover paisa? | A documented, deterministic rule. We use the largest-remainder method, with ties going to the earlier participant. | Determinism is what makes replay and undo exact. |
| Show raw debts or simplified ones? | Both. Pairwise debts by default, and a simplified plan with the fewest transfers we can find quickly. | Two views over the same data. |
| Can a settlement be any amount? | It can't create new debt. You can pay back up to what you owe and up to what the other person is owed. | A guard that keeps settle-up honest. |
| Undo? | Any expense or settlement can be undone, once, by any member. The history keeps both the action and the undo. | Append-only log, compensating entries. |
| Edit? | An edit is an undo plus a new expense. | No in-place mutation of history. |
| Currencies? | One per group in the core. Several per group as Extension B. | Decides whether one balance sheet is enough. |
| Concurrency? | Many users act on the same group at once. Different groups never block each other. | Per-group locking. |
Functional requirements
- Register users. Create a group with a name, a currency and an initial set of members. Add members. Remove a member only if their balance in that group is zero.
- Add an expense to a group: who paid, the total in minor units, the split mode, the participants, and the mode's values (none for equal, amounts for exact, basis points for percent, positive integers for shares).
- Every split must add up to the total exactly, and every invalid request must leave the group unchanged.
- Show each member's net balance (positive: the group owes you; negative: you owe the group) and the pairwise debts (who owes whom, netted per pair).
- Show a simplified plan: a list of transfers that settles everyone, with at most n − 1 transfers for n people with non-zero balances.
- Record a settlement: A paid B some amount. It must not overpay.
- Undo any expense or settlement. Undoing twice is an error.
- Keep an activity history per group: who did what, in order.
- Show a user's total balance across all their groups, per currency.
Non-functional requirements
- Money is conserved. The sum of all net balances in a group is always exactly zero.
- Replayable. Replaying the group's entries from scratch gives exactly the incremental balances. This is the invariant tests lean on most.
- Thread-safe, per group. Two expenses in one group are serialised. Two expenses in different groups run in parallel.
- Deterministic. The same inputs always produce the same shares and the same simplified plan, so tests can assert exact values.
Out of scope
Persistence, authentication, notifications ("Chen added an expense"), receipts and images, recurring expenses, and payments through a real payment provider. Each has an obvious seam, which section 8 names.
2. Core entities and relationships
| Entity | Responsibility | Notes |
|---|---|---|
SplitwiseService | Facade. Owns users and groups, validates, and is the only thing that mutates a group. | Callers never touch a balance sheet. |
User | Id and display name. | Kept minimal here. Contact details belong to a different service. |
Group | Members, currency, the balance sheet, the entries, the undone set, the activity log, and a lock. | The aggregate root: every change to a group's money goes through it. |
LedgerEntry | Anything that changes balances. Exposes edges(): a list of (debtor, creditor, amount). | The common interface for expenses, settlements and future entry types. |
Expense | An immutable record: id, payer, total, split mode, computed shares, description. | Shares are computed once and stored, never recomputed. |
Settlement | An immutable record: payer, payee, amount. | Its edge is "the payee now owes the payer", which cancels existing debt. |
SplitStrategy | Turns (total, participants, values) into shares, and validates. | Equal, exact, percent and share implementations. |
BalanceSheet | Applies edges with a sign (+1 to do, −1 to undo). Keeps nets per user and netted debts per pair. | Two derived views, updated together. |
DebtSimplifier | Turns nets into a list of transfers. | A pure function. No state, trivially testable. |
Transfer | Debtor, creditor, amount. | A value object, used for both views. |
Activity | Sequence number, actor, kind, reference, summary. | Append-only. Never edited, never deleted. |
The design hangs on one idea, so it's worth stating plainly before the diagram.
Every change to money is a list of edges. An edge says "debtor owes creditor this much". An expense of ₹90 paid by Asha and split equally with Bob and Chen produces two edges: Bob owes Asha ₹30, and Chen owes Asha ₹30. Asha's own share produces no edge, because she doesn't owe herself. A settlement where Chen pays Asha ₹30 produces one edge in the opposite direction: Asha owes Chen ₹30, which cancels Chen's debt. An undo applies the same edges with the sign flipped. The balance sheet only knows how to apply edges. It doesn't know what an expense is.
This gives three properties for free:
- One code path for all changes. Expenses, settlements, undos and any future entry type (refunds, multi-payer bills, currency conversions) go through
apply(edges, sign). - Undo is exact. Applying the same edges with sign −1 restores the previous balances to the paisa, because addition is reversible and the edges were stored, not recomputed.
- Undo works out of order. Edge application is plain addition, and addition commutes. Undoing an expense from last Tuesday doesn't require undoing everything after it. That's the decisive argument for this design over snapshots, as section 5 shows.
The invariants to protect:
sum(net.values()) == 0for every group at all times.- Rebuilding a fresh sheet from all entries not in
undonegives the same nets and pairwise debts as the live sheet. - For every expense,
sum(shares) == total. - Every entry is undone at most once.
- A settlement never pushes the payer's net above zero or the payee's net below zero.
3. Class diagram
classDiagram
class SplitwiseService {
-users: map of id to User
-groups: map of id to Group
-strategies: map of name to SplitStrategy
+addUser(id, name)
+createGroup(id, name, currency, members) Group
+addMember(groupId, user)
+removeMember(groupId, user)
+addExpense(groupId, actor, paidBy, total, kind, participants, values, description) Expense
+settle(groupId, actor, payer, payee, amount) Settlement
+undo(groupId, actor, entryId)
+balances(groupId) list of Transfer
+nets(groupId) map of user to long
+simplified(groupId) list of Transfer
+history(groupId) list of Activity
+rebuild(groupId) BalanceSheet
+userTotal(user) map of currency to long
}
class Group {
+id: String
+currency: String
+members: list of String
+entries: map of id to LedgerEntry
+undone: set of String
+activity: list of Activity
+lock
}
class LedgerEntry {
<<interface>>
+id() String
+edges() list of Edge
}
class Expense {
<<immutable>>
+paidBy: String
+total: long
+kind: String
+shares: map of user to long
}
class Settlement {
<<immutable>>
+payer: String
+payee: String
+amount: long
}
class BalanceSheet {
-net: map of user to long
-pair: map of user pair to long
+apply(edges, sign)
+nets() map
+debts() list of Transfer
}
class SplitStrategy {
<<interface>>
+split(total, users, values) map of user to long
}
class EqualSplit
class ExactSplit
class PercentSplit
class ShareSplit
class DebtSimplifier {
+simplify(nets)$ list of Transfer
}
class Money {
+toMinor(text)$ long
+allocate(total, weights)$ long array
}
class Activity {
<<immutable>>
+seq: long
+actor: String
+kind: String
+ref: String
}
SplitwiseService "1" *-- "*" Group
SplitwiseService --> SplitStrategy
Group "1" *-- "1" BalanceSheet
Group "1" *-- "*" LedgerEntry
Group "1" *-- "*" Activity
LedgerEntry <|.. Expense
LedgerEntry <|.. Settlement
SplitStrategy <|.. EqualSplit
SplitStrategy <|.. ExactSplit
SplitStrategy <|.. PercentSplit
SplitStrategy <|.. ShareSplit
EqualSplit ..> Money : allocate
PercentSplit ..> Money : allocate
ShareSplit ..> Money : allocate
SplitwiseService ..> DebtSimplifier
What's deliberately absent:
- No
Balanceentity stored per pair in a table of its own. Balances are a projection of the entries. The sheet is a cache of that projection, whichrebuildcan always recompute. - No
EqualExpense,PercentExpensesubclasses. The split mode affects how shares are computed, once. After that, every expense is the same shape: a payer and a map of shares. Subclassing on the mode would freeze a computation into the type hierarchy. - No user-level balance stored on
User. A user's total is the sum of their nets across groups, computed on demand. Storing it would be a second copy to keep in sync under concurrency, for no benefit.
4. Key flows
Adding an expense
sequenceDiagram
actor A as Asha
participant S as SplitwiseService
participant G as Group goa
participant P as EqualSplit
participant M as Money.allocate
participant B as BalanceSheet
A->>S: addExpense(goa, paidBy asha, 10000, equal, asha bob chen)
S->>S: strategy exists, total is positive
S->>G: acquire group lock
S->>S: actor, payer, participants are members, participants distinct
S->>P: split(10000, 3 users, no values)
P->>M: allocate(10000, weights 1 1 1)
M-->>P: 3334, 3333, 3333
P-->>S: asha 3334, bob 3333, chen 3333
S->>S: shares sum to total
Note over S,B: every check passed, now mutate
S->>G: store Expense e1
S->>B: apply(bob owes asha 3333, chen owes asha 3333)
S->>G: append Activity, then release lock
S-->>A: Expense e1
Everything that can fail happens before the first write. If percentages add up to 99.99%, the strategy throws, nothing has been stored, the activity log has no entry and the balances haven't moved. The ledger page calls this "validate, then mutate", and it's the single habit that most separates working machine-coding solutions from broken ones.
Simplify, then settle up
sequenceDiagram
actor C as Chen
participant S as SplitwiseService
participant D as DebtSimplifier
participant B as BalanceSheet
C->>S: simplified(goa)
S->>B: nets() under the group lock
B-->>S: asha +2666, bob +1167, chen -3833
S->>D: simplify(nets)
D->>D: largest creditor asha, largest debtor chen, transfer 2666
D->>D: largest creditor bob, largest debtor chen, transfer 1167
D-->>S: chen pays asha 2666, chen pays bob 1167
S-->>C: two transfers
C->>S: settle(goa, chen pays asha 2666)
S->>B: chen net is -3833, asha net is +2666, so allowed
S->>B: apply(asha owes chen 2666)
C->>S: settle(goa, chen pays bob 1168)
S-->>C: rejected, would create new debt
C->>S: settle(goa, chen pays bob 1167)
S->>B: apply(bob owes chen 1167)
B-->>S: all nets are zero
Note that simplified reads a snapshot and returns. It doesn't lock anything for the user while they open their banking app. When they come back and record the settlement, the guard re-checks against the current balances. If someone added an expense in the meantime, the settlement may still be valid, or it may be rejected with a clear message. Either way, money can't be created.
Undoing an expense
sequenceDiagram
actor A as Asha
participant S as SplitwiseService
participant G as Group goa
participant B as BalanceSheet
A->>S: undo(goa, e1)
S->>G: lock, look up e1
S->>S: e1 exists and is not in undone
S->>B: apply(e1 edges, sign -1)
S->>G: add e1 to undone
S->>G: append Activity undo e1
S-->>A: ok
A->>S: undo(goa, e1)
S-->>A: rejected, nothing to undo for e1
The expense record isn't deleted. It stays in entries, marked undone, and the history shows both the original "Asha paid ₹100 for dinner" and the later "Asha undid e1". That's what users expect from a money app: if a balance changed, they can see why.
Lifecycle of a ledger entry
stateDiagram-v2
[*] --> Validating: addExpense or settle
Validating --> Rejected: any check fails
Validating --> Active: stored, edges applied
Active --> Undone: undo applies edges with sign -1
Rejected --> [*]
Undone --> [*]
note right of Active
Editing an expense is
undo plus a new expense
end note
There's no Edited state. If an expense's amount or split changes in place, the history no longer explains the balances. "Undo, then add the corrected expense" keeps every state change explained by an entry, and a UI can still present it as a single "edit" with both entries linked by a reference.
What simplification does to the debt graph
The example group above, drawn as a graph of who owes whom before and after simplification:
flowchart LR
subgraph Pairwise["Pairwise debts, 3 transfers"]
direction LR
b1["bob"] -->|"3.33"| a1["asha"]
c1["chen"] -->|"23.33"| a1
c1 -->|"15.00"| b1
end
subgraph Simplified["Simplified, 2 transfers"]
direction LR
c2["chen"] -->|"26.66"| a2["asha"]
c2 -->|"11.67"| b2["bob"]
end
Both plans settle everyone. The simplified one moves ₹38.33 in total, all of it Chen's, in two transfers. The pairwise one moves ₹41.66 in three, because Bob pays Asha ₹3.33 while receiving ₹15.00 from Chen. Bob no longer has to pay anyone in the simplified plan, even though he owed Asha on the pairwise view. That second point is a product decision, not just an optimisation, and section 11 comes back to it.
5. Patterns, why, and the alternatives rejected
Strategy for split modes
Each mode is a different rule for turning a total into shares, with its own validation: equal takes no values, exact amounts must sum to the total, percentages must sum to 100%, shares must be positive. That's Strategy: one interface, split(total, users, values), and a registry from mode name to implementation. Adding "split by adjustment" (equal, plus or minus a fixed amount per person) is a new class and one line in the registry.
The shared core is allocate(total, weights). Equal is weights of 1, percent is the basis points, and shares are the share counts. Three of the four strategies are a validation check plus one call. This is a good moment in an interview to point out that the strategies differ in validation, while the arithmetic is one well-tested function. Duplicating the arithmetic per strategy is how one mode ends up rounding differently from the others.
Alternative rejected: an if/else on the mode in addExpense. It's what the code looks like at minute 20 of a machine-coding round. It breaks the open/closed principle as soon as the fifth mode arrives, and validation for all modes ends up interleaved in one method.
Alternative rejected: subclasses of Expense per mode. Discussed above. The mode decides how to compute shares once. After that, it's history.
Command for ledger entries, with undo by inverse
Each LedgerEntry is a Command in the strict sense: an object that captures a change and can apply it. Here "apply" is sheet.apply(entry.edges(), +1) and "undo" is the same call with −1. Because the entries are stored, the group can always be rebuilt by replaying them, which makes the entry list the source of truth and the balance sheet a cache. That's the event-sourcing idea at class scale.
Alternative rejected: Memento snapshots. Save the whole balance sheet before each change, and restore it to undo. That works for "undo the last thing" in a text editor. It fails here for two reasons:
- Out-of-order undo. Undoing last Tuesday's expense by restoring last Tuesday's snapshot throws away every expense since then. You'd have to restore and then replay everything after, which is the command approach with extra steps.
- Cost. A snapshot of the pairwise view is O(members²) per change. An edge list is O(participants).
Memento is the right tool when changes don't commute, such as a document where later edits depend on earlier positions. Balances are a sum, sums commute, and that's what makes inverse commands both correct and cheap here.
Alternative rejected: deleting the expense and recomputing. Deleting loses the history ("why did my balance change?"), and recomputing a group with ten thousand expenses on every undo is wasteful when the inverse edges are right there.
Facade and aggregate root
SplitwiseService is a facade over groups, and Group is an aggregate root in the DDD sense: every change to a group's money goes through the service while holding that group's lock, which is what makes the invariants enforceable. From Nouns to Classes covers aggregates. The practical consequence is that the balance sheet has no public setters. Nothing outside the service can write net["asha"] = 0 and break conservation.
Value objects for money and transfers
Transfer, Activity, Expense and Settlement are immutable. Immutability and Value Objects explains the general benefits. The specific one here: an Expense handed back to a caller can be read on another thread without a lock, and a caller can't change the shares of a stored expense after the edges were applied. Mutating a stored expense would silently break the replay invariant.
The core code keeps money as a bare long of minor units with the currency held by the group, which is enough while a group has one currency. Extension B introduces a Money(minor, currency) value object at the point where two currencies can meet, because that's when mixing them by accident becomes possible.
A pure function for simplification
simplify(nets) takes a map and returns a list. It has no state, touches no lock and reads no group. That makes it trivially testable (property tests run it on thousands of random inputs), and it means the service can swap in a different algorithm, such as the exact solver in Extension A, without touching anything else. Strategy again, if you want to name it, although a function parameter is all it needs.
Patterns deliberately not used
- Observer for "notify the group when an expense is added". Real Splitwise does this. Nothing in the requirements needs it, and adding it later is a listener list in the service. The notification service case study is what those listeners would call.
- Singleton service. Tests create a fresh service per test.
- Repository interfaces. The machine-coding ledger uses them, because swapping storage is a likely live extension there. In this design the in-memory maps live inside the service, which keeps the locking story visible. In production the group, its entries and its activity would load and save together as one aggregate.
6. Money: minor units and the remainder rule
Money deserves its own section, because it's where most expense-sharing solutions are quietly wrong.
Never use floating point. 0.1 + 0.2 isn't 0.3 in binary floating point, and the errors accumulate over a long trip. Store amounts as integers in the currency's minor unit: paise for rupees, cents for dollars. Not every currency has two decimal places. The yen has none and the Kuwaiti dinar has three, which matters in Extension B. Parse user input by hand ("12.5" becomes 1250) rather than through a float.
Percentages as basis points. "33.33%" is a common input, and as a float it's 0.3333000000000000184…. As basis points it's the integer 3333, and "do the percentages add up to 100%?" becomes the exact check sum == 10000.
The remainder has to go somewhere. ₹100.00 split three ways is 3333.33… paise each. Something has to be rounded, and the parts must still add up to exactly 10000. The options:
| Rule | Example: 10000 split 1 : 1 : 1 | Problem |
|---|---|---|
| Round each part | 3333, 3333, 3333 = 9999 | Loses a paisa. Conservation broken. |
| Payer absorbs the remainder | Payer's share 3334 | Fine for equal splits, but for 2 : 1 : 1 it can push the payer's share off by more than one unit from exact |
| First listed participant absorbs it | 3334, 3333, 3333 | Simple. With weighted splits, the first person can receive a unit that should have gone to someone with a bigger fractional part. |
| Random | Varies | Not reproducible, so replay and tests break |
| Largest remainder | 3334, 3333, 3333 | ✅ Every part is within one minor unit of its exact value, and it's deterministic |
The largest-remainder method works in three steps. Compute each part's exact value as total × weight ÷ sum of weights. Give everyone the floor of that. Then hand the leftover units, one each, to the parts with the largest fractional remainders, breaking ties by position in the participant list. For 1001 paise split 2 : 1 : 1, the exact parts are 500.5, 250.25 and 250.25. The floors are 500, 250 and 250, leaving one unit, which goes to the largest remainder, 0.5. The result is 501, 250, 250.
The integer version never computes a fraction. total × weight // W is the floor, and total × weight % W is the remainder scaled by W, which compares correctly because every part shares the same denominator. Two implementation notes:
- Overflow.
total × weightcan be large. A ₹10 crore expense is 10⁹ paise, and with basis-point weights up to 10⁴ the product is 10¹³, which fits in a 64-bit integer with a lot of room to spare. Java usesMath.multiplyExactso an absurd input throws instead of wrapping silently. Python integers don't overflow. JavaScript numbers lose integer precision above 2⁵³ ≈ 9 × 10¹⁵, so the TypeScriptallocatedoes the multiplication inBigInt. - Determinism is the point. Undo and replay assume that the shares stored on an expense are the shares. They're computed once, stored, and never recomputed. But tests, imports and any rebuild from raw inputs all assume the same input gives the same output, and the tie-break by position is what guarantees that.
7. Debt simplification
The problem
After a trip, the pairwise view might say Bob owes Asha, Chen owes Asha, and Chen owes Bob. Three transfers. But Bob is owed by Chen about as much as he owes Asha, so Chen could pay Asha directly and Bob would be out of it. Simplification finds a set of transfers that settles every balance with as few transfers as possible.
The first observation does most of the work: only net balances matter. Who originally owed whom is irrelevant to settling up. If everyone's net reaches zero, everyone is square. So simplification takes the map of nets, where creditors are positive, debtors are negative, and the values sum to zero, and produces transfers.
Any plan in which nobody both pays and receives moves exactly the sum of the positive nets in total. So all sensible plans move the same total amount of money. What differs is how many transfers they need.
Greedy min-cash-flow
The standard algorithm, and the one Splitwise-style apps are generally understood to use:
- Find the largest creditor and the largest debtor.
- Transfer
min(credit, debt)from the debtor to the creditor. - At least one of them is now at zero. Remove them.
- Repeat until nobody is left.
Each step zeroes at least one person, and the final step zeroes two, so for n people with non-zero balances it produces at most n − 1 transfers. Nobody pays and receives, so the total money moved is the minimum. Ties are broken by user id so the plan is deterministic. The code uses a linear scan per step, which is O(n²) overall and fine for any real group. Heaps make it O(n log n) if a "group" ever means a company with thousands of members.
Minimising the number of transfers exactly is NP-hard
At most n − 1 is a bound, not the optimum. Here's the structure of the real optimum. Suppose the people can be split into k disjoint groups, each of which sums to zero by itself. Each group of size m can settle internally in m − 1 transfers, so the whole thing needs n − k transfers. Conversely, any settlement plan, viewed as a graph, has connected components that each sum to zero, and a component of m people needs at least m − 1 edges to be connected. So:
where is the largest number of disjoint zero-sum subsets the nets can be partitioned into.
Now ask the simplest version of the question: can this group settle in n − 2 transfers? That's true exactly when , which means some proper, non-empty subset of the nets sums to zero. That is the subset-sum problem, which is NP-complete. To see the reduction, take any subset-sum instance (positive integers with sum and target ) and build a group with creditors and two debtors and . A proper zero-sum subset exists exactly when some of the sum to (paired with the first debtor) or to (paired with the second, which is the complement case). So a fast exact algorithm for minimum transfers would give a fast algorithm for subset sum. Finding the minimum number of transfers is NP-hard, and no polynomial-time algorithm for it is known.
Where greedy is not optimal: a worked counterexample
Take five people with these nets, in rupees:
| Person | Net |
|---|---|
| A | +6 |
| B | +5 |
| C | −3 |
| D | −3 |
| E | −5 |
Greedy runs like this:
| Step | Largest creditor | Largest debtor | Transfer | Remaining |
|---|---|---|---|---|
| 1 | A (+6) | E (−5) | E pays A 5 | A +1, B +5, C −3, D −3 |
| 2 | B (+5) | C (−3), tie with D broken by id | C pays B 3 | A +1, B +2, D −3 |
| 3 | B (+2) | D (−3) | D pays B 2 | A +1, D −1 |
| 4 | A (+1) | D (−1) | D pays A 1 | everyone at 0 |
Four transfers. But look at the nets again. E owes exactly what B is owed, and C and D together owe exactly what A is owed. That's two zero-sum groups, {B, E} and {A, C, D}, so the minimum is 5 − 2 = 3 transfers: E pays B 5, C pays A 3, D pays A 3.
Greedy went wrong at step 1. It matched the largest creditor with the largest debtor (A with E) because they were the largest, and that broke up the {B, E} pair, which was a perfect match. Greedy has no notion of "these two cancel exactly", and finding all such cancellations in general is the subset-sum problem above. Both the demo code and the tests assert that greedy returns four transfers on this input, and that the three-transfer plan settles everyone too.
How much does it matter? Greedy is never worse than n − 1, and the optimum is never better than about n / 2 (every zero-sum group has at least two people). For real groups of 4 to 10 people with arbitrary amounts, exact zero-sum subsets are rare, so greedy is usually optimal or one transfer away. When exact matters, and n is small, Extension A computes the true minimum.
8. The code
All three versions implement the same design and finish with a demo that checks: parsing and formatting, the remainder rule on three cases, the four split modes, nets after three expenses, five invalid expenses that must leave no trace, the pairwise and simplified views, settlement including a rejected overpayment, undo and double undo, replay against the incremental sheet, the history, the greedy counterexample and, in Java and Python, eight threads adding and undoing expenses on one group at once.
- Java 24:
javac SplitwiseDemo.java && java SplitwiseDemo. - Python 3.12: save as
splitwise.py, thenpython splitwise.py. The tests and extensions below import it. - TypeScript: save as
splitwise.tsin a folder with"type": "module", thennpx tsx splitwise.ts. It typechecks undertsc --strict --target es2022 --module nodenextwith@types/node.
// SplitwiseDemo.java -> javac SplitwiseDemo.java && java SplitwiseDemo
import java.util.*;
import java.util.concurrent.atomic.AtomicLong;
import java.util.stream.Collectors;
class ValidationException extends RuntimeException { ValidationException(String m) { super(m); } }
final class Money {
private Money() {}
static long toMinor(String text) { // "12.5" -> 1250, exponent 2
String[] p = text.trim().split("\\.", -1);
if (p.length > 2 || !p[0].matches("\\d+") || (p.length == 2 && !p[1].matches("\\d{1,2}")))
throw new ValidationException("bad amount " + text);
String frac = p.length == 2 ? (p[1] + "00").substring(0, 2) : "00";
return Math.addExact(Math.multiplyExact(Long.parseLong(p[0]), 100), Long.parseLong(frac));
}
static String fmt(long minor) {
return (minor < 0 ? "-" : "") + Math.abs(minor) / 100 + "." + String.format("%02d", Math.abs(minor) % 100);
}
/** Largest remainder: floor each part, hand leftover units to the biggest remainders, ties by position. */
static long[] allocate(long total, long[] weights) {
long w = 0;
for (long x : weights) { if (x < 0) throw new ValidationException("negative weight"); w += x; }
if (w <= 0) throw new ValidationException("weights must have a positive sum");
long[] parts = new long[weights.length];
long[] rems = new long[weights.length];
long given = 0;
for (int i = 0; i < weights.length; i++) {
long product = Math.multiplyExact(total, weights[i]); // throws instead of silently overflowing
parts[i] = product / w; rems[i] = product % w; given += parts[i];
}
Integer[] order = new Integer[weights.length];
for (int i = 0; i < order.length; i++) order[i] = i;
Arrays.sort(order, (a, b) -> rems[a] != rems[b] ? Long.compare(rems[b], rems[a]) : Integer.compare(a, b));
for (int k = 0; k < total - given; k++) parts[order[k]]++;
return parts;
}
}
// ---------- split strategies ----------
interface SplitStrategy { Map<String, Long> split(long total, List<String> users, List<Long> values); }
final class Splits {
static Map<String, Long> zip(List<String> users, long[] parts) {
Map<String, Long> out = new LinkedHashMap<>();
for (int i = 0; i < users.size(); i++) out.put(users.get(i), parts[i]);
return out;
}
static long[] arr(List<Long> v) { return v.stream().mapToLong(Long::longValue).toArray(); }
static void oneEach(List<String> users, List<Long> values, long min, String what) {
if (values.size() != users.size() || values.stream().anyMatch(v -> v < min))
throw new ValidationException(what);
}
}
final class EqualSplit implements SplitStrategy {
public Map<String, Long> split(long total, List<String> users, List<Long> values) {
if (!values.isEmpty()) throw new ValidationException("equal split takes no values");
long[] ones = new long[users.size()];
Arrays.fill(ones, 1);
return Splits.zip(users, Money.allocate(total, ones));
}
}
final class ExactSplit implements SplitStrategy {
public Map<String, Long> split(long total, List<String> users, List<Long> values) {
Splits.oneEach(users, values, 0, "exact split needs one non-negative amount per participant");
long sum = values.stream().mapToLong(Long::longValue).sum();
if (sum != total) throw new ValidationException("exact amounts sum to " + sum + ", expected " + total);
return Splits.zip(users, Splits.arr(values));
}
}
final class PercentSplit implements SplitStrategy { // basis points: 33.33% is 3333
public Map<String, Long> split(long total, List<String> users, List<Long> values) {
Splits.oneEach(users, values, 0, "percent split needs one non-negative percentage per participant");
if (values.stream().mapToLong(Long::longValue).sum() != 10_000)
throw new ValidationException("percentages must sum to 100%");
return Splits.zip(users, Money.allocate(total, Splits.arr(values)));
}
}
final class ShareSplit implements SplitStrategy {
public Map<String, Long> split(long total, List<String> users, List<Long> values) {
Splits.oneEach(users, values, 1, "share split needs one positive share count per participant");
return Splits.zip(users, Money.allocate(total, Splits.arr(values)));
}
}
// ---------- ledger entries (Command: apply with +1, undo with -1) ----------
record Edge(String debtor, String creditor, long amount) {}
record Transfer(String debtor, String creditor, long amount) {}
record Activity(long seq, String actor, String kind, String ref, String summary) {}
interface LedgerEntry { String id(); List<Edge> edges(); }
record Expense(String id, String paidBy, long total, String kind, Map<String, Long> shares, String description)
implements LedgerEntry {
public List<Edge> edges() {
return shares.entrySet().stream()
.filter(e -> !e.getKey().equals(paidBy) && e.getValue() > 0)
.map(e -> new Edge(e.getKey(), paidBy, e.getValue())).toList();
}
}
record Settlement(String id, String payer, String payee, long amount) implements LedgerEntry {
public List<Edge> edges() { return List.of(new Edge(payee, payer, amount)); } // cancels the debt
}
final class BalanceSheet {
final TreeMap<String, Long> net = new TreeMap<>();
final TreeMap<String, Long> pair = new TreeMap<>(); // "a|b" with a < b; positive means a owes b
void apply(List<Edge> edges, int sign) {
for (Edge e : edges) {
long x = e.amount() * sign;
net.merge(e.creditor(), x, Long::sum);
net.merge(e.debtor(), -x, Long::sum);
boolean ordered = e.debtor().compareTo(e.creditor()) < 0;
String key = ordered ? e.debtor() + "|" + e.creditor() : e.creditor() + "|" + e.debtor();
if (pair.merge(key, ordered ? x : -x, Long::sum) == 0) pair.remove(key);
}
}
Map<String, Long> nets() {
Map<String, Long> out = new TreeMap<>();
net.forEach((u, v) -> { if (v != 0) out.put(u, v); });
return out;
}
List<Transfer> debts() {
List<Transfer> out = new ArrayList<>();
pair.forEach((k, v) -> {
String[] ab = k.split("\\|");
out.add(v > 0 ? new Transfer(ab[0], ab[1], v) : new Transfer(ab[1], ab[0], -v));
});
return out;
}
}
final class DebtSimplifier {
/** Greedy min-cash-flow. At most n-1 transfers, not always the minimum (that is NP-hard). */
static List<Transfer> simplify(Map<String, Long> nets) {
if (nets.values().stream().mapToLong(Long::longValue).sum() != 0) throw new ValidationException("nets must sum to zero");
TreeMap<String, Long> credit = new TreeMap<>(), debit = new TreeMap<>();
nets.forEach((u, v) -> { if (v > 0) credit.put(u, v); else if (v < 0) debit.put(u, -v); });
List<Transfer> out = new ArrayList<>();
while (!credit.isEmpty()) {
String c = largest(credit), d = largest(debit); // Simplification: O(n) scan per step, heaps if groups get huge
long x = Math.min(credit.get(c), debit.get(d));
out.add(new Transfer(d, c, x));
if (credit.merge(c, -x, Long::sum) == 0) credit.remove(c);
if (debit.merge(d, -x, Long::sum) == 0) debit.remove(d);
}
return out;
}
private static String largest(TreeMap<String, Long> book) { // ties go to the smallest id
String best = null;
for (var e : book.entrySet()) if (best == null || e.getValue() > book.get(best)) best = e.getKey();
return best;
}
}
final class Group {
final String id, name, currency;
final List<String> members;
final BalanceSheet sheet = new BalanceSheet();
final Map<String, LedgerEntry> entries = new LinkedHashMap<>();
final Set<String> undone = new HashSet<>();
final List<Activity> activity = new ArrayList<>();
Group(String id, String name, String currency, List<String> members) {
this.id = id; this.name = name; this.currency = currency; this.members = new ArrayList<>(members);
}
}
final class SplitwiseService {
private final Map<String, String> users = new HashMap<>();
private final Map<String, Group> groups = new HashMap<>();
private final Map<String, SplitStrategy> strategies = Map.of(
"equal", new EqualSplit(), "exact", new ExactSplit(), "percent", new PercentSplit(), "share", new ShareSplit());
private final AtomicLong ids = new AtomicLong(), seq = new AtomicLong();
synchronized void addUser(String id, String name) {
if (users.putIfAbsent(id, name) != null) throw new ValidationException("user " + id + " exists");
}
synchronized Group createGroup(String id, String name, String currency, List<String> members) {
if (groups.containsKey(id)) throw new ValidationException("group " + id + " exists");
if (members.isEmpty() || new HashSet<>(members).size() != members.size() || !users.keySet().containsAll(members))
throw new ValidationException("members must be distinct, known users");
Group g = new Group(id, name, currency, members);
groups.put(id, g);
return g;
}
private synchronized Group group(String id) {
Group g = groups.get(id);
if (g == null) throw new ValidationException("no group " + id);
return g;
}
private synchronized boolean known(String user) { return users.containsKey(user); }
private void log(Group g, String actor, String kind, String ref, String summary) {
g.activity.add(new Activity(seq.incrementAndGet(), actor, kind, ref, summary));
}
void addMember(String groupId, String user) {
Group g = group(groupId);
synchronized (g) {
if (!known(user) || g.members.contains(user)) throw new ValidationException("cannot add " + user);
g.members.add(user);
}
}
void removeMember(String groupId, String user) {
Group g = group(groupId);
synchronized (g) {
if (g.sheet.net.getOrDefault(user, 0L) != 0) throw new ValidationException(user + " has an open balance");
g.members.remove(user);
}
}
Expense addExpense(String groupId, String actor, String paidBy, long total, String kind,
List<String> participants, List<Long> values, String description) {
Group g = group(groupId);
SplitStrategy strategy = strategies.get(kind);
if (strategy == null) throw new ValidationException("unknown split " + kind);
if (total <= 0) throw new ValidationException("total must be positive");
synchronized (g) { // validate everything, then mutate
for (String u : concat(actor, paidBy, participants))
if (!g.members.contains(u)) throw new ValidationException(u + " is not in " + g.name);
if (participants.isEmpty() || new HashSet<>(participants).size() != participants.size())
throw new ValidationException("participants must be non-empty and distinct");
Map<String, Long> shares = strategy.split(total, participants, values);
if (shares.values().stream().mapToLong(Long::longValue).sum() != total)
throw new IllegalStateException("strategy lost money");
Expense e = new Expense("e" + ids.incrementAndGet(), paidBy, total, kind, Map.copyOf(shares), description);
g.entries.put(e.id(), e);
g.sheet.apply(e.edges(), 1);
log(g, actor, "expense", e.id(), paidBy + " paid " + Money.fmt(total) + " for " + description);
return e;
}
}
Settlement settle(String groupId, String actor, String payer, String payee, long amount) {
Group g = group(groupId);
synchronized (g) {
if (payer.equals(payee) || !g.members.contains(payer) || !g.members.contains(payee) || amount <= 0)
throw new ValidationException("bad settlement");
if (g.sheet.net.getOrDefault(payer, 0L) > -amount || g.sheet.net.getOrDefault(payee, 0L) < amount)
throw new ValidationException(payer + " paying " + payee + " " + Money.fmt(amount) + " would create new debt");
Settlement s = new Settlement("s" + ids.incrementAndGet(), payer, payee, amount);
g.entries.put(s.id(), s);
g.sheet.apply(s.edges(), 1);
log(g, actor, "settlement", s.id(), payer + " paid " + payee + " " + Money.fmt(amount));
return s;
}
}
void undo(String groupId, String actor, String entryId) {
Group g = group(groupId);
synchronized (g) {
LedgerEntry entry = g.entries.get(entryId);
if (entry == null || g.undone.contains(entryId)) throw new ValidationException("nothing to undo for " + entryId);
g.sheet.apply(entry.edges(), -1);
g.undone.add(entryId);
log(g, actor, "undo", entryId, "undid " + entryId);
}
}
List<Transfer> balances(String groupId) { Group g = group(groupId); synchronized (g) { return g.sheet.debts(); } }
Map<String, Long> nets(String groupId) { Group g = group(groupId); synchronized (g) { return g.sheet.nets(); } }
List<Transfer> simplified(String groupId) { return DebtSimplifier.simplify(nets(groupId)); }
List<Activity> history(String groupId) { Group g = group(groupId); synchronized (g) { return List.copyOf(g.activity); } }
BalanceSheet rebuild(String groupId) {
Group g = group(groupId);
synchronized (g) {
BalanceSheet sheet = new BalanceSheet();
g.entries.forEach((id, e) -> { if (!g.undone.contains(id)) sheet.apply(e.edges(), 1); });
return sheet;
}
}
/** Cross-group snapshot: lock the groups in id order so two callers can't deadlock. */
Map<String, Long> userTotal(String user) {
List<Group> mine;
synchronized (this) {
mine = groups.values().stream().sorted(Comparator.comparing(x -> x.id)).collect(Collectors.toList());
}
return lockAll(mine, 0, user, new TreeMap<>());
}
private Map<String, Long> lockAll(List<Group> gs, int i, String user, Map<String, Long> acc) {
if (i == gs.size()) return acc;
Group g = gs.get(i);
synchronized (g) {
if (g.members.contains(user)) acc.merge(g.currency, g.sheet.net.getOrDefault(user, 0L), Long::sum);
return lockAll(gs, i + 1, user, acc);
}
}
private static List<String> concat(String a, String b, List<String> rest) {
List<String> all = new ArrayList<>(List.of(a, b));
all.addAll(rest);
return all;
}
}
public class SplitwiseDemo {
static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }
static void rejects(Runnable r, String what) {
try { r.run(); } catch (ValidationException expected) { return; }
throw new AssertionError("should reject: " + what);
}
public static void main(String[] args) throws Exception {
check(Money.toMinor("100") == 10000 && Money.toMinor("12.5") == 1250 && Money.fmt(-5).equals("-0.05"), "money");
check(Arrays.equals(Money.allocate(10000, new long[]{1, 1, 1}), new long[]{3334, 3333, 3333}), "equal");
check(Arrays.equals(Money.allocate(1000, new long[]{3333, 3333, 3334}), new long[]{333, 333, 334}), "percent");
check(Arrays.equals(Money.allocate(1001, new long[]{2, 1, 1}), new long[]{501, 250, 250}), "share");
SplitwiseService s = new SplitwiseService();
for (String u : List.of("asha", "bob", "chen", "dev")) s.addUser(u, u);
List<String> three = List.of("asha", "bob", "chen");
s.createGroup("goa", "Goa trip", "INR", three);
Expense dinner = s.addExpense("goa", "asha", "asha", Money.toMinor("100.00"), "equal", three, List.of(), "dinner");
check(dinner.shares().equals(Map.of("asha", 3334L, "bob", 3333L, "chen", 3333L)), "dinner shares");
s.addExpense("goa", "bob", "bob", Money.toMinor("60"), "percent", three, List.of(5000L, 2500L, 2500L), "fuel");
s.addExpense("goa", "chen", "chen", Money.toMinor("40"), "share", List.of("asha", "chen"), List.of(1L, 3L), "snacks");
check(s.nets("goa").equals(Map.of("asha", 2666L, "bob", 1167L, "chen", -3833L)), "nets");
Map<String, Long> before = s.nets("goa");
int logged = s.history("goa").size();
rejects(() -> s.addExpense("goa", "asha", "asha", 1000, "exact", List.of("asha", "bob"), List.of(600L, 300L), ""), "exact sum");
rejects(() -> s.addExpense("goa", "asha", "asha", 1000, "percent", List.of("asha", "bob"), List.of(5000L, 4000L), ""), "percent sum");
rejects(() -> s.addExpense("goa", "asha", "dev", 1000, "equal", List.of("asha"), List.of(), ""), "non-member");
rejects(() -> s.addExpense("goa", "asha", "asha", 1000, "share", List.of("asha", "bob"), List.of(1L, 0L), ""), "zero share");
check(s.nets("goa").equals(before) && s.history("goa").size() == logged, "rejections change nothing");
check(s.balances("goa").equals(List.of(new Transfer("bob", "asha", 333), new Transfer("chen", "asha", 2333),
new Transfer("chen", "bob", 1500))), "pairwise");
check(s.simplified("goa").equals(List.of(new Transfer("chen", "asha", 2666), new Transfer("chen", "bob", 1167))), "simplified");
s.settle("goa", "chen", "chen", "asha", 2666);
rejects(() -> s.settle("goa", "chen", "chen", "bob", 1168), "overpay");
s.settle("goa", "chen", "chen", "bob", 1167);
check(s.nets("goa").isEmpty(), "settled");
s.undo("goa", "asha", dinner.id());
check(s.nets("goa").equals(Map.of("asha", -6666L, "bob", 3333L, "chen", 3333L)), "undo");
check(s.rebuild("goa").nets().equals(s.nets("goa")), "rebuild");
rejects(() -> s.undo("goa", "asha", dinner.id()), "double undo");
check(s.history("goa").stream().map(Activity::kind).toList()
.equals(List.of("expense", "expense", "expense", "settlement", "settlement", "undo")), "history");
Map<String, Long> nets = new TreeMap<>(Map.of("A", 600L, "B", 500L, "C", -300L, "D", -300L, "E", -500L));
check(DebtSimplifier.simplify(nets).size() == 4, "greedy is not optimal here: 3 transfers suffice");
List<String> four = List.of("asha", "bob", "chen", "dev");
s.createGroup("flat", "Flat", "INR", four);
List<Thread> threads = new ArrayList<>();
for (int i = 0; i < 8; i++) {
final int t = i;
threads.add(Thread.ofPlatform().start(() -> {
for (int j = 0; j < 200; j++) {
Expense e = s.addExpense("flat", "asha", four.get(j % 4), 1000 + t + j, "equal", four, List.of(), "x");
if (j % 5 == 0) s.undo("flat", "asha", e.id());
}
}));
}
for (Thread th : threads) th.join();
check(s.nets("flat").values().stream().mapToLong(Long::longValue).sum() == 0, "conserved");
check(s.rebuild("flat").nets().equals(s.nets("flat")), "replay matches");
check(s.history("flat").size() == 8 * 240, "every action logged");
long asha = s.nets("goa").getOrDefault("asha", 0L) + s.nets("flat").getOrDefault("asha", 0L);
check(s.userTotal("asha").equals(Map.of("INR", asha)), "cross-group total");
System.out.println("splitwise checks passed");
}
}
"""splitwise.py: groups, expenses, splits, balances, debt simplification, settle-up, undo.
Run: python splitwise.py"""
from __future__ import annotations
import itertools
import threading
from dataclasses import dataclass, field
from typing import Protocol
class ValidationError(ValueError): ...
# ---------- money ----------
def to_minor(text: str, exponent: int = 2) -> int:
"""'12.5' -> 1250. Parsed by hand: floats never touch money."""
whole, _, frac = text.strip().partition(".")
if not whole.isdigit() or (frac and not frac.isdigit()) or len(frac) > exponent:
raise ValidationError(f"bad amount {text!r}")
return int(whole) * 10 ** exponent + int(frac.ljust(exponent, "0") or 0)
def fmt(minor: int, exponent: int = 2) -> str:
sign, minor = ("-" if minor < 0 else ""), abs(minor)
return f"{sign}{minor // 10 ** exponent}.{minor % 10 ** exponent:0{exponent}d}" if exponent else f"{sign}{minor}"
def allocate(total: int, weights: list[int]) -> list[int]:
"""Split `total` minor units in proportion to `weights` so the parts sum to `total` exactly.
Largest remainder method: floor every part, then give the leftover units, one each, to the
largest fractional remainders. Ties go to the earlier position, so the result is deterministic."""
w = sum(weights)
if w <= 0 or any(x < 0 for x in weights):
raise ValidationError("weights must be non-negative with a positive sum")
parts = [total * x // w for x in weights]
remainders = [total * x % w for x in weights]
leftover = total - sum(parts)
for i in sorted(range(len(weights)), key=lambda i: (-remainders[i], i))[:leftover]:
parts[i] += 1
return parts
# ---------- split strategies ----------
class SplitStrategy(Protocol):
def split(self, total: int, users: list[str], values: list[int]) -> dict[str, int]: ...
class EqualSplit:
def split(self, total, users, values):
if values:
raise ValidationError("equal split takes no values")
return dict(zip(users, allocate(total, [1] * len(users))))
class ExactSplit:
def split(self, total, users, values):
if len(values) != len(users) or any(v < 0 for v in values):
raise ValidationError("exact split needs one non-negative amount per participant")
if sum(values) != total:
raise ValidationError(f"exact amounts sum to {sum(values)}, expected {total}")
return dict(zip(users, values))
class PercentSplit:
"""Values are basis points (1% = 100), so 33.33% is expressible and the check is exact."""
def split(self, total, users, values):
if len(values) != len(users) or any(v < 0 for v in values):
raise ValidationError("percent split needs one non-negative percentage per participant")
if sum(values) != 10_000:
raise ValidationError(f"percentages sum to {sum(values) / 100}%, expected 100%")
return dict(zip(users, allocate(total, values)))
class ShareSplit:
def split(self, total, users, values):
if len(values) != len(users) or any(v <= 0 for v in values):
raise ValidationError("share split needs one positive share count per participant")
return dict(zip(users, allocate(total, values)))
STRATEGIES: dict[str, SplitStrategy] = {
"equal": EqualSplit(), "exact": ExactSplit(), "percent": PercentSplit(), "share": ShareSplit()}
# ---------- ledger entries (Command: apply with sign +1, undo with sign -1) ----------
Edge = tuple[str, str, int] # (debtor, creditor, amount)
@dataclass(frozen=True)
class Expense:
id: str
paid_by: str
total: int
kind: str
shares: dict[str, int]
description: str
def edges(self) -> list[Edge]:
return [(u, self.paid_by, s) for u, s in self.shares.items() if u != self.paid_by and s > 0]
@dataclass(frozen=True)
class Settlement:
id: str
payer: str
payee: str
amount: int
def edges(self) -> list[Edge]:
# Paying someone back is the same as them now owing you that amount: it cancels.
return [(self.payee, self.payer, self.amount)]
@dataclass(frozen=True)
class Transfer:
debtor: str
creditor: str
amount: int
@dataclass(frozen=True)
class Activity:
seq: int
actor: str
kind: str # expense, settlement, undo
ref: str
summary: str
class BalanceSheet:
"""Two views of one set of edges: each user's net, and netted debts per pair."""
def __init__(self) -> None:
self.net: dict[str, int] = {}
self.pair: dict[tuple[str, str], int] = {} # (a, b) with a < b. Positive: a owes b.
def apply(self, edges: list[Edge], sign: int = 1) -> None:
for debtor, creditor, amount in edges:
amount *= sign
self.net[creditor] = self.net.get(creditor, 0) + amount
self.net[debtor] = self.net.get(debtor, 0) - amount
key, s = ((debtor, creditor), 1) if debtor < creditor else ((creditor, debtor), -1)
self.pair[key] = self.pair.get(key, 0) + s * amount
if self.pair[key] == 0:
del self.pair[key]
def nets(self) -> dict[str, int]:
return {u: v for u, v in sorted(self.net.items()) if v != 0}
def debts(self) -> list[Transfer]:
return [Transfer(a, b, v) if v > 0 else Transfer(b, a, -v) for (a, b), v in sorted(self.pair.items())]
def simplify(nets: dict[str, int]) -> list[Transfer]:
"""Greedy min-cash-flow: repeatedly settle the largest debtor against the largest creditor.
At most n-1 transfers. Not always the minimum count: that problem is NP-hard."""
if sum(nets.values()) != 0:
raise ValidationError("nets must sum to zero")
credit = {u: v for u, v in nets.items() if v > 0}
debit = {u: -v for u, v in nets.items() if v < 0}
out: list[Transfer] = []
while credit:
# Simplification: O(n) scan per step, O(n^2) total; heaps if a group ever has thousands of members
c = min(credit, key=lambda u: (-credit[u], u))
d = min(debit, key=lambda u: (-debit[u], u))
x = min(credit[c], debit[d])
out.append(Transfer(d, c, x))
for book, u in ((credit, c), (debit, d)):
book[u] -= x
if book[u] == 0:
del book[u]
return out
@dataclass
class Group:
id: str
name: str
currency: str
members: list[str]
sheet: BalanceSheet = field(default_factory=BalanceSheet)
entries: dict[str, Expense | Settlement] = field(default_factory=dict)
undone: set[str] = field(default_factory=set)
activity: list[Activity] = field(default_factory=list)
lock: threading.Lock = field(default_factory=threading.Lock, repr=False)
class SplitwiseService:
def __init__(self) -> None:
self.users: dict[str, str] = {}
self.groups: dict[str, Group] = {}
self._ids = itertools.count(1)
self._seq = itertools.count(1)
self._lock = threading.Lock() # guards the registries and the id counters only
def _next(self, prefix: str) -> str:
with self._lock:
return f"{prefix}{next(self._ids)}"
def _log(self, g: Group, actor: str, kind: str, ref: str, summary: str) -> None:
with self._lock:
seq = next(self._seq)
g.activity.append(Activity(seq, actor, kind, ref, summary))
def _group(self, group_id: str) -> Group:
g = self.groups.get(group_id)
if g is None:
raise ValidationError(f"no group {group_id}")
return g
def add_user(self, user_id: str, name: str) -> None:
with self._lock:
if user_id in self.users:
raise ValidationError(f"user {user_id} exists")
self.users[user_id] = name
def create_group(self, group_id: str, name: str, currency: str, members: list[str]) -> Group:
with self._lock:
if group_id in self.groups:
raise ValidationError(f"group {group_id} exists")
if not members or len(set(members)) != len(members) or any(m not in self.users for m in members):
raise ValidationError("members must be distinct, known users")
g = self.groups[group_id] = Group(group_id, name, currency, list(members))
return g
def add_member(self, group_id: str, user_id: str) -> None:
g = self._group(group_id)
with g.lock:
if user_id not in self.users or user_id in g.members:
raise ValidationError(f"cannot add {user_id}")
g.members.append(user_id)
def remove_member(self, group_id: str, user_id: str) -> None:
g = self._group(group_id)
with g.lock:
if g.sheet.net.get(user_id, 0) != 0:
raise ValidationError(f"{user_id} has an open balance of {fmt(g.sheet.net[user_id])}")
g.members.remove(user_id)
def add_expense(self, group_id: str, actor: str, paid_by: str, total: int, kind: str,
participants: list[str], values: list[int] | None = None, description: str = "") -> Expense:
g = self._group(group_id)
strategy = STRATEGIES.get(kind)
if strategy is None:
raise ValidationError(f"unknown split {kind}")
if total <= 0:
raise ValidationError("total must be positive")
with g.lock: # validate everything, then mutate
for u in [actor, paid_by, *participants]:
if u not in g.members:
raise ValidationError(f"{u} is not in {g.name}")
if not participants or len(set(participants)) != len(participants):
raise ValidationError("participants must be non-empty and distinct")
shares = strategy.split(total, list(participants), list(values or []))
assert sum(shares.values()) == total # every strategy must conserve money
e = Expense(self._next("e"), paid_by, total, kind, shares, description)
g.entries[e.id] = e
g.sheet.apply(e.edges())
self._log(g, actor, "expense", e.id, f"{paid_by} paid {fmt(total)} for {description or kind}")
return e
def settle(self, group_id: str, actor: str, payer: str, payee: str, amount: int) -> Settlement:
g = self._group(group_id)
with g.lock:
if payer == payee or payer not in g.members or payee not in g.members or amount <= 0:
raise ValidationError("bad settlement")
if g.sheet.net.get(payer, 0) > -amount or g.sheet.net.get(payee, 0) < amount:
raise ValidationError(f"{payer} paying {payee} {fmt(amount)} would create new debt")
s = Settlement(self._next("s"), payer, payee, amount)
g.entries[s.id] = s
g.sheet.apply(s.edges())
self._log(g, actor, "settlement", s.id, f"{payer} paid {payee} {fmt(amount)}")
return s
def undo(self, group_id: str, actor: str, entry_id: str) -> None:
g = self._group(group_id)
with g.lock:
entry = g.entries.get(entry_id)
if entry is None or entry_id in g.undone:
raise ValidationError(f"nothing to undo for {entry_id}")
g.sheet.apply(entry.edges(), sign=-1)
g.undone.add(entry_id)
self._log(g, actor, "undo", entry_id, f"undid {entry_id}")
# ---------- reads (each returns a snapshot taken under the group lock) ----------
def balances(self, group_id: str) -> list[Transfer]:
g = self._group(group_id)
with g.lock:
return g.sheet.debts()
def nets(self, group_id: str) -> dict[str, int]:
g = self._group(group_id)
with g.lock:
return g.sheet.nets()
def simplified(self, group_id: str) -> list[Transfer]:
return simplify(self.nets(group_id))
def history(self, group_id: str) -> list[Activity]:
g = self._group(group_id)
with g.lock:
return list(g.activity)
def rebuild(self, group_id: str) -> BalanceSheet:
"""Replay every live entry. Must always equal the incremental sheet."""
g = self._group(group_id)
with g.lock:
sheet = BalanceSheet()
for eid, entry in g.entries.items():
if eid not in g.undone:
sheet.apply(entry.edges())
return sheet
def user_total(self, user_id: str) -> dict[str, int]:
"""A consistent cross-group snapshot: lock every group, always in id order."""
groups = sorted((g for g in self.groups.values() if user_id in g.members), key=lambda g: g.id)
for g in groups:
g.lock.acquire()
try:
out: dict[str, int] = {}
for g in groups:
out[g.currency] = out.get(g.currency, 0) + g.sheet.net.get(user_id, 0)
return out
finally:
for g in reversed(groups):
g.lock.release()
# ---------- demo and checks ----------
def demo() -> None:
assert to_minor("100") == 10000 and to_minor("12.5") == 1250 and fmt(-5) == "-0.05"
assert allocate(10000, [1, 1, 1]) == [3334, 3333, 3333]
assert allocate(1000, [3333, 3333, 3334]) == [333, 333, 334]
assert allocate(1001, [2, 1, 1]) == [501, 250, 250]
assert allocate(5, [1, 1, 1, 1, 1, 1, 1]) == [1, 1, 1, 1, 1, 0, 0]
s = SplitwiseService()
for u in ["asha", "bob", "chen", "dev"]:
s.add_user(u, u.title())
s.create_group("goa", "Goa trip", "INR", ["asha", "bob", "chen"])
dinner = s.add_expense("goa", "asha", "asha", to_minor("100.00"), "equal", ["asha", "bob", "chen"],
description="dinner")
assert dinner.shares == {"asha": 3334, "bob": 3333, "chen": 3333}
s.add_expense("goa", "bob", "bob", to_minor("60"), "percent", ["asha", "bob", "chen"], [5000, 2500, 2500])
s.add_expense("goa", "chen", "chen", to_minor("40"), "share", ["asha", "chen"], [1, 3])
assert s.nets("goa") == {"asha": 2666, "bob": 1167, "chen": -3833}
assert sum(s.nets("goa").values()) == 0
before = (s.nets("goa"), len(s.history("goa")))
for bad in [lambda: s.add_expense("goa", "asha", "asha", 1000, "exact", ["asha", "bob"], [600, 300]),
lambda: s.add_expense("goa", "asha", "asha", 1000, "percent", ["asha", "bob"], [5000, 4000]),
lambda: s.add_expense("goa", "asha", "dev", 1000, "equal", ["asha"]),
lambda: s.add_expense("goa", "asha", "asha", 1000, "share", ["asha", "bob"], [1, 0]),
lambda: s.add_expense("goa", "asha", "asha", 1000, "equal", ["bob", "bob"])]:
try:
bad()
raise AssertionError("should have been rejected")
except ValidationError:
pass
assert (s.nets("goa"), len(s.history("goa"))) == before # rejected commands change nothing
assert s.balances("goa") == [Transfer("bob", "asha", 333), Transfer("chen", "asha", 2333),
Transfer("chen", "bob", 1500)] # pairwise: three debts
assert s.simplified("goa") == [Transfer("chen", "asha", 2666), Transfer("chen", "bob", 1167)]
s.settle("goa", "chen", "chen", "asha", 2666)
try:
s.settle("goa", "chen", "chen", "bob", 1168)
raise AssertionError("overpaying must be rejected")
except ValidationError:
pass
s.settle("goa", "chen", "chen", "bob", 1167)
assert s.nets("goa") == {}
s.undo("goa", "asha", dinner.id)
assert s.nets("goa") == {"asha": -6666, "bob": 3333, "chen": 3333} # dinner reversed
assert s.rebuild("goa").nets() == s.nets("goa")
try:
s.undo("goa", "asha", dinner.id)
raise AssertionError("double undo must fail")
except ValidationError:
pass
kinds = [a.kind for a in s.history("goa")]
assert kinds == ["expense", "expense", "expense", "settlement", "settlement", "undo"]
# The counterexample: greedy needs 4 transfers where 3 suffice.
nets = {"A": 600, "B": 500, "C": -300, "D": -300, "E": -500}
greedy = simplify(nets)
assert len(greedy) == 4
optimal = [Transfer("E", "B", 500), Transfer("C", "A", 300), Transfer("D", "A", 300)]
for plan in (greedy, optimal):
left = dict(nets)
for t in plan:
left[t.debtor] += t.amount
left[t.creditor] -= t.amount
assert all(v == 0 for v in left.values())
# Concurrency: 8 threads hammer one group; money is conserved and the log replays exactly.
s.create_group("flat", "Flat", "INR", ["asha", "bob", "chen", "dev"])
def worker(i: int) -> None:
for j in range(200):
e = s.add_expense("flat", "asha", ["asha", "bob", "chen", "dev"][j % 4], 1000 + i + j, "equal",
["asha", "bob", "chen", "dev"])
if j % 5 == 0:
s.undo("flat", "asha", e.id)
threads = [threading.Thread(target=worker, args=(i,)) for i in range(8)]
for t in threads:
t.start()
for t in threads:
t.join()
assert sum(s.nets("flat").values()) == 0
assert s.rebuild("flat").nets() == s.nets("flat")
assert len(s.history("flat")) == 8 * 200 + 8 * 40
assert s.user_total("asha") == {"INR": s.nets("goa").get("asha", 0) + s.nets("flat").get("asha", 0)}
print("splitwise checks passed")
if __name__ == "__main__":
demo()
// splitwise.ts -> npx tsx splitwise.ts (typechecks with tsc --strict --target es2022)
import assert from "node:assert/strict";
export class ValidationError extends Error {}
// ---------- money: integer minor units ----------
export function toMinor(text: string): number {
const m = /^(\d+)(?:\.(\d{1,2}))?$/.exec(text.trim());
if (!m) throw new ValidationError(`bad amount ${text}`);
const v = Number(m[1]) * 100 + Number((m[2] ?? "").padEnd(2, "0"));
if (!Number.isSafeInteger(v)) throw new ValidationError("amount too large");
return v;
}
export const fmt = (minor: number) =>
`${minor < 0 ? "-" : ""}${Math.floor(Math.abs(minor) / 100)}.${String(Math.abs(minor) % 100).padStart(2, "0")}`;
/** Largest remainder, in BigInt so total * weight can't lose precision past 2^53. */
export function allocate(total: number, weights: number[]): number[] {
if (weights.some((x) => x < 0 || !Number.isInteger(x))) throw new ValidationError("weights must be non-negative integers");
const w = weights.reduce((a, b) => a + BigInt(b), 0n);
if (w <= 0n) throw new ValidationError("weights must have a positive sum");
const t = BigInt(total);
const parts = weights.map((x) => (t * BigInt(x)) / w);
const rems = weights.map((x) => (t * BigInt(x)) % w);
let leftover = Number(t - parts.reduce((a, b) => a + b, 0n));
const order = weights.map((_, i) => i).sort((a, b) => (rems[b] > rems[a] ? 1 : rems[b] < rems[a] ? -1 : a - b));
for (const i of order) { if (leftover-- <= 0) break; parts[i] += 1n; }
return parts.map(Number);
}
// ---------- split strategies ----------
export type Shares = Map<string, number>;
export interface SplitStrategy { split(total: number, users: string[], values: number[]): Shares }
const zip = (users: string[], parts: number[]): Shares => new Map(users.map((u, i) => [u, parts[i]]));
const sum = (xs: Iterable<number>) => { let s = 0; for (const x of xs) s += x; return s; };
function oneEach(users: string[], values: number[], min: number, what: string): void {
if (values.length !== users.length || values.some((v) => !Number.isInteger(v) || v < min)) throw new ValidationError(what);
}
export const STRATEGIES: Record<string, SplitStrategy> = {
equal: {
split(total, users, values) {
if (values.length) throw new ValidationError("equal split takes no values");
return zip(users, allocate(total, users.map(() => 1)));
},
},
exact: {
split(total, users, values) {
oneEach(users, values, 0, "exact split needs one non-negative amount per participant");
if (sum(values) !== total) throw new ValidationError(`exact amounts sum to ${sum(values)}, expected ${total}`);
return zip(users, values);
},
},
percent: { // basis points: 33.33% is 3333
split(total, users, values) {
oneEach(users, values, 0, "percent split needs one non-negative percentage per participant");
if (sum(values) !== 10_000) throw new ValidationError("percentages must sum to 100%");
return zip(users, allocate(total, values));
},
},
share: {
split(total, users, values) {
oneEach(users, values, 1, "share split needs one positive share count per participant");
return zip(users, allocate(total, values));
},
},
};
// ---------- ledger entries (Command: apply with +1, undo with -1) ----------
export interface Edge { debtor: string; creditor: string; amount: number }
export interface Transfer { debtor: string; creditor: string; amount: number }
export interface Activity { seq: number; actor: string; kind: "expense" | "settlement" | "undo"; ref: string; summary: string }
export interface LedgerEntry { readonly id: string; edges(): Edge[] }
export class Expense implements LedgerEntry {
constructor(readonly id: string, readonly paidBy: string, readonly total: number, readonly kind: string,
readonly shares: ReadonlyMap<string, number>, readonly description: string) {}
edges(): Edge[] {
return [...this.shares].filter(([u, s]) => u !== this.paidBy && s > 0)
.map(([u, s]) => ({ debtor: u, creditor: this.paidBy, amount: s }));
}
}
export class Settlement implements LedgerEntry {
constructor(readonly id: string, readonly payer: string, readonly payee: string, readonly amount: number) {}
edges(): Edge[] { return [{ debtor: this.payee, creditor: this.payer, amount: this.amount }]; }
}
export class BalanceSheet {
readonly net = new Map<string, number>();
readonly pair = new Map<string, number>(); // "a|b" with a < b, positive means a owes b
apply(edges: Edge[], sign: 1 | -1 = 1): void {
for (const { debtor, creditor, amount } of edges) {
const x = amount * sign;
this.net.set(creditor, (this.net.get(creditor) ?? 0) + x);
this.net.set(debtor, (this.net.get(debtor) ?? 0) - x);
const ordered = debtor < creditor;
const key = ordered ? `${debtor}|${creditor}` : `${creditor}|${debtor}`;
const v = (this.pair.get(key) ?? 0) + (ordered ? x : -x);
if (v === 0) this.pair.delete(key); else this.pair.set(key, v);
}
}
nets(): Record<string, number> {
return Object.fromEntries([...this.net].filter(([, v]) => v !== 0).sort(([a], [b]) => (a < b ? -1 : 1)));
}
debts(): Transfer[] {
return [...this.pair].sort(([a], [b]) => (a < b ? -1 : 1)).map(([k, v]) => {
const [a, b] = k.split("|");
return v > 0 ? { debtor: a, creditor: b, amount: v } : { debtor: b, creditor: a, amount: -v };
});
}
}
/** Greedy min-cash-flow. At most n-1 transfers, not always the minimum (that is NP-hard). */
export function simplify(nets: Record<string, number>): Transfer[] {
if (sum(Object.values(nets)) !== 0) throw new ValidationError("nets must sum to zero");
const credit = new Map<string, number>(), debit = new Map<string, number>();
for (const [u, v] of Object.entries(nets)) { if (v > 0) credit.set(u, v); else if (v < 0) debit.set(u, -v); }
// Simplification: O(n) scan per step, heaps if a group ever has thousands of members
const largest = (book: Map<string, number>) =>
[...book].reduce((best, cur) => (cur[1] > best[1] || (cur[1] === best[1] && cur[0] < best[0]) ? cur : best))[0];
const out: Transfer[] = [];
while (credit.size) {
const c = largest(credit), d = largest(debit);
const x = Math.min(credit.get(c)!, debit.get(d)!);
out.push({ debtor: d, creditor: c, amount: x });
for (const [book, u] of [[credit, c], [debit, d]] as const) {
const left = book.get(u)! - x;
if (left === 0) book.delete(u); else book.set(u, left);
}
}
return out;
}
export class Group {
readonly sheet = new BalanceSheet();
readonly entries = new Map<string, LedgerEntry>();
readonly undone = new Set<string>();
readonly activity: Activity[] = [];
constructor(readonly id: string, readonly name: string, readonly currency: string, readonly members: string[]) {}
}
/** Every method is synchronous, so on Node's single thread each one runs to completion without interleaving. */
export class SplitwiseService {
private readonly users = new Map<string, string>();
private readonly groups = new Map<string, Group>();
private ids = 0;
private seq = 0;
addUser(id: string, name: string): void {
if (this.users.has(id)) throw new ValidationError(`user ${id} exists`);
this.users.set(id, name);
}
createGroup(id: string, name: string, currency: string, members: string[]): Group {
if (this.groups.has(id)) throw new ValidationError(`group ${id} exists`);
if (!members.length || new Set(members).size !== members.length || members.some((m) => !this.users.has(m)))
throw new ValidationError("members must be distinct, known users");
const g = new Group(id, name, currency, [...members]);
this.groups.set(id, g);
return g;
}
private group(id: string): Group {
const g = this.groups.get(id);
if (!g) throw new ValidationError(`no group ${id}`);
return g;
}
private log(g: Group, actor: string, kind: Activity["kind"], ref: string, summary: string): void {
g.activity.push({ seq: ++this.seq, actor, kind, ref, summary });
}
addMember(groupId: string, user: string): void {
const g = this.group(groupId);
if (!this.users.has(user) || g.members.includes(user)) throw new ValidationError(`cannot add ${user}`);
g.members.push(user);
}
removeMember(groupId: string, user: string): void {
const g = this.group(groupId);
if ((g.sheet.net.get(user) ?? 0) !== 0) throw new ValidationError(`${user} has an open balance`);
g.members.splice(g.members.indexOf(user), 1);
}
addExpense(groupId: string, actor: string, paidBy: string, total: number, kind: string,
participants: string[], values: number[] = [], description = ""): Expense {
const g = this.group(groupId);
const strategy = STRATEGIES[kind];
if (!strategy) throw new ValidationError(`unknown split ${kind}`);
if (!Number.isSafeInteger(total) || total <= 0) throw new ValidationError("total must be a positive integer");
for (const u of [actor, paidBy, ...participants])
if (!g.members.includes(u)) throw new ValidationError(`${u} is not in ${g.name}`);
if (!participants.length || new Set(participants).size !== participants.length)
throw new ValidationError("participants must be non-empty and distinct");
const shares = strategy.split(total, [...participants], [...values]);
if (sum(shares.values()) !== total) throw new Error("strategy lost money");
const e = new Expense(`e${++this.ids}`, paidBy, total, kind, shares, description);
g.entries.set(e.id, e);
g.sheet.apply(e.edges());
this.log(g, actor, "expense", e.id, `${paidBy} paid ${fmt(total)} for ${description || kind}`);
return e;
}
settle(groupId: string, actor: string, payer: string, payee: string, amount: number): Settlement {
const g = this.group(groupId);
if (payer === payee || !g.members.includes(payer) || !g.members.includes(payee) || !(amount > 0))
throw new ValidationError("bad settlement");
if ((g.sheet.net.get(payer) ?? 0) > -amount || (g.sheet.net.get(payee) ?? 0) < amount)
throw new ValidationError(`${payer} paying ${payee} ${fmt(amount)} would create new debt`);
const s = new Settlement(`s${++this.ids}`, payer, payee, amount);
g.entries.set(s.id, s);
g.sheet.apply(s.edges());
this.log(g, actor, "settlement", s.id, `${payer} paid ${payee} ${fmt(amount)}`);
return s;
}
undo(groupId: string, actor: string, entryId: string): void {
const g = this.group(groupId);
const entry = g.entries.get(entryId);
if (!entry || g.undone.has(entryId)) throw new ValidationError(`nothing to undo for ${entryId}`);
g.sheet.apply(entry.edges(), -1);
g.undone.add(entryId);
this.log(g, actor, "undo", entryId, `undid ${entryId}`);
}
balances(groupId: string): Transfer[] { return this.group(groupId).sheet.debts(); }
nets(groupId: string): Record<string, number> { return this.group(groupId).sheet.nets(); }
simplified(groupId: string): Transfer[] { return simplify(this.nets(groupId)); }
history(groupId: string): Activity[] { return [...this.group(groupId).activity]; }
rebuild(groupId: string): BalanceSheet {
const g = this.group(groupId);
const sheet = new BalanceSheet();
for (const [id, e] of g.entries) if (!g.undone.has(id)) sheet.apply(e.edges());
return sheet;
}
}
// ---------- demo and checks ----------
function demo(): void {
assert.equal(toMinor("100"), 10000);
assert.equal(toMinor("12.5"), 1250);
assert.equal(fmt(-5), "-0.05");
assert.deepEqual(allocate(10000, [1, 1, 1]), [3334, 3333, 3333]);
assert.deepEqual(allocate(1000, [3333, 3333, 3334]), [333, 333, 334]);
assert.deepEqual(allocate(1001, [2, 1, 1]), [501, 250, 250]);
assert.deepEqual(allocate(9e15, [1, 2]), [3e15, 6e15]); // exact past 2^53 intermediate products
const s = new SplitwiseService();
for (const u of ["asha", "bob", "chen", "dev"]) s.addUser(u, u);
const three = ["asha", "bob", "chen"];
s.createGroup("goa", "Goa trip", "INR", three);
const dinner = s.addExpense("goa", "asha", "asha", toMinor("100.00"), "equal", three, [], "dinner");
assert.deepEqual([...dinner.shares.values()], [3334, 3333, 3333]);
s.addExpense("goa", "bob", "bob", toMinor("60"), "percent", three, [5000, 2500, 2500], "fuel");
s.addExpense("goa", "chen", "chen", toMinor("40"), "share", ["asha", "chen"], [1, 3], "snacks");
assert.deepEqual(s.nets("goa"), { asha: 2666, bob: 1167, chen: -3833 });
const before = JSON.stringify([s.nets("goa"), s.history("goa").length]);
assert.throws(() => s.addExpense("goa", "asha", "asha", 1000, "exact", ["asha", "bob"], [600, 300]), ValidationError);
assert.throws(() => s.addExpense("goa", "asha", "asha", 1000, "percent", ["asha", "bob"], [5000, 4000]), ValidationError);
assert.throws(() => s.addExpense("goa", "asha", "dev", 1000, "equal", ["asha"]), ValidationError);
assert.throws(() => s.addExpense("goa", "asha", "asha", 1000, "share", ["asha", "bob"], [1, 0]), ValidationError);
assert.throws(() => s.addExpense("goa", "asha", "asha", 10.5, "equal", ["asha", "bob"]), ValidationError);
assert.equal(JSON.stringify([s.nets("goa"), s.history("goa").length]), before);
assert.deepEqual(s.balances("goa"), [
{ debtor: "bob", creditor: "asha", amount: 333 },
{ debtor: "chen", creditor: "asha", amount: 2333 },
{ debtor: "chen", creditor: "bob", amount: 1500 },
]);
assert.deepEqual(s.simplified("goa"), [
{ debtor: "chen", creditor: "asha", amount: 2666 },
{ debtor: "chen", creditor: "bob", amount: 1167 },
]);
s.settle("goa", "chen", "chen", "asha", 2666);
assert.throws(() => s.settle("goa", "chen", "chen", "bob", 1168), ValidationError);
s.settle("goa", "chen", "chen", "bob", 1167);
assert.deepEqual(s.nets("goa"), {});
s.undo("goa", "asha", dinner.id);
assert.deepEqual(s.nets("goa"), { asha: -6666, bob: 3333, chen: 3333 });
assert.deepEqual(s.rebuild("goa").nets(), s.nets("goa"));
assert.throws(() => s.undo("goa", "asha", dinner.id), ValidationError);
assert.deepEqual(s.history("goa").map((a) => a.kind), ["expense", "expense", "expense", "settlement", "settlement", "undo"]);
assert.equal(simplify({ A: 600, B: 500, C: -300, D: -300, E: -500 }).length, 4); // 3 would do
console.log("splitwise checks passed");
}
if (process.argv[1]?.endsWith("splitwise.ts")) demo();
Walking through the important decisions
The pair key is ordered. The pairwise view stores one signed number per unordered pair, keyed by the two ids in sorted order. Positive means the first owes the second. That makes netting automatic. "Bob owes Asha 30" and "Asha owes Bob 30" land on the same key with opposite signs and sum to zero, at which point the entry is removed. The alternative, two directed entries per pair that you net when reading, means every reader has to remember to net.
Nets and pairs are updated in the same loop. They're two views of the same edges, and updating them separately is how they drift. Replay checks both.
assert sum(shares) == total inside addExpense. Every strategy is supposed to conserve money, and the tests check that they do. The check in the service is a second line of defence. A bug in a future strategy fails loudly at the moment it happens, instead of slowly unbalancing a group. In Java it's an IllegalStateException, not an assert, because Java assertions are off unless the JVM runs with -ea.
Settlement validation uses nets, not pairs. "Chen can pay Asha up to what Chen owes overall and up to what Asha is owed overall" makes settling through the simplified plan legal even when, pairwise, Chen never owed Asha anything. Validating against pairs would reject the very transfers the simplified view just recommended.
The ids and sequence numbers come from the service. Activity sequence numbers are global and increasing, so a merged feed across groups sorts correctly. In Java they're AtomicLongs. In Python they're itertools.count objects advanced under the service lock.
userTotal locks every group, in id order. It's the only operation that reads more than one group. Taking the locks in a fixed global order (sorted by group id) means two concurrent calls can never each hold a lock the other wants. The Java version takes them through recursion so each synchronized block releases correctly. The Python version acquires them in a loop and releases them in a finally. The alternative is to read each group under its own lock, one at a time. That's cheaper but not a consistent snapshot, because a settlement between two of the user's groups' members could land between the reads. For a display total that's usually acceptable, and it's worth offering the interviewer that trade-off.
9. Concurrency
What's shared
| State | Written by | Protected by |
|---|---|---|
| User and group registries | addUser, createGroup | The service lock |
| Id and sequence counters | Every write | Atomics in Java, the service lock in Python |
| A group's members, entries, undone set, activity, balance sheet | addMember, addExpense, settle, undo | That group's lock |
Expense, Settlement, Transfer, Activity | Nobody after creation | Immutability |
The result of simplify | Nobody, it's a fresh list | Confinement to the caller |
One lock per group
A group is the unit of consistency: every invariant (conservation, replay, settlement guard) is about one group. So the lock is per group. Different groups proceed in parallel. Within a group, operations are serialised, which costs nothing in practice. A busy group sees a few writes a minute, and each critical section is a handful of map updates.
Validation runs under the lock. "Is Dev a member?" and "would this settlement create debt?" are check-then-act sequences. If the check ran before taking the lock, another thread could remove Dev, or settle the same debt, between the check and the write. The only checks done outside the lock are the ones that don't depend on group state: the split mode exists and the total is positive.
Lock order. The only nesting in the design is group lock → service lock, when an operation inside a group takes the next id or sequence number, or checks that a user exists. The service lock is never held while taking a group lock, so that order can't invert. userTotal holds several group locks at once, always in id order, and takes no service lock while holding them. That's the whole deadlock analysis, and in an interview it's worth saying in exactly those words. Deadlocks covers lock ordering in general.
Races designed out
| Race | What would go wrong | Prevention |
|---|---|---|
| Two expenses in one group apply edges at once | Lost update on a net. Money appears or vanishes. | Group lock around validate-and-apply |
| Two people settle the same debt at once | Both pass the guard, the payee ends up owing | The guard and the apply happen under one lock |
| Two people undo the same expense at once | Applied twice, balances wrong | The undone check and insert happen under the lock |
| Undo races with a new expense | None, as long as both are serialised | Group lock. Order doesn't matter because edges commute. |
| A member is removed while an expense naming them is validated | An expense for a non-member | Membership is checked under the same lock as the write |
| A reader sees half-applied edges | Nets that don't sum to zero | Readers take the lock and copy |
Stale reads are fine, stale writes aren't
A user opens the app, sees "you owe Asha ₹26.66", pays her through their bank, and records the settlement two minutes later. Meanwhile Bob added a ₹50 expense. The user's view was stale, and that's unavoidable in any UI. What matters is that the write re-validates against current state. The settlement guard does exactly that. If the payment still fits, it's recorded. If not, the user gets an error and a fresh view. The concurrency test above does the same thing on purpose: it reads a plan, tries to settle, and accepts a rejection as a legitimate outcome.
When the lock is in a database
With persistence the per-group lock becomes one of two things:
- Pessimistic:
SELECT … FOR UPDATEon the group row at the start of each write transaction. Simple, and the throughput of one group is never the bottleneck. - Optimistic: a
versioncolumn on the group. Each write reads the version, does its work, and commits withUPDATE … WHERE id = ? AND version = ?. Zero rows updated means someone else got there first, so reload and retry. This also gives an API-level guard: the client sends the version it saw (anIf-Matchheader), and a write based on a stale view is rejected rather than silently applied.
Either way the group remains the unit, which is the point of making it the aggregate root. The movie booking case study works through the same pessimistic-versus-optimistic choice for seats.
TypeScript and the event loop
The TypeScript version has no locks because every method is synchronous. On Node's single thread, a synchronous method runs to completion before anything else runs, so addExpense is atomic for free. That stops being true the moment a method awaits something in the middle, such as a database read between validation and the write. At that point you need a per-group async mutex (a promise chain keyed by group id), and the same check-then-act reasoning applies.
10. Extensibility: "the interviewer adds X"
Extension A: the exact minimum number of transfers
"Your greedy plan has four transfers, and I can see a plan with three. Fix it."
Section 7 showed that the minimum is n − k, where k is the largest number of disjoint zero-sum groups. For small groups we can compute k exactly with dynamic programming over subsets. For each subset mask of the people, best[mask] is the most zero-sum "prefixes" in any ordering of that subset's members:
Then best[everyone] is k. Walking back down the optimal path recovers the zero-sum masks, and the difference between two consecutive ones is one group. Each group is then settled with greedy, which inside a zero-sum group of size m always uses at most m − 1 transfers. That's optimal for that group.
The cost is O(2ⁿ · n), which is about 20 million steps at n = 20, a fraction of a second. Beyond that the function falls back to greedy. That threshold is the honest answer to "what about a group of 50?": exact is infeasible in general, greedy is guaranteed at most n − 1, and for real data greedy is nearly always optimal or within one transfer.
"""Extension A: the minimum number of transfers, exactly, for small groups.
min transfers = n - k, where n is the number of people with a non-zero net and k is the largest
number of disjoint zero-sum subgroups they can be split into. Each subgroup of size m settles
internally in m - 1 transfers, and no plan can do better. Finding k is a set-partitioning problem
(NP-hard in general), so this is O(2^n * n) and only for small n."""
from splitwise import Transfer, ValidationError, simplify
MAX_EXACT = 20 # 2^20 * 20 is about 20 million steps
def simplify_exact(nets: dict[str, int]) -> list[Transfer]:
people = sorted(u for u, v in nets.items() if v != 0)
n = len(people)
if n > MAX_EXACT:
return simplify(nets) # fall back to greedy: still at most n - 1 transfers
values = [nets[u] for u in people]
full = (1 << n) - 1
total = [0] * (1 << n)
for mask in range(1, 1 << n):
low = (mask & -mask).bit_length() - 1
total[mask] = total[mask & (mask - 1)] + values[low]
if total[full] != 0:
raise ValidationError("nets must sum to zero")
# best[mask] = the most zero-sum "prefixes" in any ordering of mask's members.
best = [0] * (1 << n)
for mask in range(1, 1 << n):
best[mask] = max(best[mask ^ (1 << i)] for i in range(n) if mask >> i & 1) + (total[mask] == 0)
# Walk back down, recording the zero-sum masks on an optimal path. Consecutive ones differ by a group.
chain, mask = [], full
while mask:
if total[mask] == 0:
chain.append(mask)
gain = 1 if total[mask] == 0 else 0
i = next(i for i in range(n) if mask >> i & 1 and best[mask ^ (1 << i)] == best[mask] - gain)
mask ^= 1 << i
chain.append(0)
out: list[Transfer] = []
for outer, inner in zip(chain, chain[1:]):
group = outer & ~inner
out += simplify({people[i]: values[i] for i in range(n) if group >> i & 1})
return out
def settles(nets: dict[str, int], plan: list[Transfer]) -> bool:
left = dict(nets)
for t in plan:
left[t.debtor] += t.amount
left[t.creditor] -= t.amount
return all(v == 0 for v in left.values())
if __name__ == "__main__":
nets = {"A": 600, "B": 500, "C": -300, "D": -300, "E": -500}
greedy, exact = simplify(nets), simplify_exact(nets)
assert len(greedy) == 4 and len(exact) == 3
assert settles(nets, greedy) and settles(nets, exact)
assert Transfer("E", "B", 500) in exact
import random
rng = random.Random(7)
for _ in range(300): # exact is never worse than greedy, and both always settle everything
vals = [rng.randint(-5, 5) * 100 for _ in range(rng.randint(2, 9))]
vals.append(-sum(vals))
case = {f"u{i}": v for i, v in enumerate(vals)}
g, e = simplify(case), simplify_exact(case)
assert settles(case, g) and settles(case, e) and len(e) <= len(g)
print("exact simplification checks passed")
What changed: one new function, used in place of simplify by whoever wants it. The random check at the end compares exact and greedy on 300 inputs and confirms that exact is never worse and both always settle everyone.
Extension B: multiple currencies
"Our group went to the US and Japan. Some expenses are in dollars, some in yen, some in rupees."
The tempting design converts every foreign expense into the group currency when it's added. That bakes in an exchange rate nobody agreed to, and the result changes if you undo and redo the expense on a different day. The design that holds up keeps one balance sheet per currency. A dollar expense creates dollar debts, and nothing is converted until someone asks.
Two settlement options then follow:
- Per currency (default). Simplify each currency separately. More transfers, but no exchange-rate argument.
- Consolidated (on request). Convert every currency's nets into one target at stated rates, add them up, and simplify once. Fewer transfers.
Conversion hides a rounding trap. Converting each person's net separately and rounding each one can leave the converted nets summing to ±1 instead of 0, and then simplification fails or someone is short a paisa. The fix reuses the remainder rule: round the total that creditors are owed once, then allocate it across the creditors in proportion to their original nets, and the same total across the debtors. Both sides are then equal by construction, so the sum is exactly zero.
This is also where a real Money value object earns its place, because currencies have different numbers of minor units (yen 0, dollar 2, Kuwaiti dinar 3) and conversion has to rescale.
"""Extension B: expenses in several currencies.
Each currency keeps its own balance sheet, so nothing is converted until someone asks.
Converting is explicit, uses a stated rate, and keeps the converted nets summing to zero."""
from dataclasses import dataclass
from fractions import Fraction
from splitwise import BalanceSheet, Transfer, ValidationError, allocate, simplify
EXPONENT = {"INR": 2, "USD": 2, "EUR": 2, "JPY": 0, "KWD": 3} # minor units per currency differ
@dataclass(frozen=True)
class Money:
minor: int
currency: str
def __post_init__(self):
if self.currency not in EXPONENT:
raise ValidationError(f"unknown currency {self.currency}")
def convert_nets(nets: dict[str, int], src: str, dst: str, rate: Fraction) -> dict[str, int]:
"""`rate` is units of dst per unit of src, e.g. Fraction('83.25') INR per USD.
Converting each net and rounding separately can leave the sum at +1 or -1. Instead, round the
total once, then share it out with the same largest-remainder rule used for splits."""
scale = rate * Fraction(10 ** EXPONENT[dst], 10 ** EXPONENT[src])
credit = {u: v for u, v in nets.items() if v > 0}
debit = {u: -v for u, v in nets.items() if v < 0}
total = round(sum(credit.values()) * scale)
out: dict[str, int] = {}
for book, sign in ((credit, 1), (debit, -1)):
users = sorted(book)
if users:
for u, part in zip(users, allocate(total, [book[u] for u in users])):
out[u] = sign * part
return out
class MultiCurrencyLedger:
def __init__(self) -> None:
self.sheets: dict[str, BalanceSheet] = {}
def add(self, paid_by: str, amount: Money, shares: dict[str, int]) -> None:
if sum(shares.values()) != amount.minor:
raise ValidationError("shares must sum to the amount")
sheet = self.sheets.setdefault(amount.currency, BalanceSheet())
sheet.apply([(u, paid_by, s) for u, s in shares.items() if u != paid_by and s > 0])
def simplified(self) -> dict[str, list[Transfer]]:
"""Default: settle each currency in that currency. No rate risk, more transfers."""
return {c: simplify(sheet.nets()) for c, sheet in sorted(self.sheets.items()) if sheet.nets()}
def consolidated(self, target: str, rates: dict[str, Fraction]) -> list[Transfer]:
"""On request: convert every currency into one, then simplify once."""
combined: dict[str, int] = {}
for c, sheet in self.sheets.items():
rate = Fraction(1) if c == target else rates[c]
for u, v in convert_nets(sheet.nets(), c, target, rate).items():
combined[u] = combined.get(u, 0) + v
return simplify({u: v for u, v in combined.items() if v})
if __name__ == "__main__":
led = MultiCurrencyLedger()
led.add("asha", Money(9000, "USD"), {"asha": 3000, "bob": 3000, "chen": 3000}) # $90 hotel
led.add("bob", Money(150000, "INR"), {"asha": 50000, "bob": 50000, "chen": 50000}) # Rs 1,500 taxi
led.add("chen", Money(3000, "JPY"), {"asha": 1000, "bob": 1000, "chen": 1000}) # 3,000 yen, no minor unit
per_currency = led.simplified()
assert set(per_currency) == {"INR", "JPY", "USD"}
assert sum(len(v) for v in per_currency.values()) == 6
rates = {"USD": Fraction("83.25"), "JPY": Fraction("0.5537")}
plan = led.consolidated("INR", rates)
assert len(plan) <= 2 # three people: at most two transfers once everything is in rupees
odd = convert_nets({"a": 1, "b": 1, "c": -2}, "USD", "INR", Fraction("83.333"))
assert sum(odd.values()) == 0 # naive per-user rounding gives 83 + 83 - 167 = -1
print("multi-currency checks passed")
What changed: a ledger that maps currency to BalanceSheet, reusing the sheet, simplify and allocate unchanged. Rates are Fractions, so no float touches the conversion. In the interview, mention where the rate comes from (a rate service, snapshotted with a timestamp on the settlement) and that a consolidated plan should record which rates it used, so it can be explained later.
Extension C: several payers on one bill
"Asha paid ₹600 by card and Bob paid ₹400 in cash for a ₹1,000 dinner for three."
The edge model makes this a new entry type, not a change to the service internals. Who consumed what is still a split strategy: equal shares of 1000. Who paid is a map. Each consumer's share is owed to the payers in proportion to what they paid, which is allocate once more, so the edges sum exactly. Because the new entry has edges(), undo, replay and history work with no changes.
"""Extension C: one bill, several payers ("I paid 600 by card, you paid 400 in cash")."""
from dataclasses import dataclass
from splitwise import STRATEGIES, SplitwiseService, ValidationError, allocate
@dataclass(frozen=True)
class MultiPayerExpense:
id: str
paid: dict[str, int] # who put money in
shares: dict[str, int] # who consumed what
def edges(self):
"""Each consumer's share is owed to the payers in proportion to what they paid,
using the same deterministic allocation, so the edges sum to the bill exactly."""
payers = sorted(self.paid)
out = []
for user, share in self.shares.items():
for payer, part in zip(payers, allocate(share, [self.paid[p] for p in payers])):
if payer != user and part > 0:
out.append((user, payer, part))
return out
def add_multi_payer(svc: SplitwiseService, group_id: str, actor: str, paid: dict[str, int],
kind: str, participants: list[str], values: list[int] | None = None) -> MultiPayerExpense:
g = svc.groups[group_id]
total = sum(paid.values())
with g.lock:
if total <= 0 or any(v <= 0 for v in paid.values()):
raise ValidationError("every payer must pay a positive amount")
if any(u not in g.members for u in [actor, *paid, *participants]):
raise ValidationError("everyone must be a member")
e = MultiPayerExpense(svc._next("m"), dict(paid), STRATEGIES[kind].split(total, participants, values or []))
g.entries[e.id] = e # undo, rebuild and history work unchanged: it has edges()
g.sheet.apply(e.edges())
svc._log(g, actor, "expense", e.id, f"{', '.join(paid)} paid {total}")
return e
if __name__ == "__main__":
s = SplitwiseService()
for u in ["asha", "bob", "chen"]:
s.add_user(u, u)
s.create_group("g", "Dinner", "INR", ["asha", "bob", "chen"])
e = add_multi_payer(s, "g", "asha", {"asha": 60000, "bob": 40000}, "equal", ["asha", "bob", "chen"])
# Each eats 333.34 / 333.33 / 333.33. asha paid 600 and ate 333.34, so she is owed 266.66.
assert s.nets("g") == {"asha": 26666, "bob": 6667, "chen": -33333}
s.undo("g", "asha", e.id)
assert s.nets("g") == {} and s.rebuild("g").nets() == {}
print("multi-payer checks passed")
What changed: one new entry class and one service method. In a real codebase you'd fold it into addExpense by turning paidBy into a map with one entry for the common case. The point to make is that the balance sheet and the undo logic didn't need to know.
Other extensions to be ready for:
| Extension | Where the change goes |
|---|---|
| Edit an expense | Undo plus add, with the new activity referencing the old expense id |
| Recurring expenses (rent every month) | A scheduler that calls addExpense with an idempotency key such as rent:2026-11 so a retried job doesn't double-charge. The task scheduler builds the scheduler. |
| Itemised receipts (each person picks their items) | A new split strategy whose values are per-item assignments. Tax and tip are allocated in proportion to each person's items, using allocate. |
| Notify members when something changes | An observer on the service that calls the notification service |
| Settle through a payment provider | A settlement records a payment id and a status. Only a confirmed payment applies its edge. |
| "Simplify debts" as a per-group setting | A boolean on the group that picks which view the UI shows. Both are computed from the same sheet. |
| Persistence | Store the entries and activity. Rebuild the sheet on load, or store it with a version column and check it against a replay periodically. |
11. Testing approach
The design was chosen to make the hard properties testable, and the tests lean on three of them.
- Conservation. After any sequence of operations,
sum(nets) == 0. One random test runs 200 expenses and checks after each one. - Replay equals incremental.
rebuild(group)from the entries must match the live sheet, nets and pairs both. This one check catches a wrong sign in undo, a forgotten pair update, and a stored expense being mutated. - Rejected operations leave no trace. Snapshot the nets and the history, try six invalid expenses, and compare.
Then the specific rules:
- Money: parsing accepts
7,7.5and0.01and rejects1.234,-1,1e3,1,5and.5.allocateconserves the total on 2,000 random inputs, and every part is within one unit of its exact value. Ties go to the earlier position. Zero weights get nothing. - Splits: each mode on a hand-checked example, exact amounts that don't sum, percentages that sum to 100.01%, and a payer who isn't a participant.
- Balances: pairwise netting of two opposing debts.
- Simplification: a chain (A owes B, B owes C) collapses to one transfer. On 500 random inputs the plan always settles everyone, uses at most n − 1 transfers and never contains a zero transfer. The counterexample gives four. Unbalanced input is rejected.
- Settle and undo: settlement reduces both sides, overpayment in four different forms is rejected, settling through the simplified plan zeroes the group, undo reverses exactly, a double undo or an unknown id fails, undoing an expense after it was settled flips the debt, a settlement can be undone, and the history is append-only with increasing sequence numbers.
- Membership: a member with a balance can't be removed.
- Concurrency: eight threads run 300 rounds each across two groups, adding expenses, undoing some, reading a simplified plan and trying to settle its first transfer, and reading a cross-group total. At the end, both groups conserve money and replay matches. Any exception in a worker fails the test.
"""test_splitwise.py: python -m unittest test_splitwise -v"""
import random
import threading
import unittest
from splitwise import (SplitwiseService, Transfer, ValidationError, allocate, fmt, simplify, to_minor)
def settles(nets, plan):
left = dict(nets)
for t in plan:
left[t.debtor] = left.get(t.debtor, 0) + t.amount
left[t.creditor] = left.get(t.creditor, 0) - t.amount
return all(v == 0 for v in left.values())
class MoneyTests(unittest.TestCase):
def test_parse_and_format(self):
self.assertEqual([to_minor("0.01"), to_minor("7"), to_minor("7.5")], [1, 700, 750])
for bad in ["", "1.234", "-1", "1e3", "1,5", ".5"]:
with self.assertRaises(ValidationError):
to_minor(bad)
self.assertEqual(fmt(123456), "1234.56")
def test_allocate_always_conserves(self):
rng = random.Random(1)
for _ in range(2000):
weights = [rng.randint(0, 50) for _ in range(rng.randint(1, 8))]
if sum(weights) == 0:
continue
total = rng.randint(1, 10**9)
parts = allocate(total, weights)
self.assertEqual(sum(parts), total)
for p, w in zip(parts, weights): # no part is more than one unit from its exact value
self.assertLess(abs(p - total * w / sum(weights)), 1)
def test_allocate_is_deterministic_and_ties_go_first(self):
self.assertEqual(allocate(2, [1, 1, 1]), [1, 1, 0])
self.assertEqual(allocate(2, [1, 1, 1]), allocate(2, [1, 1, 1]))
def test_zero_weight_gets_nothing(self):
self.assertEqual(allocate(100, [0, 1, 1]), [0, 50, 50])
class Base(unittest.TestCase):
def setUp(self):
self.s = SplitwiseService()
for u in ["asha", "bob", "chen", "dev"]:
self.s.add_user(u, u)
self.s.create_group("g", "Trip", "INR", ["asha", "bob", "chen"])
def expense(self, payer, total, kind, who, values=None):
return self.s.add_expense("g", payer, payer, total, kind, who, values)
class SplitTests(Base):
def test_equal(self):
self.assertEqual(self.expense("asha", 100, "equal", ["asha", "bob", "chen"]).shares,
{"asha": 34, "bob": 33, "chen": 33})
def test_exact_must_sum(self):
with self.assertRaises(ValidationError):
self.expense("asha", 100, "exact", ["asha", "bob"], [50, 49])
self.assertEqual(self.expense("asha", 100, "exact", ["asha", "bob"], [51, 49]).shares["bob"], 49)
def test_percent_in_basis_points(self):
e = self.expense("asha", 10000, "percent", ["asha", "bob", "chen"], [3333, 3333, 3334])
self.assertEqual(sorted(e.shares.values()), [3333, 3333, 3334])
with self.assertRaises(ValidationError):
self.expense("asha", 100, "percent", ["asha", "bob"], [5000, 5001])
def test_share(self):
self.assertEqual(self.expense("asha", 900, "share", ["asha", "bob"], [2, 1]).shares, {"asha": 600, "bob": 300})
def test_payer_need_not_participate(self):
self.expense("asha", 1000, "equal", ["bob", "chen"])
self.assertEqual(self.s.nets("g"), {"asha": 1000, "bob": -500, "chen": -500})
def test_rejections_leave_no_trace(self):
snapshot = (self.s.nets("g"), self.s.history("g"))
for args in [(0, "equal", ["asha"], None), (100, "nope", ["asha"], None),
(100, "equal", [], None), (100, "equal", ["dev"], None),
(100, "equal", ["bob", "bob"], None), (100, "exact", ["bob"], [-1])]:
with self.assertRaises(ValidationError):
self.expense("asha", *args)
self.assertEqual((self.s.nets("g"), self.s.history("g")), snapshot)
class BalanceTests(Base):
def test_pairwise_debts_are_netted(self):
self.expense("asha", 1000, "exact", ["bob"], [1000])
self.expense("bob", 400, "exact", ["asha"], [400])
self.assertEqual(self.s.balances("g"), [Transfer("bob", "asha", 600)])
def test_nets_always_sum_to_zero(self):
rng = random.Random(3)
people = ["asha", "bob", "chen"]
for _ in range(200):
who = rng.sample(people, rng.randint(1, 3))
self.expense(rng.choice(people), rng.randint(1, 10**6), "equal", who)
self.assertEqual(sum(self.s.nets("g").values()), 0)
class SimplifyTests(unittest.TestCase):
def test_chain_collapses(self):
# a owes b 10, b owes c 10: one transfer, a pays c
self.assertEqual(simplify({"a": -10, "b": 0, "c": 10}), [Transfer("a", "c", 10)])
def test_at_most_n_minus_one_and_always_settles(self):
rng = random.Random(5)
for _ in range(500):
vals = [rng.randint(-10**4, 10**4) for _ in range(rng.randint(1, 12))]
vals.append(-sum(vals))
nets = {f"u{i}": v for i, v in enumerate(vals)}
plan = simplify(nets)
nonzero = sum(1 for v in vals if v)
self.assertTrue(settles(nets, plan))
self.assertLessEqual(len(plan), max(nonzero - 1, 0))
self.assertTrue(all(t.amount > 0 for t in plan))
def test_greedy_counterexample(self):
nets = {"A": 600, "B": 500, "C": -300, "D": -300, "E": -500}
self.assertEqual(len(simplify(nets)), 4)
self.assertTrue(settles(nets, [Transfer("E", "B", 500), Transfer("C", "A", 300), Transfer("D", "A", 300)]))
def test_unbalanced_input_rejected(self):
with self.assertRaises(ValidationError):
simplify({"a": 1})
class SettleAndUndoTests(Base):
def setUp(self):
super().setUp()
self.e = self.expense("asha", 900, "equal", ["asha", "bob", "chen"])
def test_settle_reduces_both_sides(self):
self.s.settle("g", "bob", "bob", "asha", 300)
self.assertEqual(self.s.nets("g"), {"asha": 300, "chen": -300})
def test_settle_cannot_create_new_debt(self):
for payer, payee, amt in [("bob", "asha", 301), ("asha", "bob", 1), ("bob", "chen", 1), ("bob", "bob", 1)]:
with self.assertRaises(ValidationError):
self.s.settle("g", payer, payer, payee, amt)
def test_settle_through_simplified_plan(self):
self.s.add_expense("g", "bob", "bob", 300, "exact", ["chen"], [300])
# chen owes asha 300 and bob 300, bob owes asha 300 and is owed 300 by chen: bob nets to zero
for t in self.s.simplified("g"):
self.s.settle("g", t.debtor, t.debtor, t.creditor, t.amount)
self.assertEqual(self.s.nets("g"), {})
def test_undo_reverses_exactly(self):
self.s.undo("g", "asha", self.e.id)
self.assertEqual(self.s.nets("g"), {})
self.assertEqual(self.s.balances("g"), [])
def test_undo_twice_and_unknown_fail(self):
self.s.undo("g", "asha", self.e.id)
for ref in [self.e.id, "e999"]:
with self.assertRaises(ValidationError):
self.s.undo("g", "asha", ref)
def test_undo_after_settlement_flips_the_debt(self):
self.s.settle("g", "bob", "bob", "asha", 300)
self.s.undo("g", "asha", self.e.id)
self.assertEqual(self.s.nets("g"), {"asha": -300, "bob": 300}) # asha now owes bob his money back
def test_undo_a_settlement(self):
st = self.s.settle("g", "bob", "bob", "asha", 300)
self.s.undo("g", "bob", st.id)
self.assertEqual(self.s.nets("g"), {"asha": 600, "bob": -300, "chen": -300})
def test_history_is_append_only(self):
self.s.undo("g", "chen", self.e.id)
h = self.s.history("g")
self.assertEqual([(a.kind, a.actor, a.ref) for a in h], [("expense", "asha", self.e.id), ("undo", "chen", self.e.id)])
self.assertLess(h[0].seq, h[1].seq)
def test_replay_matches_incremental(self):
self.s.settle("g", "bob", "bob", "asha", 100)
self.s.undo("g", "asha", self.e.id)
self.expense("chen", 700, "share", ["asha", "chen"], [3, 4])
rebuilt = self.s.rebuild("g")
self.assertEqual((rebuilt.nets(), rebuilt.debts()), (self.s.nets("g"), self.s.balances("g")))
class MembershipTests(Base):
def test_cannot_remove_member_with_balance(self):
self.expense("asha", 900, "equal", ["asha", "bob", "chen"])
with self.assertRaises(ValidationError):
self.s.remove_member("g", "bob")
self.s.add_member("g", "dev")
self.s.remove_member("g", "dev")
class ConcurrencyTests(unittest.TestCase):
def test_parallel_expenses_settlements_and_undos(self):
s = SplitwiseService()
people = [f"p{i}" for i in range(6)]
for p in people:
s.add_user(p, p)
s.create_group("g", "G", "INR", people)
s.create_group("h", "H", "INR", people)
errors = []
def worker(seed):
rng = random.Random(seed)
try:
for _ in range(300):
gid = rng.choice("gh")
e = s.add_expense(gid, "p0", rng.choice(people), rng.randint(1, 10**5), "equal",
rng.sample(people, rng.randint(1, 6)))
if rng.random() < 0.2:
s.undo(gid, "p0", e.id)
plan = s.simplified(gid)
if plan:
t = plan[0]
try:
s.settle(gid, t.debtor, t.debtor, t.creditor, t.amount)
except ValidationError:
pass # another thread moved the balance between our read and our write
s.user_total("p1")
except Exception as ex: # surfaces in the main thread
errors.append(ex)
threads = [threading.Thread(target=worker, args=(i,)) for i in range(8)]
for t in threads:
t.start()
for t in threads:
t.join()
self.assertEqual(errors, [])
for gid in "gh":
self.assertEqual(sum(s.nets(gid).values()), 0)
self.assertEqual(s.rebuild(gid).nets(), s.nets(gid))
if __name__ == "__main__":
unittest.main()
Run it with python -m unittest test_splitwise -v. The 27 tests take about a tenth of a second.
Property tests are the right tool here. Most of the random tests above are hand-rolled property tests: generate random input, check an invariant that must hold for every input. Money code has crisp invariants (conservation, exact replay, at most n − 1 transfers), and checking them on thousands of inputs finds the edge cases nobody thinks to write by hand. Libraries such as Hypothesis (Python), jqwik (Java) and fast-check (TypeScript) add shrinking, which turns a failing 40-person case into the smallest one that still fails.
12. Common mistakes
- Floating-point money. It's still the most common mistake, and it's an instant red flag in review. Use integer minor units or a decimal type.
- Rounding each share independently. The shares stop adding up to the total. Every split must conserve the total exactly, with the remainder placed by a stated rule.
- Non-deterministic remainder placement. Random choice, or iterating a hash map in whatever order it happens to have, makes tests flaky and replay inexact.
- Percentages as floats.
33.33 + 33.33 + 33.34 == 100.0may or may not be true in floating point. Basis points make it an integer check. - Storing balances only, without the entries. There's then no history, no undo, and no way to find out how a balance went wrong.
- Storing entries only, recomputing balances on every read. Correct but slow for big groups. Keep the sheet as a cache and use replay as the test.
- Undo by deleting the expense. The history loses the explanation for a balance change. Use a compensating entry.
- Memento snapshots for undo. You can't undo an old expense without discarding everything since. Inverse commands work because the effects commute.
- Mutating an expense in place to edit it. Replay no longer matches, because the edges applied at the time differ from the edges the record now produces.
- Claiming greedy gives the minimum number of transfers. It gives at most n − 1. The exact minimum is NP-hard. Saying so, with the counterexample, is one of the strongest signals in this interview.
- Validating settlements against pairwise debts. That rejects the very transfers the simplified view recommends.
- No guard on settlement amounts. An overpayment silently creates a new debt in the other direction, which users read as a bug.
- A global lock for everything. It works, but it serialises unrelated groups for no reason. The group is the natural unit.
- Checking membership or balances outside the lock. That's a check-then-act race, and it's the most common concurrency bug in submitted solutions.
balancefields onUser. A second copy of data that already exists in the groups, which then has to be kept in sync under concurrency.
The Common LLD Mistakes page covers anaemic models and god classes, which this design avoids by keeping rules on the service and arithmetic in small pure functions.
13. Interview follow-ups
"Why not let the payer absorb the rounding remainder?"
For equal splits it's almost the same as largest remainder, and some apps do exactly that. For weighted splits it can put the payer's share more than one unit away from exact, while largest remainder guarantees every share is within one unit. More importantly, whatever the rule is, it has to be stated and deterministic. An interviewer cares less about which rule you pick than about whether you noticed that a rule is needed.
"Prove greedy uses at most n − 1 transfers."
Every step transfers min(credit, debt), which brings at least one of the two people to exactly zero, and that person never appears again. There are n people with non-zero balances. After n − 2 steps at most two people are left, and since balances sum to zero they're a creditor and a debtor with equal amounts, so one more step finishes both. That's at most n − 1 steps.
"Is the exact minimum really NP-hard? Splitwise does it."
The decision version, "can these balances be settled in n − 2 transfers?", is equivalent to "does some proper non-empty subset of the balances sum to zero?". That's subset sum, which is NP-complete, so minimisation is NP-hard. What an app can do is run a heuristic, or an exact search when the group is small. For typical group sizes, exact search over subsets is fast, which may be why it appears to "just work". Splitwise doesn't publish its algorithm, so don't claim to know what it runs.
"What other objective could simplification optimise?"
Three come up. Fewest transfers is what we discussed. Least money moved is automatically achieved by any plan where nobody both pays and receives. Fewest new relationships means preferring transfers between people who already owe each other, so nobody is asked to pay a near stranger. The last is a real product concern, and it's why some apps make simplification opt-in per group. You can implement it with a tie-breaker in greedy that prefers pairs who already have a pairwise debt.
"Two people record the same dinner. How do you handle duplicates?"
The system can't know that two ₹1,200 dinners on the same evening are the same one. Options: warn when a new expense matches an existing one in amount, payer and day within a short window, and let the user confirm. Or accept a client idempotency key, so the same client retrying a request doesn't duplicate it. The second is a correctness guarantee. The first is a UX nicety.
"What happens when a member leaves with a non-zero balance?"
This design refuses until they're settled up. The alternatives are to keep them as an inactive member who still appears in balances, or to transfer their balance to another member with an explicit entry, a "write-off" or "takeover". The explicit entry keeps conservation and replay intact. Silently deleting their balance would break both.
"How would you show a user's balance across all their groups?"
Sum their net in each group, per currency. That's userTotal, and the follow-up is whether it needs to be a consistent snapshot. For a home screen, reading each group under its own lock one after another is fine. For a statement or an export, take the locks in id order, as the code does, or read from a database snapshot.
"Can you simplify debts across groups?"
Technically yes: sum the nets per person across groups and simplify once. But groups are usually separate on purpose (the flat isn't the ski trip), and a cross-group plan makes it impossible to say which group a payment settled. If offered, it should produce settlements that are split back into per-group entries, so each group's history still explains its balances.
"How does undo interact with a settlement that already happened?"
Undoing an expense applies its inverse edges, regardless of settlements. If Bob had already paid Asha back his share of a dinner that's now undone, Asha ends up owing Bob that amount, which is exactly right: he paid for something that, according to the group, didn't happen. The test test_undo_after_settlement_flips_the_debt pins this behaviour, and in an interview it's worth stating it before you're asked.
"What would change for a company expense tool with approvals?"
Entries gain a status: an expense is submitted, then approved or rejected, and only approved expenses apply their edges. That's a small state machine on the entry, plus "apply on approval" instead of "apply on add". The balance sheet, the strategies and simplification are untouched, which is another payoff of keeping the sheet ignorant of what an entry is.
Related
- Machine Coding Rounds builds the smaller expense ledger this page extends, under a 90-minute clock.
- Strategy, Command and Memento cover the patterns compared in section 5.
- Thread-Safe Class Design and Concurrency Patterns in LLD cover the locking choices in general.
- Design a Notification Service is what "notify the group" would call.
- Graph modeling covers turning problems like debt settlement into graphs.
- Design a Payment System is the distributed version of moving money correctly.