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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Design a Food Rating System

Difficulty: Medium

Problem Description

Design a food rating system that can modify the rating of a food item and return the highest-rated food item for a type of cuisine. Implement the FoodRatings class with the following methods: changeRating(String food, int newRating) to change the rating of a food item and highestRated(String cuisine) to return the highest-rated food item for a given cuisine type.

Key Insights

  • We need to associate food items with their ratings and cuisines.
  • Efficiently retrieve the highest-rated food item for a particular cuisine.
  • Handle updates to food ratings while maintaining efficient retrieval of the highest-rated food.

Space and Time Complexity

Time Complexity:

  • O(log n) for changeRating due to adjustments in a data structure.
  • O(n) for highestRated in a naive approach, but can be optimized to O(log n) using appropriate data structures.

Space Complexity:

  • O(n) to store food items, ratings, and cuisine associations.

Solution

To implement the food rating system, we can utilize two main data structures:

  1. A dictionary (hash map) to store the food name as the key and its corresponding rating and cuisine as the value.
  2. Another dictionary to maintain a priority queue (or a sorted set) for each cuisine type, allowing efficient retrieval of the highest-rated food item.

When the rating of a food item is changed, we update the rating and adjust its position in the priority queue. For retrieving the highest-rated food item, we simply access the top of the priority queue for the specified cuisine.

Code Solutions

class FoodRatings:
    def __init__(self, foods, cuisines, ratings):
        self.food_map = {}
        self.cuisine_map = {}
        self.ratings = {}
        
        for food, cuisine, rating in zip(foods, cuisines, ratings):
            self.food_map[food] = (rating, cuisine)
            self.ratings[food] = rating
            if cuisine not in self.cuisine_map:
                self.cuisine_map[cuisine] = []
            self.cuisine_map[cuisine].append(food)
        
        # Sort the foods in each cuisine to maintain order
        for cuisine in self.cuisine_map:
            self.cuisine_map[cuisine].sort(key=lambda x: (-self.food_map[x][0], x))

    def changeRating(self, food, newRating):
        # Update the rating
        oldRating, cuisine = self.food_map[food]
        self.food_map[food] = (newRating, cuisine)
        self.ratings[food] = newRating
        
        # Remove and reinsert to maintain order
        self.cuisine_map[cuisine].remove(food)
        self.cuisine_map[cuisine].append(food)
        self.cuisine_map[cuisine].sort(key=lambda x: (-self.food_map[x][0], x))

    def highestRated(self, cuisine):
        return self.cuisine_map[cuisine][0]
← Back to All Questions