LLD: Splitwise¶

Difficulty: Beginner | Time: 30–40 minutes

1. Problem Statement¶

Design an expense-splitting system (think Splitwise). Users belong to groups. An expense is added by one user (the payer) on behalf of a set of participants, and is split among them — equally, by exact amounts, or by percentage. The system tracks who owes whom, and can produce a simplified summary of net balances — the minimum set of payments that settles all debts — rather than a raw list of every individual expense.

2. Requirements¶

Functional (in scope):

• Add a user to one or more groups
• Add an Expense: payer, amount, participants, and a split strategy (equal / exact / percentage)
• Maintain a running balance between every pair of users who have ever shared an expense
• Show a user's net balance with each other user, and a group's overall balance sheet
• Simplify debts: given all pairwise balances, compute the minimum number of transactions that zeroes everyone out
• Record a settlement (partial or full payment) between two users

Explicitly out of scope for v1: multi-currency and FX conversion (touched on in Extensibility), recurring/scheduled expenses, actually moving money through a payment processor, itemized receipt splitting (who ordered which line item).

3. Entities¶

The nouns in the problem statement: User, Group, Expense, Split (abstract, with EqualSplit / ExactSplit / PercentSplit), and a Ledger that owns the pairwise balance sheet and the simplification algorithm.

4. Class Design¶

classDiagram
    class User {
        +user_id: str
        +name: str
    }

    class Group {
        +group_id: str
        +name: str
        +members: List~User~
        +ledger: Ledger
        +add_expense(expense) void
    }

    class SplitStrategy {
        <<interface>>
        +compute(amount, participants)* Dict~User, float~
    }
    class EqualSplit
    class ExactSplit
    class PercentSplit

    class Expense {
        +expense_id: str
        +payer: User
        +amount: float
        +participants: List~User~
        +strategy: SplitStrategy
        +shares() Dict~User, float~
    }

    class Ledger {
        -balances: Dict~Tuple, float~
        +apply(expense) void
        +settle(payer, payee, amount) void
        +net_balance(a, b) float
        +simplify() List~Settlement~
    }

    class Settlement {
        +from_user: User
        +to_user: User
        +amount: float
    }

    Group *-- User : composition, membership
    Group *-- Ledger : composition
    Group o-- Expense : aggregation, expenses persist as history
    Expense --> SplitStrategy : uses (injected)
    SplitStrategy <|.. EqualSplit
    SplitStrategy <|.. ExactSplit
    SplitStrategy <|.. PercentSplit
    Ledger ..> Settlement : produces

Why composition for Group *-- Ledger: a ledger has no meaning outside its group — delete the group, its balance sheet goes with it. Why aggregation for Group o-- Expense: an expense is a historical record — even if a user leaves the group, the expense they were part of stays in the group's history, so expenses conceptually outlive membership (see Class Relationships). Note Expense doesn't touch balances directly — it only knows how to compute shares via its SplitStrategy; applying those shares to the running balance sheet is the Ledger's job. That separation matters: Expense answers "how much does each participant owe for this expense," Ledger answers "who owes whom overall."

5. Patterns Applied¶

• Strategy for SplitStrategy — "equal, exact, or percentage" is named directly in the requirements as a real variation point, so Expense depends on the SplitStrategy interface rather than branching on a split-type enum. A new split type (e.g. "by shares," like 2 shares for one roommate and 1 for another) is a new class with zero edits to Expense or Ledger. See Design Patterns.
• Debt simplification is a graph problem, not a GoF pattern — and naming it as one would be forcing a fit. Model each group as a directed, weighted graph: nodes are users, an edge u → v with weight w means "u owes v amount w." After netting every pairwise edge down to at most one direction, the "simplify" operation is: given a set of nodes each with a net balance (positive = net creditor, negative = net debtor), find the minimum number of edges that transports every debtor's balance to some creditor and zeroes everyone out. This is the real algorithmic core of the problem, and it's worth stating out loud in an interview that it's a greedy min-cash-flow problem, not a design-pattern problem.
• The greedy approach — repeatedly match the largest creditor with the largest debtor — is not provably minimal in the worst case (the exact minimum-transaction problem is NP-hard in general), but it's the standard, interview-acceptable answer: it's simple, fast, and produces a good-enough reduction in practice. Naming that trade-off explicitly is worth more than pretending the greedy result is provably optimal.

6. Core Code¶

from abc import ABC, abstractmethod
from collections import defaultdict
from dataclasses import dataclass, field
from threading import Lock
import heapq
import itertools
import uuid


@dataclass(frozen=True)
class User:
    user_id: str
    name: str


class SplitStrategy(ABC):
    @abstractmethod
    def compute(self, amount: float, participants: list[User], **kwargs) -> dict[User, float]:
        """Return each participant's share. Must sum to `amount` (validated by caller)."""
        ...


class EqualSplit(SplitStrategy):
    def compute(self, amount: float, participants: list[User], **kwargs) -> dict[User, float]:
        n = len(participants)
        base = round(amount / n, 2)
        shares = {p: base for p in participants}
        # rounding remainder: the payer absorbs the leftover cent(s) rather than
        # silently under- or over-charging one arbitrary participant
        remainder = round(amount - base * n, 2)
        if remainder:
            payer = kwargs.get("payer")
            target = payer if payer in shares else participants[0]
            shares[target] = round(shares[target] + remainder, 2)
        return shares


class ExactSplit(SplitStrategy):
    def compute(self, amount: float, participants: list[User], amounts: dict[User, float] = None, **kwargs) -> dict[User, float]:
        amounts = amounts or {}
        total = round(sum(amounts.get(p, 0.0) for p in participants), 2)
        if total != round(amount, 2):
            raise ValueError(f"exact amounts sum to {total}, expected {amount}")
        return {p: amounts.get(p, 0.0) for p in participants}


class PercentSplit(SplitStrategy):
    def compute(self, amount: float, participants: list[User], percentages: dict[User, float] = None, **kwargs) -> dict[User, float]:
        percentages = percentages or {}
        total_pct = round(sum(percentages.get(p, 0.0) for p in participants), 2)
        if total_pct != 100.0:
            raise ValueError(f"percentages sum to {total_pct}, expected 100")
        return {p: round(amount * percentages.get(p, 0.0) / 100, 2) for p in participants}


@dataclass
class Expense:
    payer: User
    amount: float
    participants: list[User]
    strategy: SplitStrategy
    strategy_kwargs: dict = field(default_factory=dict)
    expense_id: str = field(default_factory=lambda: str(uuid.uuid4()))

    def shares(self) -> dict[User, float]:
        return self.strategy.compute(
            self.amount, self.participants, payer=self.payer, **self.strategy_kwargs
        )


@dataclass
class Settlement:
    from_user: User
    to_user: User
    amount: float


class Ledger:
    """Owns the pairwise balance sheet for one group and the debt-simplification algorithm."""

    def __init__(self):
        # (debtor, creditor) -> amount owed; only ever positive, one direction per pair at a time
        self._balances: dict[tuple[User, User], float] = defaultdict(float)
        self._lock = Lock()

    def _adjust(self, debtor: User, creditor: User, amount: float) -> None:
        # additive increment, not a read-then-overwrite — see Concurrency
        if debtor == creditor or amount == 0:
            return
        with self._lock:
            self._balances[(debtor, creditor)] += amount
            self._normalize(debtor, creditor)

    def _normalize(self, a: User, b: User) -> None:
        # collapse (a owes b) and (b owes a) into a single net direction
        forward = self._balances.get((a, b), 0.0)
        backward = self._balances.get((b, a), 0.0)
        net = round(forward - backward, 2)
        self._balances.pop((a, b), None)
        self._balances.pop((b, a), None)
        if net > 0:
            self._balances[(a, b)] = net
        elif net < 0:
            self._balances[(b, a)] = -net

    def apply(self, expense: Expense) -> None:
        shares = expense.shares()
        for participant, share in shares.items():
            if participant is expense.payer:
                continue
            self._adjust(debtor=participant, creditor=expense.payer, amount=share)

    def settle(self, payer: User, payee: User, amount: float) -> None:
        """Record a real-world payment: payer pays payee, reducing what payer owes payee."""
        # Validation and mutation are one critical section. Calling _adjust()
        # after an unlocked read would let two concurrent settlements both
        # validate against the same old balance and overpay it.
        with self._lock:
            current = self._balances.get((payer, payee), 0.0)
            if amount > current:
                raise ValueError(f"{payer.name} only owes {payee.name} {current}, cannot settle {amount}")
            self._balances[(payer, payee)] -= amount
            self._normalize(payer, payee)

    def net_balance(self, a: User, b: User) -> float:
        return self._balances.get((a, b), 0.0) - self._balances.get((b, a), 0.0)

    def simplify(self) -> list[Settlement]:
        """
        Greedy min-transaction settlement: repeatedly pay the largest creditor
        from the largest debtor. Uses two max-heaps so each step is O(log n)
        instead of an O(n) linear scan for the largest balance.
        """
        net: dict[User, float] = defaultdict(float)
        for (debtor, creditor), amount in self._balances.items():
            net[debtor] -= amount
            net[creditor] += amount

        # heapq is a min-heap, so negate to simulate a max-heap
        debtors = [(-bal, next(_tiebreak), u) for u, bal in net.items() if bal < -0.01]
        creditors = [(bal, next(_tiebreak), u) for u, bal in net.items() if bal > 0.01]
        heapq.heapify(debtors)
        heapq.heapify(creditors)

        settlements: list[Settlement] = []
        while debtors and creditors:
            neg_debt, _, debtor = heapq.heappop(debtors)
            credit, _, creditor = heapq.heappop(creditors)
            debt = -neg_debt

            amount = round(min(debt, credit), 2)
            settlements.append(Settlement(from_user=debtor, to_user=creditor, amount=amount))

            remaining_debt = round(debt - amount, 2)
            remaining_credit = round(credit - amount, 2)
            if remaining_debt > 0.01:
                heapq.heappush(debtors, (-remaining_debt, next(_tiebreak), debtor))
            if remaining_credit > 0.01:
                heapq.heappush(creditors, (remaining_credit, next(_tiebreak), creditor))

        return settlements


_tiebreak = itertools.count()  # breaks heap ties without comparing User objects

Why the greedy loop terminates in at most n - 1 transactions for n participants with nonzero balance: every iteration fully zeroes out at least one side of the pair popped (whichever of debt/credit was smaller), removing at least one node from further consideration. You cannot zero out more than n participants in fewer than n - 1 transfers overall (the last remaining pair still needs one transaction between them), so the greedy bound is exactly the same lower bound as the general minimum — the greedy result is optimal in the common case where debts don't have adversarial fractional overlaps, and close to optimal otherwise. That's the proof intuition to say out loud, not a full NP-hardness derivation.

7. Edge Cases¶

8. Concurrency¶

Two expenses touching an overlapping set of users can be added concurrently — e.g. Alice adds "dinner, split with Bob," while at the same instant Bob adds "cab fare, split with Alice." Both mutate the (Alice, Bob) balance pair in the same Ledger.

Why naive last-write-wins on a shared balance dict is wrong: if _adjust were written as a read-modify-write — current = balances[(a, b)]; balances[(a, b)] = current + amount — two threads could both read the same starting value, compute their own updated value from it, and the second write would clobber the first, silently losing one expense's contribution to the balance. This is the classic race condition: the bug doesn't show up as a crash, it shows up as a balance sheet that's quietly wrong.

The fix in the code above is twofold:

• _adjust wraps the read-modify-write in a lock (_lock), so the increment is atomic — no thread can observe a partially-applied update.
• Just as important as the lock: the operation itself is expressed as an additive increment (self._balances[(debtor, creditor)] += amount) rather than a set-to-value assignment. Even with a lock, a design that computed a new absolute balance from a stale read and then set it would be fragile against reordering; expressing every mutation as "add this delta" makes the operation naturally commutative — two expenses applied in either order land on the same final balance, exactly the property you want under concurrency. See Locks.

Why lock per-Ledger (i.e., per-group) rather than one global lock or one lock per user-pair: per-group is the natural grain — expenses within a group frequently touch overlapping pairs (the same small set of members), so per-pair locking would mean acquiring 2-3 locks per expense with an ordering-discipline requirement (see the deadlock note in Parking Lot) for a payoff that's marginal, since most contention in this domain is already confined to one group. A single group-wide lock is coarser but simpler and correct, and groups are typically small enough (tens of members) that lock hold time per apply() call is negligible. A global lock across all groups would be the wrong call — it would serialize unrelated groups' expenses for no reason.

9. Extensibility¶

Interview Questions¶

Key Takeaways¶

Previous: Library Management | Next: ATM