Design a Splitwise-Style Expense Splitter with Minimum-Transaction Debt Settlement

Design a shared-expense app in the style of Splitwise. Members of a group record expenses that one person paid on behalf of several people, the app keeps track of who owes whom, and a smart settlement feature tells the group which payments clear every debt. The first half of the round is low-level and high-level design: functional and non-functional requirements, the API, and the core entities. In the second half you write code, without AI assistance, for two settlement methods: - `settle()`: compute the transactions that settle everyone's accounts, and how many there are. - `settle_optimally()`: settle every account using the minimum possible number of transactions. ```text Group: A, B, C, D A paid 40 for dinner, split equally among A, B, C, D -> B, C and D each owe A 10 B paid 30 for a taxi, split equally among B, C, D -> C and D each owe B 10 C paid 20 for coffee, split equally between A and C -> A owes C 10 Net position (positive = is owed money): A +20, B +10, C -10, D -20 Paying off each pairwise debt after netting takes 4 payments; the fewest possible is 2. ``` ### Clarifying Questions - Which split types must an expense support: equal shares, exact amounts, percentages? - Is everything in one currency, and who absorbs the leftover cent when an amount does not divide evenly? - Is settlement computed per group, or across every group two people share? - Does `settle()` have to simplify debts at all, or is it enough to pay off each pair's net debt, leaving minimization to `settle_optimally()`? - Should the settlement methods return only the count, or also the list of payments (payer, payee, amount)? - Is a settlement plan only a suggestion, with balances changing only when a payment is recorded? - How many members can one group have? This decides whether an exact minimization is affordable. ### Part 1 — Requirements List the functional and non-functional requirements of the app, including the settlement feature, and say what is out of scope. ```hint Real money moves Ask which guarantees matter once the app tells people to transfer real money: what must never be lost, applied twice, or rounded away. ``` #### What This Part Should Cover - Functional scope: groups and members, expenses with split types, balances, settlement suggestions, recording payments, history - Non-functional needs that follow from handling money: exact arithmetic, consistent balances, idempotent writes, auditability - Explicit out-of-scope items and the assumptions behind them ### Part 2 — API design and core entities Define the API (endpoints or service methods with request and response shapes) and the core entities with their fields and relationships. Sketch the high-level components and say where balances and settlement plans are computed. ```hint Facts versus derived numbers Decide which records are the source of truth and which numbers can be recomputed from them, and what has to happen to a balance when an expense is edited or deleted. ``` #### What This Part Should Cover - Entities for users, groups, expenses, per-participant shares and payments, with keys and relationships - API operations for creating and editing expenses, reading balances, requesting a settlement plan and recording a payment - How balances stay correct under edits, deletions and concurrent writes - A component view: services, storage, and where settlement runs ### Part 3 — Implement settle() Implement `settle()` for a group: from the recorded expenses and payments, return a list of payments (payer, payee, amount) after which everyone is even, together with its length. It does not have to be minimal; state how many payments your approach needs in the worst case. ```hint Look past the individual debts Ask whether the payments have to follow the original debts one by one, or only have to leave every person with the right total. ``` #### What This Part Should Cover - A correct reduction of the expense history to what each person must pay or receive - An algorithm that always produces a valid plan, with its payment-count bound and running time - Integer money handling and the invariant that the group's positions sum to zero ### Part 4 — Implement settle_optimally() Implement `settle_optimally()`: return a settlement plan with the minimum possible number of payments, and that number. Argue why no plan can use fewer payments, and state how the cost of your method grows with the number of members. ```hint Where the simple plan wastes a payment Build a small group in which your `settle()` uses more payments than necessary, and look at what the better plan does differently. ``` #### What This Part Should Cover - A characterization of the minimum that comes with a proof, or a search that is clearly exhaustive - An exact algorithm, its complexity, and the group size it can handle - Reductions or pruning, and what to do for groups too large for the exact method - Tests that check validity and compare the two methods on small cases ### What a Strong Answer Covers - Settles split types, rounding, currency and the scope of a settlement before designing - Requirements that reflect money semantics: integer amounts, balances that always sum to zero, idempotent and auditable writes - An entity model and API in which balances derive from expenses and payments - A correct `settle()` with a stated bound and an exact `settle_optimally()` with an honest complexity analysis - Working code with tests, written without AI help, including groups that are already even, a single debtor, and rounding remainders ### Follow-up Questions - `settle_optimally()` is too slow for a group with dozens of members. What do you do? - An expense is edited after the group has seen a settlement plan. What changes, and what must not change? - Users only want to pay people they already owe. How does the problem change? - Members spend in different currencies. How do balances and settlement work?