← Pinterest Interview InsightsSoftware Engineer

Pinterest·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Pinterest coding round for a software engineer role. One problem, algorithmic, not too flashy on the surface but the edge cases sneak up on you if you're not careful about how you model balances.

Questions Asked (1)

Q1

Given a list of transactions where each transaction has a sender, one or more recipients, and a total amount split among recipients, return any valid list of paybacks such that every user ends up with a net balance of zero.

Algorithms & Data Structures
Author's notes

The 'any valid solution' part is what saves you here, no need to minimize transactions.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, compute each user's net balance by summing all amounts they paid and subtracting all amounts they received. Then, repeatedly match the largest creditor with the largest debtor, transferring the minimum of the two amounts, until all balances are zero. This greedy approach yields a valid (though not necessarily minimal) list of paybacks.

Pro tip: Mention that while the greedy approach is simple and correct, minimizing the number of transactions is NP-hard (related to partition), so it's acceptable to return any valid list. Also, clarify how you handle rounding if amounts are not integers.

1. Clarify input and output

Confirm the transaction format: each transaction has a sender, a list of recipients, and a total amount split among recipients. Ask whether amounts are integers or floats, and whether the output should be a list of (debtor, creditor, amount) tuples.

2. Compute net balances

Iterate through all transactions and for each user, add the amount they paid and subtract the amount they received. Store net balances in a hash map (or dictionary) mapping user to balance.

3. Separate debtors and creditors

Create two lists: one for users with negative net balance (debtors) and one for users with positive net balance (creditors). Optionally, use a max-heap or sort to efficiently pick the largest debtor and creditor.

4. Greedily settle balances

While both lists are non-empty, take the largest debtor and largest creditor, transfer the minimum of their absolute balances, and update their balances. Remove any user whose balance becomes zero.

5. Return and verify

Collect each transfer as a payback and return the list. Verify that after applying all paybacks, every user's net balance is zero (or within epsilon for floats).

Key Points to Mention

  • Net balance calculation: sum of amounts paid minus sum of amounts received for each user.
  • Greedy matching of largest debtor with largest creditor to reduce the number of transactions.
  • Time complexity: O(N log N) with sorting or heaps, where N is the number of users; O(T) to process transactions.
  • Handling floating-point amounts: use epsilon comparison or convert to cents to avoid precision issues.
  • The problem asks for any valid list, not necessarily the minimal number of transactions (which is NP-hard).
  • Edge cases: users with zero net balance, transactions with multiple recipients, and empty transaction list.

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