Hash Maps for Coding Interviews: A Crash Course

O(1)

1. Insert, update or delete a pair

• Insert: store a new key with its value, like Jin → Seoul.
• Update: assigning to an existing key replaces its value.
• Delete: remove a key and its value together.

Inserting "Jin"

O(1)

2. Check whether a key exists

• Tells you if a key is stored without looking at every pair.
• Average case is constant time, which is why maps beat lists for lookups.

Looking up "Maya"

O(n)

3. Search for a value

• Maps are indexed by key, not by value.
• Finding a value means scanning pair after pair.
• If you need fast value lookups, keep a second map from value to key.

Searching for "Seoul"

O(n)

4. Iterate over every pair

• Visits each key and value once.
• Common after building a map, for example to find the most frequent element.

Visiting all 3 pairs

1. Complement lookups

To find two numbers that add up to a target, remember each number you pass and ask whether its complement was already seen.

💡 One pass instead of comparing every pair, so O(n) instead of O(n²).

In an interview:

Map each value to its index. For every new value, check if target - value is already a key.

def two_sum(nums, target):
    index_of = {}
    for i, x in enumerate(nums):
        if target - x in index_of:
            return [index_of[target - x], i]
        index_of[x] = i

2. Spotting repeats

Keep every element you have seen in a set. The moment an element is already in it, you found a duplicate.

💡 Works for numbers, characters, coordinates, or any value you can hash.

In an interview:

Check membership first, then add. Return as soon as you find a repeat.

def has_repeat(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

3. Frequency counting

Map each element to the number of times it appears. Counts answer questions about anagrams, majority elements and the most common items.

💡 Two strings are anagrams exactly when their counts are equal.

In an interview:

Start each count at 0 with get, then add one per occurrence.

counts = {}
for ch in "banana":
    counts[ch] = counts.get(ch, 0) + 1
# {"b": 1, "a": 3, "n": 2}

Hash function

A hash function turns a key into a large number. Taking that number modulo the array size gives a bucket index.

The same key always lands in the same bucket, so lookups go straight to it.

Buckets

The map keeps an array of buckets. Each pair lives in the bucket its key hashes to.

Reading or writing a bucket by index is O(1), which is where the speed comes from.

Collisions

Two different keys can hash to the same bucket. The usual fix is to keep a short list of pairs in that bucket.

With a good hash function the lists stay tiny, so operations stay O(1) on average.

Resizing

When too many pairs share too few buckets, the map allocates an array twice as large and re-inserts every pair.

One resize costs O(n), but it happens so rarely that each insert is still O(1) amortized.