Skip to content

2353. Design a Food Rating System 👍

  • Time:
    • Constructor: $O(n)$
    • changeRating(food: str, newRating: int): $O(\log n)$
    • highestRated(cuisine: str): $O(\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class FoodRatings {
 public:
  FoodRatings(vector<string>& foods, vector<string>& cuisines,
              vector<int>& ratings) {
    for (int i = 0; i < foods.size(); ++i) {
      cuisineToRatingAndFoods[cuisines[i]].insert({-ratings[i], foods[i]});
      foodToCuisine[foods[i]] = cuisines[i];
      foodToRating[foods[i]] = ratings[i];
    }
  }

  void changeRating(string food, int newRating) {
    const string cuisine = foodToCuisine[food];
    const int oldRating = foodToRating[food];
    auto& ratingAndFoods = cuisineToRatingAndFoods[cuisine];
    ratingAndFoods.erase({-oldRating, food});
    ratingAndFoods.insert({-newRating, food});
    foodToRating[food] = newRating;
  }

  string highestRated(string cuisine) {
    return cuisineToRatingAndFoods[cuisine].begin()->second;
  }

 private:
  // {cuisine: {(-rating, food)}} stores negative rating for smarter comparison
  unordered_map<string, set<pair<int, string>>> cuisineToRatingAndFoods;
  unordered_map<string, string> foodToCuisine;
  unordered_map<string, int> foodToRating;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class FoodRatings {
  public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
    for (int i = 0; i < foods.length; ++i) {
      cuisineToRatingAndFoods.putIfAbsent(
          cuisines[i],
          new TreeSet<>((a, b)
                            -> a.getKey().equals(b.getKey()) ? a.getValue().compareTo(b.getValue())
                                                             : b.getKey().compareTo(a.getKey())));
      cuisineToRatingAndFoods.get(cuisines[i]).add(new Pair<>(ratings[i], foods[i]));
      foodToCuisine.put(foods[i], cuisines[i]);
      foodToRating.put(foods[i], ratings[i]);
    }
  }

  public void changeRating(String food, int newRating) {
    final String cuisine = foodToCuisine.get(food);
    final int oldRating = foodToRating.get(food);
    TreeSet<Pair<Integer, String>> ratingAndFoods = cuisineToRatingAndFoods.get(cuisine);
    ratingAndFoods.remove(new Pair<>(oldRating, food));
    ratingAndFoods.add(new Pair<>(newRating, food));
    foodToRating.put(food, newRating);
  }

  public String highestRated(String cuisine) {
    return cuisineToRatingAndFoods.get(cuisine).first().getValue();
  }

  // {cuisine: {(rating, food)}}
  Map<String, TreeSet<Pair<Integer, String>>> cuisineToRatingAndFoods = new HashMap<>();
  Map<String, String> foodToCuisine = new HashMap<>();
  Map<String, Integer> foodToRating = new HashMap<>();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from sortedcontainers import SortedSet


class FoodRatings:
  def __init__(self, foods: list[str], cuisines: list[str], ratings: list[int]):
    self.cuisineToRatingAndFoods = collections.defaultdict(
        lambda: SortedSet(key=lambda x: (-x[0], x[1])))
    self.foodToCuisine = {}
    self.foodToRating = {}

    for food, cuisine, rating in zip(foods, cuisines, ratings):
      self.cuisineToRatingAndFoods[cuisine].add((rating, food))
      self.foodToCuisine[food] = cuisine
      self.foodToRating[food] = rating

  def changeRating(self, food: str, newRating: int) -> None:
    cuisine = self.foodToCuisine[food]
    oldRating = self.foodToRating[food]
    ratingAndFoods = self.cuisineToRatingAndFoods[cuisine]
    ratingAndFoods.remove((oldRating, food))
    ratingAndFoods.add((newRating, food))
    self.foodToRating[food] = newRating

  def highestRated(self, cuisine: str) -> str:
    return self.cuisineToRatingAndFoods[cuisine][0][1]