Remitly·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Interviewed for a software engineering role at Remitly and got a coding problem that felt deceptively simple at first glance. The core challenge was about settling debts between accounts, which is the kind of thing you'd expect from a fintech company.

Questions Asked (1)

Given a map of account IDs to net balances (positive means owed money, negative means owes money, and the sum is guaranteed to be zero), produce a minimal list of transfers that settles all accounts to zero. Each transfer is a tuple of (sender, receiver, amount).

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was to just pair up positives and negatives greedily, which actually works fine for correctness.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Separate accounts into debtors (negative balances) and creditors (positive balances), then greedily match the largest debtor with the largest creditor to settle as much as possible in each transfer. This greedy strategy minimizes the number of transfers, though it may not be unique. Explain the algorithm, prove its optimality, and discuss trade-offs like time complexity and alternative approaches.

Pro tip: Mention that while the greedy approach minimizes the number of transfers, it may not be the only minimal solution; also, in practice, you might want to minimize the total amount transferred or consider transaction fees, which could lead to different strategies.

1. Understand the problem and constraints

Clarify that the sum of balances is zero, so settlement is always possible. Identify that a transfer reduces the sender's balance (if negative) and the receiver's balance (if positive) by the transfer amount.

2. Separate debtors and creditors

Create two lists: one for accounts with negative balances (debtors) and one for accounts with positive balances (creditors). Optionally, sort them by absolute balance to facilitate greedy matching.

3. Greedily match largest debtor with largest creditor

While both lists are non-empty, take the debtor with the most negative balance and the creditor with the most positive balance. Transfer the minimum of their absolute values, update their balances, and remove any that reach zero.

4. Analyze optimality and complexity

Explain that this greedy approach yields a minimal number of transfers (at most n-1, where n is the number of accounts). Discuss time complexity: O(n log n) if sorting is used, otherwise O(n^2) with naive selection.

5. Discuss trade-offs and alternatives

Mention that other optimal solutions may exist. Consider if minimizing total transferred amount is more important, which could lead to a different algorithm (e.g., subset-sum based). Also, note that in real systems, you might batch transfers or use a different settlement method.

Key Points to Mention

Greedy algorithm: match largest debtor with largest creditor to minimize number of transfers.
Proof of optimality: each transfer zeroes out at least one account, so at most n-1 transfers are needed, and greedy achieves this bound.
Time complexity: O(n log n) with sorting, or O(n^2) without; space complexity O(n).
Alternative approaches: dynamic programming or subset-sum to minimize total amount transferred, but these are more complex and may not reduce the number of transfers.
Handling ties: when multiple accounts have the same balance, any choice works, but consistency may matter for determinism.
Edge cases: all balances zero (no transfers), single account with zero balance, or accounts with very large numbers (use appropriate data types).

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