Autocomplete With Prefix Matching | Dataford Interview Questions

Your question is Autocomplete With Prefix Matching. Start with the requirements on the right.

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

Problem

The lululemon app needs autocomplete suggestions while a member searches for products. Given a list of unique lowercase product-search words and a lowercase query, return every word that starts with the query, ordered lexicographically.

Implement autocomplete(words, query) using a trie. Each trie node should represent one character. After locating the node for the query, traverse its descendants to collect all matching words.

Formal Specification

Input: words, a list of unique lowercase strings, and query, a lowercase string.
Output: A list of matching words in lexicographic order.
Return an empty list if no word has the query as a prefix.
An empty query matches every word.

Constraints

1 <= len(words) <= 10^5
0 <= len(query) <= 50
1 <= len(word) <= 50
Words contain only lowercase English letters
All words are unique

Function Signature

def autocomplete(words, query):