Baozi Leetcode solution 2353. Design a Food Rating System

包子面试培训

发布于 2022-11-11 14:57:35

2840

发布于 2022-11-11 14:57:35

文章被收录于专栏：包子铺里聊IT包子铺里聊IT

Blogger: https://blog.baozitraining.org/2022/09/leetcode-solution-2353-design-food.html

Youtube: https://youtu.be/TFTGvVnnq1M

B站: https://www.bilibili.com/video/BV1Ve4y1k7Fk/

博客园: https://www.cnblogs.com/baozitraining/p/16706448.html

Cover Art by Mike Sullivan

Problem Statement

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.

Problem link

Video Tutorial

You can find the detailed video tutorial here

Youtube
B站

Thought Process

If we want to optimize highestRated API call (which we should), a max heap would help achieve it with O(1). Some details about implementation.

Make each food into a class would make code clean, also maintain the order when insert/remove from the max heap through Comparable interface.
Make sure we have O(1) access to each Food object by maintaining two HashMaps.
- foodIndex, Map<String, Food> -> Key: food name, Value: Food object
- CuisineIndex, Map<String, Queue<Food>>, Key: cuisine name, Value: Max heap on rating
Follow up thought: if this is a system design question, how would you actually do it? Some read on how Youtube calculates total views.

Solutions

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

public class FoodRatings {
    
    private class Food implements Comparable<Food>{
        // skip boilerplate getter/setters
        public String food;
        public String cuisine;
        public int rating;

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

        @Override
        public int compareTo(Food o) {
            assert o != null;
            if (o.rating == this.rating) {
                return this.food.compareTo(o.food);
            }
            return o.rating - this.rating; }
    }

    // food -> Food
    private Map<String, Food> foodIndex = new HashMap<>();
    // cuisine -> MaxHeap on rating
    private Map<String, Queue<Food>> cuisineIndex = new HashMap<>();

    public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
        for (int i = 0; i < foods.length; i++) {
            Food f = new Food(foods[i], cuisines[i], ratings[i]);
            // given food is distinct

            this.foodIndex.put(f.food, f);
            /* use putIfAbsent instead
            if (!this.cuisineIndex.containsKey(f.cuisine)) {
                this.cuisineIndex.put(f.cuisine, new PriorityQueue<>());
            }
            */
            this.cuisineIndex.putIfAbsent(f.cuisine, new PriorityQueue<>());
            this.cuisineIndex.get(f.cuisine).add(f);
        }
    }

    public void changeRating(String food, int newRating) {
        Food f = this.foodIndex.get(food);
        f.rating = newRating;
        // need to update the max heap by deleting and re-inserting
        this.cuisineIndex.get(f.cuisine).remove(f);
        this.cuisineIndex.get(f.cuisine).add(f);
    }

    public String highestRated(String cuisine) {
        return this.cuisineIndex.get(cuisine).peek().food;
    }

}

Time Complexity: highestRated: O(1), changeRating: O(N) because we have to remove the object, and in order to find the object in a max heap, it is O(N) scan (even though re-insert is O(lgN)).

Space Complexity: O(N) because we used extra maps linear to food names (which is larger than cuisine names)