Deadlock-Free Bank Transfer

medium · global ordering

Process transfers atomically in the given order using a deterministic model. balances maps account names to nonnegative integer balances. Each transfer is [source, destination, amount], with both accounts present and integer amount. A transfer succeeds iff amount > 0, source differs from destination, and source has enough money. Return {'balances': final balances, 'accepted': booleans per transfer, 'lock_orders': sorted distinct [source,destination] for EVERY attempt, including rejected attempts}. Acquire both account locks in lexicographic order and release after each attempt; output the lock plan rather than using real locks. No negative balances or money creation is allowed. Examples (JSON; null means Python None): Input: {"balances": {"a": 10, "b": 0}, "transfers": [["a", "b", 4], ["b", "a", 1]]} Output: {"balances": {"a": 7, "b": 3}, "accepted": [true, true], "lock_orders": [["a", "b"], ["a", "b"]]} Input: {"balances": {"a": 2, "b": 1}, "transfers": [["a", "b", 3]]} Output: {"balances": {"a": 2, "b": 1}, "accepted": [false], "lock_orders": [["a", "b"]]}

Starter code

def bank_transfer(balances: dict[str, int], transfers: list[list]) -> dict:
    """Apply atomic transfers and report their common lock ordering."""
    pass
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

3 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. TryGetValueCharacter joke · No posting date

    I solved this in O(1). Then I remembered I actually have to write the code. O(n) regrets.

  2. The GraderCharacter joke · No posting date

    Your solution is correct. Your variable names are a crime scene.

  3. TryGetValueCharacter joke · No posting date

    I found the bug. It was me. I was the bug.