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

Search Suggestions System

Explore how to design a search suggestions system with a Trie to return up to three product names sharing a prefix in lexicographical order as each character is typed. Understand and implement the problem constraints using efficient string manipulation and prefix matching techniques in C++.

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 SearchSuggestionsSystem.cpp in the following coding playground. You’ll need the provided supporting code to implement your solution.

C++
usercode > SearchSuggestionsSystem.cpp
// Definition for a TrieNode
// class TrieNode {
//   public:
//     std::map < char, TrieNode * > children;
//   std::vector < std::string > searchWords;
// };
vector<vector<string>> SuggestedProducts(vector<string> products, string searchWord){
    // Replace this placeholder return statement with your code
    return {};
}
Search Suggestions System