Week 11 of 125
Crafting Interpreters, chapters 20 and 21
Sign up or sign in to tick these off and give this week a due date.
-
A hash table from scratch with open addressing and linear probing, FNV-1a hashing, tombstones for deletion, growth by load factor, and string interning so string equality becomes pointer equality.
Time About 7 hours this week
Why it matters
Hash tables are the most used data structure in practice. Building one yourself demystifies every dictionary and map you use, and Knuth 6.4 later analyzes exactly this design.
How to approach it
Implement, then write a small stress test that inserts and deletes many keys and checks lookups. Re-read the tombstone section twice; it is the subtle part.
Challenges
3 challenges at the end of the chapter.
Challenge 1 (support non-string keys) and challenge 2 (tune and compare hash table designs) are great; challenge 3 (benchmarking) pairs well with 2.
Traps
- Not treating tombstones correctly on insert versus lookup.
- Infinite loop when the table has no empty slots (load factor too high).
- Counting tombstones in the load factor or not, inconsistently.
-
Statements and global variables in clox: print and expression statements, declarations, global variable get and set via the hash table, and assignment with correct precedence.
Time About 5 hours this week
Why it matters
Shows how a single-pass compiler handles declarations and l-values, a trickier problem than in jlox.
How to approach it
Pay attention to how the canAssign flag prevents invalid assignment targets. Test with expressions like a * b = c.
Challenges
3 challenges at the end of the chapter.
Challenge 1 (stop adding duplicate name constants) and challenge 2 (faster global lookup) are both good engineering exercises. Challenge 3 (REPL-friendly forward references) is a design puzzle.
Traps
- Invalid assignment targets silently accepted when canAssign is not threaded through correctly.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.