Design a food rating system that can do the following:
Implement the FoodRatings class:
FoodRatings(String[] foods, String[] cuisines, int[] ratings) Initializes the system. The food items are described by foods, cuisines and ratings, all of which have a length of n.
foods[i] is the name of the ith food,cuisines[i] is the type of cuisine of the ith food, andratings[i] is the initial rating of the ith food.void changeRating(String food, int newRating) Changes the rating of the food item with the name food.String highestRated(String cuisine) Returns the name of the food item that has the highest rating for the given type of cuisine. 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] <= 108foods are distinct.food will be the name of a food item in the system across all calls to changeRating.cuisine will be a type of cuisine of at least one food item in the system across all calls to highestRated.2 * 104 calls in total will be made to changeRating and highestRated.This approach involves using dictionaries (or hash maps) to store and manage the relationships between foods, cuisines, and their ratings. We will have multiple dictionaries to efficiently perform update and retrieval operations.
The code initializes a class with dictionaries to map each food to its corresponding cuisine and rating. Another dictionary maps cuisines to lists of foods, sorted by their negative ratings (to simulate max-heap behavior using sorting). When we change a rating, we update the corresponding entry and re-sort the list for that cuisine. For retrieving the highest-rated food, we return the first item in the sorted list.
C++
Java
JavaScript
Time Complexity: O(N log N) for initialization and O(F log F) for changing rating where N is the number of foods and F is the list of foods for a cuisine.
Space Complexity: O(N) for storage of mappings.
This approach uses priority queues (heaps) to manage the highest-rated food for a cuisine. Heaps offer efficient operations for maintaining and retrieving maximum values, which can be useful for finding the highest-rated item.
The Python version uses a heap to maintain the highest-rated food for each cuisine. Negative ratings are stored to utilize the min-heap structure for max-heap behavior. If ratings change, old entries may remain invalid due to imposition of new valid values. Therefore, we remove these as necessary during the highestRated check.
Java
Time Complexity: O(N) for initialization and O(log F) for updating heap or retrieving the maximum where F is the number of foods for given cuisine.
Space Complexity: O(N) for storing the heap elements.
| Approach | Complexity |
|---|---|
| Using Dictionaries/Hash Maps | Time Complexity: O(N log N) for initialization and O(F log F) for changing rating where N is the number of foods and F is the list of foods for a cuisine. |
| Using Priority Heaps | Time Complexity: O(N) for initialization and O(log F) for updating heap or retrieving the maximum where F is the number of foods for given cuisine. |
Design a Food Rating System - Leetcode 2353 - Python • NeetCodeIO • 15,343 views views
Watch 9 more video solutions →Practice Design a Food Rating System with our built-in code editor and test cases.
Practice on FleetCode