Search Suggestions System
Explore how to design a search suggestions system that suggests up to three products matching typed prefixes using a trie data structure. Learn to handle constraints and implement the solution efficiently to improve your problem-solving skills for coding interviews.
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:
-
products.length -
products[i].length -
sum(products[i].length) - All the strings of products are unique.
products[i]consists of lowercase English letters.-
searched word.length - 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
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”
[[“camera”, “car”, “carpet”], [“camera”], [“camera”], [“camera”], [“camera”]]
[[“camera”, “car”, “carpet”], [“camera”, “car”, “carpet”], [“camera”], [“camera”], [“camera”]]
[[“camera”, “car”, “carpet”], [“camera”, “car”, “carpet”], [“camera”], [“camera”], [“camera”], [“camera”]]
[[“camera”, “car”, “carpet”], [“camera”, “car”, “carpet”], [“camera”]]
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.
Try it yourself
Implement your solution in main.js in the following coding playground. You’ll need the provided supporting code to implement your solution.
import TrieNode from "./trie_node.js";// Definition for a trie node.// class TrieNode {// constructor() {// this.searchWords = [];// this.children = {};// }// }function suggestedProducts(products, searchWord){// Replace this placeholder return statement with your codereturn [[]];}export {suggestedProducts}