# Design a Food Rating System
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/design-a-food-rating-system)
Canonical: https://scaleengineer.com/dsa/problems/design-a-food-rating-system
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Array, Hash Table, String, Heap (Priority Queue), Ordered Set
**Companies:** [Altimetrik](https://scaleengineer.com/companies/altimetrik), [Atlassian](https://scaleengineer.com/companies/atlassian)
---
## Problem
Design a food rating system that can do the following:

* **Modify** the rating of a food item listed in the system.
* Return the highest-rated food item for a type of cuisine in the system.

Implement the `FoodRatings` class:

* `FoodRatings(String[] foods, String[] cuisines, int[] ratings)` Initializes the system. The food items are described by `foods`, `cuisines` and `ratings`, all of which have a length of `n`.  
  * `foods[i]` is the name of the `ith` food,
  * `cuisines[i]` is the type of cuisine of the `ith` food, and
  * `ratings[i]` is the initial rating of the `ith` food.
* `void changeRating(String food, int newRating)` Changes the rating of the food item with the name `food`.
* `String highestRated(String cuisine)` Returns the name of the food item that has the highest rating for the given type of `cuisine`. If there is a tie, return the item with the **lexicographically smaller** name.

Note that a string `x` is lexicographically smaller than string `y` if `x` comes before `y` in dictionary order, that is, either `x` is a prefix of `y`, or if `i` is the first position such that `x[i] != y[i]`, then `x[i]` comes before `y[i]` in alphabetic order.

**Example 1:**

**Input**
["FoodRatings", "highestRated", "highestRated", "changeRating", "highestRated", "changeRating", "highestRated"]
[[["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], [9, 12, 8, 15, 14, 7]], ["korean"], ["japanese"], ["sushi", 16], ["japanese"], ["ramen", 16], ["japanese"]]
**Output**
[null, "kimchi", "ramen", null, "sushi", null, "ramen"]

**Explanation**
FoodRatings foodRatings = new FoodRatings(["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], [9, 12, 8, 15, 14, 7]);
foodRatings.highestRated("korean"); // return "kimchi"
                                    // "kimchi" is the highest rated korean food with a rating of 9.
foodRatings.highestRated("japanese"); // return "ramen"
                                      // "ramen" is the highest rated japanese food with a rating of 14.
foodRatings.changeRating("sushi", 16); // "sushi" now has a rating of 16.
foodRatings.highestRated("japanese"); // return "sushi"
                                      // "sushi" is the highest rated japanese food with a rating of 16.
foodRatings.changeRating("ramen", 16); // "ramen" now has a rating of 16.
foodRatings.highestRated("japanese"); // return "ramen"
                                      // Both "sushi" and "ramen" have a rating of 16.
                                      // However, "ramen" is lexicographically smaller than "sushi".

**Constraints:**

* `1 <= n <= 2 * 104`
* `n == foods.length == cuisines.length == ratings.length`
* `1 <= foods[i].length, cuisines[i].length <= 10`
* `foods[i]`, `cuisines[i]` consist of lowercase English letters.
* `1 <= ratings[i] <= 108`
* All the strings in `foods` are **distinct**.
* `food` will be the name of a food item in the system across all calls to `changeRating`.
* `cuisine` will be a type of cuisine of **at least one** food item in the system across all calls to `highestRated`.
* At most `2 * 104` calls **in total** will be made to `changeRating` and `highestRated`.

# Approaches
## Brute Force with Linear Scan
This approach uses simple HashMaps to store the food data. To find the highest-rated food for a cuisine, it iterates through all foods of that cuisine, comparing them one by one to find the one with the highest rating, handling ties with lexicographical comparison.
**Time:** - **Constructor**: O(N), where N is the number of initial food items.
- **`changeRating`**: O(1).
- **`highestRated`**: O(L), where L is the number of foods in the given cuisine. In the worst case, L can be equal to N. · **Space:** O(N), where N is the total number of food items. We need to store information for each food item across three maps.
**Pros:** Simple to understand and implement.; The `changeRating` operation is very fast, with O(1) time complexity.
**Cons:** `highestRated` can be slow if a cuisine has a large number of food items, leading to potential Time Limit Exceeded errors on large test cases.
### Explanation
In this straightforward approach, we use three separate HashMaps to keep track of the data. One map stores food-to-rating pairs, another stores food-to-cuisine pairs, and the third stores cuisine-to-list-of-foods pairs. 

While initializing, we populate these maps in a single pass through the input arrays. The `changeRating` operation is very efficient as it only requires a single update in the ratings map. However, the `highestRated` method's performance is dependent on the number of foods within a specific cuisine. It must perform a linear scan over all foods of that cuisine, checking each one's rating and name to determine the highest-rated one according to the rules. This can be inefficient if a cuisine category is very large.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class FoodRatings {
    private Map<String, Integer> foodRatings;
    private Map<String, String> foodCuisines;
    private Map<String, List<String>> cuisineFoods;

    public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
        foodRatings = new HashMap<>();
        foodCuisines = new HashMap<>();
        cuisineFoods = new HashMap<>();
        for (int i = 0; i < foods.length; ++i) {
            foodRatings.put(foods[i], ratings[i]);
            foodCuisines.put(foods[i], cuisines[i]);
            cuisineFoods.computeIfAbsent(cuisines[i], k -> new ArrayList<>()).add(foods[i]);
        }
    }

    public void changeRating(String food, int newRating) {
        foodRatings.put(food, newRating);
    }

    public String highestRated(String cuisine) {
        List<String> foodsInCuisine = cuisineFoods.get(cuisine);
        String bestFood = "";
        int maxRating = -1;

        for (String food : foodsInCuisine) {
            int currentRating = foodRatings.get(food);
            if (bestFood.isEmpty() || currentRating > maxRating) {
                maxRating = currentRating;
                bestFood = food;
            } else if (currentRating == maxRating) {
                if (food.compareTo(bestFood) < 0) {
                    bestFood = food;
                }
            }
        }
        return bestFood;
    }
}
```
### Algorithm
- **Data Structures**:
  - `foodRatings`: A `HashMap<String, Integer>` to map each food name to its current rating.
  - `foodCuisines`: A `HashMap<String, String>` to map each food name to its cuisine type.
  - `cuisineFoods`: A `HashMap<String, List<String>>` to group food names by their cuisine.
- **Initialization `FoodRatings(foods, cuisines, ratings)`**:
  - Iterate through the input arrays from `i = 0` to `n-1`.
  - For each item, populate the three maps with the food's name, rating, cuisine, and add it to the list of foods for its cuisine.
- **`changeRating(food, newRating)`**:
  - Simply update the rating for the given `food` in the `foodRatings` map. This is an O(1) operation.
- **`highestRated(cuisine)`**:
  - Retrieve the list of foods for the given `cuisine` from the `cuisineFoods` map.
  - Initialize `maxRating = -1` and `bestFood = ""`.
  - Iterate through the list of foods.
  - For each food, get its current rating from `foodRatings`.
  - Compare the food's rating with `maxRating`. If it's higher, or if it's equal and the food's name is lexicographically smaller than the current `bestFood`, update `maxRating` and `bestFood`.
  - After checking all foods, return `bestFood`.

## Optimized Approach using HashMap and TreeSet
This approach significantly improves the performance of finding the highest-rated food by using more advanced data structures. It maintains a sorted set of foods for each cuisine, allowing for near-instant retrieval of the top-rated item. The key is to use a `TreeSet` to automatically keep foods sorted by rating and name.
**Time:** - **Constructor**: O(N * log L), where N is the number of foods and L is the maximum number of foods in a single cuisine. Each insertion into the `TreeSet` takes O(log L).
- **`changeRating`**: O(log L) due to removal and insertion operations in the `TreeSet`.
- **`highestRated`**: O(1) to access the first element of the `TreeSet`. · **Space:** O(N), where N is the total number of food items. We store each food as a `Food` object and maintain pointers in the maps and `TreeSet`s.
**Pros:** Extremely fast `highestRated` operation, with O(1) time complexity.; Efficient `changeRating` operation with logarithmic time complexity.; Overall well-balanced and highly efficient performance for the given problem constraints.
**Cons:** More complex to implement due to the custom class and the need to manage `TreeSet` updates correctly.; Slightly higher memory overhead due to storing custom objects and the `TreeSet` data structure.
### Explanation
The core idea is to keep the foods for each cuisine sorted by rating (descending) and then by name (ascending for ties). A `TreeSet` in Java is a perfect data structure for this, as it maintains elements in sorted order and provides logarithmic time complexity for additions and removals.

We use two main data structures:
1.  `foodInfoMap`: A `HashMap<String, Food>` that maps a food's name to a custom `Food` object. This allows for quick lookups when a rating needs to be changed.
2.  `cuisineFoodMap`: A `HashMap<String, TreeSet<Food>>`. This map stores a `TreeSet` for each cuisine. The `TreeSet` automatically sorts the `Food` objects according to our defined criteria.

The `changeRating` operation is the most nuanced. Since a `TreeSet`'s order depends on the state of its objects, we cannot simply modify an object's rating while it's in the set. We must first remove the object, then update its rating, and finally add it back to the set, which will place it in its new correct position. The `highestRated` operation becomes trivial and extremely fast, as it just needs to peek at the first element of the sorted set.

```java
import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

class FoodRatings {
    // A custom class to store food details and define sorting logic.
    private class Food implements Comparable<Food> {
        String name;
        String cuisine;
        int rating;

        Food(String name, String cuisine, int rating) {
            this.name = name;
            this.cuisine = cuisine;
            this.rating = rating;
        }

        @Override
        public int compareTo(Food other) {
            // Sort by rating in descending order.
            if (this.rating != other.rating) {
                return Integer.compare(other.rating, this.rating);
            }
            // If ratings are the same, sort by name in ascending (lexicographical) order.
            return this.name.compareTo(other.name);
        }
    }

    // Map cuisine to a sorted set of foods.
    private Map<String, TreeSet<Food>> cuisineFoodMap;
    // Map food name to its Food object for quick access.
    private Map<String, Food> foodInfoMap;

    public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
        cuisineFoodMap = new HashMap<>();
        foodInfoMap = new HashMap<>();

        for (int i = 0; i < foods.length; i++) {
            Food foodItem = new Food(foods[i], cuisines[i], ratings[i]);
            foodInfoMap.put(foods[i], foodItem);
            
            cuisineFoodMap.computeIfAbsent(cuisines[i], k -> new TreeSet<>()).add(foodItem);
        }
    }

    public void changeRating(String food, int newRating) {
        // Get the Food object.
        Food foodItem = foodInfoMap.get(food);
        
        // Get the TreeSet for the specific cuisine.
        TreeSet<Food> foodSet = cuisineFoodMap.get(foodItem.cuisine);
        
        // Remove the old entry from the TreeSet.
        foodSet.remove(foodItem);
        
        // Update the rating in the Food object.
        foodItem.rating = newRating;
        
        // Add the updated Food object back to the TreeSet.
        // It will be placed in the correct sorted position.
        foodSet.add(foodItem);
    }

    public String highestRated(String cuisine) {
        // The highest-rated food is the first element in the TreeSet.
        return cuisineFoodMap.get(cuisine).first().name;
    }
}
```
### Algorithm
- **Data Structures**:
  - Define a custom `Food` class containing `name`, `cuisine`, and `rating`. This class must implement `Comparable<Food>` to define the sorting order: descending by rating, then ascending by name.
  - `foodInfoMap`: A `HashMap<String, Food>` to map a food's name to its `Food` object. This allows for O(1) access to a food's details.
  - `cuisineFoodMap`: A `HashMap<String, TreeSet<Food>>`. This maps each cuisine to a `TreeSet` of its `Food` objects. The `TreeSet` automatically maintains the foods in the desired sorted order.
- **Initialization `FoodRatings(foods, cuisines, ratings)`**:
  - Iterate through the input arrays. For each item, create a new `Food` object.
  - Store the food name and its object in `foodInfoMap`.
  - Add the `Food` object to the appropriate `TreeSet` in `cuisineFoodMap`. The `TreeSet` will handle placing it in the correct sorted position.
- **`changeRating(food, newRating)`**:
  - Look up the `Food` object in `foodInfoMap` using the food's name.
  - Get the `TreeSet` for that food's cuisine from `cuisineFoodMap`.
  - **Crucially, remove the `Food` object from the `TreeSet` before changing its rating.**
  - Update the `rating` field of the `Food` object.
  - **Add the modified `Food` object back into the `TreeSet`.** It will be re-inserted based on its new rating.
- **`highestRated(cuisine)`**:
  - Get the `TreeSet` for the given `cuisine`.
  - The highest-rated food is guaranteed to be the first element in the `TreeSet` due to our custom sorting. Return its name.

# Solutions
### Java

```java
class FoodRatings { private Map < String , TreeSet < Pair < Integer , String >>> d = new HashMap <>(); private Map < String , Pair < Integer , String >> g = new HashMap <>(); private final Comparator < Pair < Integer , String >> cmp = ( a , b ) -> { if (! a . getKey (). equals ( b . getKey ())) { return b . getKey (). compareTo ( a . getKey ()); } return a . getValue (). compareTo ( b . getValue ()); }; public FoodRatings ( String [] foods , String [] cuisines , int [] ratings ) { for ( int i = 0 ; i < foods . length ; ++ i ) { String food = foods [ i ], cuisine = cuisines [ i ]; int rating = ratings [ i ]; d . computeIfAbsent ( cuisine , k -> new TreeSet <>( cmp )). add ( new Pair <>( rating , food )); g . put ( food , new Pair <>( rating , cuisine )); } } public void changeRating ( String food , int newRating ) { Pair < Integer , String > old = g . get ( food ); int oldRating = old . getKey (); String cuisine = old . getValue (); g . put ( food , new Pair <>( newRating , cuisine )); d . get ( cuisine ). remove ( new Pair <>( oldRating , food )); d . get ( cuisine ). add ( new Pair <>( newRating , food )); } public String highestRated ( String cuisine ) { return d . get ( cuisine ). first (). getValue (); } } /** * Your FoodRatings object will be instantiated and called as such: * FoodRatings obj = new FoodRatings(foods, cuisines, ratings); * obj.changeRating(food,newRating); * String param_2 = obj.highestRated(cuisine); */
```

### CPP

```cpp
using pis = pair < int , string > ; class FoodRatings { map < string , pis > mp ; map < string , set < pis >> t ; public: FoodRatings ( vector < string >& foods , vector < string >& cuisines , vector < int >& ratings ) { int n = foods . size (); for ( int i = 0 ; i < n ; ++ i ) { string a = foods [ i ], b = cuisines [ i ]; int c = ratings [ i ]; mp [ a ] = pis ( c , b ); t [ b ]. insert ( pis ( - c , a )); } } void changeRating ( string food , int newRating ) { pis & p = mp [ food ]; t [ p . second ]. erase ( pis ( - p . first , food )); p . first = newRating ; t [ p . second ]. insert ( pis ( - p . first , food )); } string highestRated ( string cuisine ) { return t [ cuisine ]. begin () -> second ; } }; /** * Your FoodRatings object will be instantiated and called as such: * FoodRatings* obj = new FoodRatings(foods, cuisines, ratings); * obj->changeRating(food,newRating); * string param_2 = obj->highestRated(cuisine); */
```

### Python

```python
from sortedcontainers import SortedSet class FoodRatings : def __init__ ( self , foods : List [ str ], cuisines : List [ str ], ratings : List [ int ]): self . mp = {} self . t = defaultdict ( lambda : SortedSet ( key = lambda x : ( - x [ 0 ], x [ 1 ]))) for a , b , c in zip ( foods , cuisines , ratings ): self . mp [ a ] = ( b , c ) self . t [ b ]. add (( c , a )) def changeRating ( self , food : str , newRating : int ) -> None : b , c = self . mp [ food ] self . mp [ food ] = ( b , newRating ) self . t [ b ]. remove (( c , food )) self . t [ b ]. add (( newRating , food )) def highestRated ( self , cuisine : str ) -> str : return self . t [ cuisine ][ 0 ][ 1 ] # Your FoodRatings object will be instantiated and called as such: # obj = FoodRatings(foods, cuisines, ratings) # obj.changeRating(food,newRating) # param_2 = obj.highestRated(cuisine)
```