Interview Question: Autocomplete

21
1



Coding interview question from

In this video, I show how to implement a class with autocomplete functionality.

Do you have a big interview coming up with Google or Facebook? Do you want to ace your coding interviews once and for all? If so, Byte by Byte has everything that you need to go to get your dream job. We’ve helped thousands of students improve their interviewing and we can help you too.

Stuck on Dynamic Programming? Check out our free ebook: www.dynamicprogrammingbook.com

50 Practice Questions:

You can also find me on
Twitter:
Facebook:
Email: sam@byte-by-byte.com

Nguồn:https://wijstaanvooronzegrondrechten.org/

21 COMMENTS

  1. 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.

  2. 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???

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

    for(String match : dic) {

    if(match.startsWith(word)) {

    System.out.println(match);

    }

    }

    }

  4. 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!

  5. 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.

  6. 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'))

  7. 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?

  8. 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?

  9. 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.

  10. 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 .

LEAVE A REPLY

Please enter your comment!
Please enter your name here