Design a Food Rating System
Medium · Design · Array · Hash Table · String · Design · Heap (Priority Queue) · Ordered Set
Problem
Design a rating board for dishes that supports changing a dish's rating and asking for the best dish of a cuisine.
Implement FoodRatings:
- FoodRatings(foods, cuisines, ratings) registers n dishes: foods[i] is a dish name, cuisines[i] its cuisine and ratings[i] its starting rating.
- changeRating(food, newRating) sets the rating of the dish food to newRating.
- highestRated(cuisine) returns the name of the dish with the highest rating in cuisine. If several dishes tie, return the lexicographically smallest name.
Tests replay a call sequence: the first entry names the class and its constructor arguments, each later entry is a method with its arguments, and calls returning nothing report None.
Examples
Input: ops = ["FoodRatings","highestRated","changeRating","highestRated","highestRated"], args = [[["pho","ramen","tacos"],["asian","asian","mexican"],[7,9,5]],["asian"],["pho",9],["asian"],["mexican"]] Output: [None, 'ramen', None, 'pho', 'tacos']
Ramen leads with 9. After pho rises to 9 the two tie, and "pho" is lexicographically smaller.
Input: ops = ["FoodRatings","changeRating","highestRated"], args = [[["stew","soup"],["home","home"],[4,6]],["soup",1],["home"]] Output: [None, None, 'stew']
Soup drops from 6 to 1, so stew becomes the best home dish.
Input: ops = ["FoodRatings","changeRating","changeRating","highestRated","changeRating","highestRated"], args = [[["kimchi","miso","sushi"],["korean","japanese","japanese"],[9,12,8]],["sushi",16],["sushi",8],["japanese"],["miso",3],["japanese"]] Output: [None, None, None, 'miso', None, 'sushi']
Sushi goes up to 16 and back to 8, so miso still leads with 12 until it falls to 3.
Constraints
- 1 <= n <= 2 · 10^4
- n == len(foods) == len(cuisines) == len(ratings)
- 1 <= len(foods[i]), len(cuisines[i]) <= 10, lowercase English letters
- 1 <= ratings[i], newRating <= 10^8
- all dish names are distinct
- food in changeRating is always a registered dish
- cuisine in highestRated always has at least one dish
- at most 2 · 10^4 calls to changeRating and highestRated in total
Approaches
- Baseline: scan the cuisine on every query — time changeRating O(1), highestRated O(m), space O(n)
Follow-up
The lazy heap can grow with every change; a sorted set stays at n entries but needs deletion by key. The use cases ask the same questions in one function call: the best dish of each cuisine after a list of changes, and the top k dishes of one cuisine.
Related problems
Start free on Cariara · Coding problems · System design studio
