Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in Python

Search Suggestions System

Explore how to design a search suggestions system that suggests up to three product names sharing a common prefix with each typed character. Learn to implement efficient trie structures to optimize prefix matching and return lexicographically ordered suggestions in real time.

We'll cover the following...

Statement

Given an array of strings called products and a word to search, design a system that, when each character of the searched word is typed, suggests at most three product names from products. Suggested products should share a common prefix with the searched word. If more than three products exist with a common prefix, return the three product names that appear first in lexicographical order.

Return the suggested products, which will be a list of lists after each character of searched word is typed.

Constraints:

  • 1≤1 \leq products.length ≤1000\leq 1000
  • 1≤1 \leq products[i].length ≤3000\leq 3000
  • 1≤1 \leq sum(products[i].length) ≤2×103\leq 2 \times 10^3
  • All the strings of products are unique.
  • products[i] consists of lowercase English letters.
  • 1≤1 \leq searched word.length ≤1000\leq 1000
  • The searched word consists of lowercase English letters.

Examples

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Search Suggestions System

1.

What is the output if the following array of products and the word to be searched are given as input?

products = [“carpet”, “cart”, “car”, “camera”, “crate”]

searched word = “camera”

A.

[[“camera”, “car”, “carpet”], [“camera”], [“camera”], [“camera”], [“camera”]]

B.

[[“camera”, “car”, “carpet”], [“camera”, “car”, “carpet”], [“camera”], [“camera”], [“camera”]]

C.

[[“camera”, “car”, “carpet”], [“camera”, “car”, “carpet”], [“camera”], [“camera”], [“camera”], [“camera”]]

D.

[[“camera”, “car”, “carpet”], [“camera”, “car”, “carpet”], [“camera”]]

1 / 2

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3

Try it yourself

Implement your solution in main.py in the following coding playground. You’ll need the provided supporting code to implement your solution.

Python
usercode > main.py
from trie_node import TrieNode

 # Definition for a trie node.

# class TrieNode(object):

#     def __init__(self):

#         self.search_words = []

#         self.children = {}



def suggested_products(products, search_word):



    # Replace this placeholder return statement with your code

    return [[]]
Search Suggestions System