The real-world analogy: restaurant bill settlement
Imagine dining out in a group of five friends:
- The Messy Way: At the end of the night, A hands B ₹50, B hands C ₹100, and C hands A ₹30. Coins are dropped, bills are passed, and everyone wastes 15 minutes swapping physical cash.
- The Splitwise Way: Instead of physical bills passing hand-to-hand, everyone throws their receipts into a central bowl. We calculate the net result: Asha is overall +₹100 (she is owed money), Rahul is −₹70 (he owes money), and John is −₹30 (he owes money). Rather than three trades, we match Rahul to hand ₹70 to Asha, and John to hand ₹30 to Asha. The ledger matches perfectly with only two total transfers—Asha is satisfied, and John and Rahul have settled their balances.
The core design centers around tracking this net balance sheet, validating split policies (equal, percentage, exact share), and executing a matching algorithm to collapse the web of IOUs into the minimum possible transactions.
Scope it first
"Users create group expenses — one payer, many participants, split equally / by exact amounts / by percentages. Show who owes whom; simplify debts. Single currency, ignore payments/settlement execution and auth — OK?"
That scope hits everything graders look for: a Strategy seam, a money-correctness invariant, and one genuine algorithm.
UML Class Diagram
Expenseis an immutable record: who paid, how much, and the computedSplits. Edits create a new version (audit trail — finance code never destroys history).SplitStrategy— equal / exact / percent are interchangeable algorithms producingList<Split>: the cleanest Strategy showcase in any LLD classic. New split type (by shares, by adjustment) = new class, zero edits (Open/Closed, same seam as parking-lot pricing).BalanceSheetholds net balance per user (positive = is owed, negative = owes). Derived from expenses, so it's a cache — rebuildable by replay, which is your data-corruption escape hatch.
Each strategy validates its own args: exact amounts must sum to the total; percentages to 100. Validation inside the strategy, not the manager — the class that defines the rule enforces it (encapsulation).
Money: the two non-negotiables
- Never floats. ₹0.10 isn't representable in binary; pennies leak. Integer paise/cents or
BigDecimal(Level 1 said it; here it's load-bearing). - The conservation invariant: every expense's splits sum exactly to the amount, and the global net sums to zero. ₹100 split three ways is 33.33 + 33.33 + 33.34 — someone gets the spare paisa (convention: first participant). Write the assertion; mention it unprompted. It's the difference between candidates who've handled money and those who haven't.
The algorithm: debt simplification
A trip's raw expenses create a messy web of IOUs. But only net balances matter: compute each user's net, then match debtors to creditors:
Raw: A→B ₹20, B→C ₹20, C→A ₹10 Nets: A −10, B 0, C +10
Simplified: A pays C ₹10. (3 transactions → 1; B vanished entirely)
The graph view is why this works: individual edges (who-paid-whom) are noise; only each node's net flow matters, and any set of transactions that produces the same nets is equally valid.
Implementation
Below are complete implementations with thread-safe group locks and greedy settlement solvers using heaps.
Python
import heapq
import threading
from typing import Dict, List, Tuple
class User:
def __init__(self, name: str):
self.name = name
class Split:
def __init__(self, user: User, amount_cents: int = 0):
self.user = user
self.amount_cents = amount_cents
class EqualSplitStrategy:
def validate_and_split(self, total_cents: int, users: List[User]) -> List[Split]:
n = len(users)
base = total_cents // n
remainder = total_cents % n
return [Split(users[i], base + (1 if i < remainder else 0)) for i in range(n)]
class GroupBalanceSheet:
def __init__(self):
self.net_balances: Dict[User, int] = {}
self.lock = threading.Lock()
def add_expense(self, payer: User, total_cents: int, splits: List[Split]):
with self.lock:
self.net_balances[payer] = self.net_balances.get(payer, 0) + total_cents
for split in splits:
self.net_balances[split.user] = self.net_balances.get(split.user, 0) - split.amount_cents
def simplify_debts(self) -> List[Tuple[User, User, int]]:
with self.lock:
# We use max-heaps (so push negative values)
debtors = []
creditors = []
for user, bal in self.net_balances.items():
if bal < 0:
heapq.heappush(debtors, (-bal, user))
elif bal > 0:
heapq.heappush(creditors, (-bal, user))
transactions = []
while debtors and creditors:
debt_val, debtor_user = heapq.heappop(debtors)
credit_val, creditor_user = heapq.heappop(creditors)
debt = debt_val
credit = credit_val
settle_amount = min(debt, credit)
transactions.append((debtor_user, creditor_user, settle_amount))
remaining_debt = debt - settle_amount
remaining_credit = credit - settle_amount
if remaining_debt > 0:
heapq.heappush(debtors, (remaining_debt, debtor_user))
if remaining_credit > 0:
heapq.heappush(creditors, (remaining_credit, creditor_user))
return transactions
Java
import java.util.*;
import java.util.concurrent.locks.ReentrantLock;
class User {
String name;
User(String name) { this.name = name; }
}
abstract class Split {
User user;
long amountCents;
Split(User user) { this.user = user; }
Split(User user, long amt) { this.user = user; this.amountCents = amt; }
}
class EqualSplit extends Split {
EqualSplit(User user) { super(user); }
}
interface SplitStrategy {
List<Split> validateAndSplit(long totalCents, List<Split> splits);
}
class EqualSplitStrategy implements SplitStrategy {
@Override
public List<Split> validateAndSplit(long totalCents, List<Split> splits) {
int n = splits.size();
long base = totalCents / n;
long remainder = totalCents % n;
for (int i = 0; i < n; i++) {
splits.get(i).amountCents = base + (i < remainder ? 1 : 0);
}
return splits;
}
}
class Expense {
User paidBy;
long totalCents;
List<Split> splits;
Expense(User paidBy, long totalCents, List<Split> splits) {
this.paidBy = paidBy;
this.totalCents = totalCents;
this.splits = splits;
}
}
class Transaction {
User debtor;
User creditor;
long amountCents;
Transaction(User d, User c, long a) {
this.debtor = d;
this.creditor = c;
this.amountCents = a;
}
}
class GroupBalanceSheet {
final Map<User, Long> netBalances = new HashMap<>();
final ReentrantLock lock = new ReentrantLock();
void addExpense(Expense expense) {
lock.lock();
try {
User payer = expense.paidBy;
netBalances.put(payer, netBalances.getOrDefault(payer, 0L) + expense.totalCents);
for (Split split : expense.splits) {
User user = split.user;
netBalances.put(user, netBalances.getOrDefault(user, 0L) - split.amountCents);
}
} finally {
lock.unlock();
}
}
public List<Transaction> simplifyDebts() {
lock.lock();
try {
PriorityQueue<Map.Entry<User, Long>> debtors = new PriorityQueue<>(
(a, b) -> Long.compare(b.getValue(), a.getValue())
);
PriorityQueue<Map.Entry<User, Long>> creditors = new PriorityQueue<>(
(a, b) -> Long.compare(b.getValue(), a.getValue())
);
for (Map.Entry<User, Long> entry : netBalances.entrySet()) {
long bal = entry.getValue();
if (bal < 0) {
debtors.add(new AbstractMap.SimpleEntry<>(entry.getKey(), -bal));
} else if (bal > 0) {
creditors.add(new AbstractMap.SimpleEntry<>(entry.getKey(), bal));
}
}
List<Transaction> transactions = new ArrayList<>();
while (!debtors.isEmpty() && !creditors.isEmpty()) {
Map.Entry<User, Long> debtor = debtors.poll();
Map.Entry<User, Long> creditor = creditors.poll();
long settleAmount = Math.min(debtor.getValue(), creditor.getValue());
transactions.add(new Transaction(debtor.getKey(), creditor.getKey(), settleAmount));
long remainingDebt = debtor.getValue() - settleAmount;
long remainingCredit = creditor.getValue() - settleAmount;
if (remainingDebt > 0) {
debtors.add(new AbstractMap.SimpleEntry<>(debtor.getKey(), remainingDebt));
}
if (remainingCredit > 0) {
creditors.add(new AbstractMap.SimpleEntry<>(creditor.getKey(), remainingCredit));
}
}
return transactions;
} finally {
lock.unlock();
}
}
}
C++
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <mutex>
#include <algorithm>
#include <memory>
class User {
public:
std::string name;
User(std::string n) : name(n) {}
};
struct Split {
std::shared_ptr<User> user;
long amountCents;
Split(std::shared_ptr<User> u, long amt = 0) : user(u), amountCents(amt) {}
};
class EqualSplitStrategy {
public:
std::vector<Split> splitEqual(long totalCents, const std::vector<std::shared_ptr<User>>& users) {
std::vector<Split> result;
int n = users.size();
long base = totalCents / n;
long remainder = totalCents % n;
for (int i = 0; i < n; ++i) {
result.push_back(Split(users[i], base + (i < remainder ? 1 : 0)));
}
return result;
}
};
struct Transaction {
std::shared_ptr<User> debtor;
std::shared_ptr<User> creditor;
long amountCents;
Transaction(std::shared_ptr<User> d, std::shared_ptr<User> c, long a) : debtor(d), creditor(c), amountCents(a) {}
};
class GroupBalanceSheet {
private:
std::unordered_map<std::shared_ptr<User>, long> netBalances;
std::mutex mtx;
public:
void addExpense(std::shared_ptr<User> payer, long totalCents, const std::vector<Split>& splits) {
std::lock_guard<std::mutex> lock(mtx);
netBalances[payer] += totalCents;
for (const auto& split : splits) {
netBalances[split.user] -= split.amountCents;
}
}
std::vector<Transaction> simplifyDebts() {
std::lock_guard<std::mutex> lock(mtx);
auto comp = [](const std::pair<long, std::shared_ptr<User>>& a, const std::pair<long, std::shared_ptr<User>>& b) {
return a.first < b.first;
};
std::priority_queue<std::pair<long, std::shared_ptr<User>>, std::vector<std::pair<long, std::shared_ptr<User>>>, decltype(comp)> debtors(comp);
std::priority_queue<std::pair<long, std::shared_ptr<User>>, std::vector<std::pair<long, std::shared_ptr<User>>>, decltype(comp)> creditors(comp);
for (const auto& entry : netBalances) {
long bal = entry.second;
if (bal < 0) {
debtors.push({-bal, entry.first});
} else if (bal > 0) {
creditors.push({bal, entry.first});
}
}
std::vector<Transaction> transactions;
while (!debtors.empty() && !creditors.empty()) {
auto debtor = debtors.top(); debtors.pop();
auto creditor = creditors.top(); creditors.pop();
long settleAmount = std::min(debtor.first, creditor.first);
transactions.push_back(Transaction(debtor.second, creditor.second, settleAmount));
long remainingDebt = debtor.first - settleAmount;
long remainingCredit = creditor.first - settleAmount;
if (remainingDebt > 0) {
debtors.push({remainingDebt, debtor.second});
}
if (remainingCredit > 0) {
creditors.push({remainingCredit, creditor.second});
}
}
return transactions;
}
};
Interactive Quiz
1.
2.
3.
Walk a scenario + concurrency
"Trip group: A pays ₹300 dinner, equal among A,B,C" → EqualSplit.computeSplits → splits (100,100,100) → BalanceSheet: B −100, C −100, A +200. "B pays ₹150 taxi, exact: A 50, B 100" → A +50… → nets: A +150, B −50, C −100 → simplify → C pays A ₹100, B pays A ₹50. Two transactions settle the trip.
Concurrency follow-up: two expenses added to one group simultaneously → the balance update is read-modify-write. Same family as the parking-lot race: atomic per-group mutation (lock or serialized queue per group), or make balances derived only — append expenses to a log, compute nets on read; appends don't race (the event-sourcing instinct, in miniature).
1/65 separate IOUs between 4 people. First collapse them: a person's net balance is what they're owed minus what they owe. Who paid whom stops mattering — only the net does.
Q&A
Practice — level up
Splitwise's core is a graph of balances plus a greedy settlement. Train both halves on these:
Climb in order — every rung assumes the one above it. Solve on LeetCode, then tick it here; progress is saved on this device.
Warm-up — net flow on a graph
Net in/out degree on a tiny directed graph — the balance idea.
Core — propagate values across relationships
- Evaluate DivisionMedium
Walk a graph of ratios — the same shape as balances flowing across IOUs.
Stretch — the literal problem
This IS Splitwise's simplify step.Minimum transfers to settle debts (LeetCode Premium) — greedy ships, optimal is NP-hard.