Type-Ahead Prefix Matches
Navan● EasyFULLTIMEONSITE INTERVIEWProblem statement
Given a vocabulary array words and a string prefix, return every distinct vocabulary word that starts with prefix.
Matching is case-sensitive. Return the results in lexicographic order.
Interview follow-up
The interview required actual working code and then asked how it performs at scale and how to optimize it. Discuss repeated-query indexing with a trie or a sorted vocabulary, index build and update costs, output-size costs, and invalidating cached results after vocabulary changes. This is a follow-up to the coding task.
Function
autocomplete(words: String[], prefix: String) → String[]Examples
Example 1
words = ["dog","door","deer","doom","door"]prefix = "do"return = ["dog","doom","door"]The three distinct matching words are returned once in lexicographic order.
Example 2
words = ["apple","banana"]prefix = "cat"return = []No vocabulary word begins with cat.
Constraints
0 <= words.length <= 1000000 <= words[i].length, prefix.length <= 100- Every word and the prefix contain only lowercase English letters.