Mark As Completed Discussion

Good morning! Here's our prompt for today.

Description

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

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

JAVASCRIPT
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

We'll now take you through what you need to know.

How do I use this guide?