Prefix autocomplete

The baseline filters all N words with startswith(prefix) and sorts matches. It may be adequate for a small immutable dictionary, but every keystroke revisits unrelated words. A sorted word array plus binary search is a worthwhile alternative when updates are rare; a trie makes shared prefixes explicit and supports insertion.

Insertion follows/creates character edges and marks the final node terminal. Lookup first follows the prefix in O(P) steps. If an edge is missing, return empty. Otherwise perform depth-first traversal beneath that node, visiting terminal words before their descendants and child edges in sorted order. Stop after k outputs.

the current character path exactly spells the current trie node, and every word in its subtree starts with that path. Sorted child traversal emits lexicographic order; emitting the terminal first puts car before cart. The explicit iterator stack restores the character path on return and avoids Python's recursion limit for long words. No complete prefix string is copied at every intermediate node.

Let W be total inserted characters, P prefix length, S visited subtree nodes, L maximum word length, and B total output characters. Build costs O(W) time/space. Query time is O(P + S + B) for the fixed 26-character alphabet; sorting each node's at-most-26 children is constant bounded work per visit. Query auxiliary space is O(L), excluding O(B) output, because only the current path and its iterator frames are retained. A large alphabet would add child-sorting costs explicitly.

Follow-up 1 — remove car but retain cart. Predict the changed trie. Clear the terminal flag at car; prune a node only when it is nonterminal and childless. Removing cart afterward allows pruning back until another word or branch survives.

Follow-up 2 — rank by popularity. Lexical early stopping no longer finds the best k. Store/cache ranked candidates at prefix nodes, or explore using subtree score bounds. Score updates, ties, and deletions determine maintenance cost; merely sorting the first k lexical results is incorrect.

Senior depth includes terminal-versus-branch reasoning, bounded output traversal, and an independent filter/sort oracle. Lead depth addresses normalization and index-update/version contracts before adding international text or live ranking.

Reference: solution.py (download file, source below); tests cover prefix words, duplicate adds, limits, missing prefixes, dynamic insertion, and a 2,000-character word.

"""Lexicographic prefix lookup using explicit trie nodes and iterative DFS."""
from string import ascii_lowercase


class Node:
    def __init__(self):
        self.children = {}
        self.terminal = False


class Trie:
    def __init__(self, words=()):
        if isinstance(words, (str, bytes)):
            raise ValueError("expected an iterable of words, not one string")
        try:
            words = iter(words)
        except TypeError as exc:
            raise ValueError("expected an iterable of words") from exc
        self.root = Node()
        for word in words:
            self.add(word)

    @staticmethod
    def _validate(text, allow_empty=False):
        if not isinstance(text, str) or (not text and not allow_empty) or any(c not in ascii_lowercase for c in text):
            raise ValueError("lowercase ASCII words required")

    def add(self, word):
        self._validate(word)
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = Node()
            node = node.children[char]
        node.terminal = True

    def suggest(self, prefix, limit=5):
        self._validate(prefix, allow_empty=True)
        if type(limit) is not int or limit < 0:
            raise ValueError("nonnegative integer limit required")
        if limit == 0:
            return []
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        result = [prefix] if node.terminal else []
        path = list(prefix)
        stack = [iter(sorted(node.children.items()))]
        while stack and len(result) < limit:
            try:
                char, child = next(stack[-1])
            except StopIteration:
                stack.pop()
                if stack:
                    path.pop()
                continue
            path.append(char)
            if child.terminal:
                result.append(''.join(path))
            stack.append(iter(sorted(child.children.items())))
        return result[:limit]

python -m unittest discover -s curriculum/01-code/02-data-structures-algorithms/problems/30-trie-autocomplete -p 'test_*.py'