Low-Level Design: Splitwise (Expense Sharing App)
The Splitwise LLD asks you to model a shared expense tracker where users add expenses, split them among participants, and settle debts. It tests graph-based debt simplification, the Strategy pattern for split methods, and clean domain modelling. Asked at Airbnb, Stripe, Coinbase, and DoorDash.
Requirements
- Users create groups and add expenses.
- Expenses can be split equally, by exact amounts, or by percentage.
- Track who owes whom and how much.
- Simplify debts: minimize the number of transactions to settle all balances.
- Record payments (settlements).
Split Strategies (Strategy Pattern)
from abc import ABC, abstractmethod
from dataclasses import dataclass
from typing import Dict
@dataclass
class SplitResult:
shares: Dict[str, float] # user_id -> amount they owe
class SplitStrategy(ABC):
@abstractmethod
def compute(self, total: float, payer: str,
participants: list[str], **kwargs) -> SplitResult:
...
class EqualSplit(SplitStrategy):
def compute(self, total, payer, participants, **kwargs):
share = total / len(participants)
return SplitResult({uid: share for uid in participants})
class ExactSplit(SplitStrategy):
def compute(self, total, payer, participants, amounts=None, **kwargs):
if amounts is None or abs(sum(amounts.values()) - total) > 0.01:
raise ValueError("Exact amounts must sum to total")
return SplitResult(amounts)
class PercentageSplit(SplitStrategy):
def compute(self, total, payer, participants, percentages=None, **kwargs):
if percentages is None or abs(sum(percentages.values()) - 100) > 0.01:
raise ValueError("Percentages must sum to 100")
return SplitResult({uid: total * pct / 100
for uid, pct in percentages.items()})
Core Domain
import uuid
from collections import defaultdict
@dataclass
class User:
user_id: str
name: str
email: str
@dataclass
class Expense:
expense_id: str
description: str
total: float
payer_id: str
shares: Dict[str, float] # user_id -> amount they owe payer
@dataclass
class Group:
group_id: str
name: str
members: set
def add_member(self, user_id: str):
self.members.add(user_id)
Expense Service and Balance Tracking
class ExpenseService:
def __init__(self):
self.users: Dict[str, User] = {}
self.groups: Dict[str, Group] = {}
self.expenses: Dict[str, Expense] = {}
# balances[user_a][user_b] = amount user_a owes user_b (positive means owes)
self.balances: defaultdict = defaultdict(lambda: defaultdict(float))
def add_user(self, name: str, email: str) -> User:
user = User(str(uuid.uuid4())[:6], name, email)
self.users[user.user_id] = user
return user
def create_group(self, name: str, member_ids: list[str]) -> Group:
group = Group(str(uuid.uuid4())[:6], name, set(member_ids))
self.groups[group.group_id] = group
return group
def add_expense(self, group_id: str, description: str,
total: float, payer_id: str,
strategy: SplitStrategy, **kwargs) -> Expense:
group = self.groups[group_id]
split = strategy.compute(total, payer_id,
list(group.members), **kwargs)
expense = Expense(
expense_id = str(uuid.uuid4())[:6],
description = description,
total = total,
payer_id = payer_id,
shares = split.shares
)
self.expenses[expense.expense_id] = expense
# Update balance matrix
for uid, amount in split.shares.items():
if uid != payer_id:
self.balances[uid][payer_id] += amount # uid owes payer
self.balances[payer_id][uid] -= amount # payer is owed by uid
return expense
def record_payment(self, from_id: str, to_id: str, amount: float) -> None:
self.balances[from_id][to_id] -= amount
self.balances[to_id][from_id] += amount
def get_balance(self, user_id: str) -> Dict[str, float]:
return {uid: amt for uid, amt in self.balances[user_id].items() if abs(amt) > 0.01}
def simplify_debts(self) -> list[tuple[str, str, float]]:
"""
Minimize the number of transactions to settle all debts.
Algorithm: compute net balance per user, then match creditors with debtors.
"""
net: Dict[str, float] = defaultdict(float)
for user_a, owed in self.balances.items():
for user_b, amount in owed.items():
if amount > 0:
net[user_a] -= amount # user_a owes
net[user_b] += amount # user_b is owed
debtors = sorted([(amt, uid) for uid, amt in net.items() if amt 0.01], reverse=True)
transactions = []
i, j = 0, 0
debtors_list = [(uid, -amt) for amt, uid in debtors] # (uid, debt)
creditors_list = [(uid, amt) for amt, uid in creditors] # (uid, credit)
while i < len(debtors_list) and j < len(creditors_list):
debtor, debt = debtors_list[i]
creditor, credit = creditors_list[j]
payment = min(debt, credit)
transactions.append((debtor, creditor, round(payment, 2)))
debtors_list[i] = (debtor, debt - payment)
creditors_list[j] = (creditor, credit - payment)
if debtors_list[i][1] < 0.01: i += 1
if creditors_list[j][1] < 0.01: j += 1
return transactions
Usage Example
svc = ExpenseService()
alice = svc.add_user("Alice", "alice@example.com")
bob = svc.add_user("Bob", "bob@example.com")
carol = svc.add_user("Carol", "carol@example.com")
trip = svc.create_group("Trip", [alice.user_id, bob.user_id, carol.user_id])
# Alice pays $90 dinner, split equally
svc.add_expense(trip.group_id, "Dinner", 90.0,
alice.user_id, EqualSplit())
# Bob pays $60 taxi, Carol owes $20, Alice owes $40
svc.add_expense(trip.group_id, "Taxi", 60.0,
bob.user_id, ExactSplit(),
amounts={alice.user_id: 40.0, carol.user_id: 20.0})
# Show simplified settlement
for debtor, creditor, amount in svc.simplify_debts():
print(f"{debtor} pays {creditor}: ${amount:.2f}")
Debt Simplification Algorithm
The greedy algorithm reduces N*(N-1) pairwise transactions to at most N-1 transactions:
- Compute net balance per user (positive = owed money, negative = owes money).
- Sort debtors (most negative first) and creditors (most positive first).
- At each step, match the largest debtor with the largest creditor. The smaller side is settled in one transaction; the difference remains for the other side.
- Repeat until all balances are zero.
This is greedy optimal in minimising transaction count for the sum-zero constraint, but not always optimal for minimising total payment amounts (NP-hard in general).
Design Patterns Used
| Pattern | Usage |
|---|---|
| Strategy | SplitStrategy (EqualSplit, ExactSplit, PercentageSplit) — interchangeable splitting algorithms |
| Repository | ExpenseService holds users, groups, expenses — could be replaced by a DB layer |
| Value Object | SplitResult wraps the shares dict cleanly |
Interview Extensions
How would you add currency support?
Add a currency field to Expense. Balances are tracked per currency. Settlement uses exchange rates from an FX service to convert between currencies. Display balances in the user’s preferred currency. For simplification, convert all amounts to USD before the greedy algorithm.
How would you handle group member leaving mid-expense?
Leaving a group does not delete the user from past expenses (historical data is immutable). Their balance in those expenses remains. The user is excluded from new expenses going forward. The platform may offer a “settle up” reminder when a member leaves with an outstanding balance.
Asked at: Airbnb Interview Guide
Asked at: Stripe Interview Guide
Asked at: Coinbase Interview Guide
Asked at: DoorDash Interview Guide
Asked at: Shopify Interview Guide