Remember what you've seen
Episode 2 Hashing: HashSet and HashMap
▶ This video is coming to YouTube soon.
The complete guide to hashing for coding interviews, in Java. First how a hash set really works: buckets, collisions and why lookups are O(1) on average; the four questions hashing answers; what each structure costs; HashSet and HashMap in Java (add, merge, computeIfAbsent); and five traps. Then nine types, each worked as a small problem in full: examples, the brute force animated beside the running line of code, the complete code, every line explained, and the hashing solution the same way.
What you'll learn
- How a hash function, buckets and collisions make lookups O(1) on average
- HashSet and HashMap: add, contains, remove, put, getOrDefault, merge, computeIfAbsent
- Seen before? A set, and a set as a window of the last k numbers
- Look up the complement: Two Sum with a map
- Counting with a map, and with int[26]
- Grouping by a key, and set operations on two arrays
- The longest consecutive run: only start where a run starts
- Designing a set with a random pick: a map plus a list
- Five traps: Integer equality, null, mutable keys, hashCode, removing while looping
Chapters
- 0:00Intro
- 0:22How a hash set works
- 1:34Four questions hashing answers
- 2:02What each structure costs
- 2:36HashSet and HashMap in Java
- 3:45Five traps
- 4:26Nine hashing types
- 5:06Type 1 · Is there a duplicate?
- 10:35Type 2 · Duplicates close together
- 16:30Type 3 · Two numbers that add up
- 22:07Type 4 · Are they anagrams?
- 27:44Type 5 · Can the note be written?
- 33:34Type 6 · Group the anagrams
- 38:56Type 7 · What do two arrays share?
- 44:52Type 8 · Longest consecutive run
- 50:54Type 9 · A set with a random pick
- 57:26Spot the type
- 58:10Quiz: which type?
- 58:58Recap
Quiz: test yourself
The 5 questions from the end of the episode. Pick an answer to see why it's right.