I had a hashmap of max heaps instead of sortedsets and that gave me TLE after 73 test cases. It would be interesting to dive into how sorted sets in Python work after I solve this one because the interviewer could ask me the underlying data structure of the sorted set. Thanks for the video!
my solution with minheap might be helpful class FoodRatings: def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]): self.foodlst=foods self.cuisineslst=cuisines self.ratingslst=ratings # dict of heaps--- self.cudic=defaultdict(list) # food to ratings mapping--- self.fooddic={} # food to cuisine mapping-- self.foodTocudic={}
for i in range(len(foods)): heapq.heappush(self.cudic[cuisines[i]],[-ratings[i],foods[i]]) self.fooddic[foods[i]]=-ratings[i] self.foodTocudic[foods[i]]=cuisines[i] def changeRating(self, food: str, newRating: int) -> None: # modifying the rating of the food-- self.fooddic[food]=-newRating # finding the cuisine to wch the food belongs to----- cuisine=self.foodTocudic[food] # add new rating of the dish into the heap--- # old rating will be popped out in highestRated function--- heapq.heappush(self.cudic[cuisine],[-newRating,food])
def highestRated(self, cuisine: str) -> str:
# while the rating doesnt match, pop from the heap r,f=self.cudic[cuisine][0] while self.fooddic[f]!=r: heapq.heappop(self.cudic[cuisine]) r,f=self.cudic[cuisine][0]
return f
# Your FoodRatings object will be instantiated and called as such: # obj = FoodRatings(foods, cuisines, ratings) # obj.changeRating(food,newRating) # param_2 = obj.highestRated(cuisine)
I am writing this comment before watching the video, I came up with my own solution under 15 minutes involving hashmaps and max heap in python, that solution was able to pass 71/77 testcases. Now, I am watching this video after banging my head for straight 30 minutes. Hope I will find a coding mechanism which I didn't knew earlier.
Making the ratings of each tuple negative to "trick" the SortedSet to sort them in descending order is such a smart move, didn't have to write any custom class and comparator like I did and waste time, will definitely keep that it mind next time.
Yeah I struggled a bit with that implementation though as I couldn't figure out the trick that can be used with this problem. Looking through the solutions, one way to do it is to add all data into the priority queue and simply pop out outdated ones in highestRated function by checking it against the most updated map.
I thought of using a heap as well but heaps are kind of annoying to deal with for modification. Everytime we change the rating of a food we would then have to go to the corresponding cuisine and modify the heap to reflect the change in the food's rating. This is probably possible, but also a pain in the ass.
@Yuis and @mkum, i am at this point: The problem i am getting here is : for say a:2, b:5 and after modying b:1, we dont have a as highest, so we have to heapify again which is so costly, n log n: Please let me know if there are any other ways: This is because heap doesnt have heapremove, only has heappop, which is annoying. class FoodRatings: def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]): self.mapCuisineToHeap = {} self.foodToRatingAndCuisine = {} for f,c,r in zip(foods, cuisines, ratings): if c not in self.mapCuisineToHeap: self.mapCuisineToHeap[c] = [(-r, f)] else: heapq.heappush(self.mapCuisineToHeap[c], (-r,f)) self.foodToRatingAndCuisine[f] = (-r,c) def changeRating(self, food: str, newRating: int) -> None: c = self.foodToRatingAndCuisine[food][1] r = self.foodToRatingAndCuisine[food][0] self.mapCuisineToHeap[c].remove((r, food)) heapq.heappush(self.mapCuisineToHeap[c], (-newRating, food)) self.foodToRatingAndCuisine[food] = (-newRating, c) def highestRated(self, cuisine: str) -> str: return self.mapCuisineToHeap[cuisine][0][1]
Okay, finally ended up in a solution that works: In changeRating function, we simply push to the priority queue, and later in highestRated, when theres a discrepency with foodToRatingAndCuisine's rating and mapCuisineToHeap's rating, we heappop, since it rating has alreadyt been changed. class FoodRatings: def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]): self.mapCuisineToHeap = {} self.foodToRatingAndCuisine = {} for f,c,r in zip(foods, cuisines, ratings): if c not in self.mapCuisineToHeap: self.mapCuisineToHeap[c] = [(-r, f)] else: heapq.heappush(self.mapCuisineToHeap[c], (-r,f)) self.foodToRatingAndCuisine[f] = (-r,c) def changeRating(self, food: str, newRating: int) -> None: c = self.foodToRatingAndCuisine[food][1] r = self.foodToRatingAndCuisine[food][0] heapq.heappush(self.mapCuisineToHeap[c], (-newRating, food)) self.foodToRatingAndCuisine[food] = (-newRating, c) def highestRated(self, cuisine: str) -> str: while self.mapCuisineToHeap[cuisine][0][0] != self.foodToRatingAndCuisine[self.mapCuisineToHeap[cuisine][0][1]][0]: heapq.heappop(self.mapCuisineToHeap[cuisine]) return self.mapCuisineToHeap[cuisine][0][1]
This question felt like playing with Russian dolls as a 4 year old. I literally could not believe this was the actual solution. I better get used to dumb things like this.
You can also maintain a single hash map to store a tuple of the form - (cuisines[i], ratings[i]) and change the ratings. self.food_map = {} # initialize: self.food_map[foods[i]] = (cuisines[i], ratings[i]) # changeRating: ... self.food_map[food] = (cuisine, newRating)
this was basically my approach, except I had a list instead of a tuple I got a TLE cos of how I implemented the highestRated method so how did you implement your highestRated method?
@@phatboislym no changes are required for that method.. we just return the first element from the SortedSet which, as the name suggests, is already sorted according to the highest rating (descending order)
coding this problem in cpp is very frustrating,.... agghhhhhh ... I solved this in cpp within 40 mins but the time limit got 2080 ms... but still i solved this...
Came here with the hope someone would say a word about why TreeMap works, but Heap gives TLE even though they have the same O times for main operations.
This is the only channel on youtube which i follow religiously, If someday I make it to tech, It will be all because of this channel.
Learned something today with the negative on the rating to get the sorting right for the second element in the tuple. Great solution!
This was a really good problem, especially since Sorted Sets aren't covered in the original Neetcode 150!
ua-cam.com/users/shorts8nmYnhKCX4c
I had a hashmap of max heaps instead of sortedsets and that gave me TLE after 73 test cases. It would be interesting to dive into how sorted sets in Python work after I solve this one because the interviewer could ask me the underlying data structure of the sorted set. Thanks for the video!
my solution with minheap might be helpful
class FoodRatings:
def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
self.foodlst=foods
self.cuisineslst=cuisines
self.ratingslst=ratings
# dict of heaps---
self.cudic=defaultdict(list)
# food to ratings mapping---
self.fooddic={}
# food to cuisine mapping--
self.foodTocudic={}
for i in range(len(foods)):
heapq.heappush(self.cudic[cuisines[i]],[-ratings[i],foods[i]])
self.fooddic[foods[i]]=-ratings[i]
self.foodTocudic[foods[i]]=cuisines[i]
def changeRating(self, food: str, newRating: int) -> None:
# modifying the rating of the food--
self.fooddic[food]=-newRating
# finding the cuisine to wch the food belongs to-----
cuisine=self.foodTocudic[food]
# add new rating of the dish into the heap---
# old rating will be popped out in highestRated function---
heapq.heappush(self.cudic[cuisine],[-newRating,food])
def highestRated(self, cuisine: str) -> str:
# while the rating doesnt match, pop from the heap
r,f=self.cudic[cuisine][0]
while self.fooddic[f]!=r:
heapq.heappop(self.cudic[cuisine])
r,f=self.cudic[cuisine][0]
return f
# Your FoodRatings object will be instantiated and called as such:
# obj = FoodRatings(foods, cuisines, ratings)
# obj.changeRating(food,newRating)
# param_2 = obj.highestRated(cuisine)
Java also gives TLE when a map of heaps is used.
I am writing this comment before watching the video, I came up with my own solution under 15 minutes involving hashmaps and max heap in python, that solution was able to pass 71/77 testcases. Now, I am watching this video after banging my head for straight 30 minutes. Hope I will find a coding mechanism which I didn't knew earlier.
Same, I passed 72/77 with only arrays
In my opinion it's a pretty good problem. I did solve it on my own but I had to see the hints.
Making the ratings of each tuple negative to "trick" the SortedSet to sort them in descending order is such a smart move, didn't have to write any custom class and comparator like I did and waste time, will definitely keep that it mind next time.
Actually, you can just initailize a Sorted Set with a custom comparator function like this SortedSet(key=lambda x: (-x[0], x[1]))
Cant we do hashMap[cuisine] --> mapped to priority queue [(rating, food)]?
Yeah I struggled a bit with that implementation though as I couldn't figure out the trick that can be used with this problem. Looking through the solutions, one way to do it is to add all data into the priority queue and simply pop out outdated ones in highestRated function by checking it against the most updated map.
I thought of using a heap as well but heaps are kind of annoying to deal with for modification. Everytime we change the rating of a food we would then have to go to the corresponding cuisine and modify the heap to reflect the change in the food's rating. This is probably possible, but also a pain in the ass.
@Yuis and @mkum, i am at this point:
The problem i am getting here is : for say a:2, b:5 and after modying b:1, we dont have a as highest, so we have to heapify again which is so costly, n log n: Please let me know if there are any other ways:
This is because heap doesnt have heapremove, only has heappop, which is annoying.
class FoodRatings:
def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
self.mapCuisineToHeap = {}
self.foodToRatingAndCuisine = {}
for f,c,r in zip(foods, cuisines, ratings):
if c not in self.mapCuisineToHeap:
self.mapCuisineToHeap[c] = [(-r, f)]
else:
heapq.heappush(self.mapCuisineToHeap[c], (-r,f))
self.foodToRatingAndCuisine[f] = (-r,c)
def changeRating(self, food: str, newRating: int) -> None:
c = self.foodToRatingAndCuisine[food][1]
r = self.foodToRatingAndCuisine[food][0]
self.mapCuisineToHeap[c].remove((r, food))
heapq.heappush(self.mapCuisineToHeap[c], (-newRating, food))
self.foodToRatingAndCuisine[food] = (-newRating, c)
def highestRated(self, cuisine: str) -> str:
return self.mapCuisineToHeap[cuisine][0][1]
@@mkum2141 You could add a list to nullify any existing (food+old food rating) so the heap skips those values
Okay, finally ended up in a solution that works:
In changeRating function, we simply push to the priority queue, and later in highestRated, when theres a discrepency with foodToRatingAndCuisine's rating and mapCuisineToHeap's rating, we heappop, since it rating has alreadyt been changed.
class FoodRatings:
def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
self.mapCuisineToHeap = {}
self.foodToRatingAndCuisine = {}
for f,c,r in zip(foods, cuisines, ratings):
if c not in self.mapCuisineToHeap:
self.mapCuisineToHeap[c] = [(-r, f)]
else:
heapq.heappush(self.mapCuisineToHeap[c], (-r,f))
self.foodToRatingAndCuisine[f] = (-r,c)
def changeRating(self, food: str, newRating: int) -> None:
c = self.foodToRatingAndCuisine[food][1]
r = self.foodToRatingAndCuisine[food][0]
heapq.heappush(self.mapCuisineToHeap[c], (-newRating, food))
self.foodToRatingAndCuisine[food] = (-newRating, c)
def highestRated(self, cuisine: str) -> str:
while self.mapCuisineToHeap[cuisine][0][0] != self.foodToRatingAndCuisine[self.mapCuisineToHeap[cuisine][0][1]][0]:
heapq.heappop(self.mapCuisineToHeap[cuisine])
return self.mapCuisineToHeap[cuisine][0][1]
Absolute Genius
This question felt like playing with Russian dolls as a 4 year old. I literally could not believe this was the actual solution. I better get used to dumb things like this.
Hmm yeah I'll think i will just go with a naive approach 😅
You skipped the part of the problem about " If there is a tie, return the item with the lexicographically smaller name."
You can also maintain a single hash map to store a tuple of the form - (cuisines[i], ratings[i]) and change the ratings.
self.food_map = {}
# initialize:
self.food_map[foods[i]] = (cuisines[i], ratings[i])
# changeRating:
...
self.food_map[food] = (cuisine, newRating)
this was basically my approach, except I had a list instead of a tuple
I got a TLE cos of how I implemented the highestRated method
so how did you implement your highestRated method?
@@phatboislym no changes are required for that method.. we just return the first element from the SortedSet which, as the name suggests, is already sorted according to the highest rating (descending order)
coding this problem in cpp is very frustrating,.... agghhhhhh ... I solved this in cpp within 40 mins but the time limit got 2080 ms... but still i solved this...
Came here with the hope someone would say a word about why TreeMap works, but Heap gives TLE even though they have the same O times for main operations.
Searching a tree map is logn, whole searching a heap is o(n)
I don't think I'll be able to solve this in a 40 minute interview
videoon medium or hard daily problems
I really feel like this is a hard problem...
Is this low level design??
neetgoat