Hashing Practice Problems
How to Use This Problem List
Most hashing problems look different on the surface but share the same two-line insight: compute the hash of the thing you want, then check if you have seen it before. The variation is in what you hash and what counts as having seen it.
Practice by pattern, not by difficulty. When you solve five problems that all use "store seen values, check complement," the sixth one becomes instant recognition. Random difficulty-based practice builds a collection of memorized solutions instead of a transferable skill.
For each problem: spend the first three minutes identifying which hashing pattern applies before writing any code. The recognition clue column tells you what phrase or constraint in the problem statement points to each pattern.
Pattern 1: Existence Check — HashSet
Store elements as you scan. Before storing, check if the element (or some transformation of it) already exists. If yes, the answer involves that element.
| Problem | Difficulty | Recognition Clue | Key Insight |
|---|---|---|---|
| Contains Duplicate | Easy | "appears more than once" | Store seen values in a set, return true on first repeat |
| Contains Duplicate II | Easy | "within k distance" | Sliding window set of size k — remove out-of-range element |
| Happy Number | Easy | "endless loop" | Cycle detection — HashSet of seen sums detects the cycle |
| Longest Consecutive Sequence | Medium | "consecutive", "unsorted" | Only start a sequence at n where n-1 is absent from set |
| Single Number | Easy | "all appear twice except one" | XOR all elements — no HashSet needed, O(1) space |
| Missing Number | Easy | "one number missing from 0..n" | Put all in set, scan 0..n for the absent one |
| Find the Duplicate Number | Medium | "one number repeated" | Floyd's cycle detection or HashSet of seen values |
| Intersection of Two Arrays | Easy | "common elements, no duplicates" | Set of first array, scan second for matches |
| Jewels and Stones | Easy | "count stones that are jewels" | Set of jewel types, scan stones |
| Unique Email Addresses | Easy | "unique destinations" | Normalize each email, add to set, return set size |
Complexity target: O(n) time, O(n) space (O(1) for XOR/math-based problems).
What changes across problems: the element stored (value, index, sum, normalized form).
Pattern 2: Complement Lookup — HashMap
For each element, compute what you are looking for (the complement). Check if that complement was already stored in the map. If not, store the current element for future queries.
| Problem | Difficulty | Recognition Clue | Key Insight |
|---|---|---|---|
| Two Sum | Easy | "two indices that sum to target" | Store value→index, check if (target-num) exists |
| Two Sum II (sorted) | Easy | "sorted array" | Two pointers is simpler here — no HashMap needed |
| 4Sum II | Medium | "four arrays, count pairs summing to 0" | Store all (a+b) sums, count matching -(c+d) complements |
| Count Pairs With Given Sum | Easy | "count pairs summing to k" | Complement lookup — freq[k-num] pairs with current |
| Pairs of Songs With Total Durations Divisible by 60 | Medium | "pairs divisible by 60" | Store (duration % 60), complement is (60 - mod) % 60 |
| Subarray Sum Equals K | Medium | "contiguous subarray, sum = k" | Prefix sum map — count how many past sums equal current-k |
| Path Sum III | Medium | "tree paths summing to k" | DFS + prefix sum map on each root-to-node path |
Complexity target: O(n) time, O(n) space.
What changes across problems: what you store (value, index, prefix sum, pair sum), and what complement you compute.
Pattern 3: Frequency Counting
Build a distribution map of element → count in one pass. Then use that map to answer questions about the distribution.
| Problem | Difficulty | Recognition Clue | Key Insight |
|---|---|---|---|
| Valid Anagram | Easy | "same characters, possibly different order" | Increment for s, decrement for t — all-zeros means anagram |
| First Unique Character | Easy | "first character appearing once" | Two-pass: build freq, scan for first with count = 1 |
| Most Common Word | Easy | "most frequent word not in banned list" | Frequency map, exclude banned set |
| Top K Frequent Elements | Medium | "k most frequent" | Freq map + bucket sort — O(n), not O(n log n) |
| Top K Frequent Words | Medium | "k most frequent words, alphabetical tie-break" | Freq map + sort with custom comparator |
| Sort Characters By Frequency | Medium | "sort by descending frequency" | Freq map + bucket sort + repeat each char freq times |
| Majority Element | Easy | "appears more than n/2 times" | Count during scan — return when count > n/2 |
| Majority Element II | Medium | "all elements appearing > n/3 times" | At most 2 candidates — Boyer-Moore voting |
| Find All Anagrams in a String | Medium | "all starting indices of anagram" | Fixed sliding window + frequency comparison |
| Permutation in String | Medium | "does s1's permutation exist in s2?" | Fixed window of len(s1), compare frequency maps |
| Character Replacement | Medium | "replace k characters, longest uniform window" | Window valid when (length - maxFreq) ≤ k |
| Ransom Note | Easy | "can note be built from magazine?" | Magazine freq must cover note freq |
Complexity target: O(n) time. O(1) space for fixed alphabet (int[26]), O(k) for maps.
What changes across problems: what you count (chars, words, elements), how you use the counts (compare, sort, slide a window, query thresholds).
Pattern 4: Grouping by Key
Compute a canonical key for each element. Elements with the same key belong to the same group. Store groups in a Map<Key, List>.
| Problem | Difficulty | Recognition Clue | Key Insight |
|---|---|---|---|
| Group Anagrams | Medium | "group strings that are anagrams" | Key = sorted string or frequency-array tuple |
| Group Shifted Strings | Medium | "shift all chars by same amount" | Key = sequence of differences between adjacent chars |
| Find and Replace Pattern | Medium | "strings following same structural pattern" | Key = normalized pattern (first-occurrence index encoding) |
| Isomorphic Strings | Easy | "one-to-one character mapping" | Bidirectional map — both char→char directions |
| Word Pattern | Easy | "word follows a character pattern" | Bidirectional map — both char→word and word→char |
| Custom Sort String | Medium | "sort s using order in order string" | Map each char to its priority index, sort by it |
| Brick Wall | Medium | "fewest cuts crossing bricks" | Count edge positions, find most common edge |
Complexity target: O(n × k) where k = average element size (e.g., string length).
What changes across problems: what defines "same group" and what canonical key represents it.
Pattern 5: Prefix Sum + HashMap
Use a running prefix sum and a hash map to count or find subarrays with specific sum properties. The key insight: if two prefix sums differ by exactly k, the subarray between them sums to k.
| Problem | Difficulty | Recognition Clue | Key Insight |
|---|---|---|---|
| Subarray Sum Equals K | Medium | "count subarrays with sum = k", can be negative | {0:1} base case, count prefixCount[running-k] |
| Subarray Sum Divisible by K | Medium | "count subarrays with sum divisible by k" | Two same (prefix % k) values → subarray divisible by k |
| Continuous Subarray Sum | Medium | "subarray sum is multiple of k, length ≥ 2" | Same modular prefix seen ≥ 2 indices earlier |
| Longest Subarray with Equal 0s and 1s | Medium | "binary array, equal 0s and 1s" | Replace 0→-1, find longest subarray with sum = 0 |
| Minimum Operations to Reduce to Zero | Medium | "remove from ends, sum = target" | Equivalent to finding longest subarray with sum = (total - target) |
| Count Nice Subarrays | Medium | "exactly k odd numbers" | Replace odd→1, even→0, then subarray sum = k |
| Binary Subarrays with Sum | Medium | "binary array, subarray sum = goal" | Prefix sum map, count prefixCount[running - goal] |
| Maximum Size Subarray Sum Equals k | Medium | "longest subarray with sum = k" | Store first-seen index of each prefix sum |
Complexity target: O(n) time, O(n) space.
What changes across problems: what you initialize the map with, what you look up, whether you count occurrences or track first/last index.
Pattern 6: Two Maps — Bijection
When a problem requires a one-to-one mapping that must be consistent in both directions, maintain two maps simultaneously. Both char→target and target→char must agree.
| Problem | Difficulty | Recognition Clue | Key Insight |
|---|---|---|---|
| Isomorphic Strings | Easy | "consistent one-to-one mapping" | Two maps: s→t and t→s — check both before mapping |
| Word Pattern | Easy | "word follows letter pattern exactly" | Two maps: char→word and word→char |
| Find and Replace Pattern | Medium | "strings following same abstract pattern" | Encode each string as first-occurrence index sequence |
| Sentence Similarity II | Medium | "transitive similarity via pair rules" | Union-Find or normalize to canonical representative |
Complexity target: O(n) time, O(n) space.
Pattern 7: LRU / Sliding Window Deduplication
Use a hash map or hash set to track elements within a moving window, efficiently adding and removing elements at O(1).
| Problem | Difficulty | Recognition Clue | Key Insight |
|---|---|---|---|
| Longest Substring Without Repeating Characters | Medium | "longest substring, no duplicate char" | HashSet tracks window, shrink left on duplicate |
| Contains Duplicate II | Easy | "duplicate within k positions" | HashSet of size k, slide the window |
| Fruit Into Baskets | Medium | "at most 2 distinct types in window" | HashMap of counts, shrink when distinct > 2 |
| Minimum Window Substring | Hard | "smallest window containing all of t" | Two-pointer + frequency map + formed counter |
| Longest Substring with At Most K Distinct | Medium | "at most k distinct chars" | HashMap of char counts, shrink when distinct > k |
| Subarrays with K Different Integers | Hard | "exactly k distinct" | exactly(k) = atMost(k) - atMost(k-1) |
Complexity target: O(n) time, O(k) space where k = window size or distinct count.
Pattern 8: Multi-Source Hashing and Graph Problems
Use hash maps to build adjacency structures, track visited nodes, or count node degrees in graph and tree problems.
| Problem | Difficulty | Recognition Clue | Key Insight |
|---|---|---|---|
| Number of Distinct Islands | Medium | "count unique island shapes" | DFS + hash the relative path to canonicalize shape |
| Clone Graph | Medium | "deep copy a graph" | HashMap of original→clone to avoid re-cloning |
| Copy List with Random Pointer | Medium | "copy linked list with random pointers" | HashMap of original→copy for O(1) lookup of copy |
| Find Duplicate Subtrees | Medium | "duplicate subtrees in binary tree" | Serialize each subtree, count in a map |
| Evaluate Division | Medium | "chain multiplication via given ratios" | Graph of ratios + BFS/DFS for paths |
| Alien Dictionary | Hard | "character ordering from sorted words" | Build char dependency graph, topological sort |
Complexity target: O(n) time and space where n = nodes or edges.
Recommended Study Order
Week 1 — Core Patterns Pattern 1 (Existence): Contains Duplicate, Happy Number, Longest Consecutive Pattern 2 (Complement): Two Sum, Count Pairs, Pairs Divisible by 60 Week 2 — Frequency and Grouping Pattern 3 (Frequency): Valid Anagram, Top K, Find All Anagrams, Majority Element Pattern 4 (Grouping): Group Anagrams, Isomorphic Strings, Word Pattern Week 3 — Prefix Sum and Windows Pattern 5 (Prefix+Map): Subarray Sum = K, Divisible by K, Equal 0s and 1s Pattern 7 (Sliding Window): Longest No-Repeat, Min Window Substring Week 4 — Advanced Patterns Pattern 6 (Bijection): Find and Replace Pattern, Sentence Similarity Pattern 8 (Graph+Hash): Clone Graph, Copy List Random Pointer, Duplicate Subtrees Revisit any patterns that felt unclear
Problem-Solving Checklist for Hashing Problems
Before writing code, run through this for every hashing problem:
1. What are you trying to look up?
→ The value itself? → HashSet
→ A complement of the value? → HashMap value→index or value→count
→ A prefix sum? → HashMap sum→count or sum→firstIndex
→ A canonical form? → HashMap key→group
2. What constitutes "same group" or "seen before"?
→ Same value? → Store value directly
→ Same frequency profile? → Store sorted string or freq tuple
→ Same structural pattern? → Encode as first-occurrence index sequence
→ Same modular sum? → Store prefix_sum % k
3. Which direction of mapping do you need?
→ One direction only → One map
→ Must be one-to-one → Two maps (bijection)
4. Is order important?
→ Just existence → HashSet
→ First occurrence → Map value→first_index
→ Count occurrences → Map value→count
→ Preserve insertion order → LinkedHashMap / Python dict
5. Edge cases:
→ Empty input → loop never executes, default return is correct?
→ Single element → is it its own pair/complement?
→ k = 0 in prefix sum → {0:1} base case handles subarrays summing to 0?
→ Negative numbers in frequency/complement problems?
Difficulty Progression Reference
| Stage | Characteristics | Representative Problems |
|---|---|---|
| Foundation | Single map, store and check in one pass | Contains Duplicate, Two Sum, Valid Anagram |
| Early Intermediate | Two-pass (build then query), or sliding window with map | First Unique Char, Find All Anagrams, Group Anagrams |
| Intermediate | Prefix sum + map, bidirectional maps, bucket sort | Subarray Sum = K, Word Pattern, Top K |
| Late Intermediate | Combined patterns, multi-step transforms | Min Window Substring, Subarrays with K Distinct, Clone Graph |
| Advanced | Graph hashing, complex canonical forms, hard constraints | Find Duplicate Subtrees, Alien Dictionary, Evaluate Division |
Common Interview Topics by Company Focus
Product-based companies (FAANG-tier):
- ›Two Sum and its many variants appear extremely frequently
- ›Subarray sum patterns — both equals-k and divisible-by-k
- ›LRU Cache (O(1) get + put using HashMap + doubly linked list)
- ›Top K problems — frequency map + heap or bucket sort
Service-based and on-campus:
- ›Contains Duplicate, Valid Anagram, Two Sum — high frequency
- ›Group Anagrams, Majority Element — medium difficulty baseline
- ›First Unique Character in a String
Startup and mid-size tech:
- ›Practical hashing — frequency counting on real data shapes
- ›Two-map bijection problems — isomorphic strings, word pattern
- ›Sliding window with hash map at medium difficulty
Progress Tracking
After solving each problem, record:
- ›Pattern — which of the 8 patterns does this belong to?
- ›Key clue — what phrase in the problem statement identified the pattern?
- ›What you stored — value, index, prefix sum, canonical key?
- ›Edge case missed — empty input? Negative numbers? k = 0?
- ›Time to solve — target 20 minutes for medium problems under interview conditions
After 30 problems, you should be able to name the pattern within two minutes of reading any new hashing problem. That is the signal that pattern recognition is operational.
The goal is not to remember the solution to each problem — it is to internalize the structure that makes a given technique applicable, so that any novel variation is recognizable by its shape.