Topics

Design Search Autocomplete System

Hard
0/120
Average time to solve is 25m
Contributed by
+3 more companies

Problem statement

Ninja has enrolled in a system design course at Coding Ninjas, and his first assignment is to create a search autocomplete system for a search engine.

Ninja is given ‘N’ sentences ‘SENTENCES’ and ‘N’ integers ‘TIMES’, where ‘TIMES’[i] is the number of times the ‘SENTENCES’[i] was typed. Now, the instructor will input a test sentence(at least one word and end with ‘#’). As Ninja’s best friend, can you help him with the assignment?

• AutocompleteSystem(String[] sentences, int[] times)Initializes the object with the sentences and times arrays.
• List input(char c)This indicates that the user typed the character c.
• Returns an empty array [], if c == '#' and stores the inputted sentence in the system.
• Returns the top 3 historical hot sentences with the same prefix as the sentence already typed. If there are fewer than 3matches, return them all.

Here are the specific rules:

• A sentence’s hot degree is defined as the number of times a user typed the same sentence before.
• The returned top 3 hot sentences should be sorted by hot degree (The first is the hottest one). If several sentences have the same hot degree, use ASCII-code order (smaller one appears first).
• If less than three hot sentences exist, return as many as possible.
• When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list.

For Example:

``````Input:
["AutocompleteSystem","input","input","input"]
[[["i want to join faang","icecream","i love coding ninjas"],[4,3,1],["i"],["s"],["#"]]

Output:
[null,["i want to join faang","icecream","i love coding ninjas"],[],[]]

Explanation:
* AutocompleteSystem obj = new AutocompleteSystem(["i want to join faang","icecream","i love coding ninjas"],[4,3,1]);
* obj.input(“i”); // return ["i want to join faang","icecream","i love coding ninjas"]. There are three sentences that have prefix "I".
* obj.input(“s”); // return []. There is no sentence with prefix “is”
* obj.input(“#”); // return [].
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
``````1 <= T <= 10
1 <= N <= 100
1 <= SENTENCES[i].LENGTH <= 100
1 <= TIMES[i] <= 50
SENTENCES[i] consists of lowercase English letters
‘C’ is a lowercase English letter, a hash '#', or space ' '.
Each tested sentence will be a sequence of characters c that end with the character '#'.
Each tested sentence will have a length in the range [1, 200].
The words in each input sentence are separated by single spaces.
At most 5000 calls will be made to input.

Time Limit: 1 sec
``````
Sample Input 1:
``````2
3
i want to join faang
icecream
i love coding ninjas
4 3 1
is#
3
batman
superman
spiderman
4 3 2
sp#
``````
Sample Output 1:
``````[i want to join faang, icecream, i love coding ninjas]
[]
[]
[superman, spiderman]
[spiderman]
[]
``````
Explanation of Sample Input 1:
``````For the first test case,
AutocompleteSystem obj = new AutocompleteSystem(["i want to join faang","icecream","i love coding ninjas"],[4,3,1]);
obj.input(“i”); // return ["i want to join faang","icecream","i love coding ninjas"]. There are three sentences that have prefix "i".
obj.input(“s”); // return []. There is no sentence with prefix “is”
obj.input(“#”); // return [].

For the second test case,
AutocompleteSystem obj = new AutocompleteSystem([["batman","superman","spiderman"],[4,3,1]],["s"],["p"],["#"]]);
obj.input(“s”); // return [superman, spiderman]. There are two sentences that have prefix "s".
obj.input(“p”); // return [spiderman]. There is one sentence with prefix “sp”
obj.input(“#”); // return [].
``````
Sample Input 2:
``````2
2
stack and queues
trees and grpahs
3 1
t#
4
aaa
aab
abb
aac
3 2 2 1
abc#
``````
Sample Output 2:
``````[trees and graphs]
[]
[aaa, aab, abb]
[aab]
[]
[]
``````
Console