Interview Question: Autocomplete

Great typeahead implementation. Thanks for the video 🙂
I felt, instead of storing prefix we can store the "word "instead and store it in only those nodes that have isWord = true.
That will save a lot of space.

u crazy guy !! 😀

For longest prefix, from the dictionary, for the given string:

public String findLongestPrefix(String str){

Node curr = trie;

for (char c : str.toCharArray()){

if(curr.children.containsKey(c)){

curr = curr.children.get(c);

}

else

break;

}

if(curr.isEndOfWord == true)

return curr.prefix;

else

return "No matching prefix";

}

Is this code correct for finding the longest prefix for the given word???

plz do jump game problem

Great videos. But too long video. 31 mins is too much.

public static void autoComplete(Set<String> dic, String word) {

for(String match : dic) {

if(match.startsWith(word)) {

System.out.println(match);

}

}

}

I know this is late, but what would the runtime of the Trie be?

Before Trie:
O(c*n) where c is length of prefix and n is number of words in dictionary

After Trie:
O(c+n)

This is because at first, you are comparing the entire prefix to every word in the dictionary. So for each word in the dictionary, you iterate through the entire prefix. But after using a trie, you do some preprocessing to build the trie, which is O(n) time and space because you go through every word in the dictionary.

And then lookup becomes
1) Finding the prefix in the Trie, which is O(c) because the prefix is length c
2) Returning all the words associated with that prefix, which is O(n) because worst case the prefix could be "" and then you'd return all the words in the dictionary!

Correct me if my logic is wrong!

For 20:01 What if, instead of checking "i == s.length()-1" you just mark the end of the word after the loop. Because at the end of the loop, you are certainly at the end of the given word.

Hey Sam , I find your videos very useful and helpful . Can you do a video on DFS and BFS on binary tree ?

hi, i don'tif it's a bug, but when there is duplicate word, it's only add one to the results

Surprise 3:48

great video!

My python solution:

class Trie(object):

def __init__(self, words):
self.setup(words)

def setup(self, words):
self.trie_dict = {'end_here': False}

for word in words:
self.add_word(word)

def add_word(self, word):

cur_dict = self.trie_dict

for char in word:
if not char in cur_dict:
cur_dict[char] = {'end_here': False}
cur_dict = cur_dict[char]

cur_dict['end_here'] = True

def check_for(self, word):

index = 0
cur_dict = self.trie_dict

while word[index] in cur_dict:
if index + 1 == len(word):
return cur_dict[word[index]]['end_here']

cur_dict = cur_dict[word[index]]
index += 1

return False

def get_all_with_prefix(self, prefix):
node = self.get_node_from_prefix(prefix)
return [prefix + word for word in self.recursive_collect(node)]

def recursive_collect(self, node, char_prefix=''):

words = []
if node.get('end_here'):
words.append(char_prefix)

for char in node:
if char == 'end_here':
continue

temp_words = [char_prefix + word for word in
self.recursive_collect(node[char], char_prefix=char)]

words.extend(temp_words)

return words

def get_node_from_prefix(self, prefix):
cur_dict = self.trie_dict
index = 0

while prefix[index] in cur_dict:
if index + 1 == len(prefix):
return cur_dict[prefix[index]]

cur_dict = cur_dict[prefix[index]]
index += 1

return {'end_here': False}

my_trie = Trie(['man', 'manm', 'mat', 'china', 'chinese', 'chit'])
assert my_trie.check_for('man')
assert my_trie.check_for('manm')
assert my_trie.check_for('china')
assert not my_trie.check_for('manbm')
assert not my_trie.check_for('ma')

print(my_trie.get_all_with_prefix('ma'))
print(my_trie.get_all_with_prefix('chin'))
print(my_trie.get_all_with_prefix('dog'))

Wow so my thinking was correct, and they never called me back lol Oh well gonna keep searching.
Thanks for the video tho man!

Extremely well done. Thanks!

Hey, great video. If we also had to consider the weights for each phrase in the dictionary, would you still recommend a Trie? Part where I'm struggling is this –> What's the best way to store the weights such that it is available to identify the top 'm' suggestions based on an input?

This is very well explained! Thank you… very much…

Thanks for your video. Amazing walk-through of your train of thought.
I have a doubt though. For each string, we use a hash map with a character as key. What happens when the character is repeated?

That was cool.finally i understood.Thanks Sam.Waiting for u r remaining videos!!

Thank you so much for this great tutorial. Can you please make a video explaining problem 1.7 of Cracking the Coding Interview? The problem is called Rotate Matrix. It would be great if you could explain how to calculate the offset, first, last indices. Thank you in advance.

Hey Sam, I do not see you posting any new videos for some time now. Please dont stop. You have been doing a great job .