Financial & PaymentsProblem 6 of 7
Financial & PaymentsAdvanced
Splitwise
Strategy PatternObserver PatternCommand Pattern
Expense splitting with multiple strategies, debt simplification via a greedy graph algorithm, and a balance ledger that tracks net amounts instead of individual transactions.
Key Abstractions
ExpenseService
Facade for creating expenses and querying balances
Expense
Immutable record of who paid, how much, and the split breakdown
SplitStrategy
Strategy interface for equal, exact, and percentage split calculations
BalanceLedger
Net balance tracker with O(1) lookup per user pair
DebtSimplifier
Greedy graph algorithm to minimize number of settlements
User
Participant with name and unique ID
Class Diagram
The Key Insight
Splitwise is not a bill calculator. It's a balance ledger with pluggable split strategies. You never store individual transaction amounts between pairs. You store the net balance. After 50 group dinners, Alice either owes Bob money or she doesn't. One number, not 50 line items.
The other big piece is debt simplification. If Alice owes Bob $10 and Bob owes Charlie $10, you don't need two transfers. Alice pays Charlie directly. That's a greedy algorithm over net balances: sort creditors and debtors by amount, match the largest with the largest, keep going.
Requirements
Functional
- Create and manage users within expense groups
- Add expenses with different split strategies: equal, exact amounts, percentages
- Track balances between all user pairs
- Simplify debts to minimize the number of settlement transactions
- View expense history and individual balances
Non-Functional
- Split calculations must handle rounding correctly (no penny drift over time)
- Debt simplification should minimize total number of transactions
- Balance lookups should be O(1) per user pair
Design Decisions
Why a BalanceLedger instead of storing each expense's splits?
Storing raw splits means every "who owes whom" query scans all expenses. That's O(n) per query. The ledger maintains running net balances, so after 10,000 expenses, checking if Alice owes Bob is still a single hashmap lookup.
Why does the last participant absorb rounding?
Split $100 three ways and each share is $33.33. That's $99.99. Someone has to eat the penny. Assigning it to the last participant is deterministic, auditable, and matches how Splitwise and Venmo actually work. Random assignment or crediting the payer is harder to audit.
Why Strategy pattern instead of an enum with a switch?
An enum forces every new split type into ExpenseService. Strategy lets teams independently create custom split logic (like weight-based splits for roommates with different room sizes) without modifying the service. New behavior, zero changes to existing code.
Why greedy for debt simplification?
The optimal minimum-transaction problem is NP-hard in the general case (it's a variant of subset-sum). The greedy approach of matching largest creditor to largest debtor gives near-optimal results and runs in O(n log n). For a group of friends splitting dinner, greedy and optimal produce the same answer anyway.
Interview Follow-ups
- "How would you handle multi-currency expenses?" Add a
Currencyfield to expenses and aCurrencyConverterservice. Balances are stored per-currency or normalized to a base currency. - "What about recurring expenses?" A
RecurringExpensetemplate with a scheduler that callsaddExpenseon a cron. The expense object itself is identical. - "How would you handle group merging?" Combine the ledgers. Net balance math is additive, so you just sum the balance maps.
- "What if someone disputes a split?" Command pattern with an undo stack. Each expense is a command that can be reversed, recalculating balances.
Code Implementation
1 from abc import ABC, abstractmethod
2 from dataclasses import dataclass, field
3 from decimal import Decimal, ROUND_HALF_UP
4 from datetime import datetime
5 from collections import defaultdict
6 import uuid
7
8
9 @dataclass(frozen=True)
10 class User:
11 id: str
12 name: str
13
14
15 class SplitStrategy(ABC):
16 @abstractmethod
17 def split(self, amount: Decimal, participants: list[User]) -> dict[User, Decimal]: ...
18
19 def _validate(self, amount: Decimal, shares: dict[User, Decimal]) -> None:
20 total = sum(shares.values())
21 if abs(total - amount) > Decimal("0.01"):
22 raise ValueError(f"Split total {total} != expense amount {amount}")
23
24
25 class EqualSplit(SplitStrategy):
26 def split(self, amount: Decimal, participants: list[User]) -> dict[User, Decimal]:
27 n = len(participants)
28 base = (amount / n).quantize(Decimal("0.01"), ROUND_HALF_UP)
29 shares = {p: base for p in participants}
30 # Last person absorbs rounding remainder
31 remainder = amount - base * n
32 shares[participants[-1]] += remainder
33 self._validate(amount, shares)
34 return shares
35
36
37 class ExactSplit(SplitStrategy):
38 def __init__(self, exact_amounts: dict[User, Decimal]):
39 self._amounts = exact_amounts
40
41 def split(self, amount: Decimal, participants: list[User]) -> dict[User, Decimal]:
42 shares = {p: self._amounts[p] for p in participants}
43 self._validate(amount, shares)
44 return shares
45
46
47 class PercentSplit(SplitStrategy):
48 def __init__(self, percentages: dict[User, Decimal]):
49 total_pct = sum(percentages.values())
50 if abs(total_pct - Decimal("100")) > Decimal("0.01"):
51 raise ValueError(f"Percentages sum to {total_pct}, expected 100")
52 self._pcts = percentages
53
54 def split(self, amount: Decimal, participants: list[User]) -> dict[User, Decimal]:
55 shares = {}
56 running = Decimal("0")
57 for p in participants[:-1]:
58 share = (amount * self._pcts[p] / 100).quantize(Decimal("0.01"), ROUND_HALF_UP)
59 shares[p] = share
60 running += share
61 shares[participants[-1]] = amount - running # absorb rounding
62 self._validate(amount, shares)
63 return shares
64
65
66 class BalanceLedger:
67 """Tracks net balances. Positive means 'is owed money'."""
68
69 def __init__(self):
70 # Key: (min_id, max_id), Value: net from min_id's perspective
71 self._balances: dict[tuple[str, str], Decimal] = defaultdict(Decimal)
72
73 def _key(self, a: str, b: str) -> tuple[str, str]:
74 return (min(a, b), max(a, b))
75
76 def record(self, debtor: User, creditor: User, amount: Decimal) -> None:
77 k = self._key(debtor.id, creditor.id)
78 sign = Decimal("1") if creditor.id == max(debtor.id, creditor.id) else Decimal("-1")
79 self._balances[k] += sign * amount
80
81 def net_balance(self, a: User, b: User) -> Decimal:
82 """Positive means a owes b."""
83 k = self._key(a.id, b.id)
84 val = self._balances.get(k, Decimal("0"))
85 return val if a.id == min(a.id, b.id) else -val
86
87 def all_balances_for(self, user: User) -> dict[str, Decimal]:
88 result = {}
89 for (a, b), val in self._balances.items():
90 if a == user.id and val != 0:
91 result[b] = val
92 elif b == user.id and val != 0:
93 result[a] = -val
94 return result # positive = owed to user, negative = user owes
95
96
97 @dataclass
98 class Settlement:
99 from_user: User
100 to_user: User
101 amount: Decimal
102
103
104 class DebtSimplifier:
105 """Greedy approach: match largest creditor with largest debtor."""
106
107 @staticmethod
108 def simplify(net_amounts: dict[User, Decimal]) -> list[Settlement]:
109 creditors = sorted(
110 [(u, a) for u, a in net_amounts.items() if a > 0],
111 key=lambda x: x[1], reverse=True
112 )
113 debtors = sorted(
114 [(u, -a) for u, a in net_amounts.items() if a < 0],
115 key=lambda x: x[1], reverse=True
116 )
117 settlements = []
118 ci, di = 0, 0
119 while ci < len(creditors) and di < len(debtors):
120 creditor, credit = creditors[ci]
121 debtor, debt = debtors[di]
122 transfer = min(credit, debt)
123 if transfer > 0:
124 settlements.append(Settlement(debtor, creditor, transfer))
125 creditors[ci] = (creditor, credit - transfer)
126 debtors[di] = (debtor, debt - transfer)
127 if creditors[ci][1] == 0:
128 ci += 1
129 if debtors[di][1] == 0:
130 di += 1
131 return settlements
132
133
134 @dataclass
135 class Expense:
136 id: str
137 paid_by: User
138 amount: Decimal
139 splits: dict[User, Decimal]
140 description: str
141 timestamp: datetime = field(default_factory=datetime.now)
142
143
144 class ExpenseService:
145 def __init__(self):
146 self._users: dict[str, User] = {}
147 self._ledger = BalanceLedger()
148 self._expenses: list[Expense] = []
149
150 def add_user(self, user: User) -> None:
151 self._users[user.id] = user
152
153 def add_expense(
154 self,
155 paid_by: User,
156 amount: Decimal,
157 participants: list[User],
158 strategy: SplitStrategy,
159 description: str = "",
160 ) -> Expense:
161 shares = strategy.split(amount, participants)
162 expense = Expense(
163 id=str(uuid.uuid4())[:8],
164 paid_by=paid_by,
165 amount=amount,
166 splits=shares,
167 description=description,
168 )
169 # Update ledger: each participant except payer owes their share
170 for participant, share in shares.items():
171 if participant != paid_by:
172 self._ledger.record(debtor=participant, creditor=paid_by, amount=share)
173 self._expenses.append(expense)
174 return expense
175
176 def get_balances(self, user: User) -> dict[str, Decimal]:
177 return self._ledger.all_balances_for(user)
178
179 def simplify_debts(self) -> list[Settlement]:
180 net: dict[User, Decimal] = defaultdict(Decimal)
181 for (a_id, b_id), val in self._ledger._balances.items():
182 net[self._users[a_id]] += val
183 net[self._users[b_id]] -= val
184 return DebtSimplifier.simplify(net)
185
186
187 if __name__ == "__main__":
188 alice = User("1", "Alice")
189 bob = User("2", "Bob")
190 charlie = User("3", "Charlie")
191
192 svc = ExpenseService()
193 for u in [alice, bob, charlie]:
194 svc.add_user(u)
195
196 # Alice pays 300 for dinner, split equally
197 svc.add_expense(alice, Decimal("300"), [alice, bob, charlie], EqualSplit(), "Dinner")
198 print("Added: Alice paid 300 for dinner, split 3 ways")
199
200 # Bob pays 150 for cab, split equally
201 svc.add_expense(bob, Decimal("150"), [alice, bob, charlie], EqualSplit(), "Cab")
202 print("Added: Bob paid 150 for cab, split 3 ways")
203
204 # Simplified settlements
205 print("\nSimplified debts:")
206 for s in svc.simplify_debts():
207 print(f" {s.from_user.name} pays {s.to_user.name}: ${s.amount}")Common Mistakes
- ✗Storing gross amounts instead of net balances. That leads to O(n) scan on every 'who owes whom' query.
- ✗Not validating that split amounts sum to the expense total. You get silent balance drift over time.
- ✗Treating percentage splits as exact after rounding. The last person should absorb the rounding error.
- ✗Forgetting that the payer can also be a participant in the split. Common off-by-one on share count.
Key Points
- ✓Strategy pattern for split logic: equal, exact, and percentage splits without if/else chains
- ✓Balance ledger stores net amounts, not individual transactions. O(1) per-pair lookup.
- ✓Debt simplification is a greedy graph problem. Sort creditors and debtors, match greedily.
- ✓Command pattern records expense history, so undo support and audit trail come for free