FastPrep
Problem · Trie

Search Suggestions System

Learn this problem
● MediumGoogleNEW GRADOA
See Google hiring insights

Problem statement

You are given a list of products, where each product is a string. You are also given a searchWord. After each character typed, return the top k suggestions of product names that match the typed prefix.

Each product also has an associated popularity score (Map) ((P.S. changed it to String[][] for FP's convenience :)). Suggestions should be returned in order of:

  • Highest popularity score
  • If scores are equal, return the lexicographically smaller product.

    • You must return suggestions after each character of searchWord. Handle up to 1e5 products and optimize for performance.

    Function

    searchSuggestions(products: String[], popularity: String[][], searchWord: String, k: int) → String[][]

    Examples

    Example 1

    products = ["apple", "appetizer", "application", "app", "apply", "banana", "appstore"]popularity = [["apple", "80"], ["appetizer", "70"], ["application", "90"], ["app", "90"], ["apply", "85"], ["banana", "60"], ["appstore", "90"]]searchWord = "app"k = 3return = [["app", "application", "appstore"], ["app", "application", "appstore"], ["app", "application", "appstore"]]
    ~.~

    Constraints

    • 1 ≤ products.length = popularity.length ≤ 10^5
    • Product names are unique non-empty lowercase strings, and their total length is at most 10^6.
    • Each popularity row is [product, score], contains every product exactly once, and encodes the integer score as a string.
    • 1 ≤ searchWord.length ≤ 10^5
    • 1 ≤ k ≤ products.length

    More Google problems

    drafts saved locally
    public String[][] searchSuggestions(String[] products, String[][] map, String searchWord, int k) {
  // write your code here
}
    products["apple", "appetizer", "application", "app", "apply", "banana", "appstore"]
    popularity[["apple", "80"], ["appetizer", "70"], ["application", "90"], ["app", "90"], ["apply", "85"], ["banana", "60"], ["appstore", "90"]]
    searchWord"app"
    k3
    expected[["app", "application", "appstore", "app", "application", "appstore", "app", "application", "appstore"]]
    checking account