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.

Solution

To design this system, we will again use the trie data structure. Instead of simply storing the words in the prefix tree, as we did in the WordDictionary, we will now store the query strings. The AutocompleteSystem class will act as a trie that keeps a record of the previous queries and assigns them a rank based on their number of occurrences.

We will implement the AutocompleteSystem class as follows:

• Constructor: In the constructor, we will feed the historical data into the system and create a trie out of it. We will initialize the root node of trie and call the addRecord() function to add all the records.

• addRecord() function: This function inserts records in the trie by creating new nodes. Its functionality is similar to the insertWord() function that we discussed in Feature #2: Store and Fetch Words. Each node of the trie will have:

  • A children dictionary
  • A Boolean called isEnd to set the end of the query sentence
  • A new variable called data that is optional, but we can use it to store the whole query sentence in the last character of the sentence. This will increase space complexity but can make computation easier.
  • A rank variable to store the number of occurrences

  In the code below, you will notice that we are ...