Implement Search Autocomplete with a Trie

Explain how to implement search autocomplete using a trie. Describe how stored strings are indexed, how a typed prefix finds candidates, and how you would choose and return suggestions. The report identifies a trie-based autocomplete coding task but supplies no exact API, ranking rule, result limit, character set, or update protocol. Clarify those decisions rather than importing the contract of a similarly named problem. ### Constraints & Assumptions - A suggestion must satisfy the agreed prefix-matching rule. - Case normalization, tokenization, ordering, and duplicate strings need explicit policies. - Dynamic updates and usage-frequency learning are optional requirements to confirm. ### Clarifying Questions to Ask - Are suggestions ranked lexicographically, by frequency, or by another score, and how are ties broken? - Is there a fixed maximum number of suggestions? - Does entering a completed query modify the suggestion data? ```hint Finding the node for a prefix is not the same as efficiently returning the highest-ranked suggestions below it. ``` ### What a Strong Answer Covers Explain trie construction and prefix traversal, then give a complete retrieval strategy under a stated ordering choice. Discuss terminals, duplicates, normalization, update costs, and how ranking changes the data kept at each node. ### Follow-up Questions - What changes if suggestions are ranked by a score that frequently changes? - How would an empty or missing prefix behave? - When might a sorted-string index be simpler than a trie?