• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Problem Statement:

Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character '#').

You are given a string array sentences and an integer array times both of length n where sentences[i] is a previously typed sentence and times[i] is the corresponding number of times the sentence was typed. For each input character except '#', return the top 3 historical hot sentences that have the same prefix as the part of the sentence already typed.

Here are the specific rules:
The hot degree for a sentence is defined as the number of times a user typed the exactly 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 3 hot sentences exist, return as many as you can.
When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list.
Implement the AutocompleteSystem class:

AutocompleteSystem(String[] sentences, int[] times) Initializes the object with the sentences and times arrays.
List<String> 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 that have the same prefix as the part of the sentence already typed. If there are fewer than 3 matches, return them all.
Example:
AutocompleteSystem obj = new AutocompleteSystem(["i love you", "island", "iroman", "i love mango"], [5, 3, 2, 2]);

obj.input("i"); // return ["i love you", "island", "i love mango"]. There are four sentences that have prefix "i". Among them, "ironman" and "i love mango" have same hot degree. Since ' ' has ASCII code 32 and 'r' has ASCII code 114, "i love mango" should be in front of "ironman". Also we only need to output top 3 hot sentences, so "ironman" will be ignored.

obj.input(" "); // return ["i love you", "i love mango"]. There are only two sentences that have prefix "i ".

obj.input("a"); // return []. There are no sentences that have prefix "i a".

obj.input("#"); // return []. The user finished the input, the sentence "i a" should be saved as a historical sentence in system. And the following input will be counted as a new search.

Solution:




This is a Premium Content.
Please subscribe to Low Level Design course to access the content.




Further Space Optimization:



This is a Premium Content.
Please subscribe to Low Level Design course to access the content.




The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave