Pinterest·Data Scientist·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Pinterest data scientist interview with an algorithms problem dressed up as a product scenario. The debt-settlement framing was a nice touch but the core of it is just a graph/greedy problem once you strip it back.

Questions Asked (1)

You're building an expense-sharing app. Given a list of transactions where each entry has a payer, a payee, and an amount, design an algorithm that finds the minimum number of payments needed to settle all balances among the group.

Algorithms & Data StructuresSystem Design

Author's notes

I spent the first couple minutes thinking about this as a graph problem and almost went down a max-flow rabbit hole.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying that the goal is to minimize the number of transactions, not the amount transferred. Then reduce the problem to computing net balances for each person and use a greedy algorithm that repeatedly matches the largest creditor with the largest debtor, which is optimal for minimizing transaction count in practice.

Pro tip: Acknowledge that while the greedy approach is not always optimal in theory (it's NP-hard), it is the standard practical solution and works well for most real-world cases. Mention that for small groups, an exact solution via backtracking is feasible.

1. Clarify the problem and constraints

Confirm that the goal is to minimize the number of payments, not the total amount. Ask about the expected group size and whether an approximate solution is acceptable.

2. Compute net balances

For each person, calculate the net amount they owe or are owed by summing all transactions where they are payer (subtract) or payee (add).

3. Separate creditors and debtors

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

4. Apply greedy matching

While both lists are non-empty, match the largest creditor with the largest debtor, settle the smaller amount, and update their balances. Remove anyone whose balance becomes zero.

5. Analyze complexity and alternatives

Discuss time complexity (O(n log n) with sorting) and mention that the problem is NP-hard in general, so for small n, backtracking can find the exact minimum.

Key Points to Mention

Net balance calculation: sum of amounts paid minus amounts received for each person.
Greedy algorithm: repeatedly match the largest creditor with the largest debtor.
Optimality: greedy is not always optimal, but it is a 2-approximation and works well in practice.
Complexity: O(n log n) due to sorting, where n is the number of people.
Edge cases: zero balances, floating-point precision, and multiple transactions between same pair.
Alternative: backtracking for exact minimum when the number of people is small (e.g., ≤ 10).

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