One search box, two courses
This combined project brings Data structures and Algorithms together to build the café's recipe search: autocomplete as you type, an inverted index that finds matching recipes fast, ranking, and "did you mean…?" spelling suggestions — then all of it in one engine.
- Day 1: autocomplete with a trie (trees + hash maps + sorting)
- Day 2: an inverted index with two-pointer intersection
- Day 3: spelling suggestions with edit distance (dynamic programming)
- Day 4: the complete search engine
A tree of letters
A trie stores words letter by letter: every path from the root spells a prefix, and nodes that end a word keep a count. Finding all words with a prefix costs the length of the prefix plus the size of that one subtree — not the whole vocabulary.
function createTrie() {
const root = { children: {}, count: 0 };
let size = 0;
return {
insert(word, times = 1) {
let node = root;
for (const ch of word) node = node.children[ch] ??= { children: {}, count: 0 };
if (node.count === 0) size++;
node.count += times;
},
complete(prefix, k) {
let node = root;
for (const ch of prefix) {
node = node.children[ch];
if (!node) return [];
}
const found = [];
const walk = (n, word) => {
if (n.count) found.push([word, n.count]);
for (const ch of Object.keys(n.children)) walk(n.children[ch], word + ch);
};
walk(node, prefix);
return found
.sort((a, b) => b[1] - a[1] || (a[0] < b[0] ? -1 : 1))
.slice(0, k)
.map(([word]) => word);
},
size: () => size,
};
}