Watch 10 video solutions for Design a Food Rating System, a medium level problem involving Hash Table, Design, Heap (Priority Queue). This walkthrough by NeetCodeIO has 17,688 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.Problem Overview: Design a data structure that tracks foods, their cuisines, and ratings. The system must support updating a food's rating and returning the highest-rated food for a cuisine, breaking ties using lexicographical order.
Approach 1: Dictionaries / Hash Maps with Ordered Tracking (O(log n) per update, O(1)–O(log n) query)
This approach stores core relationships using hash tables. Maintain a map from food → (cuisine, rating) and another map from cuisine → ordered collection of foods sorted by rating (descending) and name (ascending). When changeRating runs, update the food's rating and reposition it inside the cuisine's ordered structure. Retrieving highestRated simply returns the first element of the ordered set. The key insight is separating identity lookup (fast with hash maps) from ranking (handled by an ordered container). Time complexity is O(log n) for updates due to reordering, and space complexity is O(n) for storing mappings and ordered structures.
Approach 2: Priority Heap per Cuisine with Lazy Updates (O(log n) update, O(log n) query)
A scalable approach uses a priority queue for each cuisine. Maintain a hash map food → (cuisine, rating) and another map cuisine → max heap containing entries like (-rating, foodName). When the rating changes, push the updated pair into the heap instead of removing the old one. During highestRated, repeatedly check the heap top against the current rating stored in the hash map. If it is outdated, pop it (lazy deletion). The first valid entry is the correct answer. Heap ordering naturally handles rating priority and lexicographic tie-breaking. Each push or pop costs O(log n), and space complexity remains O(n) though the heap may temporarily contain stale entries.
Recommended for interviews: Interviewers typically expect the heap-based design. It demonstrates understanding of system design patterns, priority queues, and lazy deletion to avoid expensive removals. The ordered-set approach is conceptually clean and efficient in languages with strong tree-based containers, but the heap + hash map combination is easier to implement in most interview environments.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Maps + Ordered Set | O(log n) update, O(1)–O(log n) query | O(n) | When the language supports efficient ordered sets or balanced trees |
| Hash Maps + Priority Heap (Lazy Deletion) | O(log n) update, O(log n) query | O(n) | General case; easiest to implement with priority queues |