Pattern #4

Hashing / Hash Map / Hash Set

Important interview questions, thinking patterns, production use cases, and Go tips for hashing problems.

Must Solve

17 core questions — solve these first.

  1. 1.Two Sum
    easy
  2. 2.Contains Duplicate
    easy
  3. 3.Valid Anagram
    easy
  4. 4.Group Anagrams
    medium
  5. 5.Intersection of Two Arrays
    easy
  6. 6.First Unique Character in a String
    easy
  7. 7.Ransom Note
    easy
  8. 8.Isomorphic Strings
    easy
  9. 9.Word Pattern
    easy
  10. 10.Happy Number
    easy
  11. 11.Longest Consecutive Sequence
    medium
  12. 12.Top K Frequent Elements
    medium
  13. 13.Subarray Sum Equals K
    medium
  14. 14.Longest Substring Without Repeating Characters
    medium
  15. 15.Find All Anagrams in a String
    medium
  16. 16.4Sum II
    medium
  17. 17.Minimum Window Substring
    hard

Also Important

9 more questions worth practicing.

  1. 18.Majority Element
    easy
  2. 19.Sort Characters By Frequency
    medium
  3. 20.Find Common Characters
    easy
  4. 21.Unique Number of Occurrences
    easy
  5. 22.Check if N and Its Double Exist
    easy
  6. 23.Contains Duplicate II
    easy
  7. 24.Encode and Decode Strings
    medium
  8. 25.Design HashMap
    easy
  9. 26.LRU Cache
    medium

How to Think

  1. Need fast lookup?Hash Map
  2. Need only know if something exists?Hash Set
  3. Need frequency/count?value → count
  4. Need remember previous index?value → index
  5. Need remove duplicates?Hash Set
  6. Need group items?key → list
  7. Need pair with target?target - current, check Map
  8. Need longest consecutive numbers?Hash Set (avoid sorting)
  9. Need subarray sum = K?Prefix Sum + Hash Map

Small Rules

Map

Store information about something.

userID → user
number → count
value  → index

Set

Store only whether something exists.

seen[value]

Complexity

Average:

Lookup → O(1)

Insert → O(1)

Delete → O(1)

Extra space usually: O(n)

Production Thinking

Fast lookup

Instead of scanning 1 million users:

Loop → O(n)

Use: userID → user → O(1)

Remove duplicate events

A server receives the same message twice.

processedMessageIDs

If ID already exists → ignore it.

Count things

productID → numberOfOrders

Very common in real systems.

Cache data

userID → cachedUser

Avoid hitting the database every time.

More speed often means more memory.

Array scan → less memory, slower lookup

Hash Map → more memory, faster lookup

Go Tips

Map

m := make(map[int]int)

Set

seen := make(map[int]bool)

Check existence

value, ok := m[key]

Go map order is not guaranteed. Do not depend on map iteration order.

Normal Go maps are not safe for concurrent writes. Production code may need locking or sync.Map.

Interview Rules

  1. Need lookup?Map
  2. Need uniqueness?Set
  3. Need frequency?Map
  4. Need value + index?Map
  5. Need pair target?Store previous values
  6. Need duplicates?Set
  7. Need grouping?Map of lists

💡 Hashing often changes O(n²) into O(n).

Remember This

Exists? → Set

Count? → Map

Index? → Map

Group? → Map

Duplicate? → Set

Fast lookup? → Hashing

Pair target? → Map

Prefix sum? → Map