Design a Food Rating System

Problem

Design a food rating system that can do the following:

• Modify the rating of a food item listed in the system.
• Return the highest-rated food item for a type of cuisine in the system.

Implement the FoodRatings class:

• FoodRatings(String[] foods, String[] cuisines, int[] ratings) Initializes the system. The food items are described by foods, cuisines and ratings, all of which have a length of n.
• foods[i] is the name of the ith food,
• cuisines[i] is the type of cuisine of the ith food, and
• ratings[i] is the initial rating of the ith food.
  • void changeRating(String food, int newRating) Changes the rating of the food item with the name food.
  • String highestRated(String cuisine) Returns the name of the food item that has the highest rating for the given type of cuisine. If there is a tie, return the item with the lexicographically smaller name.

Note that a string x is lexicographically smaller than string y if x comes before y in dictionary order, that is, either x is a prefix of y, or if i is the first position such that x[i] != y[i], then x[i] comes before y[i] in alphabetic order.

Examples

Example 1

**Input**
["FoodRatings", "highestRated", "highestRated", "changeRating", "highestRated", "changeRating", "highestRated"]
[[["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], [9, 12, 8, 15, 14, 7]], ["korean"], ["japanese"], ["sushi", 16], ["japanese"], ["ramen", 16], ["japanese"]]
**Output**
[null, "kimchi", "ramen", null, "sushi", null, "ramen"]

**Explanation**
FoodRatings foodRatings = new FoodRatings(["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], [9, 12, 8, 15, 14, 7]);
foodRatings.highestRated("korean"); // return "kimchi"
                                    // "kimchi" is the highest rated korean food with a rating of 9.
foodRatings.highestRated("japanese"); // return "ramen"
                                      // "ramen" is the highest rated japanese food with a rating of 14.
foodRatings.changeRating("sushi", 16); // "sushi" now has a rating of 16.
foodRatings.highestRated("japanese"); // return "sushi"
                                      // "sushi" is the highest rated japanese food with a rating of 16.
foodRatings.changeRating("ramen", 16); // "ramen" now has a rating of 16.
foodRatings.highestRated("japanese"); // return "ramen"
                                      // Both "sushi" and "ramen" have a rating of 16.
                                      // However, "ramen" is lexicographically smaller than "sushi".

Constraints

• 1 <= n <= 2 * 10^4
• n == foods.length == cuisines.length == ratings.length
• 1 <= foods[i].length, cuisines[i].length <= 10
• foods[i], cuisines[i] consist of lowercase English letters.
• 1 <= ratings[i] <= 10^8
• All the strings in foods are distinct.
• food will be the name of a food item in the system across all calls to changeRating.
• cuisine will be a type of cuisine of at least one food item in the system across all calls to highestRated.
• At most 2 * 10^4 calls in total will be made to changeRating and highestRated.

Solution

Method 1 – Hash Map and TreeSet for Cuisine-wise Food Management

Intuition

We need to efficiently update food ratings and quickly find the highest-rated food for each cuisine. By using a hash map to track food info and a TreeSet (or similar structure) per cuisine, we can maintain foods sorted by rating and name, allowing fast updates and queries.

Approach

1. Use a hash map food_info to map each food to its (cuisine, rating).
2. For each cuisine, use a TreeSet (or a sorted set) to keep foods sorted by (-rating, name) so the highest-rated food is always first.
3. On changeRating, update the rating in food_info, remove and re-insert the food in the cuisine's set.
4. On highestRated, return the first food in the cuisine's set.

Code

C++

#include <string>
#include <vector>
#include <unordered_map>
#include <set>
using namespace std;
class FoodRatings {
    unordered_map<string, pair<string, int>> food_info;
    unordered_map<string, set<pair<int, string>>> cuisine_foods;
public:
    FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
        for (int i = 0; i < foods.size(); ++i) {
            food_info[foods[i]] = {cuisines[i], ratings[i]};
            cuisine_foods[cuisines[i]].emplace(-ratings[i], foods[i]);
        }
    }
    void changeRating(string food, int newRating) {
        auto& [c, old] = food_info[food];
        cuisine_foods[c].erase({-old, food});
        cuisine_foods[c].emplace(-newRating, food);
        old = newRating;
    }
    string highestRated(string cuisine) {
        return cuisine_foods[cuisine].begin()->second;
    }
};

Go

import (
    "sort"
)
type FoodRatings struct {
    foodInfo map[string]struct{cuisine string; rating int}
    cuisineFoods map[string][]struct{rating int; name string}
}
func Constructor(foods, cuisines []string, ratings []int) FoodRatings {
    fr := FoodRatings{foodInfo: map[string]struct{cuisine string; rating int}{}, cuisineFoods: map[string][]struct{rating int; name string}{}}
    for i := range foods {
        fr.foodInfo[foods[i]] = struct{cuisine string; rating int}{cuisines[i], ratings[i]}
        fr.cuisineFoods[cuisines[i]] = append(fr.cuisineFoods[cuisines[i]], struct{rating int; name string}{ratings[i], foods[i]})
    }
    for c := range fr.cuisineFoods {
        sort.Slice(fr.cuisineFoods[c], func(i, j int) bool {
            if fr.cuisineFoods[c][i].rating != fr.cuisineFoods[c][j].rating {
                return fr.cuisineFoods[c][i].rating > fr.cuisineFoods[c][j].rating
            }
            return fr.cuisineFoods[c][i].name < fr.cuisineFoods[c][j].name
        })
    }
    return fr
}
func (fr *FoodRatings) ChangeRating(food string, newRating int) {
    c := fr.foodInfo[food].cuisine
    for i, f := range fr.cuisineFoods[c] {
        if f.name == food {
            fr.cuisineFoods[c][i].rating = newRating
            break
        }
    }
    sort.Slice(fr.cuisineFoods[c], func(i, j int) bool {
        if fr.cuisineFoods[c][i].rating != fr.cuisineFoods[c][j].rating {
            return fr.cuisineFoods[c][i].rating > fr.cuisineFoods[c][j].rating
        }
        return fr.cuisineFoods[c][i].name < fr.cuisineFoods[c][j].name
    })
    fr.foodInfo[food] = struct{cuisine string; rating int}{c, newRating}
}
func (fr *FoodRatings) HighestRated(cuisine string) string {
    return fr.cuisineFoods[cuisine][0].name
}

Java

import java.util.*;
public class FoodRatings {
    private Map<String, String> foodToCuisine = new HashMap<>();
    private Map<String, Integer> foodToRating = new HashMap<>();
    private Map<String, TreeSet<Food>> cuisineFoods = new HashMap<>();
    private static class Food implements Comparable<Food> {
        String name;
        int rating;
        Food(String n, int r) { name = n; rating = r; }
        public int compareTo(Food o) {
            if (rating != o.rating) return o.rating - rating;
            return name.compareTo(o.name);
        }
    }
    public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
        for (int i = 0; i < foods.length; i++) {
            foodToCuisine.put(foods[i], cuisines[i]);
            foodToRating.put(foods[i], ratings[i]);
            cuisineFoods.computeIfAbsent(cuisines[i], k -> new TreeSet<>()).add(new Food(foods[i], ratings[i]));
        }
    }
    public void changeRating(String food, int newRating) {
        String c = foodToCuisine.get(food);
        int old = foodToRating.get(food);
        cuisineFoods.get(c).remove(new Food(food, old));
        cuisineFoods.get(c).add(new Food(food, newRating));
        foodToRating.put(food, newRating);
    }
    public String highestRated(String cuisine) {
        return cuisineFoods.get(cuisine).first().name;
    }
}

Python

import bisect
class FoodRatings:
    def __init__(self, foods: list[str], cuisines: list[str], ratings: list[int]):
        self.food_info = {}  # food -> (cuisine, rating)
        self.cuisine_foods = {}  # cuisine -> sorted list of (-rating, name)
        for f, c, r in zip(foods, cuisines, ratings):
            self.food_info[f] = [c, r]
            if c not in self.cuisine_foods:
                self.cuisine_foods[c] = []
            bisect.insort(self.cuisine_foods[c], (-r, f))
    def changeRating(self, food: str, newRating: int) -> None:
        c, old = self.food_info[food]
        lst = self.cuisine_foods[c]
        idx = bisect.bisect_left(lst, (-old, food))
        lst.pop(idx)
        bisect.insort(lst, (-newRating, food))
        self.food_info[food][1] = newRating
    def highestRated(self, cuisine: str) -> str:
        return self.cuisine_foods[cuisine][0][1]

Complexity

• ⏰ Time complexity: O(log n) per operation for insert/remove in TreeSet or sorted list.
• 🧺 Space complexity: O(n), for storing food and cuisine data.