Design a Food Rating System
Problem
Support changeRating(food, newRating) and highestRated(cuisine). For ties, return the lexicographically smallest food. Use a hash map plus a per-cuisine sorted set keyed by (−rating, food).
init: [(kimchi, korean, 9), (miso, japanese, 12), (sushi, japanese, 8)]highestRated("japanese") → "miso"from sortedcontainers import SortedList
class FoodRatings:
def __init__(self, foods, cuisines, ratings):
self.food = {}
self.by_cuisine = {}
for f, c, r in zip(foods, cuisines, ratings):
self.food[f] = (r, c)
self.by_cuisine.setdefault(c, SortedList()).add((-r, f))
def changeRating(self, food, newRating):
r, c = self.food[food]
self.by_cuisine[c].remove((-r, food))
self.by_cuisine[c].add((-newRating, food))
self.food[food] = (newRating, c)
def highestRated(self, cuisine):
return self.by_cuisine[cuisine][0][1]class FoodRatings {
constructor(foods, cuisines, ratings) {
this.food = new Map();
this.byCuisine = new Map();
for (let i = 0; i < foods.length; i++) {
this.food.set(foods[i], { r: ratings[i], c: cuisines[i] });
if (!this.byCuisine.has(cuisines[i])) this.byCuisine.set(cuisines[i], []);
this.byCuisine.get(cuisines[i]).push(foods[i]);
}
}
changeRating(food, newRating) {
const e = this.food.get(food);
e.r = newRating;
}
highestRated(cuisine) {
const list = this.byCuisine.get(cuisine);
let best = list[0];
for (const f of list) {
const a = this.food.get(f), b = this.food.get(best);
if (a.r > b.r || (a.r === b.r && f < best)) best = f;
}
return best;
}
}class FoodRatings {
Map<String, int[]> food = new HashMap<>();
Map<String, String> foodCuisine = new HashMap<>();
Map<String, TreeSet<String>> byCuisine = new HashMap<>();
public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
for (int i = 0; i < foods.length; i++) {
food.put(foods[i], new int[]{ ratings[i] });
foodCuisine.put(foods[i], cuisines[i]);
byCuisine.computeIfAbsent(cuisines[i], k -> new TreeSet<>(
(a, b) -> {
int ra = food.get(a)[0], rb = food.get(b)[0];
if (ra != rb) return rb - ra;
return a.compareTo(b);
}
)).add(foods[i]);
}
}
public void changeRating(String foodName, int newRating) {
TreeSet<String> set = byCuisine.get(foodCuisine.get(foodName));
set.remove(foodName);
food.get(foodName)[0] = newRating;
set.add(foodName);
}
public String highestRated(String cuisine) {
return byCuisine.get(cuisine).first();
}
}class FoodRatings {
unordered_map<string, pair<int, string>> food;
unordered_map<string, set<pair<int, string>>> byCuisine;
public:
FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
for (int i = 0; i < (int)foods.size(); i++) {
food[foods[i]] = { ratings[i], cuisines[i] };
byCuisine[cuisines[i]].insert({ -ratings[i], foods[i] });
}
}
void changeRating(string foodName, int newRating) {
auto& e = food[foodName];
byCuisine[e.second].erase({ -e.first, foodName });
e.first = newRating;
byCuisine[e.second].insert({ -newRating, foodName });
}
string highestRated(string cuisine) {
return byCuisine[cuisine].begin()->second;
}
};Explanation
The challenge is answering highestRated(cuisine) fast even after ratings keep changing. The idea is to keep two structures: a hash map from each food to its (rating, cuisine), and per cuisine a sorted set of foods ordered so the best one is always at the front.
The sorted set is keyed by (-rating, food). Using the negative rating means higher ratings sort first, and tacking on the food name means ties break by lexicographically smallest food — exactly what the problem requires. So the best food is simply the first element.
For changeRating(food, newRating) we look up the food's old rating, remove((-r, food)) from its cuisine's sorted set, insert (-newRating, food), and update the food map. Removing and re-inserting keeps the set correctly ordered in O(log n).
highestRated(cuisine) just returns self.by_cuisine[cuisine][0][1] — the food name of the front entry. Example: with miso=12 and sushi=8 under japanese, miso is on top. After changeRating("sushi", 16), sushi's key (-16, "sushi") sorts before miso's (-12, "miso"), so highestRated("japanese") now returns sushi.