Autocomplete System Design | Dataford Interview Questions

Given an array of words, implement a system where entering a few letters returns all word strings starting with that substring (similar to Google Search autocomplete).

Asked in the Onsite stage. This coding round question was described as highly relevant to Google's search business.

Implement autocomplete(words, prefix). Return every word beginning with prefix, in lexicographic order. Matching is case-sensitive, and duplicate input words must remain duplicated in the output.

Constraints

1 <= len(words) <= 5000
1 <= len(words[i]) <= 30
0 <= len(prefix) <= 30
Words and prefix contain only lowercase English letters
Return results in lexicographic order
Preserve duplicate words

Function Signature

def autocomplete(words, prefix):

Your question is Autocomplete System Design. 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