FastPrep
Problem · Trie

Search Suggestions System

● MediumGoogleNEW GRADOA
See Google hiring insights

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.

    Examples
    01 · 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 = 3
return = [["app", "application", "appstore"], ["app", "application", "appstore"], ["app", "application", "appstore"]]
    ~.~
    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"]]
    sign in to submit