Courses › Low-Level Design › Problem Walkthroughs

Design Splitwise

Split strategies, cent rounding, net balances and simplifying debts.

Splitwise is a domain-modeling question with an algorithm hidden inside it. You need clean entities for users, groups and expenses, a pluggable split strategy (equal, exact or percentage), correct money handling, and, as the classic follow-up, an algorithm to simplify debts into fewer payments.

Requirements

  • Users belong to groups, and an expense is paid by one user and split among several.
  • Split types: equal, exact amounts and percentages.
  • Show balances: who owes whom, and how much.
  • Record a settlement payment.
  • Follow-up: simplify the group's debts into the fewest transfers.

Model

User           id, name
Group          id, name, members
Expense        id, paid_by, amount_cents, splits: list[Split], description
Split          user, amount_cents
SplitStrategy  (interface) split(amount, participants, params) -> list[Split]
  EqualSplit, ExactSplit, PercentSplit
BalanceSheet   net[user] (positive = is owed); apply(expense), settle(payer, payee, amount)
ExpenseService add_expense(...), balances(group), simplify(group)

[!TIP] Store net balances, not a list of IOUs For a group, a single number per user is enough: total paid minus total owed. Pairwise "A owes B" views can be derived from it. This keeps the data small and makes debt simplification straightforward.

Split strategies and rounding

Work in integer cents. Splitting 1000 cents three ways gives 333 each with 1 cent left over. Someone has to take that extra cent, and the splits must add up exactly to the total.

from abc import ABC, abstractmethod
from dataclasses import dataclass


@dataclass(frozen=True)
class Split:
    user: str
    amount: int          # cents


class SplitStrategy(ABC):
    @abstractmethod
    def split(self, amount, users, params=None) -> list[Split]: ...


class EqualSplit(SplitStrategy):
    def split(self, amount, users, params=None):
        base, extra = divmod(amount, len(users))
        # the first `extra` users absorb one leftover cent each
        return [Split(u, base + (1 if i < extra else 0)) for i, u in enumerate(users)]


class ExactSplit(SplitStrategy):
    def split(self, amount, users, params):
        if sum(params) != amount:
            raise ValueError("exact amounts must add up to the total")
        return [Split(u, a) for u, a in zip(users, params)]


class PercentSplit(SplitStrategy):
    def split(self, amount, users, params):
        if sum(params) != 100:
            raise ValueError("percentages must add up to 100")
        shares = [amount * p // 100 for p in params]
        shares[0] += amount - sum(shares)          # rounding remainder goes to one user
        return [Split(u, s) for u, s in zip(users, shares)]

Balances and settlement

from collections import defaultdict


class BalanceSheet:
    def __init__(self):
        self.net = defaultdict(int)       # user -> cents (positive = is owed money)

    def apply(self, paid_by, splits):
        for s in splits:
            self.net[s.user] -= s.amount
        self.net[paid_by] += sum(s.amount for s in splits)

    def settle(self, payer, payee, amount):
        self.net[payer] += amount
        self.net[payee] -= amount


class ExpenseService:
    STRATEGIES = {"equal": EqualSplit(), "exact": ExactSplit(), "percent": PercentSplit()}

    def __init__(self):
        self.sheets = defaultdict(BalanceSheet)    # group_id -> sheet
        self.expenses = defaultdict(list)

    def add_expense(self, group_id, paid_by, amount, users, kind="equal", params=None):
        if amount <= 0:
            raise ValueError("amount must be positive")
        splits = self.STRATEGIES[kind].split(amount, users, params)
        self.sheets[group_id].apply(paid_by, splits)
        self.expenses[group_id].append((paid_by, amount, splits))
        return splits

The invariant to state, and to assert in a test: the net balances in a group always sum to zero.

Simplifying debts

Given the net balances, produce a list of transfers that settles everyone. A greedy approach works well: repeatedly match the person who owes the most with the person who is owed the most, and transfer the smaller of the two amounts. Each step settles at least one person fully, so there are at most n − 1 transfers.

import heapq


def simplify(net):
    creditors = [(-amt, u) for u, amt in net.items() if amt > 0]
    debtors = [(amt, u) for u, amt in net.items() if amt < 0]
    heapq.heapify(creditors)
    heapq.heapify(debtors)
    transfers = []
    while creditors and debtors:
        c_amt, c = heapq.heappop(creditors)
        d_amt, d = heapq.heappop(debtors)
        pay = min(-c_amt, -d_amt)
        transfers.append((d, c, pay))            # d pays c
        if -c_amt > pay:
            heapq.heappush(creditors, (c_amt + pay, c))
        if -d_amt > pay:
            heapq.heappush(debtors, (d_amt + pay, d))
    return transfers
svc = ExpenseService()
svc.add_expense("trip", "ana", 3000, ["ana", "bo", "cy"])   # dinner
svc.add_expense("trip", "bo", 1500, ["ana", "bo", "cy"])    # taxi
sheet = svc.sheets["trip"]
assert sum(sheet.net.values()) == 0
assert sorted(simplify(sheet.net)) == [("cy", "ana", 1500)]

[!INTERVIEW] Greedy isn't always the minimum The greedy approach gives at most n − 1 transfers, but the true minimum can be smaller. If the group splits into subsets that each sum to zero, each subset settles on its own. Finding the exact minimum is NP-hard: it's a backtracking or bitmask DP problem over subsets, practical for groups of about 12–15 people. Say this, offer greedy as the practical choice, and you've covered the question well.

Follow-ups

  • Multiple currencies: keep a separate balance per currency, and convert only when settling, at a recorded rate.
  • Editing or deleting an expense: apply its reverse (negated splits) to the balance sheet and keep the history. Don't silently mutate.
  • Concurrency: lock per group. All of a group's balance changes go through its sheet.
  • Activity feed and notifications: emit an ExpenseAdded event to observers.
  • Audit and correctness: store expenses as the source of truth and rebuild balances from them. This is the same idea as event sourcing.

[!TIP] Practice Design Splitwise · Design a Digital Wallet · In-Memory Banking System