Settle Shared-Expense Debts, Then Reduce the Number of Payments

A group of people share expenses and record what they owe one another as a list of debts. Write code that tells them how to settle up: a list of payments after which nobody owes anybody anything. First produce any valid settlement, then change your approach so that it uses fewer payments. For example, if A owes B 10 and B owes C 10, a single payment, A paying C 10, settles everyone. ### Constraints and Clarifications - Assume the input is `debts`, a list of `(debtor, creditor, amount)` tuples meaning that `debtor` owes `creditor` the positive amount `amount`. The same two people may appear in several debts, in either direction. - Assume amounts are whole numbers in the smallest currency unit (for example, cents), and people are identified by ids of one comparable type, such as strings. - Return a list of `(payer, payee, amount)` payments, each with a positive amount. Assume any person may pay any other person, including someone they had no recorded debt with. - Not given: the number of people or debts, and whether Part 2 must always reach the smallest possible number of payments. ### Clarifying Questions - Is the input a list of pairwise debts, or a list of expenses (who paid, how much, and who shared it) that must first be turned into debts? - Are amounts integers or floating-point values, and how should rounding be handled? - May someone pay a person they had no recorded debt with? - Does the order of the returned payments matter? ### Part 1 — Settle every balance Return a list of payments that settles everyone. There is no limit on the number of payments: any list after which nobody owes anybody anything is correct. ```hint Collapse the history For each person, what single number tells you whether they should end up paying or receiving, and how much? ``` ```hint Pair the two sides Once you know who must pay and who must receive, can you walk through both groups once so that every payment fully settles at least one of its two people? ``` #### What This Part Should Cover - Turning the debt list into one balance per person, and why those balances sum to zero - Matching the people who owe with the people who are owed, and how many payments that produces - Running time, and checking the output by applying the payments to the balances - Edge cases: an empty list, debts that cancel out, and people whose balance is already zero ### Part 2 — Use fewer payments The group now wants to settle up with as few payments as possible. Change your approach to reduce the number of payments, and say whether your method always reaches the smallest possible number. ```hint Largest first Keep each side in a heap so that you can always reach the largest remaining balance. Which pair should the next payment settle, and what happens to whatever is left over? ``` ```hint Count against a lower bound If some people's balances sum to zero among themselves, they can settle without involving anyone else. How many payments does such a group of k people need at least, and what does that imply for the whole group? ``` #### Clarifying Questions for this Part - Must the result be the smallest possible number of payments for every input, or is a method that reliably uses fewer payments than Part 1 enough? - If the exact minimum is required, how many people with a nonzero balance can a group have? #### What This Part Should Cover - The heap-based matching from the largest balances down, including what goes back into the heaps after each payment - Running time, and the largest number of payments the method can produce - Whether the method always reaches the smallest possible number of payments, with a justification - What computing the exact minimum would cost, and when that cost is worth paying ### What a Strong Answer Covers - Clarifies the input format, integer amounts, and whether Part 2 needs the exact minimum before writing code - Works from net balances rather than the original debts in both parts - Working code for both parts, with a check that applying the payments brings every balance to zero - Correct heap mechanics: largest-first ordering, ties between equal balances, and re-inserting partial remainders - An honest comparison of the two parts: running time, bounds on the number of payments, and what neither guarantees ### Follow-up Questions - If the group needs the provably smallest number of payments, how would you compute it, and how large a group can that handle? - Expenses keep arriving, and anyone may ask "who should pay whom?" at any moment. What state do you keep between requests? - Payments are allowed only between people who already share a recorded debt, in either direction. How do Parts 1 and 2 change? - Expenses are split evenly, such as 10.00 among three people. How do you keep every balance exact so that the totals still cancel?