Grokking 75: Top Coding Interview Questions
Vote

0% completed

​

Search Suggestions System (medium)

Problem Statement

Given a list of distinct strings products and a string searchWord.

Determine a set of product suggestions after each character of the search word is typed. Every time a character is typed, return a list containing up to three product names from the products list that have the same prefix as the typed string.

If there are more than 3 matching products, return 3 lexicographically smallest products. These product names should be returned in lexicographical (alphabetical) order.

Examples

  1. Example 1:

.....

.....

.....

Like the course? Get enrolled and start learning!
S

singhursefamily

· 8 months ago

It seems to me that the Example 1 expected output is not in alphabetical order.

Quoting from Example 1:

  • Input: Products: ["apple", "apricot", "application"], searchWord: "app"
  • Expected Output: [["apple", "apricot", "application"], ["apple", "apricot", "application"], ["apple", "application"]]

The problem is that "apricot" comes after "application" when sorted alphabetically since the third character of "apricot" is "r" while the third character of "application" is "p" and "r" comes after "p".

So the expected output should actually be: [["apple", "application", "apricot" ], ["apple", "application", "apricot" ], ["apple", "application"]].

Please correct me if I'm mistaken.

Tuấn Trần

Tuấn Trần

· 3 years ago

Input:

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

"mouse"

Output

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

Expected

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

For prefix "m", all 5 words should be showed, do I understand it correctly?

Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Node:
    def __init__(self, val):
        self.val = val 
        self.children = {}
        self.isEnd = False
        
class Solution: 
    def suggestedProducts(self, products, searchWord):
        # build trie
        root = Node('*')
        for product in products:
            node = root
            for char in product:
                if char not in node.children:
                    node.children[char] = Node(char)
                node = node.children[char]
            node.isEnd = True
        
        # dfs on the trie
        def dfs(node, path, result):
            if node.isEnd:
                result.append(''.join(path))

            for child_node_char, child_node in node.children.items():
                path.append(child_node_char)
                df
Gustavo Alves

Gustavo Alves

· 9 months ago

<p>...</p>
Show 2 replies