Feature #2: Design Search Autocomplete System

Implementing the "Design Search Autocomplete System" feature for our "Search Engine" project.

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 auto_complete() 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 auto_complete() function as a continuous stream. For example, if the auto_complete("be") is called, and then the auto_complete("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, auto_complete("#") 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 auto_complete() function, meaning auto_complete("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 auto_complete("st") will be called. Now, the output should be ['best friend', 'best quotes', 'best birthday wishes']. Lastly, the user finishes the query, so the auto_complete("#") will be called. It will output [] and "best" will be added in the record to be used in future suggestions.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.