Top K Weighted Autocomplete
In modern search engines, predictive text systems, and recommendation engines, efficiently providing relevant and highly-ranked suggestions as a user types is critical for a superior user experience. This problem challenges you to implement a system that, given a dictionary of words and their associated frequencies (weights), can efficiently return the top K most frequent words that match a given prefix. This functionality is fundamental to improving user interaction in various applications, from search bars to messaging apps.
Implement a function getTopKWeightedSuggestions that takes a list of WordWeight objects, a query prefix string, and an integer k. The function should:
prefix.k words with the highest weights.k words as a list of strings, sorted by their weights in descending order. If there are fewer than k matching words, return all of them.Input:
words: An array of WordWeight objects. Each object has two properties: word (string) and weight (number). This array represents the entire dictionary of words and their associated importance/frequency.prefix: A string representing the current input from the user.k: An integer representing the maximum number of suggestions to return.Output:
k suggestions, sorted by weight in descending order.words array contains multiple entries for the same word, use the latest (or highest, if not specified) weight for that word. For this problem, assume each word in the input words array is unique and its weight is its final, definitive weight.prefix can be an empty string. In this case, you should return the top k most frequent words from the entire dictionary.k will always be a positive integer.Examples
Example 1
Input:
words = [{"word":"apple","weight":10},{"word":"app","weight":15},{"word":"apricot","weight":8},{"word":"apply","weight":12}], prefix = "ap", k = 2
Output:
["app","apply"]
Note:
Words starting with "ap" are "app" (15), "apply" (12), "apple" (10), "apricot" (8). The top 2 by weight are "app" and "apply".
Example 2
Input:
words = [{"word":"banana","weight":20},{"word":"band","weight":5},{"word":"badge","weight":1}], prefix = "ba", k = 5
Output:
["banana","band","badge"]
Note:
Words starting with "ba" are "banana" (20), "band" (5), "badge" (1). Since k=5 and there are only 3 matches, all are returned in descending order of weight.
Example 3
Input:
words = [{"word":"cat","weight":5},{"word":"dog","weight":10},{"word":"car","weight":5},{"word":"bird","weight":8}], prefix = "", k = 2
Output:
["dog","bird"]
Note:
With an empty prefix, all words in the dictionary are considered. Sorted by weight: "dog" (10), "bird" (8), "cat" (5), "car" (5). The top 2 are "dog" and "bird".
Constraints
1 <= words.length <= 10^51 <= words[i].word.length <= 200 <= words[i].weight <= 10^90 <= prefix.length <= 201 <= k <= words.lengthwords[i].word and prefix are lowercase English letters.Loading editor...