Design a Food Rating System solution and explanation
Google
9 more videos on this problem
Design a Food Rating System - Leetcode 2353 - PythonNeetCodeIO · 15:37 · 17K views
Design a Food Rating System | Clean Approach | Leetcode 2353 | codestorywithMIKcodestorywithMIK · 25:33 · 10K views
2353. Design a Food Rating System | Easiest & Most IntuitiveAryan Mittal · 12:31 · 2K views
Leetcode 2353 Design a Food Rating System| Easy Peasy MapsCoding Decoded · 7:47 · 2K views
2353. Design a Food Rating System (Leetcode Medium)Programming Live with Larry · 9:43 · 991 views
Design a Food Rating System | Leetcode 2353 | Heap + HashmapTechdose · 27:36 · 941 views
Daily Leetcode #1996: Sep 17, 2025 - 2353. Design a Food Rating SystemProgramming Live with Larry · 8:05 · 758 views
2353. Design a Food Rating System | Leetcode Daily - PythonLeetcode Daily · 6:38 · 468 views
Solving LeetCode 2353 Design a Food Rating System | Design Problem | Ordered Set | AmazonCode Harmony · 17:58 · 333 views
Design a Food Rating System | 2353 Leetcode | Python3CodeMeThere · 24:02 · 221 views
The problem
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.
Approach overview
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 1: Using Dictionaries/Hash Maps
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.
class FoodRatings:
def __init__(self, foods: [str], cuisines: [str], ratings: [int]):
self.food_to_cuisine = {food: cuisine for food, cuisine in zip(foods, cuisines)}
self.food_to_rating = {food: rating for food, rating in zip(foods, ratings)}
self.cuisine_to_foods = {}
for food, cuisine, rating in zip(foods, cuisines, ratings):
if cuisine not in self.cuisine_to_foods:
self.cuisine_to_foods[cuisine] = []
self.cuisine_to_foods[cuisine].append((-rating, food))
for cuisine in self.cuisine_to_foods:
self.cuisine_to_foods[cuisine].sort()
def changeRating(self, food: str, newRating: int) -> None:
old_rating = self.food_to_rating[food]
self.food_to_rating[food] = newRating
cuisine = self.food_to_cuisine[food]
self.cuisine_to_foods[cuisine] = [(-self.food_to_rating[fd], fd) if fd == food else fr
for fr in self.cuisine_to_foods[cuisine]]
self.cuisine_to_foods[cuisine].sort()
def highestRated(self, cuisine: str) -> str:
return self.cuisine_to_foods[cuisine][0][1]import java.util.*;
public class FoodRatings {
private Map<String, String> foodToCuisine = new HashMap<>();
private Map<String, Integer> foodToRating = new HashMap<>();
private Map<String, TreeSet<String>> cuisineToFoods = new HashMap<>();
public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
for (int i = 0; i < foods.length; i++) {
String food = foods[i];
String cuisine = cuisines[i];
int rating = ratings[i];
foodToCuisine.put(food, cuisine);
foodToRating.put(food, rating);
cuisineToFoods.computeIfAbsent(cuisine, k -> new TreeSet<>((a, b) -> {
int cmp = Integer.compare(foodToRating.get(b), foodToRating.get(a));
return cmp == 0 ? a.compareTo(b) : cmp;
})).add(food);
}
}
public void changeRating(String food, int newRating) {
String cuisine = foodToCuisine.get(food);
cuisineToFoods.get(cuisine).remove(food);
foodToRating.put(food, newRating);
cuisineToFoods.get(cuisine).add(food);
}
public String highestRated(String cuisine) {
return cuisineToFoods.get(cuisine).first();
}
}#include <vector>
#include <string>
#include <unordered_map>
#include <set>
#include <utility>
using namespace std;
class FoodRatings {
private:
unordered_map<string, pair<int, string>> foodInfo;
unordered_map<string, set<pair<int, string>>> cuisineData;
public:
FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
int n = foods.size();
for (int i = 0; i < n; ++i) {
foodInfo[foods[i]] = {-ratings[i], cuisines[i]};
cuisineData[cuisines[i]].insert({-ratings[i], foods[i]});
}
}
void changeRating(string food, int newRating) {
auto &[oldRating, cuisine] = foodInfo[food];
cuisineData[cuisine].erase({oldRating, food});
oldRating = -newRating;
cuisineData[cuisine].insert({oldRating, food});
}
string highestRated(string cuisine) {
return cuisineData[cuisine].begin()->second;
}
};class FoodRatings {
constructor(foods, cuisines, ratings) {
this.foodToCuisine = {};
this.foodToRating = {};
this.cuisineToFoods = {};
for (let i = 0; i < foods.length; i++) {
const food = foods[i];
const cuisine = cuisines[i];
const rating = ratings[i];
this.foodToCuisine[food] = cuisine;
this.foodToRating[food] = rating;
if (!this.cuisineToFoods[cuisine]) {
this.cuisineToFoods[cuisine] = [];
}
this.cuisineToFoods[cuisine].push({food: food, rating: rating});
}
for (const cuisine in this.cuisineToFoods) {
this.cuisineToFoods[cuisine].sort((a, b) => {
if (b.rating === a.rating) return a.food.localeCompare(b.food);
return b.rating - a.rating;
});
}
}
changeRating(food, newRating) {
const oldRating = this.foodToRating[food];
const cuisine = this.foodToCuisine[food];
this.foodToRating[food] = newRating;
const foodsList = this.cuisineToFoods[cuisine];
const index = foodsList.findIndex(item => item.food === food);
foodsList[index].rating = newRating;
foodsList.sort((a, b) => {
if (b.rating === a.rating) return a.food.localeCompare(b.food);
return b.rating - a.rating;
});
}
highestRated(cuisine) {
return this.cuisineToFoods[cuisine][0].food;
}
}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.
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.
Approach 2: Using Priority Heaps
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.
import heapq
class FoodRatings:
def __init__(self, foods: [str], cuisines: [str], ratings: [int]):
self.food_to_cuisine = {food: cuisine for food, cuisine in zip(foods, cuisines)}
self.food_to_rating = {food: rating for food, rating in zip(foods, ratings)}
self.cuisine_to_heap = {}
for food, cuisine, rating in zip(foods, cuisines, ratings):
if cuisine not in self.cuisine_to_heap:
self.cuisine_to_heap[cuisine] = []
heapq.heappush(self.cuisine_to_heap[cuisine], (-rating, food))
def changeRating(self, food: str, newRating: int) -> None:
old_rating = self.food_to_rating[food]
self.food_to_rating[food] = newRating
cuisine = self.food_to_cuisine[food]
heapq.heappush(self.cuisine_to_heap[cuisine], (-newRating, food))
def highestRated(self, cuisine: str) -> str:
max_rating_heap = self.cuisine_to_heap[cuisine]
while max_rating_heap:
rating, food = max_rating_heap[0]
if -rating == self.food_to_rating[food]:
return food
heapq.heappop(max_rating_heap)
return ""import java.util.*;
public class FoodRatings {
private Map<String, Integer> foodToRating;
private Map<String, String> foodToCuisine;
private Map<String, PriorityQueue<Pair>> cuisineToMaxHeap;
static class Pair {
int rating;
String food;
Pair(int rating, String food) {
this.rating = rating;
this.food = food;
}
}
public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
this.foodToRating = new HashMap<>();
this.foodToCuisine = new HashMap<>();
this.cuisineToMaxHeap = new HashMap<>();
for (int i = 0; i < foods.length; i++) {
foodToRating.put(foods[i], ratings[i]);
foodToCuisine.put(foods[i], cuisines[i]);
cuisineToMaxHeap.computeIfAbsent(cuisines[i], k -> new PriorityQueue<>((a, b) -> {
if (b.rating != a.rating) return Integer.compare(b.rating, a.rating);
return a.food.compareTo(b.food);
})).add(new Pair(ratings[i], foods[i]));
}
}
public void changeRating(String food, int newRating) {
int oldRating = foodToRating.get(food);
foodToRating.put(food, newRating);
String cuisine = foodToCuisine.get(food);
cuisineToMaxHeap.get(cuisine).add(new Pair(newRating, food));
}
public String highestRated(String cuisine) {
PriorityQueue<Pair> maxHeap = cuisineToMaxHeap.get(cuisine);
while (!maxHeap.isEmpty()) {
Pair top = maxHeap.peek();
if (top.rating == foodToRating.get(top.food)) {
return top.food;
}
maxHeap.poll();
}
return "";
}
}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.
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 3: Hash Table + Ordered Set
We can use a hash table d to store the foods for each cuisine, where the key is the cuisine and the value is an ordered set. Each element in the ordered set is a tuple (rating, food), sorted by rating in descending order, and if the ratings are the same, sorted by food name in lexicographical order.
We can also use a hash table g to store the rating and cuisine for each food. That is, g[food] = (rating, cuisine).
In the constructor, we iterate through foods, cuisines, and ratings, storing the rating and cuisine for each food in d and g.
In the changeRating function, we first get the original rating oldRating and cuisine cuisine of the food food, then update the rating of g[food] to newRating, remove (oldRating, food) from d[cuisine], and add (newRating, food) to d[cuisine].
In the highestRated function, we directly return the food name of the first element in d[cuisine].
In terms of time complexity, the constructor has a time complexity of O(n log n), where n is the number of foods. The other operations have a time complexity of O(log n). The space complexity is O(n).
import (
"github.com/emirpasic/gods/v2/trees/redblacktree"
)
type pair struct {
rating int
food string
}
type FoodRatings struct {
d map[string]*redblacktree.Tree[pair, struct{}]
g map[string]pair
}
func Constructor(foods []string, cuisines []string, ratings []int) FoodRatings {
d := make(map[string]*redblacktree.Tree[pair, struct{}])
g := make(map[string]pair)
for i, food := range foods {
rating, cuisine := ratings[i], cuisines[i]
g[food] = pair{rating, cuisine}
if d[cuisine] == nil {
d[cuisine] = redblacktree.NewWith[pair, struct{}](func(a, b pair) int {
return cmp.Or(b.rating-a.rating, strings.Compare(a.food, b.food))
})
}
d[cuisine].Put(pair{rating, food}, struct{}{})
}
return FoodRatings{d, g}
}
func (this *FoodRatings) ChangeRating(food string, newRating int) {
p := this.g[food]
t := this.d[p.food]
t.Remove(pair{p.rating, food})
t.Put(pair{newRating, food}, struct{}{})
p.rating = newRating
this.g[food] = p
}
func (this *FoodRatings) HighestRated(cuisine string) string {
return this.d[cuisine].Left().Key.food
}
/**
* Your FoodRatings object will be instantiated and called as such:
* obj := Constructor(foods, cuisines, ratings);
* obj.ChangeRating(food,newRating);
* param_2 := obj.HighestRated(cuisine);
*/Complexity comparison
| 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. |
| Hash Table + Ordered Set | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Design a Food Rating System easy or hard?
The problem is rated Medium because it requires combining multiple data structures and maintaining ordering after updates. The challenge lies in designing a system that avoids expensive re-sorting while still returning the correct highest-rated food.
Design a Food Rating System Python/Java solution
Python solutions typically use dictionaries and the heapq module with lazy deletion. Java implementations use HashMap for mappings and PriorityQueue for cuisine ranking. Both implementations maintain O(log n) updates and queries.
How to solve Design a Food Rating System in O(log n)?
Store food information in a hash map and maintain a max heap per cuisine containing pairs of (-rating, foodName). When a rating changes, push the updated value to the heap. During highestRated queries, remove outdated heap entries until the top matches the latest rating in the hash map.
What is the best approach for Design a Food Rating System?
The most common solution uses a hash map for fast food lookups and a max heap for each cuisine to track the highest-rated food. Rating updates push a new entry into the heap, and outdated entries are removed lazily during queries. This keeps operations around O(log n) while maintaining correct ordering.
Is Design a Food Rating System asked at Google/Amazon/Meta?
Design-style data structure problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. The question evaluates understanding of heaps, hash tables, and maintaining ordered data efficiently under updates.
What data structure is used in Design a Food Rating System?
The core data structures are hash tables for constant-time food lookups and priority queues (heaps) or ordered sets to maintain ranking by rating and lexicographical order. This combination supports efficient updates and fast retrieval of the highest-rated item.
What is the time complexity of Design a Food Rating System?
With the heap-based design, both rating updates and highest-rated queries run in O(log n) time due to heap operations. Hash map lookups remain O(1). Space complexity is O(n) because the system stores all foods and their associated structures.