Hash Map Patterns
Fast recall
Quick revision
Core answer
Whether you understand Hash Map Patterns beyond memorized syntax.
Giving a definition without explaining a practical trade-off.
Connect the concept to a small production example and state its complexity or failure mode.
Interview-ready guide
Interview answer
Two-sum, executed:
func twoSum(nums []int, target int) [2]int {
seen := make(map[int]int)
for i, n := range nums {
if j, ok := seen[target-n]; ok {
return [2]int{j, i}
}
seen[n] = i
}
return [2]int{-1, -1}
}
// twoSum([]int{2,7,11,15}, 9) → [0, 1] — verifiedThe pattern: for each element, check 'have I seen the complement (target - n)?' in a hash map — O(1) per check. One pass, O(n) time, O(n) space. The alternative (check every pair) is O(n²) — the map trade: space for time.
The counter pattern:
freq := make(map[string]int)
for _, word := range words { freq[word]++ }
// anagram check: count chars, compare mapsThe anagram check via counter, executed:
func isAnagram(a, b string) bool {
if len(a) != len(b) { return false }
counts := make(map[rune]int)
for _, r := range a { counts[r]++ }
for _, r := range b { counts[r]-- }
for _, v := range counts { if v != 0 { return false } }
return true
}
// isAnagram("listen", "silent") → true — verifiedThe patterns this enables: deduplication (the presence check), grouping (map[string][]T), indexing (map[record.ID] = position), memoization (map[args]result). The hash map is THE tool that converts 'nested loop over pairs' into 'single loop + lookup.'
Hash Map Patterns
Direct Answer
Two core patterns: (1) Lookup table — build a map of seen values, check for complements (two-sum: seen[target-n]). (2) Counter — count occurrences, group by key. Both convert O(n²) into O(n).
Deep Dive & Architecture
The hash map's complexity contract: average O(1) insert/lookup/delete, worst O(n) (all keys colliding — adversarial input). The average is what algorithmic patterns rely on: the time-space trade is 'O(n) extra memory for O(1) membership.'
The two-sum's invariant, precisely: at iteration i, the map contains exactly the first i-1 elements. Checking seen[target-n] answers 'does the complement exist among elements BEFORE i?' — the answer pair is always (earlier, current), never duplicates. The one-pass solution is the optimized form of the two-pass (build map fully, then check) — same complexity class, half the iterations.
The counter's design vs sorting: isAnagram could sort both strings and compare (O(n log n)) — the counter is O(n). The general principle: when the question is about FREQUENCY or PRESENCE, hashing is O(n); when it's about ORDER, sorting earns its log factor. The interview discipline: identify which question you're answering, choose accordingly.
Common Mistakes & Pitfalls
Giving a definition without explaining a practical trade-off.
Check your understanding
Answer these without looking back at the article.
- When would you use Hash Map Patterns in a real project?
- How would you compare Hash Map Patterns with an alternative?
- What is a common mistake when using Hash Map Patterns?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.