4. Splitwise (Expense Sharing) Intermediate → Advanced

Jump to section:

A. Realistic Interview Prompt

"Design an expense-sharing application like Splitwise. Users can form groups, add shared expenses with different splitting methods, see who owes whom, and settle up."

B. Difficulty

Intermediate for the core model (users, groups, expenses, splits, balances). Becomes Advanced once debt simplification (minimizing the number of settling transactions) and concurrent balance updates enter the conversation — the former is a genuine graph algorithm, the latter tests real correctness invariants on shared financial state.

C. What This Problem Tests

Strategy pattern for split computation — a close cousin of the pricing/allocation strategies in Problems 1 and 3
Separating "data" (who owes what) from "algorithm" (how it was computed)
Modeling an invariant explicitly (sum of all balances must always equal zero) and defending it under concurrency
Graph thinking for debt simplification (recognizing an NP-hard optimal case vs. a practical greedy approximation)
Idempotency for a financial mutation (settling up)

D. Requirements

Functional

Create users and groups (a group is a set of users)
Add an expense: total amount, payer, participants, and a split method (equal / exact / percentage)
Compute and track balances (who owes whom, and how much)
Settle up — record a payment that reduces an existing balance
View balances, both pairwise and net per user

Non-Functional

Correctness invariant: the sum of all balances across all users must always equal zero
Concurrent expense additions/settlements must not corrupt balances
Extensibility to new split types without touching existing balance logic

E. Clarifying Questions

#	Question	Why It Matters	Design Decision Affected
1	Which split types are required — equal, exact amounts, percentage, shares?	Determines the Strategy interface's parameter shape	`SplitStrategy` implementations
2	Is a Group required, or can two users split an expense directly?	Determines whether Group is mandatory or an optional container	Whether `Expense.groupId` is nullable
3	Track pairwise balances (who owes whom directly) or only net-per-user?	Pairwise supports "show me what I owe Alice specifically"; net-only can't answer that	`BalanceSheet` data shape
4	Do we need debt simplification (minimum transactions to settle a group)?	This is a real graph algorithm, not just bookkeeping	Whether `DebtSimplifier` exists
5	Can an expense be edited/deleted after creation?	Affects whether balances are mutated in place or via compensating entries	Expense mutability model
6	Must the payer be one of the split participants?	Determines if "pay for someone else" is a first-class case	Whether payer is separate from participants
7	How should rounding be handled for non-evenly-divisible amounts?	Splits must sum exactly to the total — someone absorbs the remainder	`SplitStrategy` validation/rounding rule
8	Is settling up a special kind of Expense, or a separate entity?	Affects class symmetry and whether Payment inherits from Expense	`Payment` vs. `Expense` subclassing decision
9	Are balances scoped per-group, or one global balance between two users across all groups?	Changes the key shape of the balance ledger	`BalanceSheet` key design
10	Is concurrent expense-adding expected within the same group?	Drives whether balance updates need explicit locking	Concurrency section relevance

F. Assumptions

Confirmed: equal / exact / percentage splits; groups; balance tracking; settle-up.
Assumption: pairwise net balances are tracked (not just a single net-worth number per user), since "who owes whom" is the core value proposition.
Assumption: the payer is not required to be a split participant (supports "I'll treat you").
Assumption: rounding remainders are assigned to the payer by convention, and split amounts are validated to sum exactly to the total before an expense is accepted.
Assumption: debt simplification is a follow-up capability (V6), not baked into the base design.
Assumption: settle-up is modeled as a distinct Payment entity, not an Expense subclass (see M for why).

G. Actors

Actor	Responsibility
User	Creates expenses, joins groups, views balances, settles up
System	Computes splits, maintains the balance invariant, validates every mutation

H. Core Domain Entities

Class	Responsibility	Key Attributes	Key Methods	Does NOT Handle
`User`	Identity	id, name, email	—	Balance computation
`Group`	Membership container	id, members	—	Balance computation, expense storage logic
`Expense`	Immutable record of one shared cost event	amount, paidBy, splits, groupId?, timestamp	—	Computing its own splits (delegates to a strategy at creation time)
`Split`	Data: how much one participant owes for one expense	user, amount	—	Any computation — pure data
`SplitStrategy` (interface)	Computes the list of `Split`s from a total + participants + params	—	`compute(total, participants, params)`	Persisting or applying the result
`BalanceSheet`	Single source of truth for who-owes-whom	pairwise balance map	`adjust(a, b, amount)`, `getBalance(a,b)`	Deciding why a balance changed
`Payment`	Records a settle-up action	from, to, amount, timestamp	—	Split computation (none needed)
`ExpenseService` (facade)	Orchestrates expense/payment creation + atomic balance update	—	`addExpense()`, `settleUp()`	Split math itself, balance storage itself

I. Class Relationships

Aggregation: Group has Users, but users exist independently — deleting a group must never delete its members. This is aggregation, not composition, unlike Parking Lot's Floor/Spot relationship.
Composition: Expense owns its Splits — a split has no meaning outside the expense that produced it.
Dependency: ExpenseService → SplitStrategy (interface), resolved via a factory keyed by split type.
Why is Payment a sibling of Expense, not a subclass? A payment has no participants list, no split computation, and no strategy — forcing it to inherit from Expense just to reuse "affects the balance sheet" would drag along fields and methods that don't apply, an LSP smell. Both instead go through ExpenseService, which applies their effect to BalanceSheet through a narrow, shared path.

J. Class Diagram

View Mermaid source

classDiagram
  class Group {
    members
  }
  class User {
    id
    name
  }
  class Expense {
    amount
    paidBy
    timestamp
  }
  class Split {
    user
    amount
  }
  class SplitStrategy {
    <<interface>>
    +compute(total, participants, params)
  }
  class BalanceSheet {
    +adjust(a,b,amt)
    +getBalance(a,b)
  }
  class Payment {
    from
    to
    amount
  }
  class ExpenseService {
    +addExpense()
    +settleUp()
  }
  Group o-- User
  Expense *-- Split
  SplitStrategy <|.. EqualSplitStrategy
  SplitStrategy <|.. ExactSplitStrategy
  SplitStrategy <|.. PercentSplitStrategy
  ExpenseService --> SplitStrategy
  ExpenseService --> BalanceSheet
  ExpenseService --> Payment
  ExpenseService --> Expense

K. Responsibility Mapping

Class	Responsibility	Does NOT Handle
Expense	Immutable record of what happened	How the split was computed (delegates)
SplitStrategy	The math of dividing an amount	Storing the result, updating balances
BalanceSheet	The current truth of who-owes-whom	Why a number changed (that's Expense/Payment's job to record)
ExpenseService	Orchestration — ties strategy output to a balance update atomically	Split math, balance storage internals

L. SOLID Analysis

Principle	How It's Applied	Naive Violation
SRP	`BalanceSheet` only stores numbers; `SplitStrategy` only computes; `Expense` only records facts	An `Expense` class that also mutates a global balance array inside its own constructor
OCP	New split type = new `SplitStrategy`; zero changes elsewhere	`if (splitType == "PERCENT") ... else if (splitType == "EXACT") ...` inline in `ExpenseService`
LSP	Every `SplitStrategy` must produce splits summing exactly to the total — a stated contract every implementation must honor	A strategy that silently produces splits off by a rounding cent, breaking the sum-to-zero invariant downstream
ISP	One-method `SplitStrategy` interface	A fat interface also requiring `validate()`, `format()`, `notify()`
DIP	`ExpenseService` depends on `SplitStrategy`, resolved via a factory keyed by type	`ExpenseService` directly instantiating `new PercentSplitStrategy()` inline

M. Design Patterns

Pattern	Problem It Solves	Where It Appears	When NOT to Use
Strategy	Split computation genuinely varies by type	`SplitStrategy` hierarchy	N/A — clearly justified by the stated requirement
Factory	Resolve a split-type enum to the right strategy instance	`SplitStrategyFactory`	Skip if there's truly only one split type ever
Facade	Callers shouldn't juggle strategy selection + balance updates themselves	`ExpenseService`	Skip only for a trivial two-user, one-split-type toy version
Observer (optional)	Notify group members when a new expense/payment is added	An event hook fired after a successful `addExpense`	Skip unless notifications were requested

Explicitly avoided: making Payment a subclass of Expense for code reuse (see I) — a common naive shortcut that creates an LSP violation instead of saving real work.

N. What Is Likely to Change?

Behavior	Current Design	Anticipated Change	Protecting Abstraction
Split method	Equal/Exact/Percent	Shares-based, itemized-by-receipt-line	`SplitStrategy` interface
Debt settlement	Raw pairwise balances shown	Simplified minimum-transaction suggestions	`DebtSimplifier` as a separate, read-only computation over `BalanceSheet`
Balance storage	In-memory map	Database-backed ledger, event-sourced from Expense/Payment log	`BalanceSheet` as an interface the service depends on, not a concrete map
Currency	Single currency	Multi-currency with exchange rates	`Money` as a value object encapsulating amount+currency from day one

O. Design Evolution

V1: two users, one expense, equal split only, balance update inline.
V2: introduce Group with multiple members, still equal split.
V3: extract SplitStrategy; add Exact and Percentage splits.
V4: extract BalanceSheet as an explicit pairwise ledger instead of ad hoc updates scattered in the service.
V5: add Payment/settle-up, symmetric with Expense's effect on the ledger.
V6: concurrency-safe balance updates (per-pair locking with consistent ordering) + optional DebtSimplifier for minimum-transaction settlement suggestions.

What stays stable: ExpenseService.addExpense()/settleUp() signatures. The ledger's internal storage and the debt-simplification feature are additive, not disruptive.

P. API / Interface Design

interface SplitStrategy {
  List<Split> compute(Money total, List<User> participants, Map<String,Object> params);
}

class ExpenseService {
  Expense addExpense(Money total, User paidBy, List<User> participants,
                      SplitType type, Map<String,Object> params, Optional<Group> group);
  Payment settleUp(User from, User to, Money amount, String idempotencyKey);
  Money   getBalance(User a, User b);
  Map<User, Money> getNetBalances(Group group);
}

interface SplitStrategy {
  List<Split> compute(Money total, List<User> participants, Map<String, Object> params);
}

class ExpenseService {
  Expense addExpense(Money total, User paidBy, List<User> participants, SplitType type,
                      Map<String, Object> params, Optional<Group> group) { throw new UnsupportedOperationException(); }
  Payment settleUp(User from, User to, Money amount, String idempotencyKey) { throw new UnsupportedOperationException(); }
  Money getBalance(User a, User b) { throw new UnsupportedOperationException(); }
  Map<User, Money> getNetBalances(Group group) { throw new UnsupportedOperationException(); }
}

class SplitStrategy {
public:
  virtual std::vector<Split> compute(Money total, const std::vector<std::shared_ptr<User>>& participants,
                                      const std::map<std::string, std::any>& params) = 0;
};

class ExpenseService {
public:
  Expense addExpense(Money total, std::shared_ptr<User> paidBy, const std::vector<std::shared_ptr<User>>& participants,
                      SplitType type, const std::map<std::string, std::any>& params, std::optional<Group> group);
  Payment settleUp(std::shared_ptr<User> from, std::shared_ptr<User> to, Money amount, const std::string& idempotencyKey);
  Money getBalance(std::shared_ptr<User> a, std::shared_ptr<User> b);
  std::map<std::shared_ptr<User>, Money> getNetBalances(Group group);
};

class SplitStrategy {
  compute(total, participants, params) { throw new Error('not implemented'); }
}

class ExpenseService {
  addExpense(total, paidBy, participants, type, params, group) { throw new Error('not implemented'); }
  settleUp(from, to, amount, idempotencyKey) { throw new Error('not implemented'); }
  getBalance(a, b) { throw new Error('not implemented'); }
  getNetBalances(group) { throw new Error('not implemented'); }
}

interface SplitStrategy {
  compute(total: Money, participants: User[], params: Record<string, unknown>): Split[];
}

class ExpenseService {
  addExpense(total: Money, paidBy: User, participants: User[], type: SplitType,
             params: Record<string, unknown>, group: Group | null): Expense { throw new Error('not implemented'); }
  settleUp(from: User, to: User, amount: Money, idempotencyKey: string): Payment { throw new Error('not implemented'); }
  getBalance(a: User, b: User): Money { throw new Error('not implemented'); }
  getNetBalances(group: Group): Map<User, Money> { throw new Error('not implemented'); }
}

Ownership/validation notes: addExpense validates that computed splits sum exactly to total before persisting anything — rejecting the whole operation rather than silently drifting the sum-to-zero invariant. settleUp takes an idempotency key so a client retry after a timeout can't double-adjust the balance.

Q. Pseudocode — Critical Logic

addExpense(total, payer, participants, type, params):
  strategy = strategyFactory.get(type)
  splits = strategy.compute(total, participants, params)
  assert sum(s.amount for s in splits) == total   // reject if strategy is buggy
  expense = Expense.create(total, payer, splits)
  for split in splits:
    if split.user != payer:
      balanceSheet.adjust(split.user, payer, +split.amount)  // split.user owes payer
  return expense

settleUp(from, to, amount, idemKey):
  if paymentLog.seen(idemKey): return paymentLog.get(idemKey)   // idempotent replay
  balanceSheet.adjust(from, to, -amount)
  payment = Payment.create(from, to, amount)
  paymentLog.record(idemKey, payment)
  return payment

Expense addExpense(Money total, User payer, List<User> participants,
                    SplitType type, Map<String, Object> params) {
  SplitStrategy strategy = strategyFactory.get(type);
  List<Split> splits = strategy.compute(total, participants, params);
  if (!sum(splits, s -> s.amount).equals(total)) throw new IllegalStateException("AssertionError");   // reject if strategy is buggy
  Expense expense = Expense.create(total, payer, splits);
  for (Split split : splits) {
    if (!split.user.equals(payer)) {
      balanceSheet.adjust(split.user, payer, split.amount);   // split.user owes payer
    }
  }
  return expense;
}

Payment settleUp(User from, User to, Money amount, String idemKey) {
  if (paymentLog.seen(idemKey)) return paymentLog.get(idemKey);   // idempotent replay
  balanceSheet.adjust(from, to, amount.negate());
  Payment payment = Payment.create(from, to, amount);
  paymentLog.record(idemKey, payment);
  return payment;
}

Expense addExpense(Money total, User payer, std::vector<User> participants,
                    SplitType type, std::map<std::string, std::any> params) {
  auto strategy = strategyFactory.get(type);
  auto splits = strategy->compute(total, participants, params);
  assert(sum(splits, [](const Split& s) { return s.amount; }) == total);   // reject if strategy is buggy
  Expense expense = Expense::create(total, payer, splits);
  for (const auto& split : splits) {
    if (split.user != payer) {
      balanceSheet.adjust(split.user, payer, +split.amount);   // split.user owes payer
    }
  }
  return expense;
}

Payment settleUp(User from, User to, Money amount, const std::string& idemKey) {
  if (paymentLog.seen(idemKey)) return paymentLog.get(idemKey);   // idempotent replay
  balanceSheet.adjust(from, to, -amount);
  Payment payment = Payment::create(from, to, amount);
  paymentLog.record(idemKey, payment);
  return payment;
}

addExpense(total, payer, participants, type, params) {
  const strategy = strategyFactory.get(type);
  const splits = strategy.compute(total, participants, params);
  if (sum(splits.map(s => s.amount)) !== total) throw new Error('AssertionError');   // reject if strategy is buggy
  const expense = Expense.create(total, payer, splits);
  for (const split of splits) {
    if (split.user !== payer) {
      balanceSheet.adjust(split.user, payer, +split.amount);   // split.user owes payer
    }
  }
  return expense;
}

settleUp(from, to, amount, idemKey) {
  if (paymentLog.seen(idemKey)) return paymentLog.get(idemKey);   // idempotent replay
  balanceSheet.adjust(from, to, -amount);
  const payment = Payment.create(from, to, amount);
  paymentLog.record(idemKey, payment);
  return payment;
}

addExpense(total: Money, payer: User, participants: User[], type: SplitType, params: Record<string, unknown>): Expense {
  const strategy = strategyFactory.get(type);
  const splits = strategy.compute(total, participants, params);
  if (sum(splits.map(s => s.amount)) !== total) throw new Error('AssertionError');   // reject if strategy is buggy
  const expense = Expense.create(total, payer, splits);
  for (const split of splits) {
    if (split.user !== payer) {
      balanceSheet.adjust(split.user, payer, +split.amount);   // split.user owes payer
    }
  }
  return expense;
}

settleUp(from: User, to: User, amount: Money, idemKey: string): Payment {
  if (paymentLog.seen(idemKey)) return paymentLog.get(idemKey);   // idempotent replay
  balanceSheet.adjust(from, to, -amount);
  const payment = Payment.create(from, to, amount);
  paymentLog.record(idemKey, payment);
  return payment;
}

R. End-to-End Use Case

3 friends, dinner, $90, equal split, Alice pays
  │
  ▼
ExpenseService.addExpense($90, Alice, [Alice,Bob,Carol], EQUAL)
  │
  ▼
EqualSplitStrategy.compute → [Alice:$30, Bob:$30, Carol:$30]
  │
  ▼
BalanceSheet.adjust(Bob, Alice, +$30)   // Bob owes Alice $30
BalanceSheet.adjust(Carol, Alice, +$30) // Carol owes Alice $30
  ...later...
Bob settles up $30 with Alice
  │
  ▼
ExpenseService.settleUp(Bob, Alice, $30, idemKey)
  │
  ▼
BalanceSheet.adjust(Bob, Alice, -$30)   // Bob's balance with Alice → $0

S. Data Structures

Structure	Used For	Why	Alternative & Trade-off
`Map<User, Map<User, Money>>`	Pairwise balance lookup	O(1) access per pair	Replaying the full Expense/Payment log on every read — always correct, but O(n) per query
Two max-heaps (creditors, debtors) by absolute balance	Debt simplification (greedy)	Efficiently pair the largest creditor with the largest debtor repeatedly	True optimal minimum-transaction settlement is NP-hard in general — the heap approach is a practical approximation, not guaranteed-minimal

T. Complexity Analysis

Operation	Time	Space
`addExpense`	O(participants)	O(participants)
`getBalance(a,b)`	O(1) with a materialized ledger	—
Debt simplification (greedy heap)	O(n log n)	O(n)

U. Testing Strategy

Happy path: equal split across 3 users sums correctly; percentage split summing to exactly 100%.
Edge cases: non-evenly-divisible amount (rounding); payer not among participants; single-participant "expense" (degenerate case).
Invalid input: percentages that don't sum to 100%; exact amounts that don't sum to the total — both rejected before any balance mutation.
Invariant check: after any sequence of expenses/payments, sum of all balances across all users equals zero.
Concurrency tests: concurrent expenses touching overlapping user pairs — no lost updates, invariant still holds afterward.

V. Interviewer Follow-Ups

Follow-Up	Testing	Design Change	Classes Changed	Pattern/Trade-off
"Add itemized splits by which items each person ordered."	OCP under a real new requirement	New `ItemizedSplitStrategy`	New strategy class only	Validates the Strategy investment
"Simplify a group's debts into the minimum number of payments."	Graph-thinking, recognizing NP-hardness	`DebtSimplifier` reading the ledger, greedy max-heap pairing	New read-only class	State clearly it's an approximation, not a guaranteed optimum
"Expenses need to be editable after creation."	Auditability vs. simplicity trade-off	Prefer a compensating reversal + new expense over in-place mutation	`ExpenseService`	In-place edit is simpler but destroys the audit trail of a financial system
"Two users add expenses to the same group at the same time."	Concurrency correctness	Lock all affected user-pairs in a consistent (e.g. sorted-by-ID) order per expense	`BalanceSheet`	Consistent lock ordering avoids deadlock between overlapping-participant expenses
"Support multiple currencies."	Domain model completeness	`Money` becomes a currency-aware value object; balances need a conversion policy or per-currency ledgers	`Money`, `BalanceSheet`	Real complexity jump — flag it as such rather than hand-waving
"A settle-up confirmation is lost and the client retries."	Idempotency for a financial mutation	`settleUp` keyed by an idempotency token; replay returns the original result, doesn't double-adjust	`ExpenseService.settleUp`	Non-negotiable for anything touching money
"Scale this to millions of users, like the real Splitwise."	LLD → HLD boundary	Ledger moves to a sharded database; the sum-to-zero invariant is enforced per-transaction, not globally locked	None in-process — infra change	Recognize the boundary rather than trying to "distribute" the classes themselves
"Percentages don't add up to 100%."	Input validation discipline	Reject at the strategy level before any `Expense` is created	`PercentSplitStrategy`	Fail fast, never let a bad split reach the ledger

W. Concurrency

Shared mutable state: each entry in BalanceSheet. The core invariant — total balances across all users sum to zero — must survive concurrent writes.

The multi-pair problem: a single expense with N participants touches N different balance-sheet entries at once. If two overlapping expenses lock those pairs in different orders, they can deadlock.
Mitigation: always acquire locks for the affected pairs in one consistent global order (e.g., sorted by user ID) — the standard fix for multi-resource locking, not unique to this problem.
Optimistic alternative: in a persisted design, use a version column (optimistic concurrency) on each balance row instead of pessimistic locks — retries on conflict rather than blocking, often preferable since expense creation is typically low-contention per specific pair.
Idempotency: settleUp in particular must be idempotent — a financial "did it happen twice?" bug is much worse than most other systems' retry bugs.

X. Persistence

Two valid designs, worth presenting both: (1) event-sourced — the append-only Expense/Payment log is the source of truth, and BalanceSheet is a rebuildable projection; (2) materialized-ledger — BalanceSheet rows are updated transactionally alongside each Expense/Payment write, inside the same database transaction. Materialized is faster to read; event-sourced is more auditable and self-healing if a bug ever corrupts a balance. Mentioning both, and picking one with a stated reason, reads much stronger than assuming only one exists.

Y. Scaling Boundary

Layer	What Belongs Here
LLD	User/Group/Expense/Split/BalanceSheet classes, in-process invariants, strategy pattern
HLD	A ledger service backed by a database, sharded by user or group, an API layer, caching for frequent balance reads
Distributed Systems	Maintaining the sum-to-zero invariant across a sharded/replicated store — usually solved with careful per-transaction boundaries rather than a distributed lock

Z. Failure Scenarios

Partial failure mid-expense: some balance adjustments applied, others not — must be all-or-nothing (a single transaction, or a compensating rollback).
Duplicate settle-up: must be idempotent via a client-supplied key.
Crash between "expense recorded" and "balance updated": prevented by keeping both in one transaction, or reconciled via an event-sourced rebuild.

AA. Common Bad Designs

God-object ExpenseService computing splits inline, mutating balances inline, formatting display strings inline — same trap as other problems, riskier here since it's financial data.
Payment extends Expense for code reuse — creates an LSP smell (Payment doesn't have splits or a strategy) purely to avoid writing a shared narrow interface.
No BalanceSheet at all, replaying full history on every balance query — correct but O(n) per read; acceptable for a toy version, a red flag if presented as final without discussing the materialized alternative.
Global lock around the entire ledger for every expense — correct but serializes unrelated users' expenses system-wide.

AB. Design Trade-Offs

Decision	Option A	Option B	Trade-off
Balance tracking	Pairwise ledger	Net-per-user only	Pairwise answers "who owes whom" precisely; net-only is simpler but loses that detail
Balance storage	Materialized ledger	Event-sourced (replay log)	Materialized is fast to read; event-sourced is more auditable/self-healing but slower to query
Debt simplification	Greedy max-heap pairing	Optimal min-cash-flow search	Greedy is fast and good-enough; optimal is NP-hard in general — rarely worth it in an interview
Expense edits	In-place mutation	Compensating reversal + new record	In-place is simpler; compensating preserves a clean audit trail — usually the right call for money

AC. Interviewer Evaluation

Weak candidate: hardcodes equal split only; mutates a raw balance array with no clear ledger abstraction.
Average candidate: has a Split hierarchy and a BalanceSheet, but doesn't mention the sum-to-zero invariant or concurrency.
Strong candidate: clean Strategy separation; explicitly states and tests the sum-to-zero invariant; raises idempotency for settle-up unprompted.
Exceptional candidate: all of the above, plus correctly frames debt simplification as an NP-hard optimal problem with a practical greedy approximation, and reasons about lock ordering across multi-participant expenses without being pushed.

AD. Interview Simulation

Interviewer: Design something like Splitwise.

Candidate: What split types need support — equal, exact, percentage — and do balances need to be tracked pairwise, or just net-per-user?

Interviewer: All three split types, and yes, pairwise — I want to know exactly what I owe each person.

Candidate: Then I'll separate the split data from the split algorithm — a SplitStrategy interface computes a list of Split objects from the total and participants, and an Expense just stores the result.

Interviewer: How do you guarantee the numbers stay consistent?

Candidate: I'd enforce, as an invariant, that the sum of all balances across every user always equals zero — and validate that every strategy's output sums exactly to the total before accepting the expense at all.

Interviewer: Now support settling up.

Candidate: I'd model that as a separate Payment entity, not a subclass of Expense — it has no splits or strategy, so inheriting would just carry along fields that don't apply.

Interviewer: A client retries a settle-up after a network timeout.

Candidate: settleUp needs to be idempotent — I'd have the client pass an idempotency key so a retried call returns the original result instead of adjusting the balance twice.

Interviewer: Last one — a group of 10 people has a tangled web of debts. Minimize the number of payments needed to settle everyone up.

Candidate: That's a graph min-cash-flow problem, and the truly optimal version is NP-hard. I'd use a practical greedy approach instead — repeatedly match the largest creditor with the largest debtor using two max-heaps — and I'd be upfront that it's a good approximation, not a guaranteed minimum.

AE. Online Solution Comparison

Source	Approach	Strength	Weakness	Worth Learning
ashishps1/awesome-low-level-design (GitHub)	User/Group/Expense/Split classes, Singleton `SplitwiseService`, concurrent collections	Clean baseline class list; explicit mention of `ConcurrentHashMap`/`CopyOnWriteArrayList`	Singleton service by default; no debt-simplification detail	The concurrent-collections instinct — validated and expanded on in W above
InterviewReady — Low-Level Design of Splitwise	Graph-based debt simplification via a greedy max-heap pairing of creditors/debtors	Honest about the greedy approach's limitation (can produce more transactions than optimal)	Less detail on the core Split/Strategy class design	The heap-based greedy algorithm and its explicit acknowledged limitation — both adopted directly in this document
AlgoMaster (cross-referenced)	Standard Strategy-pattern walkthrough for splits	Good baseline confirmation of the Strategy approach	Less depth on concurrency/idempotency	Useful as a sanity check against the synthesized design here

AF. Interview Cheat Sheet

Problem	Splitwise (Expense Sharing)
Difficulty	Intermediate → Advanced
Core requirements	Groups, expenses with pluggable splits, pairwise balances, settle-up
Key clarifications	Split types? Pairwise or net balances? Debt simplification needed? Rounding rule? Editable expenses?
Core entities	User, Group, Expense, Split, SplitStrategy, BalanceSheet, Payment, ExpenseService
Key relationships	Group aggregates Users; Expense composes Splits; Payment is a sibling of Expense, not a subclass
Key patterns	Strategy (splits), Factory (strategy resolution), Facade (ExpenseService)
Most important decision	Separating split data from split algorithm, and enforcing the sum-to-zero invariant explicitly
Likely-changing behavior	Split methods, debt-simplification approach, currency support
Concurrency concern	Multi-pair locking order per expense; idempotent settle-up
Top follow-ups	Debt simplification, editable expenses, multi-currency, idempotent settlement, real-world scale
Common mistakes	Payment-as-Expense-subclass; no explicit ledger; global lock; ignoring the sum-to-zero invariant
What NOT to over-engineer	Don't build optimal (NP-hard) debt simplification — greedy is the expected interview answer

AG. Full Implementation

A complete, compilable reference implementation of every class in the diagram above (composition, inheritance, interface realization, and dependency-injected strategies all preserved per section I), with a runnable demo exercising the primary flow — in Java, C++, JavaScript, and TypeScript.

// Splitwise (Expense Sharing) — full LLD implementation with demo.
// Single-file Java translation of the Mermaid class diagram in section J.
import java.util.*;

public class p4 {

    // ---------- Value objects ----------

    /** Fixed-point money (cents) to avoid floating point drift in splits/settlements. */
    static final class Money implements Comparable<Money> {
        final long cents;
        private Money(long cents) { this.cents = cents; }
        static Money ofCents(long cents) { return new Money(cents); }
        static Money of(double dollars) { return new Money(Math.round(dollars * 100)); }
        static Money zero() { return new Money(0); }
        Money plus(Money o) { return new Money(this.cents + o.cents); }
        Money minus(Money o) { return new Money(this.cents - o.cents); }
        Money negate() { return new Money(-this.cents); }
        boolean isZero() { return cents == 0; }
        public int compareTo(Money o) { return Long.compare(this.cents, o.cents); }
        public String toString() { return String.format("$%.2f", cents / 100.0); }
        public boolean equals(Object o) { return o instanceof Money && ((Money) o).cents == cents; }
        public int hashCode() { return Long.hashCode(cents); }
    }

    enum SplitType { EQUAL, EXACT, PERCENT }

    // ---------- Core entities ----------

    static final class User {
        final String id, name, email;
        User(String id, String name, String email) { this.id = id; this.name = name; this.email = email; }
        public String toString() { return name; }
    }

    /** Aggregation: Group holds Users but does not own their lifecycle. */
    static final class Group {
        final String id;
        final List<User> members = new ArrayList<>();
        Group(String id) { this.id = id; }
        void addMember(User u) { members.add(u); }
    }

    /** Pure data: how much one participant owes for one expense. No computation. */
    static final class Split {
        final User user;
        final Money amount;
        Split(User user, Money amount) { this.user = user; this.amount = amount; }
    }

    /** Immutable record of one shared-cost event. Composes its Splits. */
    static final class Expense {
        final String id;
        final Money amount;
        final User paidBy;
        final List<Split> splits; // composition — splits have no meaning outside this expense
        final String groupId; // nullable
        final long timestamp;
        Expense(String id, Money amount, User paidBy, List<Split> splits, String groupId) {
            this.id = id; this.amount = amount; this.paidBy = paidBy;
            this.splits = List.copyOf(splits); this.groupId = groupId;
            this.timestamp = System.currentTimeMillis();
        }
    }

    /** Records a settle-up action. Sibling of Expense, not a subclass (see section I). */
    static final class Payment {
        final String id;
        final User from, to;
        final Money amount;
        final long timestamp;
        Payment(String id, User from, User to, Money amount) {
            this.id = id; this.from = from; this.to = to; this.amount = amount;
            this.timestamp = System.currentTimeMillis();
        }
    }

    // ---------- SplitStrategy hierarchy ----------

    interface SplitStrategy {
        List<Split> compute(Money total, List<User> participants, Map<String, Object> params);
    }

    static final class EqualSplitStrategy implements SplitStrategy {
        public List<Split> compute(Money total, List<User> participants, Map<String, Object> params) {
            int n = participants.size();
            long base = total.cents / n;
            long remainder = total.cents % n; // distribute leftover cents deterministically
            List<Split> splits = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                long cents = base + (i < remainder ? 1 : 0);
                splits.add(new Split(participants.get(i), Money.ofCents(cents)));
            }
            return splits;
        }
    }

    @SuppressWarnings("unchecked")
    static final class ExactSplitStrategy implements SplitStrategy {
        public List<Split> compute(Money total, List<User> participants, Map<String, Object> params) {
            Map<String, Money> amounts = (Map<String, Money>) params.get("amounts"); // userId -> exact amount
            List<Split> splits = new ArrayList<>();
            for (User u : participants) {
                Money amt = amounts.get(u.id);
                if (amt == null) throw new IllegalArgumentException("Missing exact amount for " + u.id);
                splits.add(new Split(u, amt));
            }
            return splits;
        }
    }

    @SuppressWarnings("unchecked")
    static final class PercentSplitStrategy implements SplitStrategy {
        public List<Split> compute(Money total, List<User> participants, Map<String, Object> params) {
            Map<String, Double> pct = (Map<String, Double>) params.get("percentages"); // userId -> % (sums to 100)
            List<Split> splits = new ArrayList<>();
            long allocated = 0;
            for (int i = 0; i < participants.size(); i++) {
                User u = participants.get(i);
                Double p = pct.get(u.id);
                if (p == null) throw new IllegalArgumentException("Missing percentage for " + u.id);
                long cents = (i == participants.size() - 1)
                        ? total.cents - allocated // last participant absorbs rounding remainder
                        : Math.round(total.cents * (p / 100.0));
                allocated += cents;
                splits.add(new Split(u, Money.ofCents(cents)));
            }
            return splits;
        }
    }

    // ---------- BalanceSheet ----------

    /** Single source of truth for who-owes-whom. Stores one signed net cents value per unordered pair. */
    static final class BalanceSheet {
        // key: "idA|idB" with idA < idB lexicographically; value > 0 means idA owes idB.
        private final Map<String, Long> pairwise = new HashMap<>();

        private String key(User a, User b) {
            return a.id.compareTo(b.id) < 0 ? a.id + "|" + b.id : b.id + "|" + a.id;
        }

        /** a owes b `amount` more (amount may be negative to reduce/reverse). */
        void adjust(User a, User b, Money amount) {
            String k = key(a, b);
            long signed = a.id.compareTo(b.id) < 0 ? amount.cents : -amount.cents;
            pairwise.merge(k, signed, Long::sum);
        }

        /** Positive => a owes b; negative => b owes a. */
        Money getBalance(User a, User b) {
            String k = key(a, b);
            long stored = pairwise.getOrDefault(k, 0L);
            long fromAPerspective = a.id.compareTo(b.id) < 0 ? stored : -stored;
            return Money.ofCents(fromAPerspective);
        }
    }

    // ---------- Idempotent payment log ----------

    static final class PaymentLog {
        private final Map<String, Payment> byKey = new HashMap<>();
        boolean seen(String idemKey) { return byKey.containsKey(idemKey); }
        Payment get(String idemKey) { return byKey.get(idemKey); }
        void record(String idemKey, Payment p) { byKey.put(idemKey, p); }
    }

    // ---------- ExpenseService (facade) ----------

    static final class ExpenseService {
        private final Map<SplitType, SplitStrategy> strategyFactory;
        private final BalanceSheet balanceSheet = new BalanceSheet();
        private final PaymentLog paymentLog = new PaymentLog();
        private final List<Expense> expenses = new ArrayList<>();
        private int expenseCounter = 0, paymentCounter = 0;

        ExpenseService(Map<SplitType, SplitStrategy> strategyFactory) {
            this.strategyFactory = strategyFactory;
        }

        Expense addExpense(Money total, User paidBy, List<User> participants,
                            SplitType type, Map<String, Object> params, Group group) {
            SplitStrategy strategy = strategyFactory.get(type);
            List<Split> splits = strategy.compute(total, participants, params);

            long sum = 0;
            for (Split s : splits) sum += s.amount.cents;
            if (sum != total.cents) throw new IllegalStateException("Split strategy produced mismatched total");

            Expense expense = new Expense("EXP-" + (++expenseCounter), total, paidBy, splits,
                    group != null ? group.id : null);
            for (Split s : splits) {
                if (!s.user.id.equals(paidBy.id)) {
                    balanceSheet.adjust(s.user, paidBy, s.amount); // s.user owes paidBy s.amount
                }
            }
            expenses.add(expense);
            return expense;
        }

        Payment settleUp(User from, User to, Money amount, String idempotencyKey) {
            if (paymentLog.seen(idempotencyKey)) return paymentLog.get(idempotencyKey); // idempotent replay
            balanceSheet.adjust(from, to, amount.negate()); // paying down reduces what `from` owes `to`
            Payment payment = new Payment("PAY-" + (++paymentCounter), from, to, amount);
            paymentLog.record(idempotencyKey, payment);
            return payment;
        }

        Money getBalance(User a, User b) { return balanceSheet.getBalance(a, b); }

        /** net(u) = sum over others of (-balance(u, other)); positive => u is owed money overall. */
        Map<User, Money> getNetBalances(Group group) {
            Map<User, Money> net = new LinkedHashMap<>();
            for (User u : group.members) {
                long total = 0;
                for (User other : group.members) {
                    if (other == u) continue;
                    total -= balanceSheet.getBalance(u, other).cents;
                }
                net.put(u, Money.ofCents(total));
            }
            return net;
        }
    }

    // ---------- Demo ----------

    public static void main(String[] args) {
        User alice = new User("u1", "Alice", "alice@mail.com");
        User bob = new User("u2", "Bob", "bob@mail.com");
        User carol = new User("u3", "Carol", "carol@mail.com");

        Group trip = new Group("g1");
        trip.addMember(alice);
        trip.addMember(bob);
        trip.addMember(carol);

        Map<SplitType, SplitStrategy> factory = new HashMap<>();
        factory.put(SplitType.EQUAL, new EqualSplitStrategy());
        factory.put(SplitType.EXACT, new ExactSplitStrategy());
        factory.put(SplitType.PERCENT, new PercentSplitStrategy());
        ExpenseService service = new ExpenseService(factory);

        // Alice pays $100 for dinner, split equally among the three.
        service.addExpense(Money.of(100.00), alice, List.of(alice, bob, carol),
                SplitType.EQUAL, Map.of(), trip);

        // Bob pays $60 for a cab, split by exact amounts.
        Map<String, Object> exactParams = new HashMap<>();
        exactParams.put("amounts", Map.of("u1", Money.of(20.00), "u2", Money.of(20.00), "u3", Money.of(20.00)));
        service.addExpense(Money.of(60.00), bob, List.of(alice, bob, carol),
                SplitType.EXACT, exactParams, trip);

        System.out.println("Alice owes Bob: " + service.getBalance(alice, bob));
        System.out.println("Carol owes Alice: " + service.getBalance(carol, alice));

        // Carol settles part of her debt to Alice.
        service.settleUp(carol, alice, Money.of(20.00), "idem-1");
        System.out.println("After settle, Carol owes Alice: " + service.getBalance(carol, alice));

        System.out.println("Net balances:");
        service.getNetBalances(trip).forEach((u, m) -> System.out.println("  " + u + ": " + m));
    }
}

// Splitwise (Expense Sharing) — full LLD implementation with demo.
// Single-file C++ translation of the Mermaid class diagram in section J.
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <memory>
#include <variant>
#include <stdexcept>
#include <cmath>
#include <sstream>

// ---------- Money (fixed-point cents) ----------
struct Money {
    long long cents = 0;
    static Money ofCents(long long c) { return Money{c}; }
    static Money of(double dollars) { return Money{ (long long)std::llround(dollars * 100) }; }
    static Money zero() { return Money{0}; }
    Money plus(const Money& o) const { return Money{cents + o.cents}; }
    Money minus(const Money& o) const { return Money{cents - o.cents}; }
    Money negate() const { return Money{-cents}; }
    bool isZero() const { return cents == 0; }
    std::string str() const {
        std::ostringstream os;
        bool neg = cents < 0;
        long long c = neg ? -cents : cents;
        os << (neg ? "-$" : "$") << (c / 100) << "." << (c % 100 < 10 ? "0" : "") << (c % 100);
        return os.str();
    }
};

enum class SplitType { EQUAL, EXACT, PERCENT };

// ---------- Core entities ----------
struct User {
    std::string id, name, email;
};

// Aggregation: Group holds Users but does not own their lifecycle.
struct Group {
    std::string id;
    std::vector<std::shared_ptr<User>> members;
    void addMember(std::shared_ptr<User> u) { members.push_back(u); }
};

// Pure data: how much one participant owes for one expense.
struct Split {
    std::shared_ptr<User> user;
    Money amount;
};

// Params bag for strategies: keyed maps of userId -> value.
struct SplitParams {
    std::unordered_map<std::string, Money> exactAmounts;   // for ExactSplitStrategy
    std::unordered_map<std::string, double> percentages;   // for PercentSplitStrategy
};

// Immutable record of one shared-cost event. Composes its Splits.
struct Expense {
    std::string id;
    Money amount;
    std::shared_ptr<User> paidBy;
    std::vector<Split> splits; // composition
    std::string groupId;
    long long timestamp;
};

// Records a settle-up action. Sibling of Expense, not a subclass.
struct Payment {
    std::string id;
    std::shared_ptr<User> from, to;
    Money amount;
    long long timestamp;
};

// ---------- SplitStrategy hierarchy ----------
class SplitStrategy {
public:
    virtual ~SplitStrategy() = default;
    virtual std::vector<Split> compute(const Money& total, const std::vector<std::shared_ptr<User>>& participants,
                                        const SplitParams& params) = 0;
};

class EqualSplitStrategy : public SplitStrategy {
public:
    std::vector<Split> compute(const Money& total, const std::vector<std::shared_ptr<User>>& participants,
                                const SplitParams&) override {
        long long n = (long long)participants.size();
        long long base = total.cents / n;
        long long remainder = total.cents % n;
        std::vector<Split> splits;
        for (long long i = 0; i < n; i++) {
            long long cents = base + (i < remainder ? 1 : 0);
            splits.push_back({participants[i], Money::ofCents(cents)});
        }
        return splits;
    }
};

class ExactSplitStrategy : public SplitStrategy {
public:
    std::vector<Split> compute(const Money& total, const std::vector<std::shared_ptr<User>>& participants,
                                const SplitParams& params) override {
        std::vector<Split> splits;
        for (auto& u : participants) {
            auto it = params.exactAmounts.find(u->id);
            if (it == params.exactAmounts.end()) throw std::invalid_argument("Missing exact amount for " + u->id);
            splits.push_back({u, it->second});
        }
        return splits;
    }
};

class PercentSplitStrategy : public SplitStrategy {
public:
    std::vector<Split> compute(const Money& total, const std::vector<std::shared_ptr<User>>& participants,
                                const SplitParams& params) override {
        std::vector<Split> splits;
        long long allocated = 0;
        for (size_t i = 0; i < participants.size(); i++) {
            auto& u = participants[i];
            auto it = params.percentages.find(u->id);
            if (it == params.percentages.end()) throw std::invalid_argument("Missing percentage for " + u->id);
            long long cents = (i == participants.size() - 1)
                    ? total.cents - allocated
                    : (long long)std::llround(total.cents * (it->second / 100.0));
            allocated += cents;
            splits.push_back({u, Money::ofCents(cents)});
        }
        return splits;
    }
};

// ---------- BalanceSheet ----------
// Single source of truth for who-owes-whom: one signed net cents value per unordered pair.
class BalanceSheet {
    std::map<std::pair<std::string, std::string>, long long> pairwise;

    std::pair<std::string, std::string> key(const std::string& a, const std::string& b) const {
        return a < b ? std::make_pair(a, b) : std::make_pair(b, a);
    }
public:
    // a owes b `amount` more (amount may be negative to reduce/reverse).
    void adjust(const std::shared_ptr<User>& a, const std::shared_ptr<User>& b, const Money& amount) {
        auto k = key(a->id, b->id);
        long long signed_ = (a->id < b->id) ? amount.cents : -amount.cents;
        pairwise[k] += signed_;
    }

    // Positive => a owes b; negative => b owes a.
    Money getBalance(const std::shared_ptr<User>& a, const std::shared_ptr<User>& b) const {
        auto k = key(a->id, b->id);
        auto it = pairwise.find(k);
        long long stored = (it == pairwise.end()) ? 0 : it->second;
        long long fromAPerspective = (a->id < b->id) ? stored : -stored;
        return Money::ofCents(fromAPerspective);
    }
};

// ---------- Idempotent payment log ----------
class PaymentLog {
    std::unordered_map<std::string, Payment> byKey;
public:
    bool seen(const std::string& k) const { return byKey.count(k) > 0; }
    Payment get(const std::string& k) const { return byKey.at(k); }
    void record(const std::string& k, const Payment& p) { byKey[k] = p; }
};

// ---------- ExpenseService (facade) ----------
class ExpenseService {
    std::unordered_map<int, std::shared_ptr<SplitStrategy>> strategyFactory; // keyed by SplitType
    BalanceSheet balanceSheet;
    PaymentLog paymentLog;
    std::vector<Expense> expenses;
    int expenseCounter = 0, paymentCounter = 0;

public:
    ExpenseService(std::unordered_map<int, std::shared_ptr<SplitStrategy>> factory)
        : strategyFactory(std::move(factory)) {}

    Expense addExpense(const Money& total, std::shared_ptr<User> paidBy,
                        const std::vector<std::shared_ptr<User>>& participants,
                        SplitType type, const SplitParams& params, std::shared_ptr<Group> group) {
        auto strategy = strategyFactory[(int)type];
        std::vector<Split> splits = strategy->compute(total, participants, params);

        long long sum = 0;
        for (auto& s : splits) sum += s.amount.cents;
        if (sum != total.cents) throw std::logic_error("Split strategy produced mismatched total");

        Expense expense{"EXP-" + std::to_string(++expenseCounter), total, paidBy, splits,
                         group ? group->id : "", 0};
        for (auto& s : splits) {
            if (s.user->id != paidBy->id) {
                balanceSheet.adjust(s.user, paidBy, s.amount); // s.user owes paidBy s.amount
            }
        }
        expenses.push_back(expense);
        return expense;
    }

    Payment settleUp(std::shared_ptr<User> from, std::shared_ptr<User> to, const Money& amount,
                      const std::string& idempotencyKey) {
        if (paymentLog.seen(idempotencyKey)) return paymentLog.get(idempotencyKey); // idempotent replay
        balanceSheet.adjust(from, to, amount.negate()); // paying down reduces what `from` owes `to`
        Payment payment{"PAY-" + std::to_string(++paymentCounter), from, to, amount, 0};
        paymentLog.record(idempotencyKey, payment);
        return payment;
    }

    Money getBalance(const std::shared_ptr<User>& a, const std::shared_ptr<User>& b) {
        return balanceSheet.getBalance(a, b);
    }

    // net(u) = sum over others of (-balance(u, other)); positive => u is owed money overall.
    std::vector<std::pair<std::shared_ptr<User>, Money>> getNetBalances(const std::shared_ptr<Group>& group) {
        std::vector<std::pair<std::shared_ptr<User>, Money>> net;
        for (auto& u : group->members) {
            long long total = 0;
            for (auto& other : group->members) {
                if (other->id == u->id) continue;
                total -= balanceSheet.getBalance(u, other).cents;
            }
            net.push_back({u, Money::ofCents(total)});
        }
        return net;
    }
};

// ---------- Demo ----------
int main() {
    auto alice = std::make_shared<User>(User{"u1", "Alice", "alice@mail.com"});
    auto bob = std::make_shared<User>(User{"u2", "Bob", "bob@mail.com"});
    auto carol = std::make_shared<User>(User{"u3", "Carol", "carol@mail.com"});

    auto trip = std::make_shared<Group>();
    trip->id = "g1";
    trip->addMember(alice);
    trip->addMember(bob);
    trip->addMember(carol);

    std::unordered_map<int, std::shared_ptr<SplitStrategy>> factory;
    factory[(int)SplitType::EQUAL] = std::make_shared<EqualSplitStrategy>();
    factory[(int)SplitType::EXACT] = std::make_shared<ExactSplitStrategy>();
    factory[(int)SplitType::PERCENT] = std::make_shared<PercentSplitStrategy>();
    ExpenseService service(factory);

    // Alice pays $100 for dinner, split equally among the three.
    service.addExpense(Money::of(100.00), alice, {alice, bob, carol}, SplitType::EQUAL, SplitParams{}, trip);

    // Bob pays $60 for a cab, split by exact amounts.
    SplitParams exactParams;
    exactParams.exactAmounts = {{"u1", Money::of(20.00)}, {"u2", Money::of(20.00)}, {"u3", Money::of(20.00)}};
    service.addExpense(Money::of(60.00), bob, {alice, bob, carol}, SplitType::EXACT, exactParams, trip);

    std::cout << "Alice owes Bob: " << service.getBalance(alice, bob).str() << "\n";
    std::cout << "Carol owes Alice: " << service.getBalance(carol, alice).str() << "\n";

    service.settleUp(carol, alice, Money::of(20.00), "idem-1");
    std::cout << "After settle, Carol owes Alice: " << service.getBalance(carol, alice).str() << "\n";

    std::cout << "Net balances:\n";
    for (auto& [u, m] : service.getNetBalances(trip)) {
        std::cout << "  " << u->name << ": " << m.str() << "\n";
    }
    return 0;
}

// Splitwise (Expense Sharing) — full LLD implementation with demo.
// Single-file Node/JS translation of the Mermaid class diagram in section J.
'use strict';

// ---------- Money (fixed-point cents) ----------
class Money {
  constructor(cents) { this.cents = cents; }
  static ofCents(c) { return new Money(c); }
  static of(dollars) { return new Money(Math.round(dollars * 100)); }
  static zero() { return new Money(0); }
  plus(o) { return new Money(this.cents + o.cents); }
  minus(o) { return new Money(this.cents - o.cents); }
  negate() { return new Money(-this.cents); }
  isZero() { return this.cents === 0; }
  toString() {
    const neg = this.cents < 0;
    const c = Math.abs(this.cents);
    const cents = String(c % 100).padStart(2, '0');
    return `${neg ? '-' : ''}$${Math.floor(c / 100)}.${cents}`;
  }
}

const SplitType = Object.freeze({ EQUAL: 'EQUAL', EXACT: 'EXACT', PERCENT: 'PERCENT' });

// ---------- Core entities ----------
class User {
  constructor(id, name, email) { this.id = id; this.name = name; this.email = email; }
  toString() { return this.name; }
}

// Aggregation: Group holds Users but does not own their lifecycle.
class Group {
  constructor(id) { this.id = id; this.members = []; }
  addMember(u) { this.members.push(u); }
}

// Pure data: how much one participant owes for one expense. No computation.
class Split {
  constructor(user, amount) { this.user = user; this.amount = amount; }
}

// Immutable record of one shared-cost event. Composes its Splits.
class Expense {
  constructor(id, amount, paidBy, splits, groupId) {
    this.id = id; this.amount = amount; this.paidBy = paidBy;
    this.splits = [...splits]; this.groupId = groupId || null;
    this.timestamp = Date.now();
  }
}

// Records a settle-up action. Sibling of Expense, not a subclass (see section I).
class Payment {
  constructor(id, from, to, amount) {
    this.id = id; this.from = from; this.to = to; this.amount = amount;
    this.timestamp = Date.now();
  }
}

// ---------- SplitStrategy hierarchy ----------
class SplitStrategy {
  // eslint-disable-next-line no-unused-vars
  compute(total, participants, params) { throw new Error('not implemented'); }
}

class EqualSplitStrategy extends SplitStrategy {
  compute(total, participants) {
    const n = participants.length;
    const base = Math.trunc(total.cents / n);
    const remainder = total.cents % n; // distribute leftover cents deterministically
    return participants.map((u, i) => new Split(u, Money.ofCents(base + (i < remainder ? 1 : 0))));
  }
}

class ExactSplitStrategy extends SplitStrategy {
  compute(total, participants, params) {
    const amounts = params.amounts; // Map<userId, Money>
    return participants.map((u) => {
      const amt = amounts.get(u.id);
      if (!amt) throw new Error(`Missing exact amount for ${u.id}`);
      return new Split(u, amt);
    });
  }
}

class PercentSplitStrategy extends SplitStrategy {
  compute(total, participants, params) {
    const pct = params.percentages; // Map<userId, percent>
    let allocated = 0;
    return participants.map((u, i) => {
      const p = pct.get(u.id);
      if (p === undefined) throw new Error(`Missing percentage for ${u.id}`);
      const cents = (i === participants.length - 1)
        ? total.cents - allocated // last participant absorbs rounding remainder
        : Math.round(total.cents * (p / 100));
      allocated += cents;
      return new Split(u, Money.ofCents(cents));
    });
  }
}

// ---------- BalanceSheet ----------
// Single source of truth for who-owes-whom: one signed net cents value per unordered pair.
class BalanceSheet {
  constructor() { this.pairwise = new Map(); }

  _key(a, b) { return a.id < b.id ? `${a.id}|${b.id}` : `${b.id}|${a.id}`; }

  // a owes b `amount` more (amount may be negative to reduce/reverse).
  adjust(a, b, amount) {
    const k = this._key(a, b);
    const signed = a.id < b.id ? amount.cents : -amount.cents;
    this.pairwise.set(k, (this.pairwise.get(k) || 0) + signed);
  }

  // Positive => a owes b; negative => b owes a.
  getBalance(a, b) {
    const k = this._key(a, b);
    const stored = this.pairwise.get(k) || 0;
    const fromAPerspective = a.id < b.id ? stored : -stored;
    return Money.ofCents(fromAPerspective);
  }
}

// ---------- Idempotent payment log ----------
class PaymentLog {
  constructor() { this.byKey = new Map(); }
  seen(idemKey) { return this.byKey.has(idemKey); }
  get(idemKey) { return this.byKey.get(idemKey); }
  record(idemKey, p) { this.byKey.set(idemKey, p); }
}

// ---------- ExpenseService (facade) ----------
class ExpenseService {
  constructor(strategyFactory) {
    this.strategyFactory = strategyFactory; // Map<SplitType, SplitStrategy>
    this.balanceSheet = new BalanceSheet();
    this.paymentLog = new PaymentLog();
    this.expenses = [];
    this.expenseCounter = 0;
    this.paymentCounter = 0;
  }

  addExpense(total, paidBy, participants, type, params, group) {
    const strategy = this.strategyFactory.get(type);
    const splits = strategy.compute(total, participants, params || {});

    const sum = splits.reduce((acc, s) => acc + s.amount.cents, 0);
    if (sum !== total.cents) throw new Error('Split strategy produced mismatched total');

    const expense = new Expense(`EXP-${++this.expenseCounter}`, total, paidBy, splits, group ? group.id : null);
    for (const s of splits) {
      if (s.user.id !== paidBy.id) {
        this.balanceSheet.adjust(s.user, paidBy, s.amount); // s.user owes paidBy s.amount
      }
    }
    this.expenses.push(expense);
    return expense;
  }

  settleUp(from, to, amount, idempotencyKey) {
    if (this.paymentLog.seen(idempotencyKey)) return this.paymentLog.get(idempotencyKey); // idempotent replay
    this.balanceSheet.adjust(from, to, amount.negate()); // paying down reduces what `from` owes `to`
    const payment = new Payment(`PAY-${++this.paymentCounter}`, from, to, amount);
    this.paymentLog.record(idempotencyKey, payment);
    return payment;
  }

  getBalance(a, b) { return this.balanceSheet.getBalance(a, b); }

  // net(u) = sum over others of (-balance(u, other)); positive => u is owed money overall.
  getNetBalances(group) {
    const net = new Map();
    for (const u of group.members) {
      let total = 0;
      for (const other of group.members) {
        if (other === u) continue;
        total -= this.balanceSheet.getBalance(u, other).cents;
      }
      net.set(u, Money.ofCents(total));
    }
    return net;
  }
}

// ---------- Demo ----------
function main() {
  const alice = new User('u1', 'Alice', 'alice@mail.com');
  const bob = new User('u2', 'Bob', 'bob@mail.com');
  const carol = new User('u3', 'Carol', 'carol@mail.com');

  const trip = new Group('g1');
  trip.addMember(alice);
  trip.addMember(bob);
  trip.addMember(carol);

  const factory = new Map([
    [SplitType.EQUAL, new EqualSplitStrategy()],
    [SplitType.EXACT, new ExactSplitStrategy()],
    [SplitType.PERCENT, new PercentSplitStrategy()],
  ]);
  const service = new ExpenseService(factory);

  // Alice pays $100 for dinner, split equally among the three.
  service.addExpense(Money.of(100.0), alice, [alice, bob, carol], SplitType.EQUAL, {}, trip);

  // Bob pays $60 for a cab, split by exact amounts.
  const exactParams = { amounts: new Map([['u1', Money.of(20.0)], ['u2', Money.of(20.0)], ['u3', Money.of(20.0)]]) };
  service.addExpense(Money.of(60.0), bob, [alice, bob, carol], SplitType.EXACT, exactParams, trip);

  console.log('Alice owes Bob:', service.getBalance(alice, bob).toString());
  console.log('Carol owes Alice:', service.getBalance(carol, alice).toString());

  service.settleUp(carol, alice, Money.of(20.0), 'idem-1');
  console.log('After settle, Carol owes Alice:', service.getBalance(carol, alice).toString());

  console.log('Net balances:');
  for (const [u, m] of service.getNetBalances(trip)) {
    console.log(`  ${u}: ${m.toString()}`);
  }
}

if (require.main === module) {
  main();
}

module.exports = {
  Money, SplitType, User, Group, Split, Expense, Payment,
  SplitStrategy, EqualSplitStrategy, ExactSplitStrategy, PercentSplitStrategy,
  BalanceSheet, PaymentLog, ExpenseService,
};

// Splitwise (Expense Sharing) — full LLD implementation with demo.
// Single-file TypeScript translation of the Mermaid class diagram in section J.

// ---------- Money (fixed-point cents) ----------
class Money {
  private constructor(public readonly cents: number) {}
  static ofCents(c: number): Money { return new Money(c); }
  static of(dollars: number): Money { return new Money(Math.round(dollars * 100)); }
  static zero(): Money { return new Money(0); }
  plus(o: Money): Money { return new Money(this.cents + o.cents); }
  minus(o: Money): Money { return new Money(this.cents - o.cents); }
  negate(): Money { return new Money(-this.cents); }
  isZero(): boolean { return this.cents === 0; }
  toString(): string {
    const neg = this.cents < 0;
    const c = Math.abs(this.cents);
    const cents = String(c % 100).padStart(2, '0');
    return `${neg ? '-' : ''}$${Math.floor(c / 100)}.${cents}`;
  }
}

enum SplitType { EQUAL = 'EQUAL', EXACT = 'EXACT', PERCENT = 'PERCENT' }

// ---------- Core entities ----------
class User {
  constructor(public readonly id: string, public readonly name: string, public readonly email: string) {}
  toString(): string { return this.name; }
}

// Aggregation: Group holds Users but does not own their lifecycle.
class Group {
  readonly members: User[] = [];
  constructor(public readonly id: string) {}
  addMember(u: User): void { this.members.push(u); }
}

// Pure data: how much one participant owes for one expense. No computation.
class Split {
  constructor(public readonly user: User, public readonly amount: Money) {}
}

// Immutable record of one shared-cost event. Composes its Splits.
class Expense {
  readonly splits: readonly Split[];
  readonly timestamp: number = Date.now();
  constructor(
    public readonly id: string, public readonly amount: Money, public readonly paidBy: User,
    splits: Split[], public readonly groupId: string | null,
  ) { this.splits = [...splits]; }
}

// Records a settle-up action. Sibling of Expense, not a subclass (see section I).
class Payment {
  readonly timestamp: number = Date.now();
  constructor(
    public readonly id: string, public readonly from: User, public readonly to: User,
    public readonly amount: Money,
  ) {}
}

interface SplitParams {
  amounts?: Map<string, Money>;       // used by ExactSplitStrategy
  percentages?: Map<string, number>;  // used by PercentSplitStrategy
}

// ---------- SplitStrategy hierarchy ----------
interface SplitStrategy {
  compute(total: Money, participants: User[], params: SplitParams): Split[];
}

class EqualSplitStrategy implements SplitStrategy {
  compute(total: Money, participants: User[]): Split[] {
    const n = participants.length;
    const base = Math.trunc(total.cents / n);
    const remainder = total.cents % n; // distribute leftover cents deterministically
    return participants.map((u, i) => new Split(u, Money.ofCents(base + (i < remainder ? 1 : 0))));
  }
}

class ExactSplitStrategy implements SplitStrategy {
  compute(total: Money, participants: User[], params: SplitParams): Split[] {
    const amounts = params.amounts!;
    return participants.map((u) => {
      const amt = amounts.get(u.id);
      if (!amt) throw new Error(`Missing exact amount for ${u.id}`);
      return new Split(u, amt);
    });
  }
}

class PercentSplitStrategy implements SplitStrategy {
  compute(total: Money, participants: User[], params: SplitParams): Split[] {
    const pct = params.percentages!;
    let allocated = 0;
    return participants.map((u, i) => {
      const p = pct.get(u.id);
      if (p === undefined) throw new Error(`Missing percentage for ${u.id}`);
      const cents = (i === participants.length - 1)
        ? total.cents - allocated // last participant absorbs rounding remainder
        : Math.round(total.cents * (p / 100));
      allocated += cents;
      return new Split(u, Money.ofCents(cents));
    });
  }
}

// ---------- BalanceSheet ----------
// Single source of truth for who-owes-whom: one signed net cents value per unordered pair.
class BalanceSheet {
  private readonly pairwise = new Map<string, number>();

  private key(a: User, b: User): string { return a.id < b.id ? `${a.id}|${b.id}` : `${b.id}|${a.id}`; }

  // a owes b `amount` more (amount may be negative to reduce/reverse).
  adjust(a: User, b: User, amount: Money): void {
    const k = this.key(a, b);
    const signed = a.id < b.id ? amount.cents : -amount.cents;
    this.pairwise.set(k, (this.pairwise.get(k) ?? 0) + signed);
  }

  // Positive => a owes b; negative => b owes a.
  getBalance(a: User, b: User): Money {
    const k = this.key(a, b);
    const stored = this.pairwise.get(k) ?? 0;
    const fromAPerspective = a.id < b.id ? stored : -stored;
    return Money.ofCents(fromAPerspective);
  }
}

// ---------- Idempotent payment log ----------
class PaymentLog {
  private readonly byKey = new Map<string, Payment>();
  seen(idemKey: string): boolean { return this.byKey.has(idemKey); }
  get(idemKey: string): Payment | undefined { return this.byKey.get(idemKey); }
  record(idemKey: string, p: Payment): void { this.byKey.set(idemKey, p); }
}

// ---------- ExpenseService (facade) ----------
class ExpenseService {
  private readonly balanceSheet = new BalanceSheet();
  private readonly paymentLog = new PaymentLog();
  private readonly expenses: Expense[] = [];
  private expenseCounter = 0;
  private paymentCounter = 0;

  constructor(private readonly strategyFactory: Map<SplitType, SplitStrategy>) {}

  addExpense(
    total: Money, paidBy: User, participants: User[], type: SplitType,
    params: SplitParams, group: Group | null,
  ): Expense {
    const strategy = this.strategyFactory.get(type)!;
    const splits = strategy.compute(total, participants, params);

    const sum = splits.reduce((acc, s) => acc + s.amount.cents, 0);
    if (sum !== total.cents) throw new Error('Split strategy produced mismatched total');

    const expense = new Expense(`EXP-${++this.expenseCounter}`, total, paidBy, splits, group ? group.id : null);
    for (const s of splits) {
      if (s.user.id !== paidBy.id) {
        this.balanceSheet.adjust(s.user, paidBy, s.amount); // s.user owes paidBy s.amount
      }
    }
    this.expenses.push(expense);
    return expense;
  }

  settleUp(from: User, to: User, amount: Money, idempotencyKey: string): Payment {
    const existing = this.paymentLog.get(idempotencyKey);
    if (existing) return existing; // idempotent replay
    this.balanceSheet.adjust(from, to, amount.negate()); // paying down reduces what `from` owes `to`
    const payment = new Payment(`PAY-${++this.paymentCounter}`, from, to, amount);
    this.paymentLog.record(idempotencyKey, payment);
    return payment;
  }

  getBalance(a: User, b: User): Money { return this.balanceSheet.getBalance(a, b); }

  // net(u) = sum over others of (-balance(u, other)); positive => u is owed money overall.
  getNetBalances(group: Group): Map<User, Money> {
    const net = new Map<User, Money>();
    for (const u of group.members) {
      let total = 0;
      for (const other of group.members) {
        if (other === u) continue;
        total -= this.balanceSheet.getBalance(u, other).cents;
      }
      net.set(u, Money.ofCents(total));
    }
    return net;
  }
}

// ---------- Demo ----------
function main(): void {
  const alice = new User('u1', 'Alice', 'alice@mail.com');
  const bob = new User('u2', 'Bob', 'bob@mail.com');
  const carol = new User('u3', 'Carol', 'carol@mail.com');

  const trip = new Group('g1');
  trip.addMember(alice);
  trip.addMember(bob);
  trip.addMember(carol);

  const factory = new Map<SplitType, SplitStrategy>([
    [SplitType.EQUAL, new EqualSplitStrategy()],
    [SplitType.EXACT, new ExactSplitStrategy()],
    [SplitType.PERCENT, new PercentSplitStrategy()],
  ]);
  const service = new ExpenseService(factory);

  // Alice pays $100 for dinner, split equally among the three.
  service.addExpense(Money.of(100.0), alice, [alice, bob, carol], SplitType.EQUAL, {}, trip);

  // Bob pays $60 for a cab, split by exact amounts.
  const exactParams: SplitParams = {
    amounts: new Map([['u1', Money.of(20.0)], ['u2', Money.of(20.0)], ['u3', Money.of(20.0)]]),
  };
  service.addExpense(Money.of(60.0), bob, [alice, bob, carol], SplitType.EXACT, exactParams, trip);

  console.log('Alice owes Bob:', service.getBalance(alice, bob).toString());
  console.log('Carol owes Alice:', service.getBalance(carol, alice).toString());

  service.settleUp(carol, alice, Money.of(20.0), 'idem-1');
  console.log('After settle, Carol owes Alice:', service.getBalance(carol, alice).toString());

  console.log('Net balances:');
  for (const [u, m] of service.getNetBalances(trip)) {
    console.log(`  ${u.toString()}: ${m.toString()}`);
  }
}

main();

export {
  Money, SplitType, User, Group, Split, Expense, Payment, SplitParams,
  SplitStrategy, EqualSplitStrategy, ExactSplitStrategy, PercentSplitStrategy,
  BalanceSheet, PaymentLog, ExpenseService,
};

← 3. Rate Limiter 5. Ride-Sharing Service (Uber/Lyft) →