Trie Autocomplete / Prefix Search

Requirements Three related versions of the problem have appeared in interviews: Variant A — Search autocompletion (onsite coding). Create a trie from a dictionary of words, then implement suggest(prefix) to return the dictionary entries whose beginnings match the supplied prefix. Variant B — First index containing prefix (phone screen). For a word list such as ['a', 'apple', 'appz', 'b'] and query prefixes such as ['ap'], return the position of the earliest word that begins…