Foundations: measuring code · Lesson 4 of 23
Hash maps and sets
The most useful interview tool: O(1) lookups and inserts, counting and grouping.
A hash map (JavaScript's Map) stores key → value pairs. Instead of scanning an array, it computes a "drawer number" (a hash) from the key and goes straight there, so lookup, insert and delete are O(1) on average.
A Set is the same idea with keys only: "is this here?".
Key "mona"
Hash function
Bucket 3
Value 340
The same key always lands in the same bucket, so there's no searching.
// Counting: the most common hash-map pattern
const words = ["sea", "code", "sea", "learn", "code", "sea"]
const count = new Map()
for (const w of words) count.set(w, (count.get(w) || 0) + 1)
console.log(count.get("sea"), count.get("learn"), count.has("java"))
// Grouping: words with the same letters share a sorted key
const groups = new Map()
for (const w of ["eat", "tea", "tan", "ate", "nat"]) {
const key = [...w].sort().join("")
if (!groups.has(key)) groups.set(key, [])
groups.get(key).push(w)
}
console.log([...groups.values()])Map or object?
A plain object {} can act as a hash map, but Map is better for interviews: keys can be any type (real numbers, not strings), it has size, keeps insertion order, and has no inherited keys like toString.
What's the output?
const seen = new Set()
seen.add([1, 2])
seen.add("1,2")
console.log(seen.has([1, 2]), seen.has("1,2"), seen.size)What will this code print?
Order the lines
Order the lines of a hash-map two-sum (O(n)).
- Click the lines in the right order
Exercise
Write firstUnique(s) returning the index of the first non-repeating letter, or -1. It must print 3 -1.
Expected output: 3 -1
function firstUnique(s) {
}
console.log(firstUnique("aabcb"), firstUnique("aabb"))Practise on real problems
Practice problems that use what you learned here. Solve them in JavaScript, Python or C++.
Learn more from
Played 0 of 3 games
Sign in to save your progress and earn XP.