Visualized DSA Strategies

Episode 2 Hashing: HashSet and HashMap

1 h 3 min · JavaScript · Quiz

Title card of Episode 2: Hashing: HashSet and HashMap

▶ This video is coming to YouTube soon.

The complete guide to hashing for coding interviews, in JavaScript. 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; Set and Map in JavaScript (ask with has, because add returns the Set itself; get gives undefined for a missing key, so ?? 0 supplies the default; a Map of arrays to group); 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
  • Set and Map in JavaScript: add, has, delete, set, get with ?? 0, size, and for...of in insertion order
  • 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 an array of 26 counts and charCodeAt
  • Grouping by a key with a Map of arrays, 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 an array
  • Five traps: add returns the Set, array keys compare by identity, plain objects as maps, == against ===, adding while looping

Chapters

  1. 0:00Intro
  2. 0:22How a hash set works
  3. 1:40Four questions hashing answers
  4. 2:07What each structure costs
  5. 2:48Set and Map in JavaScript
  6. 4:20Five traps
  7. 5:37Nine hashing types
  8. 6:18Type 1 · Is there a duplicate?
  9. 12:08Type 2 · Duplicates close together
  10. 18:02Type 3 · Two numbers that add up
  11. 23:53Type 4 · Are they anagrams?
  12. 29:37Type 5 · Can the note be written?
  13. 35:54Type 6 · Group the anagrams
  14. 41:35Type 7 · What do two arrays share?
  15. 47:32Type 8 · Longest consecutive run
  16. 53:57Type 9 · A set with a random pick
  17. 1:00:51Spot the type
  18. 1:01:37Quiz: which type?
  19. 1:02:25Recap

Quiz: test yourself

The 5 questions from the end of the episode. Pick an answer to see why it's right.