Design a Food Rating System
Asked at Atlassian
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.
Asked At
| 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.
Visual walkthrough:
Initialize: foods=["kimchi","sushi","miso"], cuisines=["korean","japanese","japanese"], ratings=[9,12,8]
food_info = {kimchi:(korean,9), sushi:(japanese,12), miso:(japanese,8)}
cuisine_foods = {korean:{(-9,"kimchi")}, japanese:{(-12,"sushi"),(-8,"miso")}}
highestRated("japanese") → look at japanese set → smallest = (-12,"sushi") → "sushi"
changeRating("sushi", 16) → update food_info[sushi]=(japanese,16)
Remove (-12,"sushi") from japanese set, add (-16,"sushi")
highestRated("japanese") → (-16,"sushi") → "sushi"
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.
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
from 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.