Skip to content

LeetCode: 2352-Design a Food Rating System Solution

Last Updated on 2023-12-17 by Clay

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"]


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.

Solution

This problem looks like very simple, it just let us to build some lists by cuisines, and sorted the list by ratings, and when highestRated() is called, we return the highest rating food name by the cuisine that passed in. And the other hand, we need to make a changeRating() method, it can be change the rating of food.

Finally I used set data structure to solve. The element of set is pair, the first element is food rating and the second is food name. And then we need to construct the customize compare method.

So in chanagRating(), I can delete/insert the new rating-food pair into my set by time complexity O(log(n)); And in highestRated(), we just need to use O(1) to return the result.


C++ Sample Code

class FoodRatings {
private:
    struct Compare {
        bool operator()(const std::pair<int, std::string>& a, const std::pair<int, std::string>& b) const {
            if (a.first != b.first) {
                return a.first > b.first;
            }
            
            return a.second < b.second;
        }
    };

    std::unordered_map<std::string, int> food2rating;
    std::unordered_map<std::string, std::string> food2cuisine;
    std::unordered_map<std::string, std::set<std::pair<int, std::string>, Compare>> cuisine2foods;

public:
    FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
        for (int i=0; i<foods.size(); ++i) {
            food2rating[foods[i]] = ratings[i];
            food2cuisine[foods[i]] = cuisines[i];
            cuisine2foods[cuisines[i]].insert({ratings[i], foods[i]});
        }
    }
    
    void changeRating(string food, int newRating) {
        // Update highest food by cuisines
        const std::string& cuisine = food2cuisine[food];
        cuisine2foods[cuisine].erase({food2rating[food], food});
        cuisine2foods[cuisine].insert({newRating, food});

        // Update rating
        food2rating[food] = newRating;
    }
    
    std::string highestRated(string cuisine) {
        return cuisine2foods[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);
 */



References

Read More

Tags:

Leave a Reply