Design a Food Rating System

How it works

A sorted set (like TreeSet or SortedSet) maintains elements in sorted order and supports efficient insertion, deletion, and access to the minimum/maximum element. For each cuisine, we store (negative rating, food name) pairs so the smallest element corresponds to the highest rating. When updating a rating, we remove the old entry and insert the new one. Querying simply returns the first element of the set.

Steps

1. During initialization, create three structures:
   • foodToRating: maps food to its current rating.
   • foodToCuisine: maps food to its cuisine.
   • cuisineToSortedSet: maps each cuisine to a sorted set of (negative rating, food) pairs.
2. For changeRating(food, newRating): remove the old (negative old rating, food) pair from the set, update foodToRating, and insert the new (negative new rating, food) pair.
3. For highestRated(cuisine): return the food name from the first element in the sorted set (which has the highest rating due to the negative sign).

Complexity

• Time complexity:
  • O(n log n) time for initialization.
  • O(log n) time for each changeRating() function call.
  • O(1) in Python and O(log n) in other languages for each highestRated() function call.
• Space complexity: O(n)

Things to watch for

Forgetting to Handle Lexicographic Tie-Breaking

When multiple foods have the same highest rating, you must return the lexicographically smallest name. Forgetting this tie-breaker or sorting in the wrong order will produce incorrect results.

Not Removing Stale Entries from the Heap

When using a heap with lazy deletion, you must validate that the top entry's rating matches the current rating in your hash map before returning it. Stale entries from previous rating updates will otherwise be returned.

Forgetting to Map Food to Its Cuisine

When a rating changes, you need to know which cuisine the food belongs to in order to update the correct data structure. Without a foodToCuisine mapping, you cannot efficiently locate and update the food's entry.

from typing import List
from collections import defaultdict

class FoodRatings:

    def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
        self.foodToRating = {} # food -> rating
        self.foodToCuisine = {} # food -> cuisine
        self.cuisineToSortedSet = defaultdict(SortedSet) # cuisine -> SortedSet[(rating, food)]

        for i in range(len(foods)):
            self.foodToRating[foods[i]] = ratings[i]
            self.foodToCuisine[foods[i]] = cuisines[i]
            self.cuisineToSortedSet[cuisines[i]].add((-ratings[i], foods[i]))

    def changeRating(self, food: str, newRating: int) -> None:
        cuisine = self.foodToCuisine[food]
        oldRating = self.foodToRating[food]

        self.cuisineToSortedSet[cuisine].remove((-oldRating, food))
        self.foodToRating[food] = newRating
        self.cuisineToSortedSet[cuisine].add((-newRating, food))

    def highestRated(self, cuisine: str) -> str:
        return self.cuisineToSortedSet[cuisine][0][1]

class FoodRatings {
    unordered_map<string, int> foodToRating;
    unordered_map<string, string> foodToCuisine;
    unordered_map<string, set<pair<int, string>>> cuisineToSet;

public:
    FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
        for (int i = 0; i < foods.size(); i++) {
            foodToRating[foods[i]] = ratings[i];
            foodToCuisine[foods[i]] = cuisines[i];
            cuisineToSet[cuisines[i]].insert({-ratings[i], foods[i]});
        }
    }

    void changeRating(string food, int newRating) {
        string cuisine = foodToCuisine[food];
        auto& s = cuisineToSet[cuisine];

        s.erase({-foodToRating[food], food});
        foodToRating[food] = newRating;
        s.insert({-newRating, food});
    }

    string highestRated(string cuisine) {
        return begin(cuisineToSet[cuisine])->second;
    }
};