When would you reach for a hash set or hash map to solve an array problem, and what does it buy you over scanning?

technical-conceptual · Junior level · software-engineering

What the interviewer is really asking

Assesses whether the candidate recognizes hashing as the trade of space for time, and can apply it to membership, dedup, and complement-lookup patterns.

What to say

• Frame it as trading space for time: a hash set/map turns an O(n) repeated scan into an O(1) average lookup, so a whole class of nested-loop problems collapses from O(n^2) to O(n).
• Name the common patterns: membership/'have I seen this before' (dedup, finding duplicates), counting frequencies, and the complement trick (two-sum: for each value check if `target - value` is already in the map).
• State the cost so it's a real trade-off: you spend O(n) extra memory, and a hash map is unordered, so if the problem needs sorted output or you're memory-constrained, sorting + two pointers may be the better fit.

What to avoid

• Reach for a hash map reflexively for every problem without acknowledging the O(n) memory cost.
• Claim hashing keeps elements in sorted order — it doesn't; iteration order is unspecified.
• Describe the two-sum complement trick but get the lookup backwards (storing the complement instead of checking for it).

Example answers

Strong: Hashing trades memory for speed: an O(1) average lookup lets me replace a repeated inner scan. For two-sum I make one pass, and for each number I check whether `target - num` is already in the map before inserting `num` — that's O(n) time and O(n) space instead of the O(n^2) brute force of checking every pair. The map also hands me the index for free so I can return positions.

Weak: I'd use a hash map because they're fast — pretty much always the right tool for array problems.