Design Search Autocomplete System

Question: Design Search Autocomplete System Implement a search autocomplete system. At initialization, you are given historical sentences sentences and their historical input frequencies times. A user then enters a query one character at a time. For every input character c: If c != '#', return at most the top 3 historical sentences that start with the current query prefix. Rank candidates by: descending historical frequency; ascending ASCII lexicographical order when frequencies tie. If c == '#', commit the current query as a new input, increment its frequency by 1, clear the current query, and return an empty list. Follow-up The initial order of sentences[i] is arbitrary: it is not guaranteed to be ordered by popularity or lexicographical order. Your implementation must not depend on the input order. Input Format Standard input is one JSON object: { "sentences": ["i love you", "island"], "times": [5, 3], "inputs": ["i", " ", "a", "#"] } sentences[i] corresponds to times[i]. inputs is the character sequence in chronological order; # commits a query. Print a JSON array in which item j is the candidate list returned for input character j. Constraints 1 <= len(sentences) <= 100 len(sentences) == len(times) 1 <= times[i] <= 10^4 Each sentence contains only lowercase English letters and spaces and has length 1..100. 1 <= len(inputs) <= 10^4 Whenever # occurs, the current query is non-empty. Example Input {"sentences":["i love you","island","ironman","i love leetcode"],"times":[5,3,2,2],"inputs":["i"," ","a","#"]} Output [["i love you","island","i love leetcode"],["i love you","i love leetcode"],[],[]]