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 Pinterest.

What role is this question designed for?

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

Settle Group Expenses with Transfers | Pinterest Coding Question

Settle Group Expenses with Transfers

Company: Pinterest

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a list of group expense transactions from a trip. Each transaction contains: - `payer`: the person who paid the full amount. - `amount`: the total amount paid, represented as an integer number of cents. - `payees`: the people who shared this expense equally. The payer may also appear in this list, meaning they paid for their own share as well. For each transaction, the `amount` is split equally among all `payees`. Compute a list of direct transfers that settles all balances, so that every person's final net balance becomes zero. Return any valid list of transfers. Each transfer should specify: - `from`: the person who pays money. - `to`: the person who receives money. - `amount`: the amount transferred. The order of transfers does not matter. You may assume each transaction amount is evenly divisible by the number of payees. Example: ```python transactions = [ { "payer": "Alice", "amount": 4000, "payees": ["Bob", "Alice", "Charlie", "Daisy"] }, { "payer": "Charlie", "amount": 2000, "payees": ["Alice", "Charlie"] } ] ``` One valid output is: ```python [ {"from": "Bob", "to": "Alice", "amount": 1000}, {"from": "Daisy", "to": "Alice", "amount": 1000} ] ``` Explanation: - Alice should receive a net total of `2000`. - Bob owes `1000`. - Daisy owes `1000`. - Charlie is already settled.

Quick Answer: This question evaluates the ability to compute and reconcile per-person financial balances from transactional data and to translate net liabilities into direct transfers, exercising skills in numeric bookkeeping and data aggregation.

You are given a list of group expense transactions from a trip. Each transaction has a payer, an integer amount in cents, and a list of payees who shared that expense equally. The payer may or may not be included in the payees list. For each transaction, the payer initially paid the full amount, and each payee is responsible for an equal share of that amount. Compute direct money transfers that settle everyone so that each person's final net balance becomes zero. Return any valid settlement list. For deterministic testing, the reference solution processes people in lexicographic order.

Constraints

0 <= len(transactions) <= 100000
1 <= total number of payee entries across all transactions <= 200000, unless transactions is empty
Each transaction has at least one payee
Within a transaction, payees are unique
0 <= amount <= 1000000000000
For every transaction, amount is evenly divisible by len(payees)
Person names are non-empty strings

Examples

Input: ([{'payer': 'Alice', 'amount': 4000, 'payees': ['Bob', 'Alice', 'Charlie', 'Daisy']}, {'payer': 'Charlie', 'amount': 2000, 'payees': ['Alice', 'Charlie']}],)

Expected Output: [{'from': 'Bob', 'to': 'Alice', 'amount': 1000}, {'from': 'Daisy', 'to': 'Alice', 'amount': 1000}]

Explanation: Alice is owed 2000 total. Bob and Daisy each owe 1000. Charlie's balance is already zero.

Input: ([] ,)

Expected Output: []

Explanation: There are no transactions, so no transfers are needed.

Input: ([{'payer': 'Ava', 'amount': 750, 'payees': ['Ava']}],)

Expected Output: []

Explanation: Ava paid 750 and was the only payee, so Ava's paid amount exactly equals Ava's own share.

Input: ([{'payer': 'Mia', 'amount': 1200, 'payees': ['Ann', 'Ben', 'Cat']}],)

Expected Output: [{'from': 'Ann', 'to': 'Mia', 'amount': 400}, {'from': 'Ben', 'to': 'Mia', 'amount': 400}, {'from': 'Cat', 'to': 'Mia', 'amount': 400}]

Explanation: Mia paid for Ann, Ben, and Cat, but did not share the expense herself. Each payee owes Mia 400.

Input: ([{'payer': 'A', 'amount': 3000, 'payees': ['A', 'B', 'C']}, {'payer': 'D', 'amount': 1500, 'payees': ['B', 'C', 'D']}, {'payer': 'B', 'amount': 1000, 'payees': ['A', 'B']}],)

Expected Output: [{'from': 'B', 'to': 'A', 'amount': 1000}, {'from': 'C', 'to': 'A', 'amount': 500}, {'from': 'C', 'to': 'D', 'amount': 1000}]

Explanation: Final balances are A: +1500, D: +1000, B: -1000, C: -1500. The listed transfers settle all four balances.

Hints

Track each person's net balance: add the full amount to the payer, then subtract one equal share from every payee.
After computing balances, separate people who owe money from people who should receive money, then greedily match them.

Quick Overview

This question evaluates the ability to compute and reconcile per-person financial balances from transactional data and to translate net liabilities into direct transfers, exercising skills in numeric bookkeeping and data aggregation.