Frontend School

Top K Weighted Autocomplete

DSA
hard

Top K Weighted Autocomplete

Hard
Trie
Priority Queue
String
Data Structure Design

Overview

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.

What you need to do / Task

Implement a function getTopKWeightedSuggestions that takes a list of WordWeight objects, a query prefix string, and an integer k. The function should:

  1. Construct an appropriate data structure to store the words and their weights for efficient querying.
  2. Efficiently find all words that start with the given prefix.
  3. From these matching words, identify the k words with the highest weights.
  4. Return these 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 & output

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:

  • An array of strings, representing the top k suggestions, sorted by weight in descending order.

Clarifications

  • If the 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.
  • The 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.
  • All words and prefixes will consist of lowercase English letters.

Examples

1

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".

2

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.

3

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

Constraints & assumptions

  • 1 <= words.length <= 10^5
  • 1 <= words[i].word.length <= 20
  • 0 <= words[i].weight <= 10^9
  • 0 <= prefix.length <= 20
  • 1 <= k <= words.length
  • All characters in words[i].word and prefix are lowercase English letters.

What interviewers evaluate

  • Correctness: The solution must accurately identify and rank the top K weighted words for any given prefix.
  • Efficiency: The chosen data structures (e.g., Trie, Priority Queue) and algorithms should lead to optimal time and space complexity for both building the dictionary and performing queries.
  • Edge Case Handling: Proper handling of scenarios like empty prefixes, no matching words, or fewer than K matching words.
  • Code Quality: Clarity, readability, and maintainability of the code.

Loading editor...