Sponsored
Sponsored
This approach involves using dictionaries (or hash maps) to store and manage the relationships between foods, cuisines, and their ratings. We will have multiple dictionaries to efficiently perform update and retrieval operations.
Time Complexity: O(N log N) for initialization and O(F log F) for changing rating where N is the number of foods and F is the list of foods for a cuisine.
Space Complexity: O(N) for storage of mappings.
1import java.util.*;
2
3public class FoodRatings {
4
5 private Map<String, String> foodToCuisine = new HashMap<>();
6 private Map<String, Integer> foodToRating = new HashMap<>();
7 private Map<String, TreeSet<String>> cuisineToFoods = new HashMap<>();
8
9 public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
10 for (int i = 0; i < foods.length; i++) {
11 String food = foods[i];
12 String cuisine = cuisines[i];
13 int rating = ratings[i];
14 foodToCuisine.put(food, cuisine);
15 foodToRating.put(food, rating);
16
17 cuisineToFoods.computeIfAbsent(cuisine, k -> new TreeSet<>((a, b) -> {
18 int cmp = Integer.compare(foodToRating.get(b), foodToRating.get(a));
19 return cmp == 0 ? a.compareTo(b) : cmp;
20 })).add(food);
21 }
22 }
23
24 public void changeRating(String food, int newRating) {
25 String cuisine = foodToCuisine.get(food);
26 cuisineToFoods.get(cuisine).remove(food);
27 foodToRating.put(food, newRating);
28 cuisineToFoods.get(cuisine).add(food);
29 }
30
31 public String highestRated(String cuisine) {
32 return cuisineToFoods.get(cuisine).first();
33 }
34}Java's solution utilizes HashMaps for food-to-cuisine and food-to-rating mappings. Each cuisine maintains a TreeSet of food items sorted by their ratings and lexographical order for tie-breaking. When a food's rating is updated, it is removed and re-added to maintain correct order in the TreeSet. The first element of the TreeSet gives the highest-rated food.
This approach uses priority queues (heaps) to manage the highest-rated food for a cuisine. Heaps offer efficient operations for maintaining and retrieving maximum values, which can be useful for finding the highest-rated item.
Time Complexity: O(N) for initialization and O(log F) for updating heap or retrieving the maximum where F is the number of foods for given cuisine.
Space Complexity: O(N) for storing the heap elements.
1import heapq
2
3class FoodRatings:
4
The Python version uses a heap to maintain the highest-rated food for each cuisine. Negative ratings are stored to utilize the min-heap structure for max-heap behavior. If ratings change, old entries may remain invalid due to imposition of new valid values. Therefore, we remove these as necessary during the highestRated check.