{x}
blog image

Design a Food Rating System

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.

Solution Explanation

This problem requires designing a food rating system that allows modifying food ratings and retrieving the highest-rated food item for a given cuisine. The solution uses hash tables and ordered sets (or priority queues) for efficient operations.

Data Structures:

  • mp: A hash map (dictionary in Python) that stores the food item as the key and a tuple (cuisine, rating) as the value. This provides O(1) access to a food item's cuisine and rating.
  • t: A hash map that stores the cuisine as the key and an ordered set (or a priority queue) as the value. The ordered set contains tuples of (-rating, food_name). The negative rating ensures that the highest-rated food items appear first in the ordered set. The food name is included to handle ties based on lexicographical order.

Algorithm:

  • __init__ (Constructor):

    • Initializes the mp and t data structures.
    • Iterates through the input lists (foods, cuisines, ratings) and populates mp with food items, their cuisines, and ratings.
    • For each cuisine, it adds the food item with its negative rating to the ordered set in t. The negative rating ensures that higher ratings are prioritized.

  • changeRating:

    • Retrieves the current cuisine and rating for the given food item from mp.
    • Updates the rating in mp with the newRating.
    • Removes the old (cuisine, rating) tuple from the ordered set in t for the corresponding cuisine.
    • Adds the updated (cuisine, newRating) tuple to the ordered set in t.

  • highestRated:

    • Retrieves the ordered set for the given cuisine from t.
    • Returns the food name in the first element of the ordered set (the highest-rated food item).

Time and Space Complexity:

  • Time Complexity:
    • __init__: O(N log N), where N is the number of food items, due to inserting into the ordered sets.
    • changeRating: O(log N), due to removing and inserting elements into an ordered set.
    • highestRated: O(1), as accessing the first element of the ordered set is constant time.
  • Space Complexity: O(N), as both mp and t store at most N entries.

Code Explanation (Python):

The Python code utilizes defaultdict for t to automatically handle cuisines that are not yet present in the system. SortedSet (which needs to be imported from a library like sortedcontainers) is used for efficiently maintaining the order of food items based on rating and then lexicographical order. If you dont want to use sortedcontainers you can use a list and sort the list which will increase the time complexity of the highestRated method to O(N) where N is the length of the foods for that cuisine.

Code Explanation (C++):

The C++ code uses std::map for mp and std::set for t. The std::set automatically maintains order based on the custom comparison defined by the pis pair. The negative rating is used in the same way to ensure higher ratings appear first.

Both the Python and C++ code offer efficient solutions to the problem, leveraging the advantages of hash tables and ordered sets for efficient data management and retrieval. The choice between Python and C++ would depend on performance requirements and familiarity with the languages and libraries.