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

Search Suggestions System

Explore how to implement a search suggestions system that returns up to three products matching a typed prefix in lexicographical order. Understand the use of trie data structures to efficiently handle string prefix searches. This lesson helps you develop the ability to build systems that suggest relevant products as users type, practicing practical applications of tries.

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