Atomic Ledger Batches
EasySimulation · Coinbase
You maintain a ledger of account balances. initial maps account names to their starting balances, and batches is a list of batches to process in order. Each batch is a list of [account, delta] updates.
A batch is atomic: compute the effect of all of its updates together. If every account the batch touches would end with a balance >= 0, apply the whole batch. Otherwise reject it entirely, leaving every balance exactly as it was.
Details:
- An account that does not exist yet has balance
0. It is created when a batch that mentions it is accepted (even if its final balance is0); an account mentioned only in rejected batches never exists. - The same account may appear several times in one batch. Only its balance after the whole batch is checked, not intermediate values.
- An empty batch is accepted and changes nothing.
Return the final ledger as a list of [account, balance] pairs sorted by account name (normal string order).
Example 1
- Input:
- initial = {"alice": 50, "bob": 10}, batches = [[["alice", -30], ["bob", 30]], [["bob", -50], ["carol", 50]], [["alice", -20], ["dave", 20]]]
- Output:
- [["alice", 0], ["bob", 40], ["dave", 20]]
- Explanation
- The first batch moves 30 from alice to bob (alice 20, bob 40). The second would leave bob at -10, so it is rejected in full and carol is never created. The third leaves alice at exactly 0, which is allowed, and creates dave.
Example 2
- Input:
- initial = {"x": 5}, batches = [[["x", -8], ["x", 4]]]
- Output:
- [["x", 1]]
- Explanation
- Only the net effect of a batch matters: x changes by -8 + 4 = -4 and ends at 1, so the batch is accepted even though applying -8 alone would have gone negative.
Example 3
- Input:
- initial = {"usd": 0}, batches = [[["btc", 0]], [["eth", -1]]]
- Output:
- [["btc", 0], ["usd", 0]]
- Explanation
- The first batch is accepted and creates
btcwith balance 0, which is still reported, as isusdat its starting 0. The second batch is rejected, soethnever exists.
Constraints
0 <= len(initial) <= 10^4, and every initial balance is between0and10^90 <= batches.length <= 10^5- The total number of updates across all batches is at most
2 * 10^5 -10^9 <= delta <= 10^9