DEV Community

geodesic partners
geodesic partners

Posted on Originally published at geodesicpartners.co.uk

Hash maps in coding rounds: picking the key is the hard problem

#python #datastructures #algorithms #interview

Most array tasks in a coding round ask you to learn something about one element relative to the others. Usually you want to know whether it has turned up already, though quite often you'll also need a count of how many times it has appeared or the index where it sits. The obvious opening attempt simply goes and looks:

for i in range(n):
    for j in range(n):
        if i != j and a[i] == a[j]:
            return True
Enter fullscreen mode Exit fullscreen mode

On a hundred thousand elements that comes to ten billion comparisons, since you rebuild the same fact (which values are present) once per element and then throw it away again.

What the Hash map replaces

A set turns "is this value present?" from a walk over the array into a single lookup, so the whole check needs only one pass:

seen = set()
for x in a:
    if x in seen:
        return True
    seen.add(x)
Enter fullscreen mode Exit fullscreen mode

If an interviewer presses you on precision, say the lookup is expected O(1). Colliding keys can pile into one bucket, and production languages randomise their hash functions each time a program starts to guard against that risk.

What to key on

Sets and maps themselves are the easy bit, and the harder skill lies in choosing a key that turns your question into a lookup.

  • Duplicates: key on the value itself.
  • A pair adding up to a given total: key on the number and look up target - x, since you want to know if the partner has already gone past.
  • Subarrays that sum to k: key on the running sum, because if two prefix sums differ by k, the stretch between them sums to k.

I'd spend extra time on that last case, as nothing in the wording of the task mentions "prefix sum". You have to notice that what's worth remembering summarises everything you've seen so far, which no single element can tell you by itself:

from collections import Counter

def count_subarrays(a, k):
    seen = Counter({0: 1})
    total = count = 0
    for x in a:
        total += x
        count += seen[total - k]   # earlier prefixes that leave exactly k
        seen[total] += 1
    return count
Enter fullscreen mode Exit fullscreen mode

Do the lookup ahead of the insert

Most wrong answers with this approach come from one ordering bug, and you can write it without noticing:

for i, x in enumerate(a):
    if target - x in seen:        # look up first
        return (seen[target - x], i)
    seen[x] = i                   # then insert
Enter fullscreen mode Exit fullscreen mode

Swap those two steps and an element can match itself. With a = [3, 5] and a wanted sum of 6, inserting 3 ahead of the check means the lookup for 6 − 3 = 3 succeeds, so you return (0, 0) even though the array holds only one 3. In counting problems the same mistake won't crash anything; instead it quietly inflates the count, which makes the bug far harder to spot.

When not to hash

The input is already sorted. You've paid for that order, and two pointers can use it in O(1) extra space, whereas a hash map spends O(n) and ignores it. When a problem statement goes out of its way to say "sorted", the interviewer is hinting at the technique they have in mind.

The data is too big for memory. A map over a hundred million different keys runs to gigabytes, so an external sort followed by a linear scan wins here despite being O(n log n), because it streams.

Originally posted here: https://geodesicpartners.co.uk/coding-arrays-hashing-why

Top comments (0)