Problem: Autocomplete suggestions (Trie)
You are building an autocomplete feature.
Input
-
A dictionary of
n
unique words
words[i]
(lowercase a–z).
-
An integer array
freq[i]
where
freq[i]
is the usage count of
words[i]
.
-
Then
q
queries. Each query provides:
-
a
prefix
string
-
an integer
k
(number of suggestions requested)
Output
For each query, return up to k suggested completions:
-
A completion is any word that starts with
prefix
.
-
Rank by
higher frequency first
.
-
Break ties by
lexicographical order
.
Follow-up
Support updates:
-
Operation
add(word, delta)
increases that word’s frequency by
delta
(word may be new).
-
Queries after updates must reflect the new frequencies.
Constraints (reasonable interview assumptions)
-
1 ≤ n, q ≤ 2e5
-
1 ≤ |word|, |prefix| ≤ 50
-
Total characters across all words/queries can be large; solutions should be better than scanning all words per query.
Explain what data structure you would use (e.g., Trie) and implement the required operations.