Idempotent Balance Transfers
MediumHash Map · Stripe
Process balance transfers with idempotency keys, the way a payments API protects against clients retrying a request.
initial maps account ids to starting balances. Each operation is [key, sender, receiver, amount], processed in order:
- New key: if the sender's balance is at least
amount, moveamountfrom sender to receiver and the result is"applied". Otherwise nothing moves and the result is"insufficient_funds". Either way, the key now remembers its parameters(sender, receiver, amount)and its result. - Seen key, identical parameters: a retry. Nothing moves, and the result is the key's original result (even if the balance has changed since).
- Seen key, different parameters: nothing moves, the result is
"key_conflict", and the key keeps its original parameters and result.
An account missing from initial has balance 0; a receiver that gets money is added to the balances.
Return [results, balances], where results has one string per operation in order and balances is a list of [account, balance] for every account in initial plus every account that received money, sorted by account id.
Example 1
- Input:
- initial = {"alice": 50, "bob": 10}, operations = [["k1", "alice", "bob", 30], ["k1", "alice", "bob", 30], ["k2", "bob", "carol", 100], ["k1", "alice", "bob", 5], ["k2", "bob", "carol", 100]]
- Output:
- [["applied", "applied", "insufficient_funds", "key_conflict", "insufficient_funds"], [["alice", 20], ["bob", 40]]]
- Explanation
k1moves 30 from alice to bob. Its exact retry isappliedagain with no second move.k2fails because bob only has 40. Reusingk1with amount 5 is akey_conflict, and retryingk2replaysinsufficient_funds. carol never received money, so she is not listed.
Example 2
- Input:
- initial = {"a": 5}, operations = [["x", "a", "b", 10], ["y", "c", "a", 1], ["z", "b", "a", 1], ["w", "b", "a", 1]]
- Output:
- [["insufficient_funds", "insufficient_funds", "insufficient_funds", "insufficient_funds"], [["a", 5]]]
- Explanation
xfails since a has only 5.yfails because c has no balance.zandwfail too: b never received anything. No money moves, so only a appears in the balances.
Example 3
- Input:
- initial = {"a": 0, "b": 20}, operations = [["p", "a", "c", 15], ["q", "b", "a", 20], ["p", "a", "c", 15], ["r", "a", "c", 15]]
- Output:
- [["insufficient_funds", "applied", "insufficient_funds", "applied"], [["a", 5], ["b", 0], ["c", 15]]]
- Explanation
pfails at first. Afterqgives a 20, retryingpstill replaysinsufficient_fundsbecause results are remembered per key. A new keyrwith the same transfer succeeds, so a ends at 5 and c at 15.
Constraints
0 <= operations.length <= 10^50 <= initial[account] <= 10^91 <= amount <= 10^9, andsender != receiver- Keys and account ids are non-empty strings