Cruxly › Low-level design › LLD Exercises

Expense Splitting

money that cannot drift, and a settlement algorithm

Prompt: design an expense-sharing system. Users create groups, add expenses paid by one member and split among several (equally, by exact amount, or by percentage), and see who owes whom. Add a "settle up" feature that minimises the number of transactions.

45 minutes.

Applying the five moves: nouns are User, Group, Expense, and Balance — resist adding a Transaction class for every historical payment unless the prompt asks for an audit trail, since the settle-up feature only needs net balances, not history. The invariant is "the sum of every balance in a group is always zero" — say this sentence before writing addExpense, because it's the check that catches a rounding bug immediately instead of at some later, harder-to-trace point. The interface seam is the split strategy — equal, exact, percentage are three implementations of one SplitStrategy interface, since the prompt names three up front and a fourth is a predictable follow-up. No real concurrency story is the honest concurrency sentence here unless the prompt adds concurrent expense creation in the same group — say that explicitly rather than inventing a lock for a single-writer-at-a-time system.

Money first — before any class diagram

Get this wrong and every number in the system is quietly incorrect.

Never use floating point for money. 0.1 + 0.2 != 0.3 in binary floating point. Across thousands of expenses the drift is real and unexplainable to a user staring at a balance.

Use integer minor units (cents) or a BigDecimal/Decimal with an explicit rounding mode. Integer cents is simpler and faster; say which and why. A Money type with a currency attached is better than a bare long, because it makes adding USD to EUR a compile error rather than a runtime surprise — and multi-currency is a near-certain follow-up.

The three-way split problem. $10.00 split equally among three is $3.333... Each person cannot owe $3.33, because that sums to $9.99 and a cent has vanished.

The rule: the split must sum exactly to the total, always. Distribute the remainder deterministically — give the extra cent(s) to the first N participants in a stable order, so one owes $3.34 and two owe $3.33. Deterministic matters: the same expense must produce the same split every time it is recomputed, or a refresh changes what someone owes.

State this as an invariant: sum(shares) == total, exactly, for every expense. It is checkable in one line and it is the foundation everything else rests on.

The model

class Money { long minorUnits; Currency currency; }

class User { UserId id; String name; } class Group { GroupId id; Set<UserId> members; }

interface SplitStrategy { Map<UserId, Money> split(Money total, List<UserId> among, Object params); } // EqualSplit, ExactSplit, PercentageSplit

class Expense { ExpenseId id; GroupId group; UserId paidBy; Money total; Map<UserId, Money> shares; // computed once, stored Instant createdAt; }

Shares are stored, not recomputed. Non-obvious and important: if a member later leaves the group, or the split algorithm is fixed, a recomputed historical expense would change what someone owed in the past. An expense is a fact about the past; it gets computed once and frozen. This is the same instinct as the parking lot's immutable closed-ticket fee.

SplitStrategy is an interface because the prompt named three kinds — an explicit signal that a fourth (by shares, by adjustment) is coming.

Balances are derived, not stored. balance(A, B) is a fold over the group's expenses. Storing a running balance means two sources of truth that can disagree, and disagreement between them is the worst possible bug class here. If it gets slow, cache the fold and invalidate on new expense — a cache is allowed to be stale and rebuildable; a second source of truth is not. That distinction is worth saying out loud.

Settlement — be honest about the complexity

After many expenses, the group has a set of net balances that sum to zero:

A: +30 B: -20 C: -10

Minimising the number of transactions to settle a set of debts is NP-hard (it reduces to a partition problem). Say so. A candidate who claims an optimal greedy has either not thought about it or is hoping nobody checks — and this is a well-known enough result that interviewers often do.

The standard greedy, which is what to implement:

Compute each member's net balance (sum of what they paid minus sum of their shares).
Put debtors in one max-heap, creditors in another.
Repeatedly match the largest debtor with the largest creditor, transfer min(|debt|, credit), and push back whoever still has a non-zero balance.

This produces at most n-1 transactions for n members, which is a real and stateable bound. It is not always minimal — a group where two subsets happen to cancel exactly can sometimes do better — but it is simple, fast, and the deviation from optimal is small in practice.

Two correctness checks worth stating:

Net balances must sum to exactly zero. If they do not, the money invariant was violated somewhere upstream, and this is a cheap assertion that catches it.
The greedy terminates because each step zeroes at least one participant.

A design question hiding in the feature: does settling delete the expense history or add a settlement record? It must add a record. Deleting history destroys the audit trail and makes the balance underivable. A settlement is just another transaction in the ledger — which falls straight out of "balances are derived," and is a satisfying place for the earlier decision to pay off.

Follow-ups

"Multi-currency." Money already carries currency, so the type system stops the worst error. The real questions are which currency a group settles in and what exchange rate applies — the rate at expense time (stored on the expense) or at settlement time. Storing the rate on the expense is consistent with "an expense is a fact about the past."

"Simplify debts across the whole group automatically." That is the settlement algorithm running continuously rather than on demand. The design question is whether users want it: A owing B directly is socially meaningful, and rewriting it to "A owes C" surprises people. Noticing that a technically-correct feature can be a product mistake is a strong thing to say.

"Concurrency — two members add an expense at once." Expenses are append-only and balances are derived, so concurrent appends are naturally safe; this is the payoff for not storing a running balance. The only contended thing is a cached fold, and a cache can simply be invalidated. Say this — it demonstrates the earlier decision was load-bearing, not incidental.

"Delete or edit an expense." Edit is the hard one. Either version the expense (append a correction, keep history) or forbid editing after settlement. Both are defensible; silently mutating a past fact is not.

How to say it in the interview

"Two hard parts: representing money so rounding cannot silently lose a cent, and the settlement algorithm — which I should be honest is NP-hard in general, so I want a good greedy rather than a claimed optimum."

Checklist

Ruled out floating point for money and chose integer minor units or decimal
Attached currency to the money type so cross-currency addition is a type error
Made the split sum exactly to the total with a deterministic remainder rule
Stored computed shares rather than recomputing them later
Derived balances from the expense log instead of storing a running balance
Stated that minimal settlement is NP-hard rather than claiming an optimal greedy
Gave the heap-based greedy with its n-1 transaction bound
Noted that net balances must sum to zero as a cheap correctness assertion
Made settlement append a record rather than delete history

Practice this interactively