Build an Autocomplete Engine
Build a trie, hash map, and heap from scratch to power a ranked autocomplete CLI.
Introduction
30 Second Summary
Every time you type into a search bar, your phone's keyboard, or a code editor, an autocomplete engine races to predict what you want before you finish typing.
In this project, you will build a fully functional autocomplete engine from scratch using three core data structures: a custom hash map, a trie (prefix tree), and a min-heap for ranking.
What You'll Build
An interactive CLI autocomplete tool that serves instant, frequency-ranked prefix suggestions from a 50,000-word dataset.
By the end of this project, you'll have:
- A custom hash map with separate chaining and dynamic resizing that demonstrates why hash maps struggle with prefix operations.
- A trie that stores words character-by-character and returns ranked autocomplete suggestions using a min-heap.
- A benchmark suite with measurable proof of when each data structure wins and loses.
- Secret Mission: Add fuzzy matching with Levenshtein distance so your engine handles typos gracefully.
Are there any prerequisites?
This project assumes strong Python fundamentals including classes, type hints, recursion, and decorators.
You do not need prior experience with data structure implementation. The project teaches each structure from scratch.
Set Up the Project
Every autocomplete engine needs data to search through. Before you can build the data structures that power prefix lookups, you need a realistic dataset that mimics how word frequencies work in the real world.
In this step, you will create a data generator script that produces 50,000 words with frequency scores following Zipf's law. This is the same distribution found in natural language: a handful of words appear constantly, while most are rare.
In this step, get ready to:
- Create the data generation script for your autocomplete engine.
- Run the script to produce a 50,000-word frequency dataset.
- Verify the output file format is correct.
Create the data generator file
Your project folder is open in VS Code and ready for files. The first file you need is generate_data.py, the script that will build your word dataset.
- In the VS Code Explorer sidebar on the left, hover over your project folder name.
- Click the New File icon (the page icon with a plus sign) that appears.
- Type generate_data.py and press Enter.
The file opens in the editor, ready for code.
Write the word generation script
The generator uses lists of prefixes, roots, and suffixes to build compound words. It also includes a set of common English words that get high frequency scores. This mirrors real language data where words like "the" and "is" dominate.
- In generate_data.py, add the imports, function definition, and word lists by pasting this code:
"""Generate word frequency data for the autocomplete engine."""
import random
import string
def generate_word_data(num_words: int = 50000, output_file: str = "words.txt") -> None:
"""Generate a synthetic word frequency dataset.
Creates words with realistic frequency distributions following
Zipf's law: a few words are very common, most are rare.
"""
prefixes = [
"un", "re", "in", "dis", "en", "non", "pre", "mis", "over", "sub",
"inter", "trans", "super", "auto", "anti", "de", "fore", "mid",
"out", "semi", "under", "co", "counter", "cross", "ex", "multi",
]
roots = [
"act", "form", "port", "ject", "tend", "duct", "struct", "scribe",
"press", "tract", "vert", "mit", "pend", "cede", "fer", "pose",
"graph", "log", "path", "phon", "scope", "spec", "spect", "voc",
"dict", "rupt", "sect", "sequ", "sist", "solv", "vers", "vis",
"cap", "cept", "cred", "cur", "fac", "flect", "grad", "gress",
"ling", "man", "nat", "nov", "oper", "plic", "pon", "popul",
"sens", "sign", "simil", "stab", "tempt", "terr", "val", "ven",
]
suffixes = [
"tion", "sion", "ment", "ness", "able", "ible", "ful", "less",
"ous", "ive", "al", "ial", "ing", "ed", "er", "est", "ly",
"ity", "ty", "ance", "ence", "dom", "ship", "ism", "ist",
]
common_words = [
"the", "be", "to", "of", "and", "a", "in", "that", "have", "it",
"for", "not", "on", "with", "he", "as", "you", "do", "at", "this",
"but", "his", "by", "from", "they", "we", "say", "her", "she",
"or", "an", "will", "my", "one", "all", "would", "there", "their",
"what", "so", "up", "out", "if", "about", "who", "get", "which",
"go", "me", "when", "make", "can", "like", "time", "no", "just",
"him", "know", "take", "people", "into", "year", "your", "good",
"some", "could", "them", "see", "other", "than", "then", "now",
"look", "only", "come", "its", "over", "think", "also", "back",
"after", "use", "two", "how", "our", "work", "first", "well",
"way", "even", "new", "want", "because", "any", "these", "give",
"day", "most", "us", "program", "data", "process", "function",
"method", "class", "object", "array", "list", "string", "number",
"value", "type", "code", "file", "name", "test", "error", "result",
"index", "key", "node", "tree", "graph", "search", "sort",
"algorithm", "structure", "queue", "stack", "hash", "table",
"link", "point", "set", "map", "run", "build", "start", "end",
"open", "close", "read", "write", "print", "input", "output",
"return", "break", "continue", "while", "loop", "check", "system",
"network", "server", "client", "request", "response", "database",
"memory", "thread", "lock", "buffer", "cache", "stream", "packet",
"protocol", "interface", "module", "package", "library", "framework",
]What do these word lists do?
The generator combines prefixes, roots, and suffixes to produce realistic compound words like "restructure" or "transplant". The common_words list seeds the dataset with high-frequency everyday words.
This approach gives you a dataset with variety (many unique words) and realism (frequency distribution that matches natural language).
- Below the common_words list (still inside the function), add the generation logic that combines these word parts and writes them to a file:
random.seed(42)
words_with_freq: dict[str, int] = {}
# High-frequency common words (Zipf distribution)
for i, word in enumerate(common_words):
freq = max(100, int(100000 / (i + 1)))
words_with_freq[word] = freq
# Generate compound words to fill the dataset
while len(words_with_freq) < num_words:
strategy = random.randint(0, 3)
if strategy == 0:
word = random.choice(prefixes) + random.choice(roots)
elif strategy == 1:
word = random.choice(roots) + random.choice(suffixes)
elif strategy == 2:
word = random.choice(prefixes) + random.choice(roots) + random.choice(suffixes)
else:
length = random.randint(3, 12)
word = "".join(random.choices(string.ascii_lowercase, k=length))
if word not in words_with_freq and len(word) >= 2:
rank = len(words_with_freq)
freq = max(1, int(50000 / (rank + 1)) + random.randint(1, 20))
words_with_freq[word] = freq
with open(output_file, "w", encoding="utf-8") as f:
for word, freq in sorted(words_with_freq.items()):
f.write(f"{word}\t{freq}\n")
print(f"Generated {len(words_with_freq):,} words with frequencies -> {output_file}")
if __name__ == "__main__":
generate_word_data()What does this generation logic do?
The random.seed(42) ensures everyone gets the same dataset. The first loop assigns frequencies to common words using Zipf's law: the first word gets frequency 100,000, the second gets 50,000, the tenth gets 10,000, and so on.
The while loop fills the remaining 50,000 slots by combining prefixes, roots, and suffixes into compound words. Each generated word gets a lower frequency based on its rank. This mimics how real dictionaries have many rare words but few common ones.
Finally, the script writes each word and its frequency to words.txt as tab-separated pairs, sorted alphabetically.
- Save generate_data.py by pressing Cmd+S (macOS) or Ctrl+S (Windows).
✔️ Awesome, I've got everything!
Great. Make sure you have saved your file before moving on.
ⓧ I'd like to double check the full code
"""Generate word frequency data for the autocomplete engine."""
import random
import string
def generate_word_data(num_words: int = 50000, output_file: str = "words.txt") -> None:
"""Generate a synthetic word frequency dataset.
Creates words with realistic frequency distributions following
Zipf's law: a few words are very common, most are rare.
"""
prefixes = [
"un", "re", "in", "dis", "en", "non", "pre", "mis", "over", "sub",
"inter", "trans", "super", "auto", "anti", "de", "fore", "mid",
"out", "semi", "under", "co", "counter", "cross", "ex", "multi",
]
roots = [
"act", "form", "port", "ject", "tend", "duct", "struct", "scribe",
"press", "tract", "vert", "mit", "pend", "cede", "fer", "pose",
"graph", "log", "path", "phon", "scope", "spec", "spect", "voc",
"dict", "rupt", "sect", "sequ", "sist", "solv", "vers", "vis",
"cap", "cept", "cred", "cur", "fac", "flect", "grad", "gress",
"ling", "man", "nat", "nov", "oper", "plic", "pon", "popul",
"sens", "sign", "simil", "stab", "tempt", "terr", "val", "ven",
]
suffixes = [
"tion", "sion", "ment", "ness", "able", "ible", "ful", "less",
"ous", "ive", "al", "ial", "ing", "ed", "er", "est", "ly",
"ity", "ty", "ance", "ence", "dom", "ship", "ism", "ist",
]
common_words = [
"the", "be", "to", "of", "and", "a", "in", "that", "have", "it",
"for", "not", "on", "with", "he", "as", "you", "do", "at", "this",
"but", "his", "by", "from", "they", "we", "say", "her", "she",
"or", "an", "will", "my", "one", "all", "would", "there", "their",
"what", "so", "up", "out", "if", "about", "who", "get", "which",
"go", "me", "when", "make", "can", "like", "time", "no", "just",
"him", "know", "take", "people", "into", "year", "your", "good",
"some", "could", "them", "see", "other", "than", "then", "now",
"look", "only", "come", "its", "over", "think", "also", "back",
"after", "use", "two", "how", "our", "work", "first", "well",
"way", "even", "new", "want", "because", "any", "these", "give",
"day", "most", "us", "program", "data", "process", "function",
"method", "class", "object", "array", "list", "string", "number",
"value", "type", "code", "file", "name", "test", "error", "result",
"index", "key", "node", "tree", "graph", "search", "sort",
"algorithm", "structure", "queue", "stack", "hash", "table",
"link", "point", "set", "map", "run", "build", "start", "end",
"open", "close", "read", "write", "print", "input", "output",
"return", "break", "continue", "while", "loop", "check", "system",
"network", "server", "client", "request", "response", "database",
"memory", "thread", "lock", "buffer", "cache", "stream", "packet",
"protocol", "interface", "module", "package", "library", "framework",
]
random.seed(42)
words_with_freq: dict[str, int] = {}
# High-frequency common words (Zipf distribution)
for i, word in enumerate(common_words):
freq = max(100, int(100000 / (i + 1)))
words_with_freq[word] = freq
# Generate compound words to fill the dataset
while len(words_with_freq) < num_words:
strategy = random.randint(0, 3)
if strategy == 0:
word = random.choice(prefixes) + random.choice(roots)
elif strategy == 1:
word = random.choice(roots) + random.choice(suffixes)
elif strategy == 2:
word = random.choice(prefixes) + random.choice(roots) + random.choice(suffixes)
else:
length = random.randint(3, 12)
word = "".join(random.choices(string.ascii_lowercase, k=length))
if word not in words_with_freq and len(word) >= 2:
rank = len(words_with_freq)
freq = max(1, int(50000 / (rank + 1)) + random.randint(1, 20))
words_with_freq[word] = freq
with open(output_file, "w", encoding="utf-8") as f:
for word, freq in sorted(words_with_freq.items()):
f.write(f"{word}\t{freq}\n")
print(f"Generated {len(words_with_freq):,} words with frequencies -> {output_file}")
if __name__ == "__main__":
generate_word_data()Run the generator to produce your dataset
Now you will execute the script to produce the 50,000-word frequency file that your autocomplete engine will search through.
- Run the data generator by entering this command in your terminal:
python generate_data.py- You should see this output:
Generated 50,000 words with frequencies -> words.txtSeeing a ModuleNotFoundError or SyntaxError?
- Check that your file is saved. Unsaved changes in VS Code show a dot on the file tab.
- Make sure you are running the command from the same folder where generate_data.py lives. Run ls to confirm the file is in your current directory.
- If you see a syntax error, double check that the code in the double-check tab above matches your file exactly.
Help me debug my generate_data.py script
Verify the generated data file
The script should have created words.txt in your project folder. Each line contains a word and its frequency score separated by a tab character.
- Confirm the file exists by running:
ls- You should see both generate_data.py and words.txt listed in the output.
- Inspect the first 10 lines of the file by running:
head -10 words.txtWhat should I see?
Each line shows a word, a tab character, and a number. The words are sorted alphabetically. You will see entries like:
a 100000
about 2380
act 20
after 1190The number after each word is its frequency score. Notice how common words like "a" have very high frequencies (100,000) while less common words have much lower scores. This is Zipf's law in action.
On Windows without head
If head is not available, open words.txt directly in VS Code by clicking it in the Explorer sidebar. Scroll through the first few lines to confirm the tab-separated format.
Your dataset is ready. Next up, you will build a custom hash map from scratch and discover exactly why it struggles with the prefix searches that autocomplete needs.
Build the Custom Hash Map
Your project folder is ready and you have a 50,000-word dataset to work with. Now it's time to build the first data structure that will power your autocomplete engine.
A hash map is the go-to choice when you need fast exact lookups. You'll build one from scratch to understand how hashing, collision resolution, and dynamic resizing actually work under the hood. Then you'll discover its fatal weakness: prefix search.
In this step, get ready to:
- Implement a polynomial rolling hash function and the hash map skeleton.
- Add core operations (put, get, contains) with separate chaining and dynamic resizing.
- Expose the hash map's O(n) prefix search weakness.
Create the hash map skeleton and hash function
Every hash map needs two things: an array of buckets to store data, and a hash function to decide which bucket each key goes into. The quality of your hash function determines how evenly keys spread across buckets.
- Create a new file called hashmap.py in your project folder.
- Add the class definition, constructor, and hash function by pasting this code:
"""Custom hash map implementation with separate chaining."""
class HashMap:
"""Hash map using separate chaining for collision resolution.
Demonstrates why hash maps excel at exact lookups but struggle
with prefix-based operations.
"""
def __init__(self, initial_capacity: int = 16, load_factor: float = 0.75) -> None:
self._capacity = initial_capacity
self._load_factor = load_factor
self._size = 0
self._buckets: list[list[tuple[str, int]]] = [[] for _ in range(self._capacity)]
def _hash(self, key: str) -> int:
"""Compute bucket index using a polynomial rolling hash.
Multiplier 31 is a common choice: it's an odd prime that
distributes characters well across buckets. The bitmask
keeps the value in 32-bit range before taking modulo.
"""
h = 0
for char in key:
h = (h * 31 + ord(char)) & 0xFFFFFFFF
return h % self._capacityWhat does this code do?
The constructor sets up an array of empty lists (buckets). Each bucket will hold key-value pairs that hash to the same index.
The _hash method converts a string key into a bucket index. It multiplies a running total by 31 and adds each character's numeric value. The & 0xFFFFFFFF bitmask keeps the number within 32-bit range to prevent overflow issues.
Why 31 as the multiplier?
The number 31 is an odd prime that produces a good distribution of hash values for string data. It's the same multiplier Java uses in its String.hashCode() method. Being odd means it avoids the information loss that even multipliers cause through bit-shifting.
You won't see output yet. The next chunk adds the methods that use this hash function.
Implement put, get, contains, and dynamic resizing
A hash map that can only hash keys is useless. You need methods to insert data, retrieve it, and grow the table when it gets too full. When the ratio of stored keys to total buckets exceeds the load factor (0.75), the table doubles in size and rehashes everything.
- In hashmap.py, add the resize and put methods directly below the _hash method:
def _resize(self) -> None:
"""Double capacity and rehash all entries."""
old_buckets = self._buckets
self._capacity *= 2
self._buckets = [[] for _ in range(self._capacity)]
self._size = 0
for bucket in old_buckets:
for key, value in bucket:
self.put(key, value)
def put(self, key: str, value: int) -> None:
"""Insert or update a key-value pair."""
if self._size / self._capacity >= self._load_factor:
self._resize()
index = self._hash(key)
bucket = self._buckets[index]
for i, (k, _) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
self._size += 1What does this code do?
- _resize doubles the bucket array and re-inserts every existing key. This keeps chains short and lookups fast.
- put first checks if the load factor is exceeded, triggering a resize if needed. Then it hashes the key, scans the target bucket for duplicates, and either updates or appends.
- This is separate chaining in action: multiple keys can live in the same bucket as a list of tuples. Collisions don't cause data loss.
You won't see a change yet. The read methods come next.
- Below the put method, add the get and contains methods:
def get(self, key: str) -> int | None:
"""Retrieve value by exact key. O(1) average case."""
index = self._hash(key)
for k, v in self._buckets[index]:
if k == key:
return v
return None
def contains(self, key: str) -> bool:
"""Check if key exists. O(1) average case."""
return self.get(key) is not NoneWhat does this code do?
get hashes the key to find the right bucket, then scans that bucket's chain for an exact match. On average, each bucket has very few items, so this is O(1).
contains simply delegates to get and checks whether the result is None.
- Save hashmap.py.
- Test your hash map by running this in the terminal:
python -c "from hashmap import HashMap; h = HashMap(); h.put('algorithm', 500); print(h.get('algorithm'))"You should see 500 printed in the terminal.
Seeing an error?
- If you see an indentation error, make sure all methods are indented one level inside the HashMap class (4 spaces).
- If you see a name error for HashMap, confirm your file is saved as hashmap.py (lowercase) in the same folder where you're running the command.
- If the output is None instead of 500, double check the put method appends to the bucket correctly.
Why is my hash map returning None instead of the value I stored?
Add prefix search to expose the hash map's weakness
Hash maps are brilliant at answering "does this exact key exist?" in O(1) time. But autocomplete needs to answer "what words start with this prefix?" That question forces the hash map to scan every single key, because hashing destroys any relationship between similar strings.
- Below the contains method, add keys_with_prefix and the utility methods:
def keys_with_prefix(self, prefix: str) -> list[tuple[str, int]]:
"""Find all keys starting with prefix.
THIS IS THE WEAK SPOT: must scan every single key in the map.
O(n) where n is the total number of keys, regardless of how
few actually match the prefix.
"""
results = []
for bucket in self._buckets:
for key, value in bucket:
if key.startswith(prefix):
results.append((key, value))
return results
def __len__(self) -> int:
return self._size
def __contains__(self, key: str) -> bool:
return self.contains(key)
@property
def capacity(self) -> int:
return self._capacity
@property
def load(self) -> float:
return self._size / self._capacityWhy is this O(n)?
The hash function maps "algorithm" and "alpha" to completely unrelated buckets. There's no way to say "give me everything that starts with 'al'" without checking every single stored key. Even if only 5 out of 50,000 words match, you still scan all 50,000.
This is the exact problem a trie solves. In the next step, you'll build a structure where prefix search only visits the relevant branch.
- Save hashmap.py.
- Test the prefix search by running this in the terminal:
python -c "from hashmap import HashMap; h = HashMap(); h.put('algorithm', 500); h.put('alpha', 300); h.put('beta', 200); print(h.keys_with_prefix('al'))"You should see a list containing both ('algorithm', 500) and ('alpha', 300) (order may vary).
Seeing an empty list?
- Make sure keys_with_prefix iterates over self._buckets, not self._buckets[index]. It needs to scan ALL buckets.
- Confirm you're using key.startswith(prefix) (not ==) to match partial strings.
Why is my keys_with_prefix returning an empty list?
✔️ Awesome, I've got everything!
Great. Double check you've saved hashmap.py and move on to the next step.
ⓧ I'd like to double check the full code
"""Custom hash map implementation with separate chaining."""
class HashMap:
"""Hash map using separate chaining for collision resolution.
Demonstrates why hash maps excel at exact lookups but struggle
with prefix-based operations.
"""
def __init__(self, initial_capacity: int = 16, load_factor: float = 0.75) -> None:
self._capacity = initial_capacity
self._load_factor = load_factor
self._size = 0
self._buckets: list[list[tuple[str, int]]] = [[] for _ in range(self._capacity)]
def _hash(self, key: str) -> int:
"""Compute bucket index using a polynomial rolling hash.
Multiplier 31 is a common choice: it's an odd prime that
distributes characters well across buckets. The bitmask
keeps the value in 32-bit range before taking modulo.
"""
h = 0
for char in key:
h = (h * 31 + ord(char)) & 0xFFFFFFFF
return h % self._capacity
def _resize(self) -> None:
"""Double capacity and rehash all entries."""
old_buckets = self._buckets
self._capacity *= 2
self._buckets = [[] for _ in range(self._capacity)]
self._size = 0
for bucket in old_buckets:
for key, value in bucket:
self.put(key, value)
def put(self, key: str, value: int) -> None:
"""Insert or update a key-value pair."""
if self._size / self._capacity >= self._load_factor:
self._resize()
index = self._hash(key)
bucket = self._buckets[index]
for i, (k, _) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
self._size += 1
def get(self, key: str) -> int | None:
"""Retrieve value by exact key. O(1) average case."""
index = self._hash(key)
for k, v in self._buckets[index]:
if k == key:
return v
return None
def contains(self, key: str) -> bool:
"""Check if key exists. O(1) average case."""
return self.get(key) is not None
def keys_with_prefix(self, prefix: str) -> list[tuple[str, int]]:
"""Find all keys starting with prefix.
THIS IS THE WEAK SPOT: must scan every single key in the map.
O(n) where n is the total number of keys, regardless of how
few actually match the prefix.
"""
results = []
for bucket in self._buckets:
for key, value in bucket:
if key.startswith(prefix):
results.append((key, value))
return results
def __len__(self) -> int:
return self._size
def __contains__(self, key: str) -> bool:
return self.contains(key)
@property
def capacity(self) -> int:
return self._capacity
@property
def load(self) -> float:
return self._size / self._capacityYour hash map is complete. It's fast for exact lookups, but you've seen the cost of prefix search firsthand. Next up, you'll build a trie that solves this exact problem by storing words character-by-character.
Build the Trie
Your hash map works perfectly for exact lookups. But you exposed its fatal flaw: finding all words starting with a prefix requires scanning every single key.
A trie (prefix tree) solves this by storing words character-by-character. Instead of scanning 50,000 keys, a prefix lookup only traverses the length of the prefix itself. In this step, you'll build a trie from scratch and pair it with a min-heap to rank results by frequency.
In this step, get ready to:
- Create the TrieNode and Trie classes with an insert method.
- Implement prefix traversal for fast lookups.
- Add frequency-ranked autocomplete using a min-heap.
Create the TrieNode and Trie classes
A trie stores words as paths through a tree. Each node represents a single character, and a path from root to a terminal node spells out a complete word.
- Create a new file called trie.py in your project folder.
- Add the module header, import, and TrieNode class by copying this code:
"""Trie (prefix tree) implementation for fast autocomplete."""
import heapq
class TrieNode:
"""A single node in the trie."""
__slots__ = ("children", "is_end", "frequency", "word")
def __init__(self) -> None:
self.children: dict[str, TrieNode] = {}
self.is_end: bool = False
self.frequency: int = 0
self.word: str = ""What does this code do?
Each TrieNode holds four things: a dictionary of child nodes (one per character), a flag indicating whether this node ends a word, the word's frequency score, and the full word string itself.
__slots__ tells Python to skip creating a __dict__ for each node. With 50,000 words creating hundreds of thousands of nodes, this saves significant memory.
You won't see a change yet. The next chunk builds the Trie class that uses these nodes.
- Add the Trie class with its constructor and insert method below the TrieNode class:
class Trie:
"""Prefix tree optimized for autocomplete operations.
Stores words character-by-character so prefix lookups only
traverse the prefix length, not the entire dataset.
"""
def __init__(self) -> None:
self.root = TrieNode()
self._size = 0
def insert(self, word: str, frequency: int = 1) -> None:
"""Insert a word with its frequency score."""
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
if not node.is_end:
self._size += 1
node.is_end = True
node.frequency = frequency
node.word = wordWhat does this code do?
insert walks through the word one character at a time. At each character, it either follows an existing child node or creates a new one. When it reaches the last character, it marks that node as a word ending and stores the frequency.
This means the word "cat" creates three nodes (c -> a -> t), and "car" reuses the c and a nodes, branching at "r". Shared prefixes share nodes.
- Save trie.py.
- Test that insertion works by running this in your terminal:
python -c "from trie import Trie; t = Trie(); t.insert('hello', 100); print(len(t))"You should see 1 printed, confirming one word was inserted.
Seeing an ImportError?
Make sure you saved trie.py and that your terminal is in the same folder as the file. Run ls to confirm you see trie.py listed.
help me debug an ImportError when importing my trie module
Implement prefix traversal with search and starts_with
The power of a trie is prefix traversal. Instead of scanning 50,000 keys like the hash map does, you just follow character links downward. Finding all words starting with "pre" takes exactly 3 steps regardless of dataset size.
- Add the search, starts_with, and _find_node methods to your Trie class, below the insert method:
def search(self, word: str) -> bool:
"""Check if an exact word exists in the trie."""
node = self._find_node(word)
return node is not None and node.is_end
def starts_with(self, prefix: str) -> bool:
"""Check if any word in the trie starts with the given prefix."""
return self._find_node(prefix) is not None
def _find_node(self, prefix: str) -> TrieNode | None:
"""Traverse to the node representing the end of prefix."""
node = self.root
for char in prefix:
if char not in node.children:
return None
node = node.children[char]
return nodeWhat does this code do?
_find_node is the engine behind both methods. It walks down the trie one character at a time. If any character is missing, it returns None immediately. This is O(prefix_length) regardless of how many words are stored.
search checks that the node exists AND marks a complete word. starts_with only checks that the prefix path exists (any word could continue from there).
- Save trie.py and test the prefix traversal by running:
python -c "from trie import Trie; t = Trie(); t.insert('prefix', 50); t.insert('predict', 80); print(t.starts_with('pre'), t.search('prefix'), t.search('pre'))"You should see True True False. The prefix "pre" exists as a path, "prefix" is a complete word, but "pre" alone is not a stored word.
Seeing False True False or all False?
Check that _find_node iterates over each character in the prefix string. A common mistake is iterating over the word's characters in insert but forgetting the matching loop in _find_node.
help me debug my trie search and starts_with methods
Why is this faster than the hash map for prefixes?
Your hash map's keys_with_prefix scans all 50,000 keys every time, checking each one with startswith(). The trie's _find_node jumps directly to the subtree matching the prefix in O(prefix_length) steps. For a 3-character prefix, that is 3 steps vs 50,000 comparisons.
Implement autocomplete with a min-heap for top-K ranking
Finding all words with a prefix is useful, but autocomplete needs the most relevant results. You need the top-K words ranked by frequency. Python's heapq module provides a min-heap that efficiently tracks the highest-frequency words during traversal.
- Add the _collect_words helper method to your Trie class, below _find_node:
def _collect_words(
self, node: TrieNode, min_heap: list[tuple[int, str]], k: int
) -> None:
"""DFS to collect words from subtree, maintaining a top-K heap."""
if node.is_end:
if len(min_heap) < k:
heapq.heappush(min_heap, (node.frequency, node.word))
elif node.frequency > min_heap[0][0]:
heapq.heapreplace(min_heap, (node.frequency, node.word))
for child in node.children.values():
self._collect_words(child, min_heap, k)What does this code do?
This method performs a depth-first search (DFS) through the subtree below the prefix. It maintains a min-heap of size K. The smallest frequency always sits at the top of the heap (min_heap[0][0]).
When the heap has fewer than K items, every word gets pushed in. Once the heap is full, only words with higher frequency than the current minimum replace it (via heapreplace). This gives you the top-K results in O(n log k) time instead of sorting all matches in O(n log n).
You won't see a change yet. The next chunk adds the public autocomplete method that calls this helper.
- Add the autocomplete method and __len__ to your Trie class. Place autocomplete between starts_with and _find_node, and __len__ at the very end of the class:
def autocomplete(self, prefix: str, top_k: int = 10) -> list[tuple[str, int]]:
"""Return top-K words matching prefix, ranked by frequency."""
node = self._find_node(prefix)
if node is None:
return []
min_heap: list[tuple[int, str]] = []
self._collect_words(node, min_heap, top_k)
results = []
while min_heap:
freq, word = heapq.heappop(min_heap)
results.append((word, freq))
results.reverse()
return results
def __len__(self) -> int:
return self._sizeWhat does this code do?
autocomplete first uses _find_node to jump directly to the prefix node. Then it calls _collect_words to DFS through the subtree, collecting the top-K highest-frequency words into the min-heap.
Finally, it pops all items from the heap (which come out in ascending order) and reverses them so the highest-frequency word is first. The result is a list of (word, frequency) tuples ranked from most to least frequent.
- Save trie.py and test the full autocomplete pipeline by running:
python -c "from trie import Trie; t = Trie(); t.insert('program', 500); t.insert('process', 300); t.insert('protocol', 100); t.insert('print', 800); print(t.autocomplete('pro', top_k=3))"You should see [('process', 300), ('protocol', 100), ('program', 500)] or a similar list with the three "pro" words ranked by frequency. The exact order depends on heap tie-breaking, but print should NOT appear (it starts with "pri", not "pro").
Seeing an empty list?
If autocomplete returns [], check that _find_node returns the correct node (not None) and that _collect_words checks node.is_end before pushing to the heap.
Also verify you imported heapq at the top of the file.
help me debug my trie autocomplete returning empty results
✔️ Awesome, I've got everything!
Great. Double check you've saved trie.py before moving on.
ⓧ I'd like to double check the full code
Here is the complete trie.py file. Make sure yours matches:
"""Trie (prefix tree) implementation for fast autocomplete."""
import heapq
class TrieNode:
"""A single node in the trie."""
__slots__ = ("children", "is_end", "frequency", "word")
def __init__(self) -> None:
self.children: dict[str, TrieNode] = {}
self.is_end: bool = False
self.frequency: int = 0
self.word: str = ""
class Trie:
"""Prefix tree optimized for autocomplete operations.
Stores words character-by-character so prefix lookups only
traverse the prefix length, not the entire dataset.
"""
def __init__(self) -> None:
self.root = TrieNode()
self._size = 0
def insert(self, word: str, frequency: int = 1) -> None:
"""Insert a word with its frequency score."""
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
if not node.is_end:
self._size += 1
node.is_end = True
node.frequency = frequency
node.word = word
def search(self, word: str) -> bool:
"""Check if an exact word exists in the trie."""
node = self._find_node(word)
return node is not None and node.is_end
def starts_with(self, prefix: str) -> bool:
"""Check if any word in the trie starts with the given prefix."""
return self._find_node(prefix) is not None
def autocomplete(self, prefix: str, top_k: int = 10) -> list[tuple[str, int]]:
"""Return top-K words matching prefix, ranked by frequency."""
node = self._find_node(prefix)
if node is None:
return []
min_heap: list[tuple[int, str]] = []
self._collect_words(node, min_heap, top_k)
results = []
while min_heap:
freq, word = heapq.heappop(min_heap)
results.append((word, freq))
results.reverse()
return results
def _find_node(self, prefix: str) -> TrieNode | None:
"""Traverse to the node representing the end of prefix."""
node = self.root
for char in prefix:
if char not in node.children:
return None
node = node.children[char]
return node
def _collect_words(
self, node: TrieNode, min_heap: list[tuple[int, str]], k: int
) -> None:
"""DFS to collect words from subtree, maintaining a top-K heap."""
if node.is_end:
if len(min_heap) < k:
heapq.heappush(min_heap, (node.frequency, node.word))
elif node.frequency > min_heap[0][0]:
heapq.heapreplace(min_heap, (node.frequency, node.word))
for child in node.children.values():
self._collect_words(child, min_heap, k)
def __len__(self) -> int:
return self._sizeYour trie is ready. It finds prefix matches in O(prefix_length) and ranks them by frequency using a heap. Next up, you'll wire the trie into an interactive CLI so you can type prefixes and see instant autocomplete suggestions.
Wire Up the Autocomplete Engine
You have a trie that inserts words and returns top-K matches by frequency. You have a hash map that proves why prefix search needs a better structure. Now it's time to wire these pieces into something you can actually use.
In this step, you'll build an interactive CLI that loads the 50,000-word dataset into your trie and serves instant prefix suggestions as you type.
In this step, get ready to:
- Load the full word dataset into the trie engine.
- Build an interactive CLI with ranked autocomplete, visual frequency bars, and custom commands.
Create the data loader and engine builder
The autocomplete engine needs a way to read words.txt and feed its contents into the trie. You'll put the file-loading logic in a module called benchmark.py because the next step will expand it into a full benchmark suite.
- Create a new file called benchmark.py in your project folder.
- Add the data-loading function by pasting this code:
"""Performance benchmarks comparing trie vs hash map for prefix operations."""
def load_word_data(filepath: str) -> list[tuple[str, int]]:
"""Load word frequency data from a tab-separated file."""
words = []
with open(filepath, "r", encoding="utf-8") as f:
for line in f:
line = line.strip()
if "\t" in line:
word, freq = line.split("\t", 1)
words.append((word, int(freq)))
return wordsWhat does this code do?
This function reads each line of words.txt, splits on the tab character, and returns a list of (word, frequency) tuples. It skips any line that doesn't contain a tab, making it resilient to blank lines.
- Save benchmark.py.
Now you'll create the main entry point that loads data and builds the trie.
- Create a new file called main.py in your project folder.
- Add the imports and engine-builder function by pasting this code:
"""Interactive autocomplete CLI combining trie + heap for ranked results."""
import sys
from trie import Trie
from benchmark import load_word_data
def build_engine(filepath: str = "words.txt") -> Trie:
"""Load word data and build the trie-based autocomplete engine."""
print(f"Loading words from {filepath}...")
words = load_word_data(filepath)
trie = Trie()
for word, freq in words:
trie.insert(word, freq)
print(f"Loaded {len(trie):,} words into autocomplete engine.\n")
return trieWhat does this code do?
- It imports your Trie class and the load_word_data helper you just wrote.
- build_engine reads the word file, inserts every word-frequency pair into a fresh trie, then returns the populated trie ready for queries.
- Save main.py. You won't run it yet because the interactive loop comes next.
Add the interactive CLI with frequency bars and commands
The engine can load data, but you need a way to interact with it. The CLI loop accepts prefix queries and displays ranked results with visual frequency bars so you can see relative popularity at a glance.
- In main.py, add the interactive_mode function and the __main__ block below the build_engine function:
def interactive_mode(trie: Trie) -> None:
"""Run the interactive autocomplete loop."""
print("=" * 50)
print(" AUTOCOMPLETE SEARCH ENGINE")
print(" Type a prefix to see suggestions.")
print(" Commands: :quit, :top <n> (set results count)")
print("=" * 50)
top_k = 10
while True:
try:
query = input("\n> ").strip()
except (EOFError, KeyboardInterrupt):
print("\nGoodbye!")
break
if not query:
continue
if query == ":quit":
print("Goodbye!")
break
if query.startswith(":top "):
try:
top_k = int(query.split()[1])
print(f"Now showing top {top_k} results.")
except (ValueError, IndexError):
print("Usage: :top <number>")
continue
results = trie.autocomplete(query, top_k=top_k)
if not results:
print(f" No matches for '{query}'")
else:
print(f" Top {len(results)} matches for '{query}':")
max_word_len = max(len(w) for w, _ in results)
bar_max = max(1, results[0][1])
for word, freq in results:
bar_len = max(1, freq * 40 // bar_max)
bar = "\u2588" * min(40, bar_len)
print(f" {word:<{max_word_len}} (freq: {freq:>6}) {bar}")
if __name__ == "__main__":
filepath = sys.argv[1] if len(sys.argv) > 1 else "words.txt"
trie = build_engine(filepath)
interactive_mode(trie)What does this code do?
- The while True loop continuously reads input, calling trie.autocomplete(query, top_k=top_k) on every prefix the user types.
- The :quit command exits the loop. The :top <n> command changes how many results appear (default 10).
- The frequency bar uses the Unicode block character (\u2588) scaled relative to the highest-frequency result. This gives you an instant visual sense of how popular each suggestion is.
- The __main__ block accepts an optional file path argument, defaulting to words.txt.
- Save main.py.
- Run the autocomplete engine by running this command:
python main.pyYou should see a loading message followed by the autocomplete banner, then a > prompt waiting for your input.
- Type str and press Enter.
You should see ranked suggestions like string, structure, and stream with frequency bars showing their relative popularity.
- Try a few more prefixes: pro, al, inter.
- Type :top 5 to reduce results to 5, then try another prefix to see fewer suggestions.
- Type :quit to exit the engine.
Seeing a ModuleNotFoundError?
- If the error mentions benchmark, make sure you saved benchmark.py in the same folder as main.py.
- If the error mentions trie, confirm trie.py is also in the same folder. All your Python files must share one directory.
- Make sure your terminal is in the project folder before running the command. Use ls to verify you can see all your .py files listed.
Why can't Python find my module?
Why is this so fast?
When you type a 3-character prefix, the trie traverses exactly 3 nodes to reach the subtree of matching words. It never looks at the other 49,900+ words that don't match.
Your hash map would have to scan all 50,000 keys for the same query. The next step will put numbers on this difference with a full benchmark suite.
✔️ Awesome, I've got everything!
Great. Double check you've saved both benchmark.py and main.py.
ⓧ I'd like to double check the full code
Here is the complete benchmark.py so far (more functions get added in the next step):
"""Performance benchmarks comparing trie vs hash map for prefix operations."""
def load_word_data(filepath: str) -> list[tuple[str, int]]:
"""Load word frequency data from a tab-separated file."""
words = []
with open(filepath, "r", encoding="utf-8") as f:
for line in f:
line = line.strip()
if "\t" in line:
word, freq = line.split("\t", 1)
words.append((word, int(freq)))
return wordsHere is the complete main.py:
"""Interactive autocomplete CLI combining trie + heap for ranked results."""
import sys
from trie import Trie
from benchmark import load_word_data
def build_engine(filepath: str = "words.txt") -> Trie:
"""Load word data and build the trie-based autocomplete engine."""
print(f"Loading words from {filepath}...")
words = load_word_data(filepath)
trie = Trie()
for word, freq in words:
trie.insert(word, freq)
print(f"Loaded {len(trie):,} words into autocomplete engine.\n")
return trie
def interactive_mode(trie: Trie) -> None:
"""Run the interactive autocomplete loop."""
print("=" * 50)
print(" AUTOCOMPLETE SEARCH ENGINE")
print(" Type a prefix to see suggestions.")
print(" Commands: :quit, :top <n> (set results count)")
print("=" * 50)
top_k = 10
while True:
try:
query = input("\n> ").strip()
except (EOFError, KeyboardInterrupt):
print("\nGoodbye!")
break
if not query:
continue
if query == ":quit":
print("Goodbye!")
break
if query.startswith(":top "):
try:
top_k = int(query.split()[1])
print(f"Now showing top {top_k} results.")
except (ValueError, IndexError):
print("Usage: :top <number>")
continue
results = trie.autocomplete(query, top_k=top_k)
if not results:
print(f" No matches for '{query}'")
else:
print(f" Top {len(results)} matches for '{query}':")
max_word_len = max(len(w) for w, _ in results)
bar_max = max(1, results[0][1])
for word, freq in results:
bar_len = max(1, freq * 40 // bar_max)
bar = "\u2588" * min(40, bar_len)
print(f" {word:<{max_word_len}} (freq: {freq:>6}) {bar}")
if __name__ == "__main__":
filepath = sys.argv[1] if len(sys.argv) > 1 else "words.txt"
trie = build_engine(filepath)
interactive_mode(trie)Your autocomplete engine is live. You can type any prefix and get instant ranked suggestions from a 50,000-word dataset. Next, you'll benchmark the trie against the hash map to see exactly how much faster prefix search is.
Benchmark and Compare
Your autocomplete engine works. You can type prefixes and get instant ranked results from 50,000 words. But how do you prove the trie is actually faster than the hash map for prefix search?
In this step, you will build a benchmark suite that measures build time, memory usage, exact lookup speed, and prefix search speed for both structures. The numbers will show you exactly where each data structure wins and loses.
In this step, get ready to:
- Create a benchmark suite with precise timing and memory measurement.
- Run head-to-head comparisons on your 50,000-word dataset.
- Analyze when to use each structure in real-world systems.
Create the benchmark suite
Claiming one data structure is faster than another means nothing without measurement. You need a controlled experiment that isolates each operation and times it with high precision.
- Create a new file called benchmark.py in your project folder.
- Add the imports and utility functions by pasting this code:
"""Performance benchmarks comparing trie vs hash map for prefix operations."""
import random
import sys
import time
from hashmap import HashMap
from trie import Trie
def load_word_data(filepath: str) -> list[tuple[str, int]]:
"""Load word frequency data from a tab-separated file."""
words = []
with open(filepath, "r", encoding="utf-8") as f:
for line in f:
line = line.strip()
if "\t" in line:
word, freq = line.split("\t", 1)
words.append((word, int(freq)))
return words
def estimate_size(obj: object) -> int:
"""Rough memory estimate for nested objects using recursive getsizeof."""
seen: set[int] = set()
def _sizeof(o: object) -> int:
obj_id = id(o)
if obj_id in seen:
return 0
seen.add(obj_id)
size = sys.getsizeof(o)
if isinstance(o, dict):
size += sum(_sizeof(k) + _sizeof(v) for k, v in o.items())
elif isinstance(o, (list, tuple)):
size += sum(_sizeof(item) for item in o)
elif hasattr(o, "__slots__"):
size += sum(
_sizeof(getattr(o, slot))
for slot in o.__slots__
if hasattr(o, slot)
)
elif hasattr(o, "__dict__"):
size += _sizeof(vars(o))
return size
return _sizeof(obj)What does this code do?
load_word_data reads the tab-separated words.txt file and returns a list of (word, frequency) tuples. Both the trie and hash map will use this same dataset.
estimate_size recursively walks through an object's children to estimate total memory. Python's built-in sys.getsizeof only reports shallow size (the object itself, not what it references). The recursive version gives a more realistic picture of how much RAM each structure actually uses.
- Save benchmark.py.
- You won't see a change yet. The next chunk adds the timing functions that use these utilities.
- Add the three benchmark timing functions below estimate_size by pasting this code:
def benchmark_build(
words: list[tuple[str, int]],
) -> tuple[HashMap, Trie, float, float]:
# Time how long it takes to insert all 50k words into each structure
hmap = HashMap(initial_capacity=1024)
start = time.perf_counter()
for word, freq in words:
hmap.put(word, freq)
hashmap_time = time.perf_counter() - start
trie = Trie()
start = time.perf_counter()
for word, freq in words:
trie.insert(word, freq)
trie_time = time.perf_counter() - start
return hmap, trie, hashmap_time, trie_time
def benchmark_exact_lookup(
hmap: HashMap, trie: Trie, test_words: list[str]
) -> tuple[float, float]:
# Time exact key lookups (hash map's strength)
start = time.perf_counter()
for word in test_words:
hmap.get(word)
hashmap_time = time.perf_counter() - start
start = time.perf_counter()
for word in test_words:
trie.search(word)
trie_time = time.perf_counter() - start
return hashmap_time, trie_time
def benchmark_prefix_search(
hmap: HashMap, trie: Trie, prefixes: list[str]
) -> tuple[float, float]:
# Time prefix-based search (trie's strength)
start = time.perf_counter()
for prefix in prefixes:
hmap.keys_with_prefix(prefix)
hashmap_time = time.perf_counter() - start
start = time.perf_counter()
for prefix in prefixes:
trie.autocomplete(prefix, top_k=10)
trie_time = time.perf_counter() - start
return hashmap_time, trie_timeWhat does this code do?
Each function isolates one operation and times it for both data structures using time.perf_counter(). This gives nanosecond-level precision, which is critical for measuring operations that complete in milliseconds.
- benchmark_build measures insertion time for all 50,000 words.
- benchmark_exact_lookup measures 1,000 random exact key lookups.
- benchmark_prefix_search measures 500 prefix-based queries. This is where the trie should dominate.
- Save benchmark.py.
- You won't see output yet. The next chunk adds the main runner that calls these functions and prints results.
- Add the run_benchmarks function and the __main__ guard below benchmark_prefix_search by pasting this code:
def run_benchmarks(filepath: str = "words.txt") -> None:
# Load data and run all benchmarks in sequence
print("Loading word data...")
words = load_word_data(filepath)
print(f"Loaded {len(words):,} words\n")
# Build performance
print("=" * 60)
print("BUILD PERFORMANCE")
print("=" * 60)
hmap, trie, hmap_build, trie_build = benchmark_build(words)
print(f" HashMap: {hmap_build:.4f}s")
print(f" Trie: {trie_build:.4f}s")
ratio_label = "slower" if trie_build > hmap_build else "faster"
print(f" Ratio: Trie is {trie_build / hmap_build:.1f}x {ratio_label}")
# Memory usage
print(f"\nMEMORY USAGE (estimated)")
print("-" * 60)
hmap_mem = estimate_size(hmap)
trie_mem = estimate_size(trie)
print(f" HashMap: {hmap_mem / 1024 / 1024:.2f} MB")
print(f" Trie: {trie_mem / 1024 / 1024:.2f} MB")
mem_label = "more" if trie_mem > hmap_mem else "less"
print(f" Ratio: Trie uses {trie_mem / hmap_mem:.1f}x {mem_label} memory")
# Exact lookup
print(f"\n{'=' * 60}")
print("EXACT LOOKUP (1000 random words)")
print("=" * 60)
random.seed(123)
test_words = [w for w, _ in random.sample(words, min(1000, len(words)))]
hmap_exact, trie_exact = benchmark_exact_lookup(hmap, trie, test_words)
print(f" HashMap: {hmap_exact:.6f}s")
print(f" Trie: {trie_exact:.6f}s")
if hmap_exact > 0:
print(f" Ratio: HashMap is {trie_exact / hmap_exact:.1f}x faster")
# Prefix search
print(f"\n{'=' * 60}")
print("PREFIX SEARCH (500 random prefixes, top-10 results)")
print("=" * 60)
prefixes = list(
{w[: random.randint(2, 4)] for w, _ in random.sample(words, min(2000, len(words)))}
)[:500]
hmap_prefix, trie_prefix = benchmark_prefix_search(hmap, trie, prefixes)
print(f" HashMap: {hmap_prefix:.6f}s (scans ALL {len(hmap):,} keys per query)")
print(f" Trie: {trie_prefix:.6f}s (traverses only matching subtree)")
if trie_prefix > 0:
print(f" Ratio: Trie is {hmap_prefix / trie_prefix:.1f}x faster")
# Summary of when to use each structure
print(f"\n{'=' * 60}")
print("WHEN TO USE WHICH")
print("=" * 60)
print(
" Hash Map wins at:\n"
" - Exact key lookups (O(1) average)\n"
" - Memory efficiency for sparse datasets\n"
" - Non-string keys (integers, tuples, etc.)\n"
"\n"
" Trie wins at:\n"
" - Prefix search / autocomplete (O(prefix_len + matches))\n"
" - Lexicographic ordering (free from DFS traversal)\n"
" - Predictable worst-case performance (no hash collisions)\n"
"\n"
" Heap (used inside the trie):\n"
" - Efficiently maintains top-K results during traversal\n"
" - O(n log k) to find top-K from n candidates\n"
" - Better than sorting all results: O(n log n)\n"
)
if __name__ == "__main__":
run_benchmarks()What does this code do?
run_benchmarks is the orchestrator. It loads the word data once, builds both structures, then runs each benchmark in sequence. The output is formatted into labeled sections so you can see the comparison at a glance.
Notice how prefix search uses a set comprehension to generate unique random prefixes of length 2-4. This simulates real autocomplete queries where users type a few characters and expect results.
- Save benchmark.py.
Seeing a syntax error?
Make sure the f-strings with nested braces (like f"\n{'=' * 60}") are copied exactly. The outer {} is part of the f-string expression. Also check that the multiline print() at the end uses string concatenation across multiple lines, not commas.
Help me debug a syntax error in my benchmark.py file
✔️ Awesome, I've got everything!
Great. Double check you have saved benchmark.py.
ⓧ I'd like to double check the full code
"""Performance benchmarks comparing trie vs hash map for prefix operations."""
import random
import sys
import time
from hashmap import HashMap
from trie import Trie
def load_word_data(filepath: str) -> list[tuple[str, int]]:
"""Load word frequency data from a tab-separated file."""
words = []
with open(filepath, "r", encoding="utf-8") as f:
for line in f:
line = line.strip()
if "\t" in line:
word, freq = line.split("\t", 1)
words.append((word, int(freq)))
return words
def estimate_size(obj: object) -> int:
"""Rough memory estimate for nested objects using recursive getsizeof."""
seen: set[int] = set()
def _sizeof(o: object) -> int:
obj_id = id(o)
if obj_id in seen:
return 0
seen.add(obj_id)
size = sys.getsizeof(o)
if isinstance(o, dict):
size += sum(_sizeof(k) + _sizeof(v) for k, v in o.items())
elif isinstance(o, (list, tuple)):
size += sum(_sizeof(item) for item in o)
elif hasattr(o, "__slots__"):
size += sum(
_sizeof(getattr(o, slot))
for slot in o.__slots__
if hasattr(o, slot)
)
elif hasattr(o, "__dict__"):
size += _sizeof(vars(o))
return size
return _sizeof(obj)
def benchmark_build(
words: list[tuple[str, int]],
) -> tuple[HashMap, Trie, float, float]:
hmap = HashMap(initial_capacity=1024)
start = time.perf_counter()
for word, freq in words:
hmap.put(word, freq)
hashmap_time = time.perf_counter() - start
trie = Trie()
start = time.perf_counter()
for word, freq in words:
trie.insert(word, freq)
trie_time = time.perf_counter() - start
return hmap, trie, hashmap_time, trie_time
def benchmark_exact_lookup(
hmap: HashMap, trie: Trie, test_words: list[str]
) -> tuple[float, float]:
start = time.perf_counter()
for word in test_words:
hmap.get(word)
hashmap_time = time.perf_counter() - start
start = time.perf_counter()
for word in test_words:
trie.search(word)
trie_time = time.perf_counter() - start
return hashmap_time, trie_time
def benchmark_prefix_search(
hmap: HashMap, trie: Trie, prefixes: list[str]
) -> tuple[float, float]:
start = time.perf_counter()
for prefix in prefixes:
hmap.keys_with_prefix(prefix)
hashmap_time = time.perf_counter() - start
start = time.perf_counter()
for prefix in prefixes:
trie.autocomplete(prefix, top_k=10)
trie_time = time.perf_counter() - start
return hashmap_time, trie_time
def run_benchmarks(filepath: str = "words.txt") -> None:
print("Loading word data...")
words = load_word_data(filepath)
print(f"Loaded {len(words):,} words\n")
print("=" * 60)
print("BUILD PERFORMANCE")
print("=" * 60)
hmap, trie, hmap_build, trie_build = benchmark_build(words)
print(f" HashMap: {hmap_build:.4f}s")
print(f" Trie: {trie_build:.4f}s")
ratio_label = "slower" if trie_build > hmap_build else "faster"
print(f" Ratio: Trie is {trie_build / hmap_build:.1f}x {ratio_label}")
print(f"\nMEMORY USAGE (estimated)")
print("-" * 60)
hmap_mem = estimate_size(hmap)
trie_mem = estimate_size(trie)
print(f" HashMap: {hmap_mem / 1024 / 1024:.2f} MB")
print(f" Trie: {trie_mem / 1024 / 1024:.2f} MB")
mem_label = "more" if trie_mem > hmap_mem else "less"
print(f" Ratio: Trie uses {trie_mem / hmap_mem:.1f}x {mem_label} memory")
print(f"\n{'=' * 60}")
print("EXACT LOOKUP (1000 random words)")
print("=" * 60)
random.seed(123)
test_words = [w for w, _ in random.sample(words, min(1000, len(words)))]
hmap_exact, trie_exact = benchmark_exact_lookup(hmap, trie, test_words)
print(f" HashMap: {hmap_exact:.6f}s")
print(f" Trie: {trie_exact:.6f}s")
if hmap_exact > 0:
print(f" Ratio: HashMap is {trie_exact / hmap_exact:.1f}x faster")
print(f"\n{'=' * 60}")
print("PREFIX SEARCH (500 random prefixes, top-10 results)")
print("=" * 60)
prefixes = list(
{w[: random.randint(2, 4)] for w, _ in random.sample(words, min(2000, len(words)))}
)[:500]
hmap_prefix, trie_prefix = benchmark_prefix_search(hmap, trie, prefixes)
print(f" HashMap: {hmap_prefix:.6f}s (scans ALL {len(hmap):,} keys per query)")
print(f" Trie: {trie_prefix:.6f}s (traverses only matching subtree)")
if trie_prefix > 0:
print(f" Ratio: Trie is {hmap_prefix / trie_prefix:.1f}x faster")
print(f"\n{'=' * 60}")
print("WHEN TO USE WHICH")
print("=" * 60)
print(
" Hash Map wins at:\n"
" - Exact key lookups (O(1) average)\n"
" - Memory efficiency for sparse datasets\n"
" - Non-string keys (integers, tuples, etc.)\n"
"\n"
" Trie wins at:\n"
" - Prefix search / autocomplete (O(prefix_len + matches))\n"
" - Lexicographic ordering (free from DFS traversal)\n"
" - Predictable worst-case performance (no hash collisions)\n"
"\n"
" Heap (used inside the trie):\n"
" - Efficiently maintains top-K results during traversal\n"
" - O(n log k) to find top-K from n candidates\n"
" - Better than sorting all results: O(n log n)\n"
)
if __name__ == "__main__":
run_benchmarks()Run the benchmarks and analyze results
- Run the benchmark suite by executing this command in your terminal:
python benchmark.pyYou should see a formatted output with four benchmark sections: BUILD PERFORMANCE, MEMORY USAGE, EXACT LOOKUP, and PREFIX SEARCH. Each section shows timing for both the hash map and trie, plus a ratio comparing them.
What should I see?
Your exact numbers will vary based on your machine, but the patterns should be consistent:
- Build time: The trie is slower to build (more pointer overhead per character).
- Memory: The trie uses more memory (one node per character vs one entry per word).
- Exact lookup: The hash map wins. O(1) average-case with direct bucket access.
- Prefix search: The trie wins massively. It only traverses the matching subtree while the hash map scans all 50,000 keys for every query.
Seeing a ModuleNotFoundError?
Make sure you are running the command from inside your project folder where hashmap.py, trie.py, and words.txt all live. If the error mentions hashmap or trie, those files must be in the same directory as benchmark.py.
Help me fix a ModuleNotFoundError when running benchmark.py
Connect results to real-world systems
The "WHEN TO USE WHICH" section at the bottom of your output summarizes the trade-offs. These are the same trade-offs that production systems navigate every day.
Where do these structures appear in the real world?
Redis sorted sets use radix trees (compressed tries) for range queries. Elasticsearch uses finite state transducers (a trie variant) for its term dictionary. Your browser's address bar autocomplete uses a trie-like structure ranked by visit frequency.
Hash maps still dominate for exact lookups. Every database index, DNS cache, and in-memory session store relies on O(1) key access. The lesson: there is no universally "best" data structure. The operation you optimize for determines the right choice.
Why does the heap matter here?
Your trie's autocomplete method uses a min-heap to track the top-K results during DFS traversal. Without it, you would collect all matches and sort them: O(n log n). The heap gives you O(n log k) where k is the number of results you want. When k=10 and n=5,000 matches, that difference is significant.
Secret mission
Add Fuzzy Matching
Your autocomplete engine only handles exact prefixes right now. Real search engines like Google and VS Code handle typos gracefully. Can you add Levenshtein distance-based fuzzy matching that leverages your trie's structure to prune impossible branches during search?
Clean Up Your Resources
Clean Up Your Resources
This project runs entirely locally, so there are no ongoing costs. Your files will stay on your Desktop until you decide to remove them.
Resources you used:
- Project folder on your Desktop containing generate_data.py, hashmap.py, trie.py, benchmark.py, main.py, and words.txt.
Keep everything running
No action needed. Choose this if you want to keep experimenting with your autocomplete engine or extend it further.
- Your project files remain on your Desktop.
- You can re-run the engine any time with python main.py.
- The generated words.txt data file is about 1 MB and takes no ongoing resources.
Pause - I'll come back to this later
There are no running processes or services to stop. Your files sit on disk and consume no memory or CPU when idle.
- Close the VS Code window for the project.
- Your files stay on the Desktop until you're ready to return.
Delete - I don't want to use this again
Remove all project files from your machine. This deletes everything you built in this project.
- Close VS Code if it's still open with the project.
- Delete the project folder from your Desktop by running the appropriate command for your system.
On macOS or Linux:
cd ~/Desktop
rm -rf autocomplete-engineOn Windows:
cd ~\Desktop
rmdir /s /q autocomplete-engine- Confirm the folder is gone by running ls (macOS/Linux) or dir (Windows) in your Desktop directory. You should no longer see your project folder listed.
Nice Work!
Nice Work!
You just built a fully functional autocomplete engine from scratch and proved, with real benchmark numbers, why data structure choice matters.
You've learned how to:
- Built a custom hash map with separate chaining, dynamic resizing, and a polynomial rolling hash function.
- Built a trie (prefix tree) optimized for autocomplete with frequency-ranked results using a min-heap to efficiently extract top-K matches.
- Benchmarked both structures head-to-head and observed the trie's massive advantage for prefix operations versus the hash map's strength at exact lookups.
- Added fuzzy matching with Levenshtein distance and trie-based pruning for typo tolerance.
Ready to quiz yourself?