Compute transfers to balance account debts
Company: Remitly
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
## Problem: Balance accounts by generating transfers
You are given a dictionary/map `balances` from `accountId -> netBalance`.
- A **positive** balance means the account should **receive** money (is owed money).
- A **negative** balance means the account should **pay** money (owes money).
- The sum of all balances is guaranteed to be **0**.
Produce a list of transfers that will settle all accounts to net 0.
### Output format
Return a list of transfers like:
- `(fromAccount, toAccount, amount)` where `amount > 0`
After applying all transfers:
- Every account’s balance becomes exactly `0`.
### Example
Input:
```text
{ A: -5, B: 2, C: 3 }
```
One valid output:
```text
[(A, B, 2), (A, C, 3)]
```
### Notes / constraints
- You may return **any** valid set of transfers.
- Prefer fewer transfers if possible, but correctness is the priority.
Quick Answer: This question evaluates a candidate's ability to convert per-account net balances into a set of transfers, testing algorithmic problem solving, data-structure manipulation, and correctness under conservation invariants in transactional systems.
You are given a map `balances` from `accountId -> netBalance`.
- A **positive** balance means the account should **receive** money (is owed money).
- A **negative** balance means the account should **pay** money (owes money).
- The sum of all balances is guaranteed to be **0**.
Produce a list of transfers `(fromAccount, toAccount, amount)` with `amount > 0` such that, after applying all transfers, every account's balance becomes exactly `0`.
**Example**
Input: `{A: -5, B: 2, C: 3}`
One valid output: `[(A, B, 2), (A, C, 3)]`
**Canonical (deterministic) output used by this console**
To make the answer reproducible, sort the debtors (accounts that owe money) and the creditors (accounts owed money) by `accountId`, then greedily match the smallest-id debtor against the smallest-id creditor, emitting a transfer of `min(owed, owedTo)` and advancing whichever side reaches `0`. Continue until all balances settle. This yields at most `n - 1` transfers for `n` non-zero accounts.
**Notes / constraints**
- Any valid set of transfers settles the accounts; this console grades against the canonical sorted-greedy output above.
- Accounts with a balance of `0` need no transfer.
- An empty map yields an empty transfer list.
Constraints
- The sum of all balances is exactly 0.
- Balances are integers; positive = owed money (receive), negative = owes money (pay).
- 0 <= number of accounts <= 10^5.
- Accounts with balance 0 are ignored and need no transfer.
- Return at most n - 1 transfers for n non-zero accounts.
Examples
Input: ({'A': -5, 'B': 2, 'C': 3},)
Expected Output: [('A', 'B', 2), ('A', 'C', 3)]
Explanation: A owes 5; it pays B (2) and C (3) in id order, settling everyone.
Input: ({},)
Expected Output: []
Explanation: No accounts means no transfers.
Hints
- Split accounts into debtors (negative balance) and creditors (positive balance); the absolute owed amount equals the magnitude of the balance.
- Sort both groups by accountId so the matching order is deterministic and reproducible.
- Use two pointers: transfer min(debtorOwed, creditorOwed) from the current debtor to the current creditor, subtract it from both, and advance whichever side hits 0.
- Stop when either group is exhausted; because the total sums to 0, both finish together.