DSA: Topic 2: Hash Maps & Sets

Why interviewers ask hash map questions

They want to see if you can:

• Trade a little extra memory for much faster runtime.
• Recognise repeated lookups.
• Avoid nested loops.

A common interview progression is:

Candidate writes O(n²) → Interviewer asks, "Can you optimise this?" → Expected answer: use a hash map.

---

What is a Hash Map?

In Python, a hash map is a dictionary.

student = {
    "Alice": 95,
    "Bob": 88,
    "Charlie": 91
}

Accessing a value:

print(student["Bob"])
# 88

Average time complexity:

• Insert: O(1)
• Search: O(1)
• Delete: O(1)

This is why dictionaries are so powerful.

---

What is a Set?

A set stores unique elements.

nums = {3, 7, 2}

print(7 in nums)
# True

Use a set when:

• You only care whether an item exists.
• You need to remove duplicates.

Example:

nums = [1, 2, 2, 3, 3, 4]

unique = set(nums)

print(unique)
# {1, 2, 3, 4}

---

When should you think "Hash Map"?

Ask yourself these questions:

1. Am I repeatedly searching for values?
2. Am I checking if something already exists?
3. Am I counting frequencies?
4. Am I matching pairs?
5. Am I removing duplicates?

If the answer is "yes", a dictionary or set is often the right tool.

---

Interview Pattern 1: Frequency Counting

Problem

Find the number that appears most often.

Example:

nums = [1, 2, 1, 3, 2, 1]

Instead of counting each number repeatedly (which is slow), build a frequency table:

freq = {}

for num in nums:
    freq[num] = freq.get(num, 0) + 1

print(freq)

Output:

{1: 3, 2: 2, 3: 1}

This pattern appears in problems like:

• Majority Element
• Top K Frequent Elements
• First Unique Character

---

Interview Pattern 2: Fast Lookup

Problem

Does the array contain duplicates?

Brute force:

Compare every pair

Time: O(n²)

Optimised:

seen = set()

for num in nums:
    if num in seen:
        return True
    seen.add(num)

return False

Time: O(n)

This is the expected interview solution.

---

Interview Pattern 3: Two Sum

This is one of the most famous interview questions.

Problem

nums = [2, 7, 11, 15]
target = 9

Return the indices of two numbers whose sum is 9.

Brute Force

for i in range(len(nums)):
    for j in range(i + 1, len(nums)):
        if nums[i] + nums[j] == target:
            return [i, j]

Time: O(n²)

---

Optimised Solution

Keep a dictionary of numbers you've already seen.

def two_sum(nums, target):
    seen = {}

    for i, num in enumerate(nums):
        complement = target - num

        if complement in seen:
            return [seen[complement], i]

        seen[num] = i

Time: O(n)

This is the solution interviewers usually expect.

---

Common Dictionary Methods

d = {}

d["apple"] = 5          # Insert/update

print(d["apple"])       # Access

print(d.get("banana"))  # None (instead of KeyError)

print(d.get("banana", 0))  # Default value

Iterating:

for key, value in d.items():
    print(key, value)

---

Common Set Methods

s = set()

s.add(5)

s.add(10)

s.remove(5)

print(10 in s)

---

Common Interview Mistakes

Mistake 1: Forgetting duplicate keys overwrite values

d = {}

d[1] = "A"
d[1] = "B"

print(d)

Output:

{1: 'B'}

The second assignment replaces the first.

---

Mistake 2: Accessing a missing key directly

count = {}

print(count["apple"])

This raises a KeyError.

Safer:

count.get("apple", 0)

---

Mistake 3: Using a list instead of a set for membership checks

if x in my_list:

This is O(n).

If you're only checking existence many times, use a set:

if x in my_set:

Average time: O(1).

---

Real Interview Problems

Master these:

1. Two Sum ⭐⭐⭐⭐⭐
2. Contains Duplicate ⭐⭐⭐⭐⭐
3. Valid Anagram ⭐⭐⭐⭐
4. Group Anagrams ⭐⭐⭐⭐
5. Majority Element ⭐⭐⭐⭐
6. Top K Frequent Elements ⭐⭐⭐⭐
7. First Unique Character ⭐⭐⭐
8. Happy Number ⭐⭐⭐

---

Interview Tip

When you're given an array, pause before coding and ask:

"Will I need to search or count elements repeatedly?"

If the answer is yes, consider a dictionary or set before reaching for nested loops. This habit alone can turn many brute-force solutions into optimal ones.

Practice

Try solving these without looking up solutions:

1. Return True if an array contains duplicates.
2. Count the frequency of each word in a list of strings.
3. Solve Two Sum in O(n).
4. Find the first non-repeating character in a string.

Once you're comfortable with hash maps and sets, the next topic is Two Pointers, one of the most frequently tested techniques for array and string problems.