Retrieval: when is a trie worth it?

Two problems rebuilt cold, plus the honest answer about when a set is better.

Quick check· 5 min

Trie or set?

You must implement autocomplete: given a typed prefix, return every stored word beginning with it. Which structure, and why?

A trie, because walking to the prefix node then collecting everything beneath it is proportional to the answer sizeA set, checking each stored word against the prefixA sorted list with binary search to the first match, then scanning forwardA hash map from every possible prefix to its matching words

Problem· 15 min

Implement Trie, from scratch

You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.

Problem· 20 min

Word Search, from scratch

Tries

107 / 170

TriesLesson 4 of 4About 45 min