FastPrepTop K Query Suggestions

Top K Query Suggestions

Microsoft logoMicrosoft● MediumNEW GRADPHONE SCREEN
Learn

Problem statement

You are given distinct historical search queries, their positive frequencies, several requested prefixes, and an integer k.

For each prefix, return at most k queries that start with that prefix. Rank matches by decreasing frequency, breaking ties lexicographically. Matching is case-sensitive, and results for the prefixes must stay in input order.

Function

topKQuerySuggestions(queries: String[], frequencies: int[], prefixes: String[], k: int) → String[][]

Examples

Example 1

queries = ["new york","news","new jersey","network","new york times"]frequencies = [50,70,40,60,30]prefixes = ["ne","new "]k = 2return = [["news","network"],["new york","new jersey"]]

For ne, the two highest frequencies belong to news and network. The space in new narrows the second result.

Example 2

queries = ["cat","car"]frequencies = [5,5]prefixes = ["ca","z"]k = 3return = [["car","cat"],[]]

Equal frequencies use lexicographic order, and a prefix with no match returns an empty list.

Constraints

  • 1 <= queries.length = frequencies.length <= 50000
  • 1 <= prefixes.length <= 1000
  • 1 <= queries[i].length <= 100 and 0 <= prefixes[i].length <= 100
  • Queries are distinct and contain lowercase English letters and single spaces only
  • 1 <= frequencies[i] <= 10^9
  • 1 <= k <= 20

More Microsoft problems

See Microsoft hiring insights
public String[][] topKQuerySuggestions(String[] queries, int[] frequencies, String[] prefixes, int k) {
  // Write your code here.
}
queries["new york","news","new jersey","network","new york times"]
frequencies[50,70,40,60,30]
prefixes["ne","new "]
k2
expected[["news", "network"], ["new york", "new jersey"]]
Checking account…