Problem Statement in English

You’re asked to design a food rating system that can efficiently manage and query food items based on their ratings and cuisines.

The system should support the following operations:

  1. FoodRatings(foods: List[str], cuisines: List[str], ratings: List[int]): Initialize the food rating system with the given foods, cuisines, and ratings.
  2. changeRating(food: str, newRating: int): Change the rating of the specified food item.
  3. highestRated(cuisine: str): Return the name of the highest-rated food item in the specified cuisine.

Approach

  1. Use a max heap to keep track of the highest-rated food items for each cuisine.
  2. Use a hashmap to store the current rating and cuisine of each food item.
  3. When changing a food item’s rating, update both the heap and the hashmap.
  4. When querying the highest-rated food item, pop elements from the heap until the top element is valid (i.e., its rating matches the hashmap).

Solution in Python


class FoodRatings:

    def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
        self.maxheaps = {}
        self.db = {}

        for i in range(len(foods)):
            f = foods[i]
            c = cuisines[i]
            r = ratings[i]

            if c not in self.maxheaps:
                self.maxheaps[c] = []

            heappush(self.maxheaps[c], (-r, f))
            self.db[f] = (r, c)

    def changeRating(self, food: str, newRating: int) -> None:
        oldRating, cuisine = self.db[food]

        self.db[food] = (newRating, cuisine)
        heappush(self.maxheaps[cuisine], (-newRating, food))

    def highestRated(self, cuisine: str) -> str:
        while True:
            rating, name = self.maxheaps[cuisine][0]
            rating *= -1

            r, _ = self.db[name]

            if r == rating:
                return name
            else:
               heappop(self.maxheaps[cuisine])

Complexity

  • Time: $O(k \log n)$
    Since each operation (insertion and deletion) in a heap takes $O(\log n)$ time, where $n$ is the number of food items in the cuisine. Here, $k$ is the number of operations performed.

  • Space: $O(n)$
    We use a hashmap to store the current rating and cuisine of each food item, which takes $O(n)$ space, where $n$ is the number of food items.

And we are done.