Build a banking engine with pending transfers. A successful transfer from `src` to `dst` immediately debits `src` and creates a pending transfer with a unique integer ID starting from 1. The destination does not receive the money until `accept` is called with the correct destination account and transfer ID. A wrong acceptance attempt must fail but must not destroy the pending transfer. For convenience, this sub-problem also includes `create`, `deposit`, and `balance` operations.
Examples
Input: ([('create', 'A', 1), ('create', 'B', 1), ('deposit', 'A', 100, 2), ('transfer', 'A', 'B', 40, 3), ('balance', 'A', 4), ('accept', 'B', 1, 5), ('balance', 'B', 6)],)
Expected Output: [True, True, 100, 1, 60, True, 40]
Explanation: The transfer debits A immediately and credits B only on acceptance.
Input: ([('create', 'A', 1), ('create', 'B', 1), ('deposit', 'A', 20, 2), ('transfer', 'A', 'B', 30, 3), ('balance', 'A', 4), ('accept', 'B', 1, 5)],)
Expected Output: [True, True, 20, None, 20, False]
Explanation: The transfer fails because A does not have enough money.
Input: ([('create', 'A', 1), ('create', 'B', 1), ('create', 'C', 1), ('deposit', 'A', 50, 2), ('transfer', 'A', 'B', 20, 3), ('accept', 'C', 1, 4), ('balance', 'B', 5), ('accept', 'B', 1, 6), ('balance', 'B', 7)],)
Expected Output: [True, True, True, 50, 1, False, 0, True, 20]
Explanation: The wrong destination cannot accept the transfer, but the correct destination still can later.
Input: ([('create', 'A', 1), ('create', 'B', 1), ('deposit', 'A', 0, 2), ('transfer', 'A', 'B', 0, 3), ('accept', 'B', 1, 4), ('accept', 'B', 1, 5), ('balance', 'A', 6), ('balance', 'B', 6)],)
Expected Output: [True, True, 0, 1, True, False, 0, 0]
Explanation: A zero-amount transfer is allowed, but it can only be accepted once.
Solution
def solution(operations):
balances = {}
pending = {}
next_transfer_id = 1
result = []
for op in operations:
kind = op[0]
if kind == 'create':
_, acc_id, _ = op
if acc_id in balances:
result.append(False)
else:
balances[acc_id] = 0
result.append(True)
elif kind == 'deposit':
_, acc_id, amount, _ = op
if acc_id not in balances:
result.append(None)
else:
balances[acc_id] += amount
result.append(balances[acc_id])
elif kind == 'transfer':
_, src, dst, amount, _ = op
if src == dst or src not in balances or dst not in balances or balances[src] < amount:
result.append(None)
else:
balances[src] -= amount
pending[next_transfer_id] = (src, dst, amount)
result.append(next_transfer_id)
next_transfer_id += 1
elif kind == 'accept':
_, dst, transfer_id, _ = op
if transfer_id not in pending:
result.append(False)
else:
_, real_dst, amount = pending[transfer_id]
if dst != real_dst or real_dst not in balances:
result.append(False)
else:
balances[real_dst] += amount
del pending[transfer_id]
result.append(True)
elif kind == 'balance':
_, acc_id, _ = op
result.append(balances.get(acc_id))
else:
raise ValueError('Unknown operation type')
return resultTime complexity: O(n) average time. Space complexity: O(a + p), where a is the number of accounts and p is the number of pending transfers.