Question 1120

Ten Keystrokes Deep

Your typeahead service walks a trie built from 200 million historical queries. For a single letter prefix the subtree below the matching node holds tens of millions of leaves, and p99 latency blows past the 60 ms budget on early keystrokes. What is the standard fix?

A

Shard the trie by first character across more nodes so each server owns fewer prefixes

B

Store precomputed top k completions at every trie node so a lookup ends at the node itself

C

Refuse to suggest anything until the user has typed four characters, so subtrees stay small

D

Replace the trie with a hash map from full query string to popularity, read on each keystroke