← Pinterest Interview Insights

Pinterest·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026

Summary

Pinterest SWE interview that threw a group expense settlement problem at me, the kind that looks like a simple graph question until you realize there's actual algorithmic depth hiding underneath it.

Questions Asked (1)

Q1

Given a list of payments where each entry records who paid, how much, and on whose behalf (one or more people), compute the minimum number of transfers needed to settle all debts in the group and output the list of transfers as debtor, creditor, and amount.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

My first instinct was to just compute net balances and greedily match the biggest debtor to the biggest creditor using a max-heap.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, compute each person's net balance by summing all payments made and received. Then, use a greedy algorithm to match the largest debtor with the largest creditor, settling as much as possible in each transfer, until all balances are zero. This minimizes the number of transfers.

Pro tip: Mention that while the greedy approach is optimal for minimizing the number of transfers, it may not be unique; also, consider edge cases like multiple people per payment and floating-point precision.

1. Parse and Aggregate

Iterate through the list of payments, and for each payment, subtract the amount from the payer's balance and add an equal share to each beneficiary's balance. This yields each person's net balance.

2. Separate Debtors and Creditors

Create two lists: one for people with negative balances (debtors) and one for people with positive balances (creditors). Ignore those with zero balance.

3. Greedy Matching

While both lists are non-empty, take the largest debtor and largest creditor, and transfer the minimum of their absolute balances. Update their balances and remove any that become zero.

4. Output Transfers

Record each transfer as a tuple (debtor, creditor, amount) and return the list of transfers.

Key Points to Mention

  • Net balance calculation: sum of payments made minus sum of payments received (or vice versa).
  • Greedy algorithm: always match the largest debtor with the largest creditor to minimize the number of transactions.
  • Optimality: the greedy approach yields the minimum number of transfers for this problem.
  • Handling multiple beneficiaries: split the payment amount equally among them.
  • Edge cases: zero balances, floating-point precision, and the possibility of multiple optimal solutions.
  • Time complexity: O(n log n) due to sorting, where n is the number of people.

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