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]// Min-heap of [-rating, food]; stale entries are skipped lazily.
class Heap {
constructor() { this.a = []; }
// entry a sorts before b: higher rating first, then smaller food.
_less(x, y) { return x[0] !== y[0] ? x[0] < y[0] : x[1] < y[1]; }
push(e) {
const a = this.a; a.push(e);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (!this._less(a[i], a[p])) break;
[a[i], a[p]] = [a[p], a[i]]; i = p;
}
}
peek() { return this.a[0]; }
pop() {
const a = this.a, top = a[0], last = a.pop();
if (a.length) {
a[0] = last;
let i = 0;
for (;;) {
const l = 2 * i + 1, r = l + 1; let s = i;
if (l < a.length && this._less(a[l], a[s])) s = l;
if (r < a.length && this._less(a[r], a[s])) s = r;
if (s === i) break;
[a[i], a[s]] = [a[s], a[i]]; i = s;
}
}
return top;
}
}
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], new Heap());
this.byCuisine.get(cuisines[i]).push([-ratings[i], foods[i]]);
}
}
changeRating(food, newRating) {
const e = this.food.get(food);
e.r = newRating;
this.byCuisine.get(e.c).push([-newRating, food]);
}
highestRated(cuisine) {
const heap = this.byCuisine.get(cuisine);
// Discard entries whose rating is stale, then the top is the answer.
while (-heap.peek()[0] !== this.food.get(heap.peek()[1]).r) heap.pop();
return heap.peek()[1];
}
}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.