Skip to main content

Top-K Autocomplete Suggestions

medium
TrieStringHeapSortingTrie AutocompleteTop K Heap
Asked atGoogleAmazonMicrosoftLinkedin

Problem Description

You are building an autocomplete feature for a search engine. You have a list of `(phrase, frequency)` pairs representing how often each phrase has been searched. Given a query prefix, return the top `k` most frequent phrases that start with that prefix, sorted in descending order of frequency. If two phrases have equal frequency, break ties alphabetically.

Write a function `autocompleteTopK(phrases, frequencies, prefix, k)` that returns the top-k results.

**Example 1:**
```
Input:
phrases = ["data science", "data structures", "data mining", "database", "dating"]
frequencies = [80, 95, 60, 75, 40]
prefix = "dat"
k = 3
Output: ["data structures", "data science", "database"]
```

**Example 2:**
```
Input:
phrases = ["go", "golang", "google", "gorilla", "gopher"]
frequencies = [50, 50, 90, 30, 50]
prefix = "go"
k = 4
Output: ["google", "go", "golang", "gopher"]
```

*Note: In Example 2, "go", "golang", and "gopher" all have frequency 50 and are sorted alphabetically among themselves.*

Constraints

  • 1 <= phrases.length == frequencies.length <= 10000
  • 1 <= phrases[i].length <= 100
  • 1 <= frequencies[i] <= 10^6
  • 1 <= prefix.length <= 50
  • 1 <= k <= phrases.length
  • All characters are lowercase English letters and spaces

Follow-up

Extend the solution to support O(P) query time by storing the top-k list directly at every trie node during insertion.

Hints

Try the problem first. If you get stuck, you can reveal hints one at a time.

Solution

Leaderboard

No entries yet for python.

Be the first — submit an accepted solution.