Baozi Leetcode solution 2353. Design a Food Rating System
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 byfoods
,cuisines
andratings
, all of which have a length ofn
.foods[i]
is the name of theith
food,cuisines[i]
is the type of cuisine of theith
food, andratings[i]
is the initial rating of theith
food.
void changeRating(String food, int newRating)
Changes the rating of the food item with the namefood
.String highestRated(String cuisine)
Returns the name of the food item that has the highest rating for the given type ofcuisine
. 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 tochangeRating
.cuisine
will be a type of cuisine of at least one food item in the system across all calls tohighestRated
.- At most
2 * 104
calls in total will be made tochangeRating
andhighestRated
.
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)
References
- Task Scheduler using heap
- LRU Cache using heap
相关文章
- ☆打卡算法☆LeetCode 218. 天际线问题 算法解析
- 上升下降字符串 | LeetCode
- LeetCode 700题 题解答案集合 Python
- leetcode-792匹配子序列的单词数(桶)
- LeetCode 155. 最小栈
- JavaScript刷LeetCode拿offer-树的遍历
- JavaScript刷LeetCode拿offer-分治_2023-03-01
- 用javascript分类刷leetcode---动态规划
- LeetCode-分治
- JavaScript刷LeetCode模板技巧篇(一)2
- LeetCode-84-柱状图中最大的矩形
- 【leetcode 29】 两数相除(中等)
- 改变未来:Oracle修改System密码(oracle修改system密码)