Search Suggestions System: Coding Interview Question

In this post, we will solve this LeetCode coding interview questions efficiently by utilizing the Trie data structure.

Problem Statement

You are given an array of strings products and a string searchWord.

Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return a list of lists of the suggested products after each character of searchWord is typed.

Introduction

Given an array of strings products and a string searchWord, we are to design a system that suggests at most three product names from products after each character of searchWord is typed.

Suggestions are sorted in lexicographical order and any matches for searchWord are in products. If there are more than three viable options, we pick the top three in lexicographical order. If there are no viable options to suggest for a particular character, we will have an empty list.

Problem Breakdown

To better understand the problem, let’s look at an example.

We have a list of products = [“mobile”, “mouse”, “moneypot”, “monitor”, “mousepad”], and the searchWord is “mouse”.

The system will give suggestions after each character of the searchWord is typed.

1. First character of searchWord = “m”
2. All products start with “m”, but the system can only suggest three product names at most. As the products are sorted lexicographically, the system suggests [“mobile”,”moneypot”,”monitor”].
3. Second character of searchWord = “o”
4. With the current searchWord “mo”, the products that start with “mo” are [“mobile”,”moneypot”,”monitor”]. Again, the system suggests three product names [“mobile”,”moneypot”,”monitor”].
5. Third character of searchWord = “u”
6. Now, the searchWord becomes “mou”. The products starting with “mou” are [“mouse”,”mousepad”]. So, the system suggests [“mouse”,”mousepad”].

For the rest of the characters “s”, “e” in the searchWord “mouse”, the system will continue suggesting [“mouse”,”mousepad”] as these are the only two products which start with “mous” and “mouse” respectively.

So, the final output for this given example would be:

[
  ["mobile","moneypot","monitor"],
  ["mobile","moneypot","monitor"],
  ["mouse","mousepad"],
  ["mouse","mousepad"],
  ["mouse","mousepad"]
]

Hope this breakdown helps you to understand the problem and the approach for solving it.

Approach

Given the problem’s requirements, it seems like a Trie would be an ideal data structure to use. We can insert all the product names into a Trie, and then every time we need to search, we can just descend down the Trie.

Here’s how we can implement this:

1. First, we sort the products array. This ensures that when we are inserting into our Trie, lexicographically smaller words are inserted first.
2. We then create a Trie and insert all the products into it.
3. We initialize an empty result list to store our suggestions.
4. For each character in searchWord, we descend down the Trie, adding suggestions as we go. We add these suggestions to our result list.

Java Solution

Now let’s implement our approach in Java. Here is the code:

class Solution {
    class TrieNode {
        TrieNode[] children;
        List<String> suggestions;
        
        TrieNode() {
            children = new TrieNode[26];
            suggestions = new ArrayList<>();
        }
    }
    
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        TrieNode root = new TrieNode();
        Arrays.sort(products);  // sort products.
        
        // Insert products into trie.
        for (String product : products) {
            insertProduct(product, root);
        }
        
        List<List<String>> result = new ArrayList<>();
        
        // Search for the searchWord in the trie.
        for (char c : searchWord.toCharArray()) {
            if (root != null) {
                root = root.children[c - 'a'];
            }
            result.add(root == null ? Arrays.asList() : root.suggestions);
        }
        
        return result;
    }
    
    private void insertProduct(String product, TrieNode root) {
        TrieNode node = root;
        for (char c : product.toCharArray()) {
            if (node.children[c - 'a'] == null) {
                node.children[c - 'a'] = new TrieNode();
            }
            node = node.children[c - 'a'];
            
            // add products to the suggestion list.
            if (node.suggestions.size() < 3) {
                node.suggestions.add(product);
            }
        }
    }
}

Conclusion

Trie is an efficient data structure for solving problems involving prefixes. This problem is a typical application of Trie. The name trie has been derived from the word retrieve, as Trie is very efficient in retrieving items based on their prefixes.

Time Complexity

The time complexity for this solution can be categorized into two parts:

1. Sorting the products array: The time complexity of sorting an array of n strings (each of maximum length k) is O(nklog(n)).
2. Inserting into the Trie and Searching: Inserting all the products into the Trie would take O(n*k), where n is the number of products and k is the average length of a product.

So, the overall time complexity would be O(nklog(n) + nk), dominated by the O(nk*log(n)) from the sorting operation.

Space Complexity

The space complexity for this solution is primarily dictated by the space used by the Trie data structure. In the worst case, if there are no common prefixes among the words, the space used would be O(n*k), where n is the number of products and k is the maximum length of a product.

Therefore, we can say the space complexity is O(n*k).

Please follow me if you found this article helpful and want to dive deeper into data structures and algorithms — there’s much more to come!