Back to Notes

Design Splitwise (Expense Sharing & Debt Simplification)

1. Problem & Why It's Asked

Two distinct sub-problems disguised as one: (1) modeling an expense split (equal, exact, percentage), and (2) debt simplification — given a tangle of who-owes-whom, compute the minimum number of transactions to settle everyone up. The second part is a genuine graph/greedy algorithm problem hiding inside an OOD question, which is what makes this a step up from Parking Lot/LRU Cache.

2. Requirements

Functional: add an expense paid by one user, split among a group (equal / exact amounts / percentage); track running balances between users; simplify debts to a minimal transaction list; support settling a single debt.

Non-functional: simplification should minimize transaction count (not just be correct, but efficient — reducing "A owes B owes C" chains). Extensible to new split types without touching the balance/simplification core.

3. Class Diagram

classDiagram
    class SplitStrategy {
        <<interface>>
        +compute_shares(amount, participants) dict
    }
    class EqualSplit {
        +compute_shares(amount, participants) dict
    }
    class ExactSplit {
        +compute_shares(amount, shares) dict
    }
    class PercentSplit {
        +compute_shares(amount, percentages) dict
    }
    class Expense {
        +str paid_by
        +float amount
        +dict shares
    }
    class Splitwise {
        -dict~str,float~ balances
        +add_expense(paid_by, amount, participants, strategy)
        +settle() list
    }
    SplitStrategy <|.. EqualSplit
    SplitStrategy <|.. ExactSplit
    SplitStrategy <|.. PercentSplit
    Splitwise --> SplitStrategy
    Splitwise "1" --> "*" Expense

4. Design Pattern: Strategy for Split Types

Equal/exact/percentage splits are interchangeable computation rules behind one interface — the same reasoning as pricing in [[Parking Lot]] and the algorithm choice in [[Rate Limiter (OOD)]]. See [[OOD Design Patterns]].

5. Implementation — Balances & Split Strategies

from abc import ABC, abstractmethod
from collections import defaultdict
from dataclasses import dataclass


class SplitStrategy(ABC):
    @abstractmethod
    def compute_shares(self, amount: float, participants: list[str], **kwargs) -> dict[str, float]:
        ...


class EqualSplit(SplitStrategy):
    def compute_shares(self, amount, participants, **kwargs):
        share = round(amount / len(participants), 2)
        return {p: share for p in participants}


class ExactSplit(SplitStrategy):
    def compute_shares(self, amount, participants, exact_amounts: dict[str, float] = None, **kwargs):
        if round(sum(exact_amounts.values()), 2) != round(amount, 2):
            raise ValueError("Exact shares must sum to the total amount")
        return exact_amounts


class PercentSplit(SplitStrategy):
    def compute_shares(self, amount, participants, percentages: dict[str, float] = None, **kwargs):
        if round(sum(percentages.values()), 2) != 100.0:
            raise ValueError("Percentages must sum to 100")
        return {p: round(amount * pct / 100, 2) for p, pct in percentages.items()}


class Splitwise:
    def __init__(self):
        self.balances: dict[str, float] = defaultdict(float)  # positive = owed to them, negative = they owe

    def add_expense(self, paid_by: str, amount: float, participants: list[str],
                     strategy: SplitStrategy, **kwargs) -> None:
        shares = strategy.compute_shares(amount, participants, **kwargs)
        self.balances[paid_by] += amount
        for participant, share in shares.items():
            self.balances[participant] -= share

6. The Hard Part: Debt Simplification

Naively, if A paid for B and C, and separately B paid for C, you'd have a chain: C owes B, B owes A (net), and so on — potentially many pairwise transactions even though the net obligations are simple. The goal: minimum number of transactions to zero out every balance.

Greedy approach: at each step, match the person who owes the most with the person who is owed the most, settle the smaller of the two amounts, and repeat. This is a greedy heuristic, not provably minimal in every case (the true minimum-transaction problem is NP-hard in general — related to minimum cash flow / a variant of bin-covering), but the greedy max-debtor/max-creditor pairing is the standard accepted interview answer and performs well in practice.

flowchart TD
    A[Collect all non-zero balances] --> B[Split into creditors +ve<br/>and debtors -ve]
    B --> C[Sort both by magnitude<br/>descending]
    C --> D{Any creditors<br/>and debtors left?}
    D -- yes --> E[Match largest debtor<br/>with largest creditor]
    E --> F[Settle min of the two amounts<br/>record transaction]
    F --> D
    D -- no --> G[Done — all balances zero]

def settle(self) -> list[tuple[str, str, float]]:
    creditors = [(p, b) for p, b in self.balances.items() if b > 0.01]
    debtors = [(p, -b) for p, b in self.balances.items() if b < -0.01]
    creditors.sort(key=lambda x: -x[1])
    debtors.sort(key=lambda x: -x[1])

    transactions: list[tuple[str, str, float]] = []
    i, j = 0, 0
    while i < len(creditors) and j < len(debtors):
        creditor_name, credit_amt = creditors[i]
        debtor_name, debt_amt = debtors[j]
        settled = min(credit_amt, debt_amt)
        transactions.append((debtor_name, creditor_name, round(settled, 2)))

        creditors[i] = (creditor_name, credit_amt - settled)
        debtors[j] = (debtor_name, debt_amt - settled)
        if creditors[i][1] < 0.01:
            i += 1
        if debtors[j][1] < 0.01:
            j += 1
    return transactions

Why this reduces transaction count: each iteration fully zeroes out at least one person (whichever of the matched pair had the smaller amount), so the number of transactions is bounded by (number of non-zero balances - 1), not the number of original individual expenses — this is the concrete mechanism behind "simplification."

7. Edge Cases

  • Floating-point drift: repeated +=/-= on floats accumulates small errors; the 0.01 threshold in settle() treats near-zero balances as settled rather than leaving spurious tiny debts. Production systems store money in integer cents/paise specifically to avoid this class of bug entirely — worth naming as the "real" fix versus the threshold band-aid.
  • A participant who is also the payer: EqualSplit still includes the payer in participants by default (they owe their own share back to themselves, net effect is correct) — but this should be an explicit design decision stated out loud, not an accident.
  • Exact/percentage splits that don't sum correctly: validated eagerly in the strategy (raise ValueError) rather than silently producing wrong balances.

8. Extensibility

  • New split type (e.g., "shares" — 2 shares for one person, 1 for another): implement a new SplitStrategy — zero changes to Splitwise.add_expense or settle().
  • Group-scoped balances (multiple friend groups, not one global balance sheet): key balances by (group_id, user_id) instead of user_id alone; settle() runs per-group.
  • Partial settlement (pay back only part of a debt): add a direct record_payment(from, to, amount) method that adjusts balances directly, independent of add_expense — the balance sheet doesn't care whether a balance changed because of a new expense or a settlement payment.

9. Interview Drills

  1. Why not just record every individual expense as its own transaction and let users track their own balance? — That's O(number of expenses) transactions users have to track, when the net obligations are usually much simpler — the whole value of Splitwise is collapsing many expenses into a small number of net settling transactions.
  2. Is the greedy settle() algorithm guaranteed to produce the mathematically minimum number of transactions? — No — minimum transaction count in general is a harder combinatorial problem; the greedy max-debtor/max-creditor pairing is a good practical heuristic that performs well and is simple to implement/explain, which is why it's the standard interview answer, but stating the "not provably optimal, but practically good" caveat unprompted is a strong signal.
  3. How would you handle currency conversion if group members use different currencies? — Store each expense with its original currency and amount, convert to a common ledger currency at a fixed/fetched exchange rate at record time for balance computation, but retain the original currency for display — this is a scope question worth asking the interviewer rather than assuming.

Cross-links

[[OOD Design Patterns]] · [[SOLID Principles]] · [[Parking Lot]]