Tries interview questions
A trie stores strings by their prefixes, so any question about words that start with something becomes a walk down the tree rather than a scan of the whole dictionary.
How do I solve tries interview questions?
A trie is a tree where each edge is a character and each path from the root spells a prefix. It answers prefix questions, autocomplete and dictionary lookups in time proportional to the word length, not the number of words, and prunes searches in word-grid problems when no word starts with the current path.
How to recognise a tries problem
The question mentions prefixes, autocomplete, a dictionary of words, or words that match a pattern with wildcards.
You must search many words at once, for example in a grid, and a single-word search repeated for each word would be too slow.
A hash set of words answers whole-word lookups but not whether anything starts with a given prefix.
How to build the solution
Define a node with a map from character to child (or a fixed array of 26) and a flag for end of word.
Insert a word by walking from the root, creating a child for any missing character, and set the end flag on the last node.
Search or check a prefix by walking the characters; if a child is missing the answer is no, and the end flag distinguishes a word from a mere prefix.
For a word grid, build a trie of the words and run depth-first search from each cell, following the trie as you go, and stop a path as soon as the trie has no matching child.
Classic problems to practise
Implement Trie (Prefix Tree), Design Add and Search Words Data Structure, Word Search II, Replace Words, Longest Word in Dictionary, Autocomplete System, Longest Common Prefix.
Mistakes interviewers see
Confusing a prefix with a word by forgetting the end-of-word flag.
Using a 26-slot array when the input can contain other characters, or a map when the alphabet is tiny and speed matters; state the choice.
Not stating the cost: insert and search are linear in the word length, and memory is linear in the total characters stored.
Rebuilding or rescanning the dictionary for every query, which defeats the purpose of the trie.
Practise it as an interview
Take a topic-based interview on tries to practise the pattern the way it is asked: say the pattern before you code, write and run the solution in a live editor, and answer the cross-questions about edge cases and complexity. The scored report shows whether you lost points explaining, coding or defending. Your first 3 single-question interviews are free for life, every interview report is free, and a new account also gets 6 welcome credits.
Frequently asked questions
When is a trie better than a hash set?
When you need prefix queries or want to prune a search by prefix. For plain membership of whole words, a hash set is simpler and as fast.
What is the space cost of a trie?
Up to the total number of characters across all words, plus the per-node overhead of the child map or array.