Notes
Requirements
The requirements. Users belong to groups. Anyone can add an expense: who paid, how much, and how it is split among which members, equally, by exact amounts or by percentages. The app shows what each person owes or is owed, suggests a short list of payments that settles everything, records those payments when they happen, and notifies the group about new expenses.
Clarify the money rules first, because they decide the data types. One currency per group for now. When a hundred rupees is split three ways, someone pays thirty-four and the others thirty-three; the total must always match exactly. Exact amounts must add up to the bill, and percentages to a hundred, or the expense is rejected. The payer and everyone in the split must be group members.
- users and groups of users
- add an expense: who paid,
- how much, split among whom
- splits: equal, exact amounts,
- or percentages
- show what each person owes
- or is owed
- simplify: fewest payments
- record a settle-up payment
- notify members of new expenses
- one currency per group?
- yes, multi-currency later
- rounding: 100 split 3 ways?
- 34, 33, 33: never lose 1
- must splits add up exactly?
- yes, reject otherwise
- payer must be in the group?
- yes
- edit or delete expenses?
- version two
Entities
The entities. The service holds groups. A group has members, a list of expenses, and a running balance per member. An expense records who paid, the total, a note, and its shares, where each share says one user owes one amount. Users are plain records. Everything except the group is immutable once created, which matters later for thread safety and for keeping an honest history.
Class diagram
In code, almost everything is a record. A user, a share, an expense and a suggested payment never change after creation. Amounts are whole paise stored in a long. Never use double for money: binary floating point cannot represent most decimal amounts, and small errors add up across hundreds of expenses until the balances no longer sum to zero.
record User(String id, String name)
enum SplitType { EQUAL, EXACT, PERCENT }
record Share(User user, long amount)
record Expense(long id, String groupId,
String note, User paidBy,
long amount, List<Share> shares)
record Payment(User from, User to,
long amount)
amounts are paise: 12000.00 = 1200000 Net balances
A key design choice: how to store who owes what. A pairwise ledger, a cell for every pair of users, grows with the square of the group and still needs simplifying at the end. Instead keep one signed number per user: positive means they are owed, negative means they owe. Adding an expense credits the payer the full amount and debits each share. The numbers always sum to zero, which is a free correctness check.
- positive: is owed money
- negative: owes money
- sum over the group is always 0
- add expense:
- net[payer] += amount
- net[each share] -= share
- pairwise ledger: N x N cells,
- and still needs simplifying
Strategy and Factory
Each way of splitting is a Strategy: one interface that turns an amount and a list of users into shares, with equal, exact and percent implementations. Each class also validates its own input: exact amounts must add up, percentages must total a hundred. A small factory method maps the split type to the right strategy, so the service never contains a chain of if statements. Adding shares by weight later is one more class and one more case.
interface SplitStrategy {
List<Share> split(long amount,
List<User> users, List<Double> v);
}
static SplitStrategy splitFor(SplitType t) {
return switch (t) {
case EQUAL -> new EqualSplit();
case EXACT -> new ExactSplit();
case PERCENT -> new PercentSplit();
};
} Rounding
Rounding is where weak answers lose money. For an equal split, integer division gives the base share and the remainder is a few leftover paise; give one extra paisa to the first few people. A hundred among three becomes thirty-four, thirty-three, thirty-three. For percentages, round each share but give the last person whatever is left, so the total always matches. Interviewers often test exactly this case.
equal: 100 among 3 base = 100 / 3 = 33, extra = 1 shares: 34, 33, 33 percent: last person gets amount - sum(others) so rounding never drifts exact: sum != amount -> reject
Flow: add an expense
The add-expense flow. Compute the shares first, outside any lock, because it only reads the arguments. Then lock this one group, check that the payer and everyone in the split are members, append the expense, credit the payer and debit each share. Release the lock, then notify listeners. Notifying outside the lock means a slow email sender can never block someone else adding an expense.
Here is the demo in the code. The planner pays twelve thousand for a villa split equally among four. The driver pays nine thousand for dinners with exact shares. The chef pays a thousand for scooters split fifty, twenty-five, twenty-five among three. The guest buys snacks for a hundred. The planner is owed about five thousand nine hundred and sixty-seven, the driver three thousand nine hundred and sixty-seven, and the other two owe. The total is exactly zero.
shares = splitFor(type).split(..)
synchronized (group) {
check payer and users are members
expenses.add(expense)
net[payer] += amount
for (s : shares) net[s.user] -= s.amt
}
for (l : listeners) l.onExpense(g, e) - Planner pays villa 12,000
- equal among 4
- Driver pays dinners 9,000
- exact: 3k, 1.5k, 2.5k, 2k
- Chef pays scooters 1,000
- 50/25/25 among 3
- Guest pays snacks 100
- Planner +5,966.66
- Driver +3,966.67
- Chef -4,783.33 Guest -5,150
Simplify debts
Simplifying debts uses the net balances directly. Put creditors in one max-heap and debtors in another. Repeatedly take the biggest of each, make a payment of the smaller of the two amounts, and push back whoever still has a balance. Every payment fully settles at least one person, so a group of n people needs at most n minus one payments. Our example settles in three.
Is greedy the minimum? Not always. The true minimum comes from splitting people into as many groups as possible whose balances sum to zero, and that is a hard problem in general. For small groups, under about fifteen people, a bitmask dynamic programming search finds the exact minimum. For anything bigger, the greedy answer with at most n minus one payments is what real apps use. Saying this unprompted scores well.
owed = max-heap of creditors owes = max-heap of debtors while both non-empty: c = owed.poll(); d = owes.poll() pay = min(c.amount, -d.amount) plan.add(d pays c, pay) push back whoever is not settled every payment settles someone: at most n - 1 payments
- greedy: at most n - 1 payments
- true minimum: split people into
- the most groups that each sum
- to zero, then n - groups
- that is NP-hard in general
- small groups (under ~15):
- bitmask DP finds the minimum
- otherwise: greedy is the norm
Settle up
Settling up is simple with net balances. When the guest pays the planner five thousand one hundred and fifty, add that amount to the guest's balance and subtract it from the planner's, under the group lock. After all three suggested payments, every balance is exactly zero and simplify returns an empty plan, which the demo asserts. Storing it as a payment record also keeps a clear history.
Concurrency
Concurrency. Two friends may add expenses to the same group at the same moment, and the balance updates must not interleave. Lock the smallest thing that has to change together, which is one group. Groups live in a concurrent map, and different groups never block each other. Split maths happens before the lock, notifications after it, and balance reads return a copy so callers never see a half-updated map.
- groups: ConcurrentHashMap
- lock per group: synchronized(g)
- two groups never block
- split math outside the lock
- listeners called after unlock
- balances() returns a copy
- expense ids: AtomicLong
- records: immutable, shareable
Observer
Notifications are the Observer pattern. An activity feed, an email digest and push notifications each register an expense listener. The service calls them after the lock is released, so slow or failing channels cannot hold up anyone's balance. Adding a new channel, like a weekly summary, is a new listener and no change to the expense code.
Extensibility
Extensions. Editing or deleting an expense should append a reversing entry instead of rewriting history, so balances can always be rebuilt and audited. Shares by weight is a new strategy. Multiple currencies convert at the rate on the expense date. Recurring rent is a scheduler that adds an expense each month. In a database, the expense ledger is the source of truth and balances are a cache of it.
- edit or delete: append a
- reversing entry, keep history
- shares by weight: new strategy
- multi-currency: convert at the
- rate on the expense date
- recurring rent: a scheduler
- adds expenses monthly
- storage: append-only ledger,
- balances are a cache of it
Follow-ups
Expect follow-ups. Why not double for money? Rounding drift. Why at most n minus one payments? Each one settles at least one person. Is the true minimum easy? No, it is hard in general, so use bitmask search only for small groups. Two people editing the same expense? Use a version number and reject stale updates. And a one-off expense between two friends is just a two-person group, so no special case is needed.
- why not double for money?
- how do you avoid lost paise?
- n - 1 payments: prove it
- minimum payments: complexity?
- two users edit the same
- expense? version numbers
- balances drift after a bug?
- rebuild from the ledger
- non-group expenses?
- a two-person group
Say it like this
The short version. Expenses are immutable records with shares in paise. Split rules are strategies chosen by a factory, and they always add up exactly. Each group keeps one net balance per user, updated under that group's own lock. Two heaps simplify the debts into at most n minus one payments, and notifications are observers called outside the lock.
- "Expenses are immutable records
- with shares in paise. Splits
- are strategies from a factory
- and always add up exactly. A
- group keeps one net balance per
- user under its own lock. Two
- heaps simplify debts in at most
- n - 1 payments."