Design a Food Rating System
MedPrompt
Design a food rating system that can do the following:
- Modify the rating of a food item listed in the system.
- Return the highest-rated food item for a type of cuisine in the system.
Implement the FoodRatings class:
FoodRatings(String[] foods, String[] cuisines, int[] ratings)Initializes the system. The food items are described byfoods,cuisinesandratings, all of which have a length ofn.foods[i]is the name of theithfood,cuisines[i]is the type of cuisine of theithfood, andratings[i]is the initial rating of theithfood.
void changeRating(String food, int newRating)Changes the rating of the food item with the namefood.String highestRated(String cuisine)Returns the name of the food item that has the highest rating for the given type ofcuisine. If there is a tie, return the item with the lexicographically smaller name.
Note that a string x is lexicographically smaller than string y if x comes before y in dictionary order, that is, either x is a prefix of y, or if i is the first position such that x[i] != y[i], then x[i] comes before y[i] in alphabetic order.
Example 1:
Input
["FoodRatings", "highestRated", "highestRated", "changeRating", "highestRated", "changeRating", "highestRated"]
[[["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], [9, 12, 8, 15, 14, 7]], ["korean"], ["japanese"], ["sushi", 16], ["japanese"], ["ramen", 16], ["japanese"]]
Output
[null, "kimchi", "ramen", null, "sushi", null, "ramen"]
Explanation
FoodRatings foodRatings = new FoodRatings(["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], [9, 12, 8, 15, 14, 7]);
foodRatings.highestRated("korean"); // return "kimchi"
// "kimchi" is the highest rated korean food with a rating of 9.
foodRatings.highestRated("japanese"); // return "ramen"
// "ramen" is the highest rated japanese food with a rating of 14.
foodRatings.changeRating("sushi", 16); // "sushi" now has a rating of 16.
foodRatings.highestRated("japanese"); // return "sushi"
// "sushi" is the highest rated japanese food with a rating of 16.
foodRatings.changeRating("ramen", 16); // "ramen" now has a rating of 16.
foodRatings.highestRated("japanese"); // return "ramen"
// Both "sushi" and "ramen" have a rating of 16.
// However, "ramen" is lexicographically smaller than "sushi".
Constraints:
1 <= n <= 2 * 104n == foods.length == cuisines.length == ratings.length1 <= foods[i].length, cuisines[i].length <= 10foods[i],cuisines[i]consist of lowercase English letters.1 <= ratings[i] <= 108- All the strings in
foodsare distinct. foodwill be the name of a food item in the system across all calls tochangeRating.cuisinewill be a type of cuisine of at least one food item in the system across all calls tohighestRated.- At most
2 * 104calls in total will be made tochangeRatingandhighestRated.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses simple HashMaps to store the food data. To find the highest-rated food for a cuisine, it iterates through all foods of that cuisine, comparing them one by one to find the one with the highest rating, handling ties with lexicographical comparison.
Algorithm
- Data Structures:
foodRatings: AHashMap<String, Integer>to map each food name to its current rating.foodCuisines: AHashMap<String, String>to map each food name to its cuisine type.cuisineFoods: AHashMap<String, List<String>>to group food names by their cuisine.
- Initialization
FoodRatings(foods, cuisines, ratings):- Iterate through the input arrays from
i = 0ton-1. - For each item, populate the three maps with the food's name, rating, cuisine, and add it to the list of foods for its cuisine.
- Iterate through the input arrays from
changeRating(food, newRating):- Simply update the rating for the given
foodin thefoodRatingsmap. This is an O(1) operation.
- Simply update the rating for the given
highestRated(cuisine):- Retrieve the list of foods for the given
cuisinefrom thecuisineFoodsmap. - Initialize
maxRating = -1andbestFood = "". - Iterate through the list of foods.
- For each food, get its current rating from
foodRatings. - Compare the food's rating with
maxRating. If it's higher, or if it's equal and the food's name is lexicographically smaller than the currentbestFood, updatemaxRatingandbestFood. - After checking all foods, return
bestFood.
- Retrieve the list of foods for the given
Walkthrough
In this straightforward approach, we use three separate HashMaps to keep track of the data. One map stores food-to-rating pairs, another stores food-to-cuisine pairs, and the third stores cuisine-to-list-of-foods pairs.
While initializing, we populate these maps in a single pass through the input arrays. The changeRating operation is very efficient as it only requires a single update in the ratings map. However, the highestRated method's performance is dependent on the number of foods within a specific cuisine. It must perform a linear scan over all foods of that cuisine, checking each one's rating and name to determine the highest-rated one according to the rules. This can be inefficient if a cuisine category is very large.
import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map; class FoodRatings { private Map<String, Integer> foodRatings; private Map<String, String> foodCuisines; private Map<String, List<String>> cuisineFoods; public FoodRatings(String[] foods, String[] cuisines, int[] ratings) { foodRatings = new HashMap<>(); foodCuisines = new HashMap<>(); cuisineFoods = new HashMap<>(); for (int i = 0; i < foods.length; ++i) { foodRatings.put(foods[i], ratings[i]); foodCuisines.put(foods[i], cuisines[i]); cuisineFoods.computeIfAbsent(cuisines[i], k -> new ArrayList<>()).add(foods[i]); } } public void changeRating(String food, int newRating) { foodRatings.put(food, newRating); } public String highestRated(String cuisine) { List<String> foodsInCuisine = cuisineFoods.get(cuisine); String bestFood = ""; int maxRating = -1; for (String food : foodsInCuisine) { int currentRating = foodRatings.get(food); if (bestFood.isEmpty() || currentRating > maxRating) { maxRating = currentRating; bestFood = food; } else if (currentRating == maxRating) { if (food.compareTo(bestFood) < 0) { bestFood = food; } } } return bestFood; }}Complexity
Time
- **Constructor**: O(N), where N is the number of initial food items. - **`changeRating`**: O(1). - **`highestRated`**: O(L), where L is the number of foods in the given cuisine. In the worst case, L can be equal to N.
Space
O(N), where N is the total number of food items. We need to store information for each food item across three maps.
Trade-offs
Pros
Simple to understand and implement.
The
changeRatingoperation is very fast, with O(1) time complexity.
Cons
highestRatedcan be slow if a cuisine has a large number of food items, leading to potential Time Limit Exceeded errors on large test cases.
Solutions
Solution
class FoodRatings { private Map < String , TreeSet < Pair < Integer , String >>> d = new HashMap <>(); private Map < String , Pair < Integer , String >> g = new HashMap <>(); private final Comparator < Pair < Integer , String >> cmp = ( a , b ) -> { if (! a . getKey (). equals ( b . getKey ())) { return b . getKey (). compareTo ( a . getKey ()); } return a . getValue (). compareTo ( b . getValue ()); }; public FoodRatings ( String [] foods , String [] cuisines , int [] ratings ) { for ( int i = 0 ; i < foods . length ; ++ i ) { String food = foods [ i ], cuisine = cuisines [ i ]; int rating = ratings [ i ]; d . computeIfAbsent ( cuisine , k -> new TreeSet <>( cmp )). add ( new Pair <>( rating , food )); g . put ( food , new Pair <>( rating , cuisine )); } } public void changeRating ( String food , int newRating ) { Pair < Integer , String > old = g . get ( food ); int oldRating = old . getKey (); String cuisine = old . getValue (); g . put ( food , new Pair <>( newRating , cuisine )); d . get ( cuisine ). remove ( new Pair <>( oldRating , food )); d . get ( cuisine ). add ( new Pair <>( newRating , food )); } public String highestRated ( String cuisine ) { return d . get ( cuisine ). first (). getValue (); } } /** * Your FoodRatings object will be instantiated and called as such: * FoodRatings obj = new FoodRatings(foods, cuisines, ratings); * obj.changeRating(food,newRating); * String param_2 = obj.highestRated(cuisine); */Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.