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.
This approach significantly improves the performance of finding the highest-rated food by using more advanced data structures. It maintains a sorted set of foods for each cuisine, allowing for near-instant retrieval of the top-rated item. The key is to use a TreeSet to automatically keep foods sorted by rating and name.
Algorithm
- Data Structures:
- Define a custom
Foodclass containingname,cuisine, andrating. This class must implementComparable<Food>to define the sorting order: descending by rating, then ascending by name. foodInfoMap: AHashMap<String, Food>to map a food's name to itsFoodobject. This allows for O(1) access to a food's details.cuisineFoodMap: AHashMap<String, TreeSet<Food>>. This maps each cuisine to aTreeSetof itsFoodobjects. TheTreeSetautomatically maintains the foods in the desired sorted order.
- Define a custom
- Initialization
FoodRatings(foods, cuisines, ratings):- Iterate through the input arrays. For each item, create a new
Foodobject. - Store the food name and its object in
foodInfoMap. - Add the
Foodobject to the appropriateTreeSetincuisineFoodMap. TheTreeSetwill handle placing it in the correct sorted position.
- Iterate through the input arrays. For each item, create a new
changeRating(food, newRating):- Look up the
Foodobject infoodInfoMapusing the food's name. - Get the
TreeSetfor that food's cuisine fromcuisineFoodMap. - Crucially, remove the
Foodobject from theTreeSetbefore changing its rating. - Update the
ratingfield of theFoodobject. - Add the modified
Foodobject back into theTreeSet. It will be re-inserted based on its new rating.
- Look up the
highestRated(cuisine):- Get the
TreeSetfor the givencuisine. - The highest-rated food is guaranteed to be the first element in the
TreeSetdue to our custom sorting. Return its name.
- Get the
Walkthrough
The core idea is to keep the foods for each cuisine sorted by rating (descending) and then by name (ascending for ties). A TreeSet in Java is a perfect data structure for this, as it maintains elements in sorted order and provides logarithmic time complexity for additions and removals.
We use two main data structures:
foodInfoMap: AHashMap<String, Food>that maps a food's name to a customFoodobject. This allows for quick lookups when a rating needs to be changed.cuisineFoodMap: AHashMap<String, TreeSet<Food>>. This map stores aTreeSetfor each cuisine. TheTreeSetautomatically sorts theFoodobjects according to our defined criteria.
The changeRating operation is the most nuanced. Since a TreeSet's order depends on the state of its objects, we cannot simply modify an object's rating while it's in the set. We must first remove the object, then update its rating, and finally add it back to the set, which will place it in its new correct position. The highestRated operation becomes trivial and extremely fast, as it just needs to peek at the first element of the sorted set.
import java.util.HashMap;import java.util.Map;import java.util.TreeSet; class FoodRatings { // A custom class to store food details and define sorting logic. private class Food implements Comparable<Food> { String name; String cuisine; int rating; Food(String name, String cuisine, int rating) { this.name = name; this.cuisine = cuisine; this.rating = rating; } @Override public int compareTo(Food other) { // Sort by rating in descending order. if (this.rating != other.rating) { return Integer.compare(other.rating, this.rating); } // If ratings are the same, sort by name in ascending (lexicographical) order. return this.name.compareTo(other.name); } } // Map cuisine to a sorted set of foods. private Map<String, TreeSet<Food>> cuisineFoodMap; // Map food name to its Food object for quick access. private Map<String, Food> foodInfoMap; public FoodRatings(String[] foods, String[] cuisines, int[] ratings) { cuisineFoodMap = new HashMap<>(); foodInfoMap = new HashMap<>(); for (int i = 0; i < foods.length; i++) { Food foodItem = new Food(foods[i], cuisines[i], ratings[i]); foodInfoMap.put(foods[i], foodItem); cuisineFoodMap.computeIfAbsent(cuisines[i], k -> new TreeSet<>()).add(foodItem); } } public void changeRating(String food, int newRating) { // Get the Food object. Food foodItem = foodInfoMap.get(food); // Get the TreeSet for the specific cuisine. TreeSet<Food> foodSet = cuisineFoodMap.get(foodItem.cuisine); // Remove the old entry from the TreeSet. foodSet.remove(foodItem); // Update the rating in the Food object. foodItem.rating = newRating; // Add the updated Food object back to the TreeSet. // It will be placed in the correct sorted position. foodSet.add(foodItem); } public String highestRated(String cuisine) { // The highest-rated food is the first element in the TreeSet. return cuisineFoodMap.get(cuisine).first().name; }}Complexity
Time
- **Constructor**: O(N * log L), where N is the number of foods and L is the maximum number of foods in a single cuisine. Each insertion into the `TreeSet` takes O(log L). - **`changeRating`**: O(log L) due to removal and insertion operations in the `TreeSet`. - **`highestRated`**: O(1) to access the first element of the `TreeSet`.
Space
O(N), where N is the total number of food items. We store each food as a `Food` object and maintain pointers in the maps and `TreeSet`s.
Trade-offs
Pros
Extremely fast
highestRatedoperation, with O(1) time complexity.Efficient
changeRatingoperation with logarithmic time complexity.Overall well-balanced and highly efficient performance for the given problem constraints.
Cons
More complex to implement due to the custom class and the need to manage
TreeSetupdates correctly.Slightly higher memory overhead due to storing custom objects and the
TreeSetdata structure.
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); */using pis = pair < int , string > ; class FoodRatings { map < string , pis > mp ; map < string , set < pis >> t ; public: FoodRatings ( vector < string >& foods , vector < string >& cuisines , vector < int >& ratings ) { int n = foods . size (); for ( int i = 0 ; i < n ; ++ i ) { string a = foods [ i ], b = cuisines [ i ]; int c = ratings [ i ]; mp [ a ] = pis ( c , b ); t [ b ]. insert ( pis ( - c , a )); } } void changeRating ( string food , int newRating ) { pis & p = mp [ food ]; t [ p . second ]. erase ( pis ( - p . first , food )); p . first = newRating ; t [ p . second ]. insert ( pis ( - p . first , food )); } string highestRated ( string cuisine ) { return t [ cuisine ]. begin () -> second ; } }; /** * 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); */from sortedcontainers import SortedSet class FoodRatings : def __init__ ( self , foods : List [ str ], cuisines : List [ str ], ratings : List [ int ]): self . mp = {} self . t = defaultdict ( lambda : SortedSet ( key = lambda x : ( - x [ 0 ], x [ 1 ]))) for a , b , c in zip ( foods , cuisines , ratings ): self . mp [ a ] = ( b , c ) self . t [ b ]. add (( c , a )) def changeRating ( self , food : str , newRating : int ) -> None : b , c = self . mp [ food ] self . mp [ food ] = ( b , newRating ) self . t [ b ]. remove (( c , food )) self . t [ b ]. add (( newRating , food )) def highestRated ( self , cuisine : str ) -> str : return self . t [ cuisine ][ 0 ][ 1 ] # Your FoodRatings object will be instantiated and called as such: # obj = FoodRatings(foods, cuisines, ratings) # obj.changeRating(food,newRating) # 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.