How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Compute minimal transfers to settle group expenses

Quick Overview

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.

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.

Input: ([{'payer': 'a', 'amount': 1000, 'payees': ['b']}],)

Expected Output: [{'payer': 'b', 'amount': 1000, 'payees': ['a']}]

Explanation: a paid 1000 entirely for b, so b owes a 1000. A single transfer b -> a settles it.

Input: ([{'payer': 'a', 'amount': 1000, 'payees': ['a']}],)

Expected Output: []

Explanation: a paid 1000 for only themselves, so a's net balance is 0. No one owes anyone; no transfers.

Input: ([{'payer': 'a', 'amount': 3000, 'payees': ['a', 'b', 'c']}, {'payer': 'b', 'amount': 3000, 'payees': ['a', 'b', 'c']}],)

Expected Output: [{'payer': 'c', 'amount': 1000, 'payees': ['a']}, {'payer': 'c', 'amount': 1000, 'payees': ['b']}]

Explanation: Each expense splits 3000 into 1000 shares. a: +3000 -1000 -1000 = +1000. b: -1000 +3000 -1000 = +1000. c: -1000 -1000 = -2000. c owes 2000 total; greedy pays c -> a 1000 then c -> b 1000 (two transfers, the minimum).

Input: ([{'payer': 'x', 'amount': 6000, 'payees': ['x', 'y', 'z']}],)

Expected Output: [{'payer': 'y', 'amount': 2000, 'payees': ['x']}, {'payer': 'z', 'amount': 2000, 'payees': ['x']}]

Explanation: x paid 6000 split 3 ways (2000 each). x net = 6000 - 2000 = +4000; y and z each owe 2000. y -> x 2000, z -> x 2000.

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.

Quick Overview