Top Up Accounts Below a Threshold from Surplus Accounts and Log Each Transfer

You are given a dictionary that maps account IDs to their current balances, and a threshold amount. Some accounts hold less than the threshold. Rebalance the accounts by transferring money between them so that every account that is below the threshold ends up with at least the threshold, and record every transfer you make as a transaction. Write a function that takes the balances and the threshold and returns the list of transactions, where each transaction records the source account, the destination account and the amount moved. You may also return the resulting balances. For example (illustrative values), with a threshold of 100 and balances `{"A": 20, "B": 180, "C": 90, "D": 110}`, accounts `A` and `C` are below the threshold, and a valid result moves money out of `B` and `D` into them until all four accounts hold at least 100. ```hint Classify before you move anything Before making any transfer, work out how far each account is above or below the threshold, and whether the totals make the goal reachable at all. ``` ```hint Size each transfer deliberately Choose each transfer's amount so that no transfer is wasted, and work out how many transfers your method can produce in the worst case. ``` ### Constraints and Clarifications - Account IDs are unique strings; balances and the threshold are amounts in the same currency. - Money moves only between the given accounts; none is created or destroyed. ### Clarifying Questions - May an account that gives money drop below the threshold itself, or must donors stay at or above it? - What should happen if the total amount above the threshold is not enough to cover every shortfall: raise an error, do nothing, or rebalance partially? - Is any valid set of transfers acceptable, or should the number of transactions be minimized? - Should accounts that were below the threshold end exactly at the threshold, or may they receive more? - Are balances whole units (such as cents) or fractional amounts? - Should the input dictionary be modified in place or left unchanged? ### What a Strong Answer Covers - A feasibility check before any balance changes - Donors never pushed below the threshold (or an explicitly agreed alternative policy), and every shortfall fully covered - A transaction log whose replay against the original balances reproduces the final balances exactly - Exact money handling with no floating-point drift - Time and space complexity, and an upper bound on the number of transactions - Tests for already-balanced input, infeasible input, exact fits, and shortfalls that must be split across donors ### Follow-up Questions - Can your approach guarantee the fewest possible transactions? If not, why is that hard, and what heuristic would you use? - Each transfer now costs a fixed fee paid by the sender. How do the plan and the feasibility check change? - The accounts hold different currencies with given exchange rates. What changes in the model and in the log? - Other payments update these balances while you are rebalancing. How do you make the rebalance safe to run and safe to retry?