Problem: Concurrent Money Transfer System

You are tasked with designing and implementing a transfer function for an in-memory bank account system. This system manages a collection of bank accounts, each identified by an accountId and holding a balance (represented in integer cents).

The transfer(fromId, toId, amount) function will be invoked concurrently by multiple threads.

Task Requirements

Your implementation of transfer(fromId, toId, amount) must satisfy the following critical properties:

• Concurrency Correctness: Ensure no lost updates occur when multiple transfers happen simultaneously.
• Atomicity: Each transfer must be an all-or-nothing operation. Either the full amount is successfully moved from the source account (fromId) to the destination account (toId), or the state of both accounts remains entirely unchanged.
• Deadlock-Freedom: The system must prevent deadlocks, especially when concurrent transfers involve overlapping sets of accounts.

Operational Rules

The transfer function must adhere to these rules:

• The amount to be transferred must be strictly greater than zero.
• Both the fromId and toId accounts must exist within the system.
• Transfers must be rejected if the fromId account has insufficient funds.
• The global invariant of the total sum of money across all accounts must remain constant after any successful transfer.

Assumptions

• The system operates within a single process / single JVM environment. Distributed transactions are explicitly out of scope.
• You are permitted to use standard concurrency primitives such as synchronized blocks, ReentrantLock, ReadWriteLock, or other appropriate mechanisms.

Deliverable

Your solution should include:

• The API design for the transfer function.
• A detailed implementation approach, specifically explaining how you ensure correctness under concurrency and prevent deadlocks.