Implement a thread-safe money transfer

Problem: Implement a concurrent-safe transfer function

You are given an in-memory store of bank accounts:

• Each account has an accountId and a balance (integer cents).
• Multiple threads may call transfer(fromId, toId, amount) concurrently.

Task

Implement transfer(fromId, toId, amount) such that it is:

• Correct under concurrency (no lost updates).
• Atomic: either the money moves from fromId to toId entirely, or nothing changes.
• Deadlock-free under concurrent transfers between overlapping accounts.

Rules

• Validate inputs:
  • amount > 0
  • accounts must exist
  • reject/return failure on insufficient funds
• The total sum of money across all accounts must remain unchanged after any successful transfer.

Assumptions

• Single process / single JVM (no distributed transactions).
• You may use locks (e.g., synchronized/ReentrantLock/ReadWriteLock) or other concurrency primitives.

Deliverable

Provide the API design and implementation approach, including how you prevent deadlocks and ensure correctness.

Thread-Safe Money Transfer (Sequential Correctness Model)

Problem

You maintain an in-memory store of bank accounts. Each account has an accountId and an integer balance (in cents). In production, many threads call transfer(fromId, toId, amount) concurrently, and your real implementation must be correct under concurrency (no lost updates), atomic (the money fully moves or nothing changes), and deadlock-free (e.g. by always acquiring the two account locks in a consistent global order — lock the smaller id first, then the larger).

This console grades the deterministic correctness core that your locking strategy must protect: applying a sequence of transfer requests in order and enforcing every validation rule. Implement a function that takes the initial accounts and a list of transfer operations, applies each one, and reports the final balances and a per-operation success flag.

Input

• accounts: a list of [accountId, balance] pairs. accountId is a string; balance is a non-negative integer (cents).
• operations: a list of [fromId, toId, amount] transfer requests, applied in the given order.

A transfer succeeds only if ALL of these hold

1. amount > 0 (reject zero and negative amounts).
2. Both fromId and toId exist in the store.
3. fromId has sufficient funds (balance[fromId] >= amount).

On success, money moves atomically: balance[fromId] -= amount, balance[toId] += amount. On failure, nothing changes and the operation is recorded as failed. A self-transfer (fromId == toId) with a valid amount and sufficient funds is a no-op that still counts as a success (the net balance is unchanged). The total sum of money across all accounts is invariant across any successful transfer.

Output

Return [finalAccounts, results] where:

• finalAccounts is the list of [accountId, balance] pairs in the same order as the input accounts.
• results is a list of booleans, one per operation, in order: true if that transfer succeeded, false otherwise.

Concurrency design (what the real, multi-threaded version must add)

• Guard each account's balance with its own lock (or use one lock per account / a striped lock map).
• To avoid deadlock when two threads transfer between the same overlapping accounts in opposite directions, always acquire locks in a fixed global order (e.g. by accountId), never in call order.
• Read-validate-write must happen while both locks are held so the operation is atomic and free of lost updates.

Constraints

• accountId values are unique strings.
• Initial balances are non-negative integers (cents).
• amount may be any integer; only amount > 0 is a valid transfer.
• Operations are applied strictly in the order given.
• A transfer referencing a missing account fails and changes nothing.
• The total sum of all balances is invariant across any successful transfer.

Examples

Example 1

Input: ([['A', 100], ['B', 50]], [['A', 'B', 30]])
Output: [[['A', 70], ['B', 80]], [True]]

Explanation: A valid transfer of 30 from A to B: A drops to 70, B rises to 80, total 150 unchanged.

Example 2

Input: ([['A', 100], ['B', 50]], [['A', 'B', 200]])
Output: [[['A', 100], ['B', 50]], [False]]

Explanation: Insufficient funds (A has only 100), so the transfer fails and nothing changes.

Hints

1. Build a dictionary from accountId to balance, but keep the original account order separately so you can emit final balances in input order.
2. Validate in three guards before mutating: amount > 0, both ids present, and source has enough funds. Any failure appends false and leaves all balances untouched.
3. For the real concurrent implementation, the key insight is deadlock avoidance: never lock accounts in call order. Sort the two account ids and always lock the smaller one first, then the larger, so two opposing transfers can't each hold one lock and wait on the other.