Expense Sharing (Splitwise)

medium · balances, greedy settlement

Brief-reported interview attribution (unverified): Flipkart, Amazon, Uber

How to approach an LLD round

Requirements

  • Functional: split an expense equally among participants (remainder cents to the first participants), track net balances, settle using the specified deterministic largest-balance greedy strategy (not guaranteed to use the fewest transfers).
  • Non-functional: money is integer cents (no floats); the settlement plan must be deterministic (ties by name); the settlement rule must be replaceable.
  • Out of scope: groups, currencies, recurring expenses, payments.

Statement

Design the core of Splitwise. Friends record expenses; each expense is split equally among its participants (the payer is a participant like anyone else). Balances are integer cents: positive means others owe this person. settle_up returns the deterministic greedy transactions that settle everyone, as (debtor, creditor, amount_cents) tuples sorted by (debtor, creditor).

class Splitwise:
    def __init__(self):
    def add_expense(self, payer, amount_cents, participants):
        # -> True if recorded, False if the participant list is empty or the amount is negative
    def balance(self, person):
        # -> net balance in cents (0 for an unknown person)
    def all_balances(self):
        # -> {person: balance} for everyone with a non-zero balance, sorted by person
    def settle_up(self):
        # -> [(debtor, creditor, amount_cents), ...] sorted by (debtor, creditor)

Rules. An equal split divides the amount into amount // n per participant; the amount % n leftover cents go one each to the first participants in the list order. The payer's balance increases by the full amount they paid; every participant's balance decreases by their share. Settlement is greedy: repeatedly match the largest debtor with the largest creditor (ties broken by name), settling the smaller of the two amounts. People with a zero balance never appear in settle_up.

The specified greedy settlement is not a guarantee of the globally fewest transactions.

Money units: all amounts and balances are integer cents.

Tests use explicit inputs and injected clocks/callbacks. No network, real threads or application-server execution is involved.

Class design (SOLID)

Expense (payer, amount, participants, and the share split; SRP). BalanceSheet (net balances; SRP). SettlementStrategy (ABC interface) + GreedySettlementStrategy (largest-debtor ↔ largest-creditor; OCP — a minimum-transfer solver swaps in). Splitwise orchestrates and takes the strategy as a constructor argument (DIP). Pattern: Strategy (settlement).

Public demo

# Public demo: run after implementing the class API above.
s = Splitwise()
s.add_expense('Alice', 1000, ['Alice', 'Bob'])
print(s.balance('Alice'))
print(s.balance('Bob'))
print(s.settle_up())

Reference solution and hidden tests

Locked. Open the interactive editor and attempt the problem; the reference, hidden test descriptions, pattern explanation and complexity are available only after an explicit reveal.

Concurrency

Expenses are independent records — the only shared state is the balance sheet, so guard add_expense with one lock on the sheet. The reference is single-threaded; the lock is described here.

Trade-offs & extensions

Greedy settlement is not always minimal (the true minimum is NP-hard), but it is simple, deterministic and close. Extending: unequal splits (a SplitStrategy), and a Payment record when a transfer is actually made.

Starter code

from abc import ABC, abstractmethod

class Expense:

    def __init__(self, payer, amount, participants):
        """Initialize the state described in the problem."""
        pass

    def shares(self):
        """Implement the return value and rules in the API contract."""
        pass

class BalanceSheet:

    def __init__(self):
        """Initialize the state described in the problem."""
        pass

    def apply(self, expense):
        """Implement the return value and rules in the API contract."""
        pass

    def balance(self, person):
        """-> net balance in cents (0 for an unknown person)"""
        pass

    def all_balances(self):
        """-> {person: balance} for everyone with a non-zero balance, sorted by person"""
        pass

class SettlementStrategy(ABC):

    @abstractmethod
    def settle(self, balances):
        """Implement the return value and rules in the API contract."""
        pass

class GreedySettlementStrategy(SettlementStrategy):

    def settle(self, balances):
        """Implement the return value and rules in the API contract."""
        pass

class Splitwise:

    def __init__(self, strategy=None):
        """Initialize the state described in the problem."""
        pass

    def add_expense(self, payer, amount_cents, participants):
        """-> True if recorded, False if the participant list is empty or the amount is negative"""
        pass

    def balance(self, person):
        """-> net balance in cents (0 for an unknown person)"""
        pass

    def all_balances(self):
        """-> {person: balance} for everyone with a non-zero balance, sorted by person"""
        pass

    def settle_up(self):
        """-> [(debtor, creditor, amount_cents), ...] sorted by (debtor, creditor)"""
        pass
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

4 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. InterviewerCharacter joke · No posting date

    Walk me through your thinking. No, not out loud. In code. In silence. While I watch.

  2. Me at 2amCharacter joke · No posting date

    My code works. I have no idea why. I am afraid to touch it. I am going to bed.

  3. Rubber DuckCharacter joke · No posting date

    Quack. (Translation: have you tried printing it?)

  4. RecruiterCharacter joke · No posting date

    We loved your energy. We went with the candidate whose code compiled.