Expense Sharing (Splitwise)
medium · balances, greedy settlement
Brief-reported interview attribution (unverified): Flipkart, Amazon, Uber
How to approach an LLD roundRequirements
- 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
Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.
Return to the Python interpreter