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.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the Strategy pattern in a Splitwise LLD and why use it?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “The Strategy pattern defines a family of split algorithms (EqualSplit, ExactSplit, PercentageSplit) behind a common interface (SplitStrategy). The ExpenseService calls strategy.compute() without knowing which algorithm is being used. Adding a new split method (e.g., ShareSplit, CustomRatioSplit) requires only a new class, not changing ExpenseService. This follows the Open-Closed Principle.”
}
},
{
“@type”: “Question”,
“name”: “How does the debt simplification algorithm work in Splitwise?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Compute a net balance per user by summing all debts and credits. Users with negative net balance owe money; users with positive balance are owed. Sort both lists. Greedily match the largest debtor with the largest creditor: the smaller side is settled in one transaction; the larger side retains the difference. This reduces N*(N-1)/2 pairwise debts to at most N-1 transactions.”
}
},
{
“@type”: “Question”,
“name”: “How do you track who owes whom in a multi-user expense?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Maintain a balance matrix: balances[user_a][user_b] = amount user_a owes user_b (positive) or is owed by user_b (negative). When an expense is added: for each non-payer, increment balances[uid][payer_id] by their share and decrement balances[payer_id][uid] by the same amount. On settlement: decrement balances[debtor][creditor] by the payment amount.”
}
},
{
“@type”: “Question”,
“name”: “How would you handle currency conversion in a multi-currency expense?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Add a currency field to Expense. Track balances as a dict of {currency: amount} per user pair. For settlement and simplification, convert all amounts to a base currency (USD) using current exchange rates from an FX service. Display balances in the user’s preferred currency by converting back. Store original currency and exchange rate at expense creation time for historical accuracy.”
}
},
{
“@type”: “Question”,
“name”: “What is the data model for a Splitwise-style application?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Core entities: User (id, name, email), Group (id, name, members), Expense (id, description, total, payer_id, shares), Payment (id, from_id, to_id, amount, timestamp). The balance matrix is derived by replaying all expenses and payments — or maintained as a materialized view updated on every expense/payment event. Expenses are immutable after creation; corrections use a separate credit expense.”
}
}
]
}
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