Top K Frequent Search Suggestions
Airbnb's search experience is paramount for connecting guests with unique stays and experiences. When users begin typing into the search bar, providing relevant and popular suggestions can significantly enhance usability and reduce friction. This problem asks you to implement a system that, given a list of historical search queries and a user's current input prefix, efficiently returns the top k most frequent full queries that start with that prefix.
Implement the getTopKFrequentSuggestions function that performs the following:
queries, calculate the frequency of each unique query.prefix string, traverse your data structure to identify all full queries that begin with this prefix.k most frequent ones. If there are fewer than k matching queries, return all of them.queries: An array of strings representing historical search queries. Each string is a valid query.
k: An integer representing the maximum number of suggestions to return.
prefix: A string representing the user's current input.
Return: An array of strings, representing the top k most frequent suggestions, sorted as specified.
'a'-'z').queries array.k is 0, an empty array should be returned.prefix, an empty array should be returned.Examples
Example 1
Input:
queries = ["apple", "app", "apple", "apricot", "banana"], k = 2, prefix = "ap"
Output:
["apple","app"]
Note:
Queries and their frequencies: "apple": 2, "app": 1, "apricot": 1, "banana": 1. Matching queries for prefix "ap" are "apple" (2), "app" (1), "apricot" (1). Sorted by frequency (desc) then alphabetically (asc): [("apple", 2), ("app", 1), ("apricot", 1)]. Top 2 are "apple", "app".
Example 2
Input:
queries = ["flight", "fly", "fluffy", "flower"], k = 3, prefix = "flo"
Output:
["flower"]
Note:
Queries and their frequencies: all are 1. Only "flower" matches prefix "flo". Since k=3 and only one match, we return all matches.
Example 3
Input:
queries = ["apple", "banana", "apricot", "grape", "avocado"], k = 2, prefix = "a"
Output:
["apple","apricot"]
Note:
Queries and their frequencies: "apple":1, "banana":1, "apricot":1, "grape":1, "avocado":1. Matching queries for prefix "a" are "apple" (1), "apricot" (1), "avocado" (1), "banana" (1). Sorted alphabetically among those with same frequency: "apple", "apricot", "avocado", "banana". Top 2 are "apple", "apricot".
Constraints
1 <= queries.length <= 10^41 <= queries[i].length <= 100queries[i] consists of lowercase English letters ('a'-'z').0 <= k <= queries.length1 <= prefix.length <= 100prefix consists of lowercase English letters ('a'-'z').10^5.Loading editor...