2353. Design a Food Rating System
Asked at Atlassian
Difficulty
Medium
Time
O(log n) per changeRating and pe
Space
O(n)
Pattern
Array
Companies
1
Problem
Design a class FoodRatings that keeps track of food items, each belonging to one cuisine and having a rating. It must support two operations after setup: change a food's rating, and ask for the best food in a cuisine.
The constructor receives three parallel arrays of length n: foods (names), cuisines (the cuisine each food belongs to), and ratings (starting rating of each food). Food names are all different.
changeRating(food, newRating) sets the rating of that food to newRating. highestRated(cuisine) returns the name of the food in that cuisine with the highest rating. If two or more foods share the top rating, return the one whose name is lexicographically smaller (comes first in dictionary order).
A food's cuisine never changes, only its rating. Both methods may be called many times, so each call should be fast.
Two operations on the same data
Constraints
- ●
1 <= n <= 2 * 10^4 - ●
n == foods.length == cuisines.length == ratings.length - ●
1 <= foods[i].length, cuisines[i].length <= 10 - ●
foods[i] and cuisines[i] contain only lowercase English letters - ●
1 <= ratings[i] <= 10^8 - ●
All strings in foods are distinct - ●
food passed to changeRating is always a food in the system - ●
cuisine passed to highestRated always has at least one food
Examples
["FoodRatings", "highestRated", "highestRated", "changeRating", "highestRated", "changeRating", "highestRated"]
[[["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "j[null, "kimchi", "ramen", null, "sushi", null, "ramen"]["FoodRatings", "changeRating", "highestRated"]
[[["a", "b"], ["x", "x"], [5, 5]], ["a", 3], ["x"]][null, null, "b"]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Atlassian | Medium | View all Atlassian questions → |
How to Think About It
Brute force: store foods in a list, and for highestRated, scan all foods of the given cuisine to find the max. That's O(n) per query. Too slow for frequent lookups.
Key insight: use three data structures together. A hash map for food→rating, a hash map for food→cuisine, and a hash map of cuisine→sorted set (or max-heap) of foods sorted by rating then name.
The hash map pair (food→rating, food→cuisine) gives O(1) lookup for the changeRating operation. The sorted set per cuisine gives O(log n) for finding the highest-rated food and for updating ratings.
For the sorted set, use a TreeSet in Java or a SortedList + dict in Python. The set stores tuples of (-rating, food_name) so the smallest element (highest rating, lexicographically smallest name) is at the front. In C++, use set of pairs.
Edge cases: multiple foods with same rating (lexicographically smallest wins), changing rating to same value, foods with initial rating of 0.
Optimal Approach
Data structures:
food_cuisine: hash map, food → cuisine namefood_rating: hash map, food → current ratingcuisine_foods: hash map, cuisine → sorted set of (-rating, food_name) pairs
FoodRatings(foods, cuisines, ratings):
For each food, populate all three data structures.
changeRating(food, newRating):
Look up old rating from food_rating.
Remove (-old_rating, food) from cuisine_foods[cuisine].
Update food_rating[food] = newRating.
Add (-new_rating, food) to cuisine_foods[cuisine].
highestRated(cuisine):
Return the food name from the first element of cuisine_foods[cuisine].
The sorted set ensures the first element has the highest rating (and smallest name for ties).
Time: O(log n) for changeRating and highestRated (sorted set operations). O(1) for hash map lookups. Space: O(n) for all data structures.
Three maps plus a sorted set per cuisine
What Trips People Up in Real Interviews
Using a heap alone. A max-heap gives O(1) highest rated, but O(n) for removing an arbitrary element during changeRating. You need a sorted set for O(log n) updates and queries.
Forgetting to handle ties. When two foods have the same rating, the lexicographically smallest name wins. Store (-rating, name) tuples so the sorted set naturally handles this.
Updating only one data structure during changeRating. You must update both the food_rating map AND the cuisine_foods sorted set. Forgetting either breaks consistency.
Not removing the old entry before adding the new one. You can't modify an element in a sorted set in place. Remove the old (-old_rating, food) first, then add (-new_rating, food).
Storing rating as positive in the sorted set. Store (-rating, food) so the sorted set's natural ordering puts the highest rating first. Alternatively, use a custom comparator.
Solution Code
O(log n) per changeRating and pe timefrom sortedcontainers import SortedSet
class FoodRatings:
def __init__(self, foods, cuisines, ratings):
self.food_cuisine = {}
self.food_rating = {}
self.cuisine_foods = {}
for food, cuisine, rating in zip(foods, cuisines, ratings):
self.food_cuisine[food] = cuisine
self.food_rating[food] = rating
if cuisine not in self.cuisine_foods:
self.cuisine_foods[cuisine] = SortedSet()
self.cuisine_foods[cuisine].add((-rating, food))
def changeRating(self, food, newRating):
cuisine = self.food_cuisine[food]
oldRating = self.food_rating[food]
self.cuisine_foods[cuisine].remove((-oldRating, food))
self.food_rating[food] = newRating
self.cuisine_foods[cuisine].add((-newRating, food))
def highestRated(self, cuisine):
return self.cuisine_foods[cuisine][0][1]Frequently Asked Questions
What is the Design a Food Rating System problem?
Design a food rating system that can modify the rating of a food item and return the highest-rated food for a given cuisine. Implement the FoodRatings class with constructor, changeRating, and highestRated methods.
How do you solve Design a Food Rating System?
The optimal approach runs in O(log n) per changeRating and pe time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Design a Food Rating System?
Design a Food Rating System is asked at Atlassian. It is a medium difficulty problem.
What are common mistakes on Design a Food Rating System?
- Using a heap alone. A max-heap gives `O(1)` highest rated, but `O(n)` for removing an arbitrary element during changeRating. You need a sorted set for `O(log n)` updates and queries.
- Forgetting to handle ties. When two foods have the same rating, the lexicographically smallest name wins. Store (-rating, name) tuples so the sorted set naturally handles this.
- Updating only one data structure during changeRating. You must update both the `food_rating` map AND the `cuisine_foods` sorted set. Forgetting either breaks consistency.
- Not removing the old entry before adding the new one. You can't modify an element in a sorted set in place. Remove the old (-old_rating, food) first, then add (-new_rating, food).
- Storing rating as positive in the sorted set. Store (-rating, food) so the sorted set's natural ordering puts the highest rating first. Alternatively, use a custom comparator.