Google Search Autocomplete | Dataford Interview Questions

Given a dictionary/list of words, take a typed substring as input and return all words in the dictionary that start with that substring (i.e. implement Google Search-style autocomplete).

Asked in the onsite coding round stage. Candidate noted the problem felt closely related to Google's core search/autocomplete business; unsure if it's a commonly recurring question.

Contract

Implement autocomplete(words, prefix). Return matching words in lexicographic order. An empty prefix matches every word.

Constraints

1 <= len(words) <= 5,000
1 <= len(word) <= 50
0 <= len(prefix) <= 50
Words are unique lowercase strings
The returned words must be in lexicographic order

Function Signature

def autocomplete(words, prefix):

Your question is Google Search Autocomplete. 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