Hashing: The Interview Perspective

Hash tables show up in interviews across a wide range of problems: two sum, anagram detection, frequency counting, and duplicate identification. The data structure itself is simple. What makes hash tables valuable is the guarantee they provide: $O(1)$ average-case lookup by key. That guarantee is what makes certain classes of problems tractable.

Why interviewers reach for hashing

A hashing problem is almost always about lookup speed. Arrays and linked lists require scanning every element to find a match. Hash tables compute the location of any key directly, giving us $O(1)$ average-case access regardless of how many elements the structure contains.

The signal to reach for a hash table is almost always a scan that happens more than once. If we are checking whether an element exists in a collection we have already processed or looking up a value we computed earlier in the traversal, a hash table eliminates that repeated work. The moment we find ourselves scanning backward through a list or running a nested loop to check a condition, we should ask whether a hash table can replace that second scan with a single $O(1)$ lookup. ...