Trie Autocomplete System | Dataford Interview Questions

Twitch Search needs to return relevant autocomplete suggestions as a viewer types. Given unique search phrases with popularity scores, build a Trie-backed autocomplete system that returns the best matching phrases for each prefix.

Rank suggestions by descending score. If two phrases have the same score, order them lexicographically. Return at most k suggestions for every query prefix.

Formal Specification

Implement autocomplete(entries, queries, k), where entries is a list of [phrase, score] pairs, queries is a list of prefixes, and k is the maximum number of suggestions. Return a list whose ith element contains the ranked suggestions for queries[i].

Phrases and prefixes contain lowercase English letters and spaces. Matching is case-sensitive. The input contains no duplicate phrases.

Constraints

1 <= len(entries) <= 100,000
1 <= len(phrase) <= 100
0 <= score <= 10^9
1 <= len(queries) <= 100,000
0 <= len(prefix) <= 100
1 <= k <= 10
The total number of characters across all phrases is at most 10^6
All phrases are unique

Function Signature

def autocomplete(entries, queries, k):

Your question is Trie Autocomplete System. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem