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

Search Suggestions System

Explore how to implement a search suggestions system using tries to efficiently retrieve up to three product names sharing a prefix as each character of the search word is entered. Understand the approach to manage string arrays and optimize 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 SearchSuggestion.java in the following coding playground. You’ll need the provided supporting code to implement your solution.

Java
usercode > SearchSuggestion.java
import java.util.*;
// Definition for a trie node.
// public class Node {
//     Node [] child = new Node [26];
//     LinkedList<String> searchWords = new LinkedList<>();
// }
class SearchSuggestion {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        // Replace this placeholder return statement with your code
        return null;
    }
}
Search Suggestions System