Design a Tour-Expense Splitter That Minimizes Payments

A four-piece band wants an app to track shared costs on tour: gas, lodging, meals, gear rental. Whoever pays logs the expense and who it was split among; the app keeps a running net balance per member (positive means the group owes them, negative means they owe the group) and can propose payments that clear every balance.

The first half of this exercise is requirements and design: functional and non-functional requirements, the public API, and the core entities (members, expenses, splits, balances). The second half is implementing two settlement methods on top of that design:

• settle(balances) -> list[(payer, payee, amount)]: produce some set of payments that zeroes out every balance.
• settle_optimally(balances) -> list[(payer, payee, amount)]: produce a set of payments that zeroes out every balance using the fewest possible transactions.

Four members: Mia, Theo, Priya, Sam
  Mia pays $60 for gas, split evenly among all four      -> Theo, Priya, Sam each owe Mia $15
  Theo pays $45 for a motel room, split among Theo, Priya, Sam (Mia didn't stay) -> Priya, Sam each owe Theo $15
  Priya pays $30 for strings, split between Priya and Sam only -> Sam owes Priya $15

Net balances once everything above is tallied up: Mia is owed $45, Theo is owed $15, Priya owes $15, and Sam owes $45.
Settling each debtor/creditor pair independently works but needs 3 separate payments; a smarter pairing can clear the whole group in just 2.

Clarifying Questions

• What split types does an expense need to support beyond equal shares — exact dollar amounts, percentages, shares weighted by some factor?
• Should the whole app assume a single currency, and when a split can't divide a charge into whole cents, which member's share quietly takes the extra penny?
• If the same two people are in several different tours or groups together, should their running balances combine into one number, or stay separate per group?
• Can settle() get away with doing nothing clever — just turning each existing net debt into its own payment — or does even the baseline method need to try to combine some payments?
• Beyond the raw transaction count, what should a caller actually get back: amounts, names, some ordering guarantee?
• Think about mutation: calling either settlement function to preview a plan shouldn't be indistinguishable from actually executing a transfer — how does the design keep those two notions separate?

Part 1 — Requirements and design

List the functional and non-functional requirements, sketch the public API, and name the core entities and their relationships.

What this part should cover

• Scope: members, groups, expenses with configurable split types, and the balance ledger derived from them.
• Non-functional needs once the app starts telling people to actually transfer money: no expense ever silently lost or double-counted, no two concurrent updates corrupting a balance, deterministic rounding.
• A clean separation between 'what the ledger currently owes' (derived, read-mostly) and 'what was actually paid' (an append-only log of real transfers).

Part 2 — Implement settle() and settle_optimally()

Implement both functions given a dict of member -> net balance in cents (positive = owed, negative = owes, and the values always sum to zero).

What this part should cover

• settle: a straightforward greedy pairing of debtors and creditors that is clearly correct but not necessarily minimal.
• settle_optimally: a search or graph-based approach that actually minimizes the transaction count, with a clear argument for why it's correct and a sense of how its cost scales with group size.