Search History-Based Auto-Complete
Solve a hard-level problem for designing search auto-complete that suggests keywords based on search history using tries.
Problem statement
Design and implement an auto-complete system that returns the top three "hot" suggestions based on historical searches. The suggestions must be in lexicographical order. The degree of hotness of a search suggestion is the number of times a user typed the same sentence before. The input is a character array.
Example
Sample input
searchData: ['h','i','s','\n','h','e','r','\n','h','i','m','\n','h','i','t','\n','h','i','m','\n','h','i','\n']
Sample output
query = hautocomplete suggestion -->query = hiautocomplete suggestion -->query = hisautocomplete suggestion -->query = hautocomplete suggestion --> hisquery = heautocomplete suggestion -->query = herautocomplete suggestion -->query = hautocomplete suggestion --> her hisquery = hiautocomplete suggestion --> hisquery = himautocomplete suggestion -->query = hautocomplete suggestion --> her him hisquery = hiautocomplete suggestion --> him hisquery = hitautocomplete suggestion -->query = hautocomplete suggestion --> her him hisquery = hiautocomplete suggestion --> him his hitquery = himautocomplete suggestion --> himquery = hautocomplete suggestion --> him her hisquery = hiautocomplete suggestion --> him his hit
Explanation
query = h
autocomplete suggestion --> No suggestion is returned as there are no records in datastore currently for "h".
query = hi
autocomplete suggestion --> No suggestion is returned as there are no records in datastore currently for "hi".
query = his
autocomplete suggestion --> No suggestion is returned as there are no records in datastore currently for "his".
query = h
autocomplete suggestion --> his ("his" is returned as "his" has been searched once previously)
query = he
autocomplete suggestion --> No suggestion is returned as there are no records in datastore currently for "he".
query = her
autocomplete suggestion --> No suggestion is returned as there are no records in datastore currently for "her".
query = h
autocomplete suggestion --> her his ("her", "his" are returned lexicographical order as "his" and "her" have been searched once previously).
query = hi
autocomplete suggestion --> his ("his" is returned, as "his" has been searched once previously).
query = him
autocomplete suggestion --> No suggestion is returned as there are no records in datastore currently for "him".
query = h
autocomplete suggestion --> her him his ("her", "him", "his" are returned in lexicographical order as "his", "her", "him" have been searched once previously)
query = hi
autocomplete suggestion --> him his ("him", "his" are returned in lexicographical order as "him", "his" have been searched previously)
query = hit
autocomplete suggestion --> No suggestion is returned as there are no records in datastore currently for "hit".
query = h
autocomplete suggestion --> her him his ("her", "him", "his" are returned in lexicographical order as "his", "her", "him" have been searched once previously. "hit" is not returned as we need to provide only three suggestions).
query = hi
autocomplete suggestion --> him his hit ("him", "his", "hit" are returned in lexicographical order as "him", "his", "hit" have been searched once previously).
query = him
autocomplete suggestion --> him ("him" is returned as "him" has been searched previously).
query = h
autocomplete suggestion --> him her his ("him" has been searched twice previously so it appears on top in suggestions. "her", "his" are returned in lexicographical order as they have been searched once previously).
query = hi
autocomplete suggestion --> him his hit ("him", "his", "hit" has been searched twice previously so it appears on top in suggestions. "his", "hit" are returned in lexicographical order as they have been searched once previously).
Try it yourself
Try to solve the problem yourself before reading the solution.
#include <iostream>#include <vector>using namespace std;vector<vector<string>> findQueryResults(vector<char> searchQuery){// your code goes herevector<vector<string>> result;return result;}
Intuition
In this problem, we need to create the datastore from the search data itself and return the suggestion based on historical search frequency. This problem will also be solved using tries because of its requirement of ...