Hash Maps & Sets
Practice & Revision
HashMap pattern recognition decision tree, cheat sheet, and Top 15 must-solve hash map and set interview problems.
1. Introduction
This section serves as your comprehensive reference and practice guide for Hash Maps & Sets. Master these templates, review the decision tree, and solve the curated Top 15 interview problems to prepare for technical interviews.
2. HashMap Pattern Decision Tree
Use this flow chart to determine which hash pattern fits your problem:
3. Revision Cheat Sheet
Common Hash Patterns Summary
| Pattern | Key Configuration | Value Configuration | Common Problem |
|---|---|---|---|
| Complement Lookup | Element Value | Element Index | Two Sum |
| Frequency Counting | Element / Character | Integer Count | Valid Anagram / First Unique Char |
| First Seen Index | Prefix Sum | First Seen Index | Longest Subarray Sum Equals K |
| Anagram Grouping | Sorted Word String | List of Words | Group Anagrams |
| Unique Elements | Element Value | None (Set) | Contains Duplicate / Intersection |
4. Top 15 Must-Solve HashMap & Set Problems
5. Problem-Solving Framework
When solving hash-based questions, follow this checklist:
1. Trade Space for Time:
- If an algorithm uses nested loops to look up elements, search for matches, or compare indices, use a HashSet or HashMap to cache items and reduce lookup to O(1).
2. Determine Key Uniqueness:
- Does key order matter? In Java, use LinkedHashMap to preserve insertion order. For sorted keys, use TreeMap.
3. Optimize Key Footprint:
- For character sets, replace HashMaps with size-26 or size-128 primitive integer arrays to optimize constant factors.
6. Quiz
Question 1: In the 'Contiguous Array' problem (find max length of binary subarray with equal 0s and 1s), how do we configure the HashMap?
Answer: We treat0 as -1 and 1 as +1. We calculate the running prefix sum. If the same prefix sum has occurred before, the subarray between the two occurrences has a sum of 0 (equal 0s and 1s). We store {prefixSum: firstSeenIndex} in the map and update maximum length.
Question 2: How does 'Insert Delete GetRandom O(1)' achieve O(1) random retrieval?
Answer: A HashMap alone cannot choose a random element inO(1) because buckets are sparse. We pair a dynamic array (List) with a HashMap. The List stores elements contiguously to allow O(1) index lookup via random numbers. The HashMap stores {element: listIndex} to locate items instantly during deletions.
Question 3: In C++, what is the difference in complexities between std::map and std::unordered_map?
Answer:std::unordered_map is a hash table, giving average O(1) lookup and insertion.std::map is a self-balancing Red-Black Tree, giving guaranteed O(log N) lookup/insertion while keeping keys sorted.Question 4: What is the optimal space complexity for 'Happy Number' set cycle detection?
Answer:O(log N) auxiliary space, since the number of digits decreases exponentially, and we store at most a few dozen intermediate sums before hitting a cycle or 1.
Question 5: Why do we initialize the prefixSum map with {0: 1} in prefix sum subarray count queries?
Answer: Because if a prefix sum itself equals the targetK, then sum - K = 0. Without the 0 mapping, we would miss counting subarrays that start at index 0.