Two Sum
Prompt
We've got a list of account balances and a target transfer amount. Walk me through how you'd find two accounts whose balances add up to the target.
How this round runs
The spec is deliberately thin — clarify before you write code, and expect me to change a constraint once you have something working.
Model answer
Start by clarifying: is there exactly one pair, or could there be many? Can an account pair with itself? Is the list sorted? Are balances unique?
Brute force first — nested loop over every pair, O(n^2) time, O(1) space.
State it, then improve it: one pass with a hash map from balance to index. For
each balance, check whether target - balance is already in the map; if so
return both indices, otherwise store the current one. That is O(n) time and
O(n) space.
function findPair(balances, target) {
const seen = new Map();
for (let i = 0; i < balances.length; i++) {
const need = target - balances[i];
if (seen.has(need)) return [seen.get(need), i];
seen.set(balances[i], i);
}
return null;
}
Dry-run on [3, 7, 1] with target 8: see 3 (store), see 7 (need 1, not yet),
see 1 (need 7, found) → return the indices of 7 and 1.
- Asked at least one clarifying question before coding
- Named the brute force, then optimized to the hash-map approach
- Stated time and space complexity before and after optimizing
- Dry-ran the final code on a concrete input
- Can you do better than the nested-loop approach? → the hash-map one pass
- What if the list does not fit in memory? → external or streaming, or sort then two-pointer
- What if there can be duplicate balances or multiple valid pairs? → the output contract changes