Trie and Prefix Indexing

What's being tested

Tests construction and use of a Trie (prefix tree) for efficient prefix indexing, exact-word lookup, and longest-prefix matching. Interviewers probe correctness (terminal vs. prefix), per-node metadata for fast top-K or frequency-aware queries, and time/space complexity tradeoffs.

Patterns & templates

• insert / search — traverse nodes per character, create child nodes as needed; O(L) time, O(1) extra space beyond nodes, where L is word length.

• Terminal flag vs. prefix — store is_end boolean and optionally an exact-word payload to distinguish words from mere prefixes.

• Per-node metadata — keep count, freq, or topK list at nodes to answer aggregate queries in O(L + K) time. Update these during insert/delete.

• Children representation — use hash map for variable alphabet or fixed array for small alphabets; memory ~O(total_chars) nodes × child-pointer-size.

• Lazy deletion — clear is_end and decrement metadata; prune nodes only when safe to avoid expensive recursive deletes.

• Longest-match replacement — greedy scan: advance as long as matching child exists and track last is_end; overall O(N + M) for text size N and average match M per start.

• Collect/top-K traversal — DFS from prefix node, early-stop with maintained heap for K best; complexity O(nodes_in_subtrie + K log K).

Common pitfalls

Pitfall: Treating every node with children as a word—forgetting to check is_end leads to false positives for exact search.

Pitfall: Failing to update per-node topK on deletes/updates, causing stale suggestions.

Pitfall: Assuming constant alphabet; using fixed arrays for large Unicode input wastes memory.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.