After a climbing club's night out, the treasurer settles everyone's share with one batch of transfers. Either the whole batch goes through, or none of it does: a half-applied batch would leave the books in a mess.
Build Ledger with:
-
open(account_id, initial) -> bool: create an account holdinginitial(an int). ReturnFalse(changing nothing) if the id is taken orinitialis negative. -
balance(account_id) -> int | None: the balance, orNonefor an unknown account. -
settle(transfers) -> int:transfersis a list of(source, target, amount)tuples, applied in order. Each transfer must be valid at the moment it is applied, taking the earlier transfers of the same batch into account:- both accounts exist and
source != target, amountis a positive int,sourceholds at leastamount(after the earlier transfers in the batch).
If every transfer is valid, apply them all and return
-1. Otherwise return the index of the first invalid transfer and leave every balance exactly as it was before the call. An empty batch returns-1. - both accounts exist and
L = Ledger()
L.open("ann", 50); L.open("bo", 0); L.open("cy", 10)
L.settle([("ann", "bo", 30), ("bo", "cy", 30)]) # -1: bo received 30 first, so it can pay 30
L.balance("bo"), L.balance("cy") # (0, 40)
L.settle([("cy", "ann", 40), ("cy", "bo", 1)]) # 1: cy is empty after the first transfer
L.balance("cy"), L.balance("ann") # (40, 20): nothing changed
The club has a lot of members (think 100,000 accounts) and a batch usually touches only a few of them, so the cost of settle should depend on the batch size, not on the number of accounts: don't copy every balance for each batch.
Show hint
keep a small dict of pending balances for just the accounts this batch touches (read the real balance the first time you see an account). Check each transfer against the pending values; only when all of them pass, copy the pending values into the real balances.