Design Splitwise (Expense Sharing)
You'll learn to
- -Model users, groups, expenses, and splits (equal, exact, percentage) as an extensible Strategy hierarchy
- -Design a balance-simplification algorithm that minimizes the number of settling-up transactions
Splitwise-style expense sharing rewards a candidate who spots two separate problems hiding in one prompt: modeling how an expense splits among people (an extensibility problem, solved with a familiar pattern), and computing the minimum set of payments to settle all debts (a genuinely interesting algorithm problem).
Step 1: Users, Groups, and Expenses
class User:
def __init__(self, user_id: str, name: str):
self.user_id = user_id
self.name = name
class Expense:
def __init__(self, paid_by: User, amount: float, participants: list[User], split_strategy: "SplitStrategy"):
self.paid_by = paid_by
self.amount = amount
self.participants = participants
self.split_strategy = split_strategy
def calculate_splits(self) -> dict[User, float]:
return self.split_strategy.split(self.amount, self.participants)Step 2: Split Types as Strategy
Equal split, exact-amount split, and percentage split are three different algorithms for the same problem ("how much does each participant owe"), which is precisely the Strategy shape from earlier in this course - Expense depends on the SplitStrategy interface, never on which concrete split type is active.
class SplitStrategy(ABC):
@abstractmethod
def split(self, amount: float, participants: list[User]) -> dict[User, float]: ...
class EqualSplit(SplitStrategy):
def split(self, amount: float, participants: list[User]) -> dict[User, float]:
share = amount / len(participants)
return {p: share for p in participants}
class ExactSplit(SplitStrategy):
def __init__(self, amounts: dict[User, float]):
self._amounts = amounts
def split(self, amount: float, participants: list[User]) -> dict[User, float]:
assert abs(sum(self._amounts.values()) - amount) < 0.01, "Exact amounts must sum to total"
return self._amounts
class PercentageSplit(SplitStrategy):
def __init__(self, percentages: dict[User, float]):
self._percentages = percentages
def split(self, amount: float, participants: list[User]) -> dict[User, float]:
assert abs(sum(self._percentages.values()) - 100) < 0.01, "Percentages must sum to 100"
return {u: amount * pct / 100 for u, pct in self._percentages.items()}Step 3: Tracking Net Balances
Rather than storing every individual "who owes whom how much" pairwise, the cleaner model tracks one net balance per user (positive means the group owes them, negative means they owe the group), updated as each expense is recorded - the paying user's balance increases by the full amount, and every participant's balance decreases by their computed share.
Step 4: Simplifying Debts - the Actual Algorithm
The interesting problem: given each user's net balance, compute the minimum number of transactions to settle everyone to zero. A greedy approach - repeatedly matching the person owed the most against the person who owes the most, settling the smaller of the two amounts, and repeating - produces a good, simple-to-explain result (not always mathematically optimal in the worst case, but effective and easy to reason about, which matters more than provable optimality in a 45-minute round).
import heapq
def simplify_debts(balances: dict[User, float]) -> list[tuple[User, User, float]]:
creditors = [(-bal, user) for user, bal in balances.items() if bal > 0.01]
debtors = [(bal, user) for user, bal in balances.items() if bal < -0.01]
heapq.heapify(creditors) # most-owed at the top (negated for a max-heap via heapq's min-heap)
heapq.heapify(debtors) # most-owing at the top
transactions = []
while creditors and debtors:
owed, creditor = heapq.heappop(creditors)
owes, debtor = heapq.heappop(debtors)
amount = min(-owed, -owes)
transactions.append((debtor, creditor, amount))
if -owed - amount > 0.01:
heapq.heappush(creditors, (owed + amount, creditor))
if -owes - amount > 0.01:
heapq.heappush(debtors, (owes + amount, debtor))
return transactionsNaming the trade-off explicitly is worth doing here: "this greedy approach isn't provably minimal in every case, but it's a strong, explainable heuristic - the provably optimal version is a harder graph problem that isn't worth the interview time unless asked."
Interview Signal is part of Pro
See a real weak answer next to a real strong one for this exact topic.
Quiz is part of Pro
Test what you just read with a short quiz, and bank the XP.