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
- Keep a map from food to its current
(cuisine, rating)for O(1) lookups. - Keep, per cuisine, a max-heap of
(-rating, foodName)so the top is the best candidate. - 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.
- 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.