⚡Flashcard Drill➔
NeetCode #143LC-2353MediumArrays & Hashing
← Back to All Problems

#143 · #2353 · Design a Food Rating System(设计食物评分系统)

📌 Problem Statement & Constraints

Design a food rating system. Each food has a cuisine and a rating. Implement changeRating(food, newRating) and highestRated(cuisine), which returns the highest-rated food in that cuisine (ties broken by lexicographically smallest name). Constraints: at most 2 * 10^4 calls.

💡 Core Algorithmic Approaches

  1. Keep a map from food to its current (cuisine, rating) for O(1) lookups.
  2. Keep, per cuisine, a max-heap of (-rating, foodName) so the top is the best candidate.
  3. Because ratings change, the heap becomes stale. Use lazy deletion: push the new rating on every change, and when querying, pop entries whose stored rating no longer matches the current one.
  4. The tuple ordering (-rating, name) makes ties resolve to the lexicographically smallest name automatically.

💻 Benchmark Python3 Implementation

class FoodRatings:
    def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
        import heapq
        from collections import defaultdict
        self.info = {}                     # food -> [cuisine, rating]
        self.heaps = defaultdict(list)     # cuisine -> max-heap of (-rating, food)
        for f, c, r in zip(foods, cuisines, ratings):
            self.info[f] = [c, r]
            heapq.heappush(self.heaps[c], (-r, f))

    def changeRating(self, food: str, newRating: int) -> None:
        import heapq
        c, _ = self.info[food]
        self.info[food][1] = newRating
        heapq.heappush(self.heaps[c], (-newRating, food))   # stale entry left behind

    def highestRated(self, cuisine: str) -> str:
        import heapq
        h = self.heaps[cuisine]
        while True:
            neg_r, f = h[0]
            if self.info[f][1] == -neg_r:  # entry is current
                return f
            heapq.heappop(h)               # discard the stale entry

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(log n) amortised per operation: each changeRating pushes one heap entry, and each stale entry is popped at most once across all queries.
💾 Space Complexity
O(n + total number of rating changes) for the heaps, since stale entries accumulate.

⚠️ Interview Pitfalls & Follow-ups

  • Trying to remove the old heap entry eagerly: heaps do not support O(log n) arbitrary removal; lazy deletion is the standard technique.
  • Forgetting the staleness check: a stale entry with the highest rating would be returned incorrectly.
  • Using a max-heap keyed only by rating: ties must resolve to the lexicographically smallest food name, which the (-rating, name) tuple ordering handles.
  • Rebuilding the heap on every query: O(n log n) per call, far too slow.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems