Design a Food Rating System
Problem Description
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
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.
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
In this approach, we maintain lists to track the food, cuisine, and ratings. Every operation such as adding, removing, or finding the highest rating will require iterating through these lists.
Approach:
- Keep a simple list of food items along with their respective cuisines and ratings.
- While changing ratings, directly modify the list for that food item.
- For finding the highest-rated food in a cuisine, iterate through the full list to find the food item with the highest rating for that cuisine.
Code:
- Time Complexity:
changeRating: O(n) where n is the number of foods.highestRated: O(n) for searching through the list.- Space Complexity: O(n) for storing the food items.
2. HashMap with Sorting
Intuition:
Using HashMaps to store foods and their details allows for faster access and update. However, for finding the highest rated food of a specific cuisine, sorting is still required, which can be optimized further.
Approach:
- Use a HashMap to store food details, allowing O(1) access for updates.
- Store cuisines in a HashMap with a list of foods to facilitate easy sorting for rating retrieval.
Code:
- Time Complexity:
changeRating: O(1) for direct update via HashMap.highestRated: O(m log m), where m is the number of foods for a specific cuisine.- Space Complexity: O(n + m) where n is the number of foods and m the number of cuisines.
3. TreeMap with HashMap
Intuition:
Leverage the TreeMap that keeps entries sorted based on keys, which can be used to maintain a sorted order of the ratings while supporting efficient lookup for finding the highest rated meal.
Approach:
- Utilize a HashMap for storing food ratings quickly accessible for updates.
- For each cuisine, use a TreeMap with the food names as keys, which automatically maintains a sorted order of foods by rating in descending order.
- Directly fetch the first entry of the TreeMap for highest-rated food retrieval.
Code:
- Time Complexity:
changeRating: O(log m) where m is the number of interacting foods in the same cuisine due to the TreeMap operations.highestRated: O(1), quick access to the highest rating using TreeMap.- Space Complexity: O(n + k) where n is the number of foods and k is the space for maintaining TreeMap entries per cuisine.