Implement a trie for autocomplete: insert words and return all completions of a prefix.

TL;DR: A trie (prefix tree) stores words character by character down a tree, so finding all completions of a prefix is: walk the prefix once (O(len(prefix))), then DFS from that node to collect every word below it. Lookup time is independent of the dictionary size, which is why it beats scanning a list. Mark word ends, and for real autocomplete, rank completions (by frequency) rather than returning them arbitrarily.

Query prefix ca: walk c then a (two steps), then DFS below a yields car, card, cat.

How to approach it. State why a trie over a list/hashset: prefix queries are O(prefix length), not O(number of words), and it shares common prefixes (memory efficiency). Then implement insert and prefix-search (walk to the prefix node, DFS to gather words), and raise the ranking follow-up that turns it into real autocomplete.

A strong answer.

class TrieNode:
    def __init__(self):
        self.children = {}        # char -> TrieNode
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

    def completions(self, prefix: str):
        node = self.root
        for ch in prefix:                      # walk to the prefix node: O(len(prefix))
            if ch not in node.children:
                return []                      # prefix not present
            node = node.children[ch]
        out = []
        def dfs(n, path):                      # collect every word below the prefix
            if n.is_word:
                out.append(prefix + path)
            for ch, child in n.children.items():
                dfs(child, path + ch)
        dfs(node, "")
        return out

What a strong candidate explains:

• Why a trie. Walking the prefix is O(len(prefix)), independent of how many words are stored, so autocomplete stays fast on a huge dictionary. A linear scan of all words to find prefix matches is O(N·len) and does not scale. Tries also share common prefixes, saving memory versus storing every full string.
• is_word flag. A node can be both a complete word and a prefix of longer words ("car" and "card"), so you mark word ends rather than relying on leaves.
• Prefix search = walk then DFS. Navigate to the node for the prefix, then depth-first collect every descendant marked is_word.

Key takeaways

• Prefix lookup is O(len(prefix)), independent of dictionary size; a list scan is O(N·len) and does not scale.
• is_word distinguishes a stored word from a mere prefix ("car" inside "card"), so do not rely on leaves.
• Real autocomplete ranks completions by frequency/score; precompute top-k at each node for near O(1) retrieval.
• A node-per-char trie is memory-heavy; compress with a radix/Patricia trie or a DAWG that shares suffixes.

What interviewers probe next.

• "Rank completions (real autocomplete)?" Store a frequency/score at each word end; to return the top-k, either DFS and heap-select, or cache the top completions at each node (precomputed) for O(1)-ish retrieval. Production typeahead is ranking, not just matching.
• "Memory at scale?" A node-per-char trie is memory-heavy; compress with a radix/Patricia trie (merge single-child chains) or a DAWG (share suffixes too), and on mobile, optimize node layout (a Google-flavored follow-up).
• "Complexity?" Insert and prefix-walk are O(word/prefix length); collecting completions is O(total characters in the matched subtree).
• "Fuzzy / typo-tolerant autocomplete?" Combine the trie with edit-distance search (bounded Levenshtein) or n-gram indexing.

Common mistakes.

• Scanning a word list for prefix matches instead of using a trie, which does not scale.
• Forgetting is_word, so you cannot tell a stored word from a mere prefix.
• Returning completions unranked, when real autocomplete needs frequency/score ordering.
• Ignoring memory: a naive trie can be huge; mention radix/DAWG compression.