Good morning! Here's our prompt for today.

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 ofstrings
) 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)
whereN
is number of strings
Try to solve this here or in Interactive Mode.
How do I practice this challenge?
xxxxxxxxxx
'PASSED: ' + 'Can instantiate a trie, add `cherry`, and get a depth of `6`'
var assert = require('assert');
​
class Trie {
// fill this class out
add(val) {}
​
search(val) {}
​
remove(val) {}
}
​
// const trie = new Trie();
// console.log(trie.add('cherry'));
// console.log(trie);
// console.log(trie.search('cherry'));
​
function Node(val) {
this.val = val;
this.left = null;
this.right = null;
}
​
// Regular binary trees
var tree1 = new Node(4);
tree1.left = new Node(1);
tree1.right = new Node(3);
​
var tree2 = new Node(5);
tree2.left = new Node(10);
We'll now take you through what you need to know.
How do I use this guide?