Feature #2: Design Search Autocomplete System

Description

The second feature we want to implement is the auto-complete query. This is the feature that prompts the search engine to give you some suggestions to complete your query when you start typing something in the search bar. These suggestions are given based on common queries that users have searched already that match the prefix you have typed. Moreover, these suggestions are ranked based on how popular each query is.

Assume the search engine has the following history of queries: ["beautiful", "best quotes", "best friend", "best birthday wishes", "instagram", "internet"]. Additionally, you have access to the number of times each query was searched. The following list shows the number each query string occurred, respectively: [30, 14, 21, 10, 10, 15]. Given these parameters, we want to implement an AutoComplete() function that takes in an incomplete query a user is typing and recommends the top three queries that match the prefix and are most popular.

The system should consider the inputs of the AutoComplete() function as a continuous stream. For example, if the AutoComplete("be") is called, and then the AutoComplete("st") is called, the complete input at that moment will be "best". The input stream will end when a specific delimiter is passed. In our case, the delimiter is "#", and, AutoComplete("#") will be called. This marks the end of the query string. At this point, your system should store this input string in the record, or if it already exists, it should increase its number of instances.

Suppose, the current user has typed "be" in the search bar; this will be the input for the AutoComplete() function, meaning AutoComplete("be") will be called. It will return ['beautiful', 'best friend', 'best quotes'] because these queries match the prefix and are the most popular. The order of queries in the output list is determined by popularity. Then, the user adds "st" to the query, making the string "best", and the AutoComplete("st") will be called. Now, the output should be ['best friend', 'best quotes', 'best birthday wishes']. Lastly, the user finishes the query, so the AutoComplete("#") will be called. It will output [] and "best" will be added in the record to be used in future suggestions.