Module 4
Hashing
Trade a little memory for a lot of speed: remember what you've seen, count it, or group by a key, all in O(1) per lookup.
Hash maps and hash sets are the most useful tools in coding interviews. Whenever a slow solution searches for something it has already passed ("have I seen x?", "where was the partner of x?"), a hash structure usually turns that search into a single O(1) lookup.
This module explains how they work inside, so you can predict their cost and avoid their traps, then drills the three main uses: complement lookup, counting, and grouping by a computed key.
Part 1
Learn the ideas
- 4.1How a HashMap Works InsideBuckets, hash codes, equals, collisions and resizing: why lookups are O(1) on average and what can make them slow.15 min
- 4.2The Complement TrickTurn "find two elements that combine to a target" from O(n²) into O(n) by remembering each element as you pass it.12 min
- 4.3Counting and GroupingUse `merge` to count and `computeIfAbsent` to group, and choose a key that makes equivalent items collide on purpose.12 min
- 4.4Hashing PitfallsArrays as keys, mutable keys, boxed comparisons and missing keys: the bugs that make correct-looking hash code fail.8 min
Part 2
Solve the problems
In order of difficulty. Each one shows the pattern it teaches.
The complement trick: for each number, look up
target − numberamong the numbers already seen.Compare two strings by letter counts with a 26-slot array instead of sorting.
Two passes: count everything first, then use the counts while scanning in the original order.
Grouping by a computed key: equivalent items must produce the same key, different items different keys.
Count first, then select: bucket sort by frequency gives O(n), beating a full sort.
Use a set to find where runs start (x − 1 absent), then count each run once: O(n) without sorting.