Hash Tables from Scratch Checkpoint

Optional

28 min · Intermediate

A review of this module. Skip it if you feel confident; the next module does not need it.

Fix the mistakes

The slips that cost marks in this module. Spot each one, then check the fix.

This checkpoint mixes slots, collisions, resizing and designs. Work each answer out by hand, then run the code to check it.

Slots, collisions and probing

Given a table size and keys, you should be able to say each key's slot, which keys collide, and where linear probing places them. Work it out on paper first, then check with code.

Python

1slots = [None] * 52for key in [12, 7, 22, 3]:3    i = key % 54    while slots[i] is not None:5        i = (i + 1) % 56    slots[i] = key7print(slots)

Example 1 · Anagram groups by counting

Python

words = ["tea", "eat", "tan", "ate", "nat", "bat"]groups = {}for word in words:    groups.setdefault("".join(sorted(word)), []).append(word)print(len(groups), sorted(map(len, groups.values())))

Output

3 [1, 2, 3]

What this code does

Words with the same sorted letters share a key, so the dictionary groups them in one pass.
The keys are strings, so a hash is used, but only the grouping is printed, which does not depend on the hash value.

Keys 12, 7 and 22 all start at slot 2. They take slots 2, 3 and 4. Key 3 wants slot 3, finds it taken and moves on to slot 4, then wraps to slot 0.

Load factor and resizing

A table grows when it is too full. Know the load factor, the doubling rule and why a resize rehashes every key. Count how many times a table doubles for a given number of inserts.

Python

1capacity, resizes = 4, 02for count in range(1, 41):3    if count > 0.75 * capacity:4        capacity *= 25        resizes += 16print(capacity, resizes)

Example 2 · First repeated order id

Python

1ids = [41, 17, 8, 17, 41, 99]2seen = set()3for order in ids:4    if order in seen:5        print(order)6        break7    seen.add(order)

Output

What this code does

A set answers "seen before?" in constant time on average.
The scan stops at the first repeat, 17. A nested loop would take O(n squared) time.

The table doubles from 4 to 8 at the 4th key, to 16 at the 7th, to 32 at the 13th and to 64 at the 25th. A table with 40 keys ends at 64 slots after 4 resizes.

Hash map in a design

When a problem needs constant-time lookup plus order, a random pick or a count, pair a dictionary with a second structure. Say the time and the space out loud: here O(1) per operation and O(n) space.

Python

1from collections import OrderedDict2recent = OrderedDict()3for key in [1, 2, 1, 3]:4    recent[key] = True5    recent.move_to_end(key)6print(list(recent))

Example 3 · Resize moves keys

Python

keys = [5, 9, 14, 3]print([k % 4 for k in keys])print([k % 8 for k in keys])

Output

[1, 1, 2, 3]
[5, 1, 6, 3]

What this code does

With 4 slots keys 5 and 9 share slot 1.
After doubling to 8 slots all four keys have their own slot, so the remainders changed and each key had to be placed again.

Using key 1 again moves it to the end, so the least recently used key is always first in the dictionary.

Module quiz

Questions from the whole module. Your first answer is your score.

Problems

Graded easy to hard, using everything from this module.

Try each one yourself first. Use the hint if you get stuck. Mark it as done when it works.

Exercise 1· Easy

Print the slots (key % 7) of keys [15, 22, 29, 8] as a list.

Expected output

[1, 1, 1, 1]

Exercise 2· Easy

Print the load factor of a table with 24 keys in 32 slots.

Expected output

0.75

Exercise 3· Easy

Print the number of different words in ["pen", "ink", "pen", "pad", "ink"] using a set.

Expected output

Exercise 4· Medium

Insert [10, 18, 26, 3] into 8 slots with linear probing and print the table.

Expected output

[None, None, 10, 18, 26, 3, None, None]

Exercise 5· Medium

Print how many resizes happen for 100 inserts when the capacity starts at 4 and doubles if count is more than 0.75 of the capacity.

Expected output

Exercise 6· Medium

Count the pairs of equal numbers (i < j) in [1, 3, 1, 3, 3, 2] with a dictionary of counts.

Expected output

Exercise 7· Hard

A cache of capacity 2 gets the keys [1, 2, 1, 3, 2]. Using LRU eviction, print the keys left in the cache from oldest to newest.

Expected output

[3, 2]

Exercise 8· Hard

Print the length of the longest stretch of distinct numbers in [4, 2, 4, 5, 6, 2, 7] (a window with no repeats), using a dictionary of last positions.

Expected output

Interview questions

Questions interviewers ask on this topic.

Finish up

Mark complete & continue

Next: Must-do problems: Hash Tables from Scratch

Hash Tables from Scratch Checkpoint

Optional

28 min · Intermediate

Need help? Ask a tutor

A review of this module. Skip it if you feel confident; the next module does not need it.

Fix the mistakes

The slips that cost marks in this module. Spot each one, then check the fix.

This checkpoint mixes slots, collisions, resizing and designs. Work each answer out by hand, then run the code to check it.

Slots, collisions and probing

Given a table size and keys, you should be able to say each key's slot, which keys collide, and where linear probing places them. Work it out on paper first, then check with code.

Python

1slots = [None] * 52for key in [12, 7, 22, 3]:3    i = key % 54    while slots[i] is not None:5        i = (i + 1) % 56    slots[i] = key7print(slots)

Example 1 · Anagram groups by counting

Python

words = ["tea", "eat", "tan", "ate", "nat", "bat"]groups = {}for word in words:    groups.setdefault("".join(sorted(word)), []).append(word)print(len(groups), sorted(map(len, groups.values())))

Output

3 [1, 2, 3]

What this code does

Words with the same sorted letters share a key, so the dictionary groups them in one pass.
The keys are strings, so a hash is used, but only the grouping is printed, which does not depend on the hash value.

Keys 12, 7 and 22 all start at slot 2. They take slots 2, 3 and 4. Key 3 wants slot 3, finds it taken and moves on to slot 4, then wraps to slot 0.

Load factor and resizing

A table grows when it is too full. Know the load factor, the doubling rule and why a resize rehashes every key. Count how many times a table doubles for a given number of inserts.

Python

1capacity, resizes = 4, 02for count in range(1, 41):3    if count > 0.75 * capacity:4        capacity *= 25        resizes += 16print(capacity, resizes)

Example 2 · First repeated order id

Python

1ids = [41, 17, 8, 17, 41, 99]2seen = set()3for order in ids:4    if order in seen:5        print(order)6        break7    seen.add(order)

Output

What this code does

A set answers "seen before?" in constant time on average.
The scan stops at the first repeat, 17. A nested loop would take O(n squared) time.

The table doubles from 4 to 8 at the 4th key, to 16 at the 7th, to 32 at the 13th and to 64 at the 25th. A table with 40 keys ends at 64 slots after 4 resizes.

Hash map in a design

When a problem needs constant-time lookup plus order, a random pick or a count, pair a dictionary with a second structure. Say the time and the space out loud: here O(1) per operation and O(n) space.

Python

1from collections import OrderedDict2recent = OrderedDict()3for key in [1, 2, 1, 3]:4    recent[key] = True5    recent.move_to_end(key)6print(list(recent))

Example 3 · Resize moves keys

Python

keys = [5, 9, 14, 3]print([k % 4 for k in keys])print([k % 8 for k in keys])

Output

[1, 1, 2, 3]
[5, 1, 6, 3]

What this code does

With 4 slots keys 5 and 9 share slot 1.
After doubling to 8 slots all four keys have their own slot, so the remainders changed and each key had to be placed again.

Using key 1 again moves it to the end, so the least recently used key is always first in the dictionary.

Module quiz

Questions from the whole module. Your first answer is your score.

Pick an answer to see if it is right. 0/12 answered.

Question 1 of 12

A hash function must give equal keys:

Question 2 of 12

Keys 4, 12 and 20 go into 8 slots. How many different slots are used?

Question 3 of 12

What does this print?

Python

1slots = [None] * 52for key in [12, 7, 22]:3    i = key % 54    while slots[i] is not None:5        i = (i + 1) % 56    slots[i] = key7print(slots)

Question 4 of 12

Why is a tombstone used when deleting in open addressing?

Question 5 of 12

What does this print?

Python

capacity = 4for count in range(1, 7):    if count > 0.75 * capacity:        capacity *= 2print(capacity)

Question 6 of 12

Why is average insert O(1) although a resize costs O(n)?

Question 7 of 12

In chaining, lookup cost is mainly decided by:

Question 8 of 12

Which data structure pair gives an O(1) LRU cache by hand?

Question 9 of 12

What does this print?

Python

left = {"a": 1, "b": 2}print(left.keys() == {"a", "b"})

Question 10 of 12

Which cannot be used as a key?

Question 11 of 12

In swap-delete, what do you do after copying the last item into the freed place?

Question 12 of 12

A plain string `hash()` printed twice in two runs of Python:

Problems

Graded easy to hard, using everything from this module.

Try each one yourself first. Use the hint if you get stuck. Mark it as done when it works.

Exercise 1· Easy

Print the slots (key % 7) of keys [15, 22, 29, 8] as a list.

Expected output

[1, 1, 1, 1]

Exercise 2· Easy

Print the load factor of a table with 24 keys in 32 slots.

Expected output

0.75

Exercise 3· Easy

Print the number of different words in ["pen", "ink", "pen", "pad", "ink"] using a set.

Expected output

Exercise 4· Medium

Insert [10, 18, 26, 3] into 8 slots with linear probing and print the table.

Expected output

[None, None, 10, 18, 26, 3, None, None]

Exercise 5· Medium

Print how many resizes happen for 100 inserts when the capacity starts at 4 and doubles if count is more than 0.75 of the capacity.

Expected output

Exercise 6· Medium

Count the pairs of equal numbers (i < j) in [1, 3, 1, 3, 3, 2] with a dictionary of counts.

Expected output

Exercise 7· Hard

A cache of capacity 2 gets the keys [1, 2, 1, 3, 2]. Using LRU eviction, print the keys left in the cache from oldest to newest.

Expected output

[3, 2]

Exercise 8· Hard

Print the length of the longest stretch of distinct numbers in [4, 2, 4, 5, 6, 2, 7] (a window with no repeats), using a dictionary of last positions.

Expected output

Interview questions

Questions interviewers ask on this topic.

5 questions. Answer out loud first, then compare.

Finish up

Mark complete & continue

Next: Must-do problems: Hash Tables from Scratch

Slots, collisions and probing

What this code does

Load factor and resizing

What this code does

Hash map in a design

What this code does

Exercise 1· Easy

Exercise 2· Easy

Exercise 3· Easy

Exercise 4· Medium

Exercise 5· Medium

Exercise 6· Medium

Exercise 7· Hard

Exercise 8· Hard

Slots, collisions and probing

What this code does

Load factor and resizing

What this code does

Hash map in a design

What this code does

A hash function must give equal keys:

Keys 4, 12 and 20 go into 8 slots. How many different slots are used?

What does this print?

Why is a tombstone used when deleting in open addressing?

What does this print?

Why is average insert O(1) although a resize costs O(n)?

In chaining, lookup cost is mainly decided by:

Which data structure pair gives an O(1) LRU cache by hand?

What does this print?

Which cannot be used as a key?

In swap-delete, what do you do after copying the last item into the freed place?

A plain string hash() printed twice in two runs of Python:

Exercise 1· Easy

Exercise 2· Easy

Exercise 3· Easy

Exercise 4· Medium

Exercise 5· Medium

Exercise 6· Medium

Exercise 7· Hard

Exercise 8· Hard

Q1Walk through what happens when you insert into a hash table.

Q2Compare chaining and linear probing.

Q3Why is a resize needed and what does it cost?

Q4Describe an LRU cache.

Q5When would you pick a set or dict over a list?

A hash function must give equal keys:

Keys 4, 12 and 20 go into 8 slots. How many different slots are used?

What does this print?

Why is a tombstone used when deleting in open addressing?

What does this print?

Why is average insert O(1) although a resize costs O(n)?

In chaining, lookup cost is mainly decided by:

Which data structure pair gives an O(1) LRU cache by hand?

What does this print?

Which cannot be used as a key?

In swap-delete, what do you do after copying the last item into the freed place?

A plain string hash() printed twice in two runs of Python:

Q1Walk through what happens when you insert into a hash table.

Q2Compare chaining and linear probing.

Q3Why is a resize needed and what does it cost?

Q4Describe an LRU cache.

Q5When would you pick a set or dict over a list?

A plain string `hash()` printed twice in two runs of Python:

A plain string `hash()` printed twice in two runs of Python: