Here is the interview question prompt, presented for reference.

Suppose you're asked during an interview to design an autocompletion system. On the client side, you have an input box. When users start typing things into the input, it should parse what's been typed and make suggestions based on that.

For example, if the user has typed "cat", we may fetch "cat", "category", and "catnip" as recommendations to display. This seems pretty simple-- we could just do a scan of all the words that start with "cat" and retrieve them. You can do this by storing the words in an array and doing a binary search in O(log n) time complexity, with n being the number of words to search through.

But what if you have millions of words to retrieve and wanted to separate the search time from vocabulary size?

A trie (for data reTRIEval), or prefix tree, would be what you want. Let's implement one today.

We should implement: - An add method that can add words to the trie - A search method that returns the depth of a word - A remove method that removes the word

Constraints

• Total number of characters (not total number of strings) to be inserted <= 100000
• The characters will only comprise of lowercase alphabets
• Expected time complexity for add, search and delete : O(n) n being the length of the word
• Expected space complexity : O(26 * n * N) where N is number of strings

You can see the full challenge with visuals at this link.