← Pinterest Interview Insights

Pinterest·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026Remote

Summary

One-hour phone screen for a Pinterest SWE role. The coding problem was a trip expense settlement question that felt like it assumed you'd seen something similar before, which I hadn't quite.

Questions Asked (1)

Q1

A group of friends go on a trip together. You're given a list of transactions, each with a payer, a total amount, and a list of people the payment covered. Write a function that outputs the minimal set of payments needed to settle all balances between the group.

Algorithms & Data StructuresData Modeling
Author's notes

My first instinct was to model it as a graph of who owes whom, which got complicated fast.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, compute each person's net balance by summing what they paid and subtracting what they owe. Then, use a greedy algorithm to match the largest creditor with the largest debtor, settling as much as possible in each transaction, to minimize the number of payments. This reduces the problem to minimizing cash flow, which is NP-hard in general but the greedy approach works well in practice and is optimal for many cases.

Pro tip: Mention that while the greedy approach is not always optimal, it is widely used and often produces the minimal number of transactions; for exact optimality, you could use backtracking or DP for small groups, but that's exponential. Also, clarify that the problem assumes all debts are settled exactly, with no rounding issues.

1. Compute net balances

For each person, calculate their net balance by adding amounts they paid and subtracting amounts they owe for transactions they were covered by. This gives a list of positive (creditors) and negative (debtors) balances.

2. Separate creditors and debtors

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

3. Greedy matching

While there are debtors and creditors, take the largest debtor and largest creditor, settle the minimum of their absolute amounts, and record a payment from debtor to creditor. Update their balances and repeat until all are zero.

4. Return the payments

Collect all recorded payments as the minimal set of transactions needed to settle all balances.

Key Points to Mention

  • Net balance calculation: sum of payments made minus sum of shares owed.
  • Greedy algorithm: repeatedly match largest debtor with largest creditor.
  • Time complexity: O(n log n) due to sorting, or O(n^2) if using simple max search.
  • Optimality: greedy is not always optimal, but often produces minimal or near-minimal transactions.
  • Edge cases: zero balances, floating point precision, and ensuring all balances sum to zero.
  • Alternative approaches: backtracking or DP for exact minimal transactions (exponential time).

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