Compute minimal transfers to settle group expenses
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
A group of friends go on a trip and share expenses. Each expense is recorded as an object:
- `payer` (string): who paid the full amount
- `amount` (integer): total amount paid (assume in cents to avoid floating point)
- `payees` (string[]): the friends who should share this expense **equally**
Each payee owes an equal share of that expense. The payer may also appear in `payees` (meaning they also consume/share the expense).
### Task
Given an array of such expenses, compute a set of **money transfers between friends** that settles all debts:
- After applying your transfers, every person’s net balance becomes 0 (no one owes/is owed).
- The transfers should be **minimal** in the sense of using the **fewest number of payments/transactions** possible.
- If multiple minimal answers exist, returning any one is acceptable.
### Output format
Return an array of transfer objects:
- `payer`: the person who sends money (the debtor)
- `amount`: the amount sent (integer, in cents)
- `payees`: an array containing exactly **one** person who receives the money (the creditor)
Example transfer: `{ payer: "bob", amount: 1000, payees: ["alice"] }` meaning “bob pays alice 1000 cents”.
### Example
**Input**
```js
[
{ payer: 'alice', amount: 4000, payees: ['bob', 'jess', 'alice', 'sam'] },
{ payer: 'jess', amount: 2000, payees: ['jess', 'alice'] }
]
```
**Output (one valid minimal answer)**
```js
[
{ payer: 'bob', amount: 1000, payees: ['alice'] },
{ payer: 'sam', amount: 1000, payees: ['alice'] }
]
```
### Notes / Constraints
- `amount` is divisible by `payees.length` (so equal splitting is exact).
- Names are case-sensitive strings.
- You may assume the input size is large enough that an efficient solution is expected.
Quick Answer: This question evaluates the ability to compute per-person net balances and optimize peer-to-peer payments to minimize the total number of transactions, exercising algorithmic reasoning, numeric bookkeeping under equal-split constraints, and efficiency for larger inputs.
A group of friends share trip expenses. Each expense is an object with `payer` (string, who paid the full amount), `amount` (integer in cents), and `payees` (list of strings who share the expense equally). The payer may appear in `payees` (they also consume a share). `amount` is always divisible by `len(payees)`, so each payee's share is an exact integer.
Write a function `minTransfers(expenses)` that returns a list of money transfers that settles all debts so every person's net balance becomes 0. Each transfer is an object `{ payer, amount, payees }` where `payer` is the debtor sending money, `amount` is the integer cents sent, and `payees` is a list containing exactly one creditor receiving the money.
The transfers should be minimal (use as few transactions as practical). To make the output deterministic and gradable, settle balances greedily: after computing each person's net balance, sort the debtors and the creditors lexicographically by name, then repeatedly match the current debtor against the current creditor, transferring `min(remaining_debt, remaining_credit)`, advancing whichever side hits zero.
Example:
Input: `[{payer:'alice', amount:4000, payees:['bob','jess','alice','sam']}, {payer:'jess', amount:2000, payees:['jess','alice']}]`
Output: `[{payer:'bob', amount:1000, payees:['alice']}, {payer:'sam', amount:1000, payees:['alice']}]`
Constraints
- amount is divisible by len(payees), so each share is an exact integer (cents).
- Names are case-sensitive strings.
- The payer may also appear in payees (they consume a share too).
- Each output transfer's payees list contains exactly one creditor.
- Net balances always sum to 0, so a full settlement always exists.
Examples
Input: ([{'payer': 'alice', 'amount': 4000, 'payees': ['bob', 'jess', 'alice', 'sam']}, {'payer': 'jess', 'amount': 2000, 'payees': ['jess', 'alice']}],)
Expected Output: [{'payer': 'bob', 'amount': 1000, 'payees': ['alice']}, {'payer': 'sam', 'amount': 1000, 'payees': ['alice']}]
Explanation: alice paid 4000 split 4 ways (1000 each): alice net = 4000 - 1000 = +3000 before the second expense. jess paid 2000 split 2 ways (1000 each): jess net = -1000 (exp1) + 2000 - 1000 (exp2 own share) = 0; alice loses another 1000 -> +2000. bob and sam each owe 1000. Greedy by sorted name: bob -> alice 1000, sam -> alice 1000.
Input: ([],)
Expected Output: []
Explanation: No expenses means no balances and no transfers.
Hints
- First reduce every expense to a single net balance per person (in cents): a payer gains the full amount, and every payee loses amount / len(payees).
- People with a positive balance are creditors (owed money); people with a negative balance are debtors (owe money). People with zero balance need no transfer.
- Sort debtors and creditors lexicographically by name to make the result deterministic, then greedily transfer min(remaining_debt, remaining_credit) between the current debtor and creditor, advancing whichever side reaches zero.