Design Splitwise (Expense Sharing)
You'll learn to
- -Spot the two problems hiding in an expense-sharing prompt: how a bill is split, and how to settle up
- -Model equal, exact and percentage splits as swappable strategies, and track one net balance per person
- -Settle a real three-person example in fewer payments with a greedy match, and state its limits honestly
Think of friends on a weekend away. One pays for dinner, another for a taxi, a third for snacks, and everyone keeps a tab on a phone. At the end, nobody wants to make six separate bank transfers. An expense-sharing app such as Splitwise has two problems hiding in it. The first is how one bill splits among people, which is a question about extensibility and is solved with a familiar pattern. The second is working out the smallest set of payments that settles everyone, which is a small but genuine algorithm problem.
Step 1: Users, Groups and Expenses
The nouns give the first classes: a user, a group of users, and an expense, which records who paid, how much, who took part, and how the amount is divided.
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 a Strategy
Equal, exact-amount and percentage splits are three ways to answer one question: "how much does each participant owe?" That is the Strategy shape. Expense depends on a SplitStrategy interface and never on which concrete split is in use, so a fourth kind (by shares, say) is a new class and nothing else changes.
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: Track One Net Balance per Person
Storing every "A owes B this much" pair gets messy fast: with n people there can be up to n × (n - 1) / 2 pairs. Keep one net balance per person instead. Positive means the group owes them, negative means they owe the group. Recording an expense changes at most n numbers: the payer's balance goes up by the full amount, and each participant's goes down by their share.
Step 4: Simplify the Debts
Now the interesting part. Given each person's net balance, find few payments that bring everyone to zero. The greedy approach is to match the person owed the most with the person who owes the most, settle the smaller of the two amounts, and repeat. It is simple to explain and gives a good answer. It is not always the mathematical minimum, but it is never more than n - 1 payments for n people, because each payment fully clears at least one person.
Run the demo on a concrete weekend. Alice pays 90 for dinner, split equally among the three. Bob pays 60 for a taxi, also equal. Carol pays 30 for snacks, split 50, 25 and 25 percent. Predict the balances first. Alice is owed 90 and owes 30, 20 and 15, which nets to +25.
Without simplifying, each of the three expenses leaves two people owing the payer, so six debts. After netting, Carol owes 27.5 in total, and she pays Alice 25 and Bob 2.5. Two payments, which is the n - 1 limit for three people.
Name the trade-off aloud: "this greedy approach is not provably minimal in every case, but it is a strong, explainable heuristic. The provably optimal version is a much harder graph problem, not worth the interview time unless you ask for it." Notice also the name in each heap entry: with two equal balances, Python would otherwise try to compare two User objects and crash.
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.
Forge Level 46: Splitwise / Expense Sharing asks you to implement add_expense()/get_balance() for an expense group, graded by running your actual code against real test cases.
Discussion0
Join the Discussion
Sign in to leave comments, reply to others, or like insights.
No comments yet. Be the first to start the thread!