We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Design a Food Rating System

Number: 2429

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Design a system to manage food items where each food has a name, a type of cuisine, and a rating. The system must allow updating a food's rating and efficiently returning the highest-rated food for a given cuisine. When two foods have the same rating, the one with the lexicographically smaller name should be returned.

Key Insights

  • Use a hash map to store each food's current rating and cuisine.
  • Maintain a max heap for each cuisine to retrieve the highest-rated food quickly.
  • Store tuples of (-rating, food) in the heap. The negative rating turns the min-heap (default in many languages) into a max-heap.
  • Handle rating updates with lazy deletion: insert the updated rating into the heap and, during retrieval, discard stale entries whose rating does not match the latest value in the hash map.
  • Lexicographical order is naturally supported by storing the food name in the tuple and relying on tuple comparison.

Space and Time Complexity

Time Complexity:

  • changeRating: O(log n) due to heap insertion.
  • highestRated: O(log n) amortized as stale entries are lazily removed from the heap.

Space Complexity: O(n) for storing the maps and heaps.

Solution

We create three primary data structures:

  1. A map from food to its current rating (foodToRating).
  2. A map from food to its cuisine (foodToCuisine).
  3. A map from cuisine to a max heap (cuisineToHeap) that stores pairs of (-rating, food).

When a food’s rating is updated, we update the foodToRating map and push the new (-rating, food) tuple onto the appropriate heap. When a query for the highest-rated food is made, we repeatedly check the top of the heap for that cuisine. If the top entry’s rating (after sign inversion) matches the current rating in foodToRating, it is returned; otherwise, we pop the stale value and continue. This lazy deletion avoids the overhead of directly removing outdated entries from the heap.

Code Solutions

import heapq

class FoodRatings:
    def __init__(self, foods, cuisines, ratings):
        # Map food to its current rating.
        self.food_to_rating = {}
        # Map food to its cuisine.
        self.food_to_cuisine = {}
        # Map each cuisine to a heap of (-rating, food) pairs.
        self.cuisine_to_heap = {}
        
        for food, cuisine, rating in zip(foods, cuisines, ratings):
            self.food_to_rating[food] = rating
            self.food_to_cuisine[food] = cuisine
            if cuisine not in self.cuisine_to_heap:
                self.cuisine_to_heap[cuisine] = []
            # Store negative rating to simulate a max-heap; food name ensures lexicographic order.
            heapq.heappush(self.cuisine_to_heap[cuisine], (-rating, food))
    
    def changeRating(self, food, newRating):
        # Retrieve corresponding cuisine.
        cuisine = self.food_to_cuisine[food]
        # Update the food's rating.
        self.food_to_rating[food] = newRating
        # Push the new rating into the cuisine heap.
        heapq.heappush(self.cuisine_to_heap[cuisine], (-newRating, food))
    
    def highestRated(self, cuisine):
        heap = self.cuisine_to_heap[cuisine]
        # Remove stale entries until the top of the heap is valid.
        while heap:
            rating_neg, food = heap[0]
            if -rating_neg == self.food_to_rating[food]:
                return food
            heapq.heappop(heap)
        return ""
← Back to All Questions