Apex Coding Interview Challenge #8

Implement an autocomplete system. That is, given a query string s and a set of all possible query strings, return all strings in the set that have s as a prefix.

For example, given the query string de and the set of strings [dog, deer, deal], return [deer, deal].

Hint: Try preprocessing the dictionary into a more efficient data structure to speed up queries.

Solution

public Map<String, List<String>> mapOfDictionary(List<String> wordsLst){
    Map<String, List<String>> dictionaryMap = new Map<String, List<String>>();
    
    for (String w : wordsLst){
        List<String> wordChars = new List<String>(w.split(''));
        String concatChars = '';
        for (String wordChar : wordChars){
            concatChars += wordChar;
            if (dictionaryMap.containsKey(concatChars)){
                List<String> wordsForChars = dictionaryMap.get(concatChars);
                wordsForChars.add(w);
                dictionaryMap.put(concatChars, wordsForChars);
            } else {
                dictionaryMap.put(concatChars, new List<String>{w});
            }
        }   
    }
   
    return dictionaryMap;
}

public List<String> getWordsForAutoComplete(String word){
    Map<String, List<String>> dictionaryMap = mapOfDictionary(new List<String>{'dog', 'deer', 'deal'});
    return dictionaryMap.get(word);
}

Testing

System.debug(getWordsForAutoComplete('de')); //(deer, deal)

Complexity Analysis
Time complexity: O(n^2)
Space complexity:  O(m*n) //m – max length of string, n – amount of words

2 Comments on “Apex Coding Interview Challenge #8”

  1. Hello Thys!
    I am wondering about Space complexity in this assignment.
    Since there is basically a prefix map of all possible substrings with all of the words, then space complexity would be O(26*m*n) = O(m,n) , where m — max length of each word, and n – amount of words in total.

  2. Hi kurunve, yes you are correct. Try some of my other challenges and let me know.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: