Design Splitwise — Low-Level Design

Problem framing

Splitwise tracks who paid for what among a group and who owes whom. Design pressure: multiple split modes (equal, exact, percent, shares); maintaining balance sheet incrementally (don't recompute from scratch); settling up (minimize number of transfers when 4 people have tangled debts); edge cases (rounding, multi-currency, payer in participants).

LLD-level: single-instance OO design unless asked about scale. Strategy choices and simplification algorithm are the grade.

Clarifying questions

Groups required or two-friend splits outside groups. Split modes (equal, exact per person, percentage, shares like A:2/B:1). Currency single or multi. Settlement (record cash repayments? compute simplification?). Edit/delete expenses (adds reconciliation). Persistence. Concurrency (multiple users adding expenses simultaneously).

Assumptions

Expenses live in a Group; two-friend splits modeled as special group. Four split modes: EQUAL, EXACT, PERCENT, SHARES. Single currency core; multi-currency as extension. Settling records cash repayments + supports simplification on demand. Edits/deletes as extension (reversal of original split). In-memory with GroupRepository interface. Concurrent expense additions in same group; per-group lock on balance updates.

Core entities

User: immutable id + name + email. Group: list of members, list of expenses, BalanceSheet. Expense: immutable record (id, payer, total, currency, description, splits per participant, timestamp). Split: (user, amount). Sum == expense total. SplitStrategy interface: computeSplits(total, participants, params) → List. One impl per mode. BalanceSheet: Map<UserId, Map<UserId, Money>> 'A owes B'. Incremental updates on expense add. netBalance(a, b). SettlementStrategy interface: simplify(BalanceSheet) → List. Default = greedy creditor/debtor matching. Transfer: (from, to, amount). SplitwiseService: facade — addExpense, recordSettlement, getBalances, getSimplifiedTransfers.

Split strategies

All implement same interface; differ in how to break total into per-user Splits.

EqualSplit: convert to cents, integer-divide, distribute remainder cents to first N participants for fairness. perHead = totalCents / n; remainder = totalCents - perHead*n; for i in 0..n: cents = perHead + (i < remainder ? 1 : 0).

PercentSplit: requires SplitParams.percents map. Validate sum == 100. Each participant's share = total * percent / 100.

SharesSplit: requires SplitParams.shares map (weights). totalShares = sum. Each share = total * weight / totalShares; same remainder distribution as EqualSplit.

Rounding rule for EQUAL and SHARES: convert to integer cents, integer-divide, distribute remaining cents one each to first N participants. Documented and predictable; no floating point. Same rule for refunds on delete.

Balance sheet — incremental updates

Recomputing from all expenses every time is wasteful. Maintain incrementally.

Matrix: outer key debtor, inner key creditor, value amount owed. matrix[debtor][creditor] = cents owed.

applyExpense(e): for each Split, skip payer's own share. Else s.user() owes e.paidBy() s.amount() — adjust(debtor=s.user(), creditor=e.paidBy(), amount).

applyTransfer(t): t.from pays t.to — reduces from's debt to to. adjust(debtor=t.to, creditor=t.from, amount).

adjust: compute net = currentBalance + amount. Normalize — keep only one direction per pair non-zero. If positive, store debtor → creditor; remove reverse. If negative, flip and store creditor → debtor. If zero, remove both.

Normalization keeps matrix small and lookups O(1). Avoids 'A owes B 10, B owes A 7' redundancy.

Settle up — greedy simplification

Tangled debt graph; find minimum number of transfers. Exact minimum is NP-hard; standard approximation is greedy max-creditor / max-debtor pairing — near-optimal in practice.

Algorithm:

1. 1
   Compute each user's net balance (credits - debts)
2. 2
   Max-heap of creditors (positive balances), max-heap of debtors (most negative balances)
3. 3
   While both non-empty: take largest creditor C and largest debtor D. Transfer = min(|C|, |D|). Emit Transfer(D → C, transfer). Adjust balances; remove if zero.

For 4-5 people: typically 2-3 transfers instead of 6+ pairwise. O(N log N) where N = users with non-zero balance.

End-to-end flow — add expense + settle

Alice paid $30 dinner for [Alice, Bob, Carol] EQUAL split.

Svc.addExpense → EqualSplit.computeSplits($30, [Alice, Bob, Carol]) → [Alice $10, Bob $10, Carol $10] → Group.addExpense → BalanceSheet.applyExpense → Bob → Alice +$10, Carol → Alice +$10.

Later: getSimplifiedTransfers → [Bob → Alice $10, Carol → Alice $10].

Bob actually pays → Svc.recordSettlement(Transfer(Bob → Alice $10)) → BalanceSheet.applyTransfer → Bob's debt cleared.

Concurrency

Two boundaries:

1. 1

   Per-group balance updates: applyExpense and applyTransfer mutate the matrix. Acquire per-group ReentrantLock for the duration. Cross-group operations don't contend.

2. 2

   Reads: getBalances and getSimplifiedTransfers should be consistent snapshots. Either copy under same lock, or ReadWriteLock (writers exclusive, readers shared).

Real distributed: per-group state in DB with optimistic lock on group's version field; all becomes a single transaction. Interview-level fine with in-memory locks.

Failure modes and edge cases

• Rounding remainder: $10 / 3 → [$3.34, $3.33, $3.33]. Document rule (extra cent to first N, deterministic)
• Payer in participants: own split doesn't generate self-debt; skip in applyExpense
• Edit/delete expense: apply reverse expense, then new one. Audit log; never lose history
• Multi-currency: store original-currency amounts in expense; balance sheet per original currency. Conversion is view concern, not storage. Settlement handles multi-currency or normalizes first
• Floating point: never. BigDecimal (cents) or custom Money value object
• Cycle of debts: simplification handles naturally — nets to zero → no transfer
• Self-transfer: Transfer(A → A) invalid; reject at construction
• User leaving group with non-zero balance: require settlement first; record final transfer log

Extensibility

• New split mode (ITEMIZED restaurant bill where each line maps to specific eaters): new SplitStrategy impl. No other changes
• New settlement strategy (minimize transfers constrained to existing creditor/debtor edges): new SettlementStrategy
• Multi-currency: CurrencyConverter port; balance sheet per currency or convert at view time
• Reminders/notifications: publish BalanceUpdatedEvent when balance large or stale
• Receipt OCR / auto-import: ExpenseSource adapter parses receipts → Expense objects
• Analytics: expense history becomes CQRS read model; main aggregate stays clean

Trade-offs and alternatives

• Incremental matrix vs recompute on read: incremental O(1) reads but careful update logic. Recompute simple but O(N²) per query. Active groups → incremental wins
• Greedy simplification vs optimal (NP): greedy near-optimal in practice; optimal exponential, not worth it
• In-memory vs persistent: in-memory fine for interview; production wraps Group as JPA aggregate with BalanceSheetEmbeddable and @Version
• Strategy interface vs enum+switch: Strategy scales as modes grow; lets each mode's params live with impl. Enum+switch fits 2 modes, then bloats
• Per-group lock vs lock-free: lock correct + simple; lock-free overkill for low-contention domain
• Single vs multi-currency: single right starting point. Multi-currency adds conversion semantics that should be deliberate design, not afterthought

Recommendation

Build Splitwise around three entities (User, Group, Expense) with a SplitStrategy interface for the split modes (Equal, Exact, Percent, Shares) and a SettlementStrategy interface for simplification. Maintain the BalanceSheet incrementally as a normalized debtor→creditor matrix; never recompute from scratch. Use the greedy max-creditor / max-debtor algorithm to minimize transfers (near-optimal in practice; exact is NP-hard). Always work in cents / BigDecimal; document the remainder distribution rule. Per-group ReentrantLock around mutations is enough for the interview level; production maps cleanly to a JPA aggregate with optimistic locking. Multi-currency, edit/delete, and notifications are clear extensions that drop in without touching the core flow.