Pinterest·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Pinterest coding round for a software engineer role. One problem, fairly focused on greedy balance settling. Not the hardest problem I've seen but the 'to' field being a list tripped me up at first.

Questions Asked (1)

Given a list of transactions where each transaction has a sender, one or more receivers (amount split equally), and a total amount, return any list of paybacks that brings every user's net balance to zero. You don't need to minimize the number of paybacks.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The multi-receiver part is what got me initially.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, compute each user's net balance by summing credits and debits from all transactions, then separate users into debtors and creditors. Use a greedy two-pointer strategy to match the largest debtor with the largest creditor, settling the smaller amount and repeating until all balances are zero. This approach is simple, correct, and runs in O(n log n) time due to sorting.

Pro tip: Mention that while the problem doesn't require minimizing paybacks, you can note that the greedy approach often produces a near-optimal number of transactions, and discuss the trade-off between simplicity and optimality. Also, clarify that the order of paybacks doesn't matter as long as net balances are zero.

1. Compute Net Balances

Iterate through all transactions, and for each, subtract the total amount from the sender and add an equal share to each receiver. Accumulate these into a map of user to net balance.

2. Separate Debtors and Creditors

Create two lists: one for users with negative net balance (debtors) and one for users with positive net balance (creditors). Ignore users with zero balance.

3. Sort and Match

Sort both lists by absolute balance (or use a max-heap). Repeatedly take the largest debtor and largest creditor, and settle the smaller of the two amounts, updating their balances and recording a payback.

4. Repeat Until Settled

Continue the matching process until all balances are zero. Return the list of paybacks (from debtor to creditor with the settled amount).

Key Points to Mention

Net balance calculation: sender is debited total amount, each receiver is credited equal share.
Data structures: use hash map for balances, lists or heaps for debtors/creditors.
Greedy matching: always settle the largest debtor with the largest creditor to reduce number of transactions.
Time complexity: O(n log n) due to sorting, where n is number of users involved.
Edge cases: zero balances, single user, transactions with multiple receivers, floating point precision if amounts are not integers.
Trade-off: greedy is not always optimal for minimizing transactions, but problem doesn't require minimization; can mention alternative approaches like backtracking for optimal but exponential.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.