DIY: Suggest Relevant Sentences

Solve the interview question "Suggest Relevant Sentences" in this lesson.

Problem statement

Design a system that will guess how a specific string will end. This system will make suggestions by tracking the history of strings that it has seen before. The input() function should take a continuous stream of input, which will end when "#" is found. Each call to the function should give the three most relevant suggestions based on the prefix. Initially, the historical data will be entered into the system. However, whenever a new input is complete, it should also be added to the historical data.

Input

The system will be initialized using a list of strings containing suggestions for possible sentences and a list of integers that represent those sentences’ rankings. An example input is provided below

sentences = {"beautiful", "best quotes", "best friend", "best birthday wishes", "instagram", "internet"}

The input() function will take a string as input. This input will be a continuous stream that ends at "#". For example, we can make three function calls to the input() function using the following strings to collectively mean the string "insta".

"in"
"sta"
"#"

Output

The output will be a list of strings containing the three most relevant results. The following is an example output:

{'internet', 'instagram', 'insta'}
{'instagram'}
{}

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