Design a Food Rating System

main.md

Question

Approach

I maintain three structures: (1) a map foodInfo from food → (cuisine, currentRating), (2) for each cuisine, a max-heap keyed by (-rating, name) so highest rating (and lexicographically smallest name on ties) is on top, and (3) a map heapByCuisine from cuisine → its heap. When a rating changes, I update foodInfo and push a new (-newRating, name) into that cuisine’s heap—no deletions. In highestRated, I lazy-clean the heap top: while the heap’s top pair doesn’t match the current rating in foodInfo, I pop it; the first matching top is the correct answer. All operations are $O(\log n)$ per push/pop, satisfying the constraints.

Implementation

class FoodRatings:

    def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
        self.foodInfo: Dict[str, Tuple[str, int]] = {}
        self.heapByCuisine: Dict[str, List[Tuple[int, str]]] = {}

        for f, c, r in zip(foods, cuisines, ratings):
            self.foodInfo[f] = (c, r)
            if c not in self.heapByCuisine:
                self.heapByCuisine[c] = []
            heapq.heappush(self.heapByCuisine[c], (-r, f))

    def changeRating(self, food: str, newRating: int) -> None:
        c, _ = self.foodInfo[food]
        self.foodInfo[food] = (c, newRating)
        heapq.heappush(self.heapByCuisine[c], (-newRating, food))

    def highestRated(self, cuisine: str) -> str:
        heap = self.heapByCuisine[cuisine]
        while heap:
            neg_r, name = heap[0]
            current_c, current_r = self.foodInfo[name]
            if current_c == cuisine and -neg_r == current_r:
                return name
            heapq.heappop(heap)
        return ""

Complexities

• Time: changeRating $O(\log n)$; highestRated amortized $O(\log n)$ due to lazy pops
• Space: $O(n)$ for maps and heaps (each rating change keeps an extra heap entry until popped)