Implement core data structures from scratch, with tests
You don’t really understand a data structure until you’ve built it and broken it. You implement the three that show up in almost every codebase, a hash map, an LRU cache, and a trie, with a real test suite and honest complexity analysis, not a copy from the standard library.
What you'll build
Clean, fully-tested implementations of a hash map (with collision handling and resizing), an LRU cache (O(1) get/put), and a trie, each with documented time/space complexity, edge-case tests, and a benchmark comparing your hash map against the language’s built-in map.
See how we teach, before you sign up
You don't just get code dumped on you. Every starter file and every solution is explained line-by-line, in plain English. Here's one real file from this project:
_EMPTY = object() # never-used slot
_TOMBSTONE = object() # deleted slot (open addressing)
class HashMap:
"""Open-addressing hash map. You implement the bodies."""
def __init__(self, capacity: int = 8, load_factor: float = 0.75) -> None:
self._cap = capacity
self._load_factor = load_factor
self._size = 0
self._slots = [_EMPTY] * capacity # each slot: _EMPTY | _TOMBSTONE | (key, value)
self.collisions = 0
self.resizes = 0
def put(self, key, value) -> None:
raise NotImplementedError
def get(self, key):
raise NotImplementedError
def delete(self, key) -> bool:
raise NotImplementedError
def stats(self) -> dict:
return {
"size": self._size,
"capacity": self._cap,
"load_factor": self._size / self._cap,
"collisions": self.collisions,
"resizes": self.resizes,
}Reading this file
_EMPTY = object()A unique sentinel marking an untouched slot, using a private object means it can never collide with a real key._TOMBSTONE = object()Marks a slot whose key was deleted so lookups keep probing past it instead of stopping early.load_factor: float = 0.75The fullness threshold, once the table passes 75 percent full it resizes to keep operations fast.self._slots = [_EMPTY] * capacityThe backing array, every key lands in one of these slots; this is the storage the whole map is built on.self.collisions = 0A counter you increment when a key's home slot is taken, the single most useful health metric for a hash map.raise NotImplementedErrorA placeholder that forces the tests to fail until you write the real logic, your starting point.
The interface to fill in. Tests import HashMap and exercise put/get/delete + stats().
That's 1 of 7 explained code blocks in this single project.
The build, milestone by milestone
- 1
Build a hash map from first principles
5 guided stepsThe hash map is the most-used structure in software and the most-asked-about in interviews. Building one forces you to confront hashing, collisions, and amortized cost, concepts you only half-know until you implement them.
- 2
Build an O(1) LRU cache
5 guided stepsThe LRU cache is the canonical “compose two structures to beat a complexity bound” problem, a hash map alone can’t do O(1) eviction, and a list alone can’t do O(1) lookup. Caches like this sit in front of nearly every real database.
- 3
Build a trie and prove the complexity
5 guided stepsTries trade memory for blazing prefix lookups, the foundation of autocomplete (your next capstone). Writing the complexity table for all three forces you to reason about cost honestly instead of guessing.
- 4
Instrument the structures and put a number on the memory cost
5 guided stepsA structure’s real cost is not just operation time, it is collisions, resizes, and bytes held. Cheap instrumentation turns invisible behaviour into numbers, the same way a metric or a memory profiler does in production.
What's inside when you start
You'll walk away with
This is portfolio-grade. Build it free.
Sign up to unlock every milestone step-by-step, the code skeletons, full reference solutions, and checkable tasks, with your progress saved as you build.
Start building