Trie / Prefix Tree

Trie Implementation in JavaScript

A trie (prefix tree) supports insert, exact-match search, and prefix-search in O(L) where L is the word length, regardless of how many words are stored. This makes it the right structure for autocomplete, spell-check, and IP-routing tables. This snippet covers a Map-backed trie with insert and search, the startsWith prefix scan that powers autocomplete, and a wordsWithPrefix collector that returns every match.

Trie Implementation in Python

A trie (prefix tree) stores strings character-by-character so prefix queries run in O(length) instead of O(N * length). The Pythonic shape uses a dict of dicts plus a sentinel key for 'word ends here'. This entry covers the dict-of-dicts trie, a class-based variant with explicit nodes, and the autocomplete query you build it for.

Trie Essentials

Prompts on the prefix-tree shape, insert and lookup costs, and the autocomplete pattern. Builds the model before tackling KMP-like or word-search problems.

Design Typeahead / Autocomplete

Design a typeahead/autocomplete service like Google Search's suggestion bar that returns the top 10 ranked completions for a query prefix in under 100ms p99, scaling to 5B searches per day with a multi-billion-entry suggestion index. The interview centerpiece is the data structure choice (trie vs sorted strings vs ngram index) and the offline pipeline that ranks suggestions by frequency, recency, personalization, and click-through rate. We cover the trie with precomputed top-K per node, edge n-gram indexes for typo tolerance, the MapReduce/Spark batch pipeline that rebuilds suggestions nightly, and the per-region edge cache that absorbs 99% of traffic.