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,cuisinesandratings, all of which have a length ofn.foods[i]is the name of theithfood,cuisines[i]is the type of cuisine of theithfood, andratings[i]is the initial rating of theithfood.
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 * 104n == foods.length == cuisines.length == ratings.length1 <= foods[i].length, cuisines[i].length <= 10foods[i],cuisines[i]consist of lowercase English letters.1 <= ratings[i] <= 108- All the strings in
foodsare distinct. foodwill be the name of a food item in the system across all calls tochangeRating.cuisinewill be a type of cuisine of at least one food item in the system across all calls tohighestRated.- At most
2 * 104calls in total will be made tochangeRatingandhighestRated.
Video Tutorial
You can find the detailed video tutorial hereThought 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
1 import java.util.HashMap;
2 import java.util.Map;
3 import java.util.PriorityQueue;
4 import java.util.Queue;
5
6 public class FoodRatings {
7
8 private class Food implements Comparable<Food>{
9 // skip boilerplate getter/setters
10 public String food;
11 public String cuisine;
12 public int rating;
13
14 public Food(String food, String cuisine, int rating) {
15 this.food = food;
16 this.cuisine = cuisine;
17 this.rating = rating;
18 }
19
20 @Override
21 public int compareTo(Food o) {
22 assert o != null;
23 if (o.rating == this.rating) {
24 return this.food.compareTo(o.food);
25 }
26 return o.rating - this.rating; }
27 }
28
29 // food -> Food
30 private Map<String, Food> foodIndex = new HashMap<>();
31 // cuisine -> MaxHeap on rating
32 private Map<String, Queue<Food>> cuisineIndex = new HashMap<>();
33
34 public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
35 for (int i = 0; i < foods.length; i++) {
36 Food f = new Food(foods[i], cuisines[i], ratings[i]);
37 // given food is distinct
38
39 this.foodIndex.put(f.food, f);
40 /* use putIfAbsent instead
41 if (!this.cuisineIndex.containsKey(f.cuisine)) {
42 this.cuisineIndex.put(f.cuisine, new PriorityQueue<>());
43 }
44 */
45 this.cuisineIndex.putIfAbsent(f.cuisine, new PriorityQueue<>());
46 this.cuisineIndex.get(f.cuisine).add(f);
47 }
48 }
49
50 public void changeRating(String food, int newRating) {
51 Food f = this.foodIndex.get(food);
52 f.rating = newRating;
53 // need to update the max heap by deleting and re-inserting
54 this.cuisineIndex.get(f.cuisine).remove(f);
55 this.cuisineIndex.get(f.cuisine).add(f);
56 }
57
58 public String highestRated(String cuisine) {
59 return this.cuisineIndex.get(cuisine).peek().food;
60 }
61
62 }
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)