Efficient Autocomplete System with Top-K Frequency Suggestions

snapchat Design a search autocomplete system that can provide suggestions based on user input prefixes. Assume there is a dictionary with a set of strings, and the user inputs a query string character by character. Return the top 3 matches based on historical frequency. Assume the historical data in the dictionary is large, and the system should perform well. Example Input i\n \na\n#\n