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.
1class FoodRatings {
2 constructor(foods, cuisines, ratings) {
3 this.foodToCuisine = {};
4 this.foodToRating = {};
5 this.cuisineToFoods = {};
6
7 for (let i = 0; i < foods.length; i++) {
8 const food = foods[i];
9 const cuisine = cuisines[i];
10 const rating = ratings[i];
11 this.foodToCuisine[food] = cuisine;
12 this.foodToRating[food] = rating;
13
14 if (!this.cuisineToFoods[cuisine]) {
15 this.cuisineToFoods[cuisine] = [];
16 }
17 this.cuisineToFoods[cuisine].push({food: food, rating: rating});
18 }
19
20 for (const cuisine in this.cuisineToFoods) {
21 this.cuisineToFoods[cuisine].sort((a, b) => {
22 if (b.rating === a.rating) return a.food.localeCompare(b.food);
23 return b.rating - a.rating;
24 });
25 }
26 }
27
28 changeRating(food, newRating) {
29 const oldRating = this.foodToRating[food];
30 const cuisine = this.foodToCuisine[food];
31 this.foodToRating[food] = newRating;
32
33 const foodsList = this.cuisineToFoods[cuisine];
34 const index = foodsList.findIndex(item => item.food === food);
35 foodsList[index].rating = newRating;
36
37 foodsList.sort((a, b) => {
38 if (b.rating === a.rating) return a.food.localeCompare(b.food);
39 return b.rating - a.rating;
40 });
41 }
42
43 highestRated(cuisine) {
44 return this.cuisineToFoods[cuisine][0].food;
45 }
46}In JavaScript, we employ plain objects to map foods to their cuisines and ratings. Each cuisine holds an ordered list of food objects. Changes in ratings trigger an update and re-sort of this list based on new ratings and lexicographical order.
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 java.util.*;
2
3
Java's implementation uses a PriorityQueue as a max-heap storing pairs of ratings and food names. The priority queue sorts lexicographically for tie-breaking. Updates add new valid ratings to the heap and invalid entries are removed lazily during the highestRated request.