Design Search Autocomplete System
Hard · Trie · about 35 minutes
Asked at Pinterest, Microsoft, Amazon, Google, Uber.
Design autocomplete for a search box. You get the historical sentences and how many times each was typed. The user then types one character at a time; '#' ends the current sentence.
AutocompleteSystem(sentences, times)loads the history.input(c): ifcis'#', record the sentence typed so far (adding 1 to its count) and return[].
Otherwise append c to the current input and return the top 3 historical sentences that start with it, ordered by count (highest first), with ties broken by ASCII order. Return fewer if fewer match.
Sentences contain lowercase letters and spaces.