Design a Food Rating System - Leetcode 2353 - Python

Поділитися
Вставка
  • Опубліковано 16 гру 2024

КОМЕНТАРІ • 38

  • @schrodingerskatt222
    @schrodingerskatt222 Рік тому +9

    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.

  • @Daniel-fn6tj
    @Daniel-fn6tj 4 місяці тому +1

    Learned something today with the negative on the rating to get the sorting right for the second element in the tuple. Great solution!

  • @theteacher010
    @theteacher010 Рік тому +12

    This was a really good problem, especially since Sorted Sets aren't covered in the original Neetcode 150!

    • @adrian333dev
      @adrian333dev Рік тому

      ua-cam.com/users/shorts8nmYnhKCX4c

  • @gmh14
    @gmh14 Рік тому +2

    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!

    • @satwiktatikonda764
      @satwiktatikonda764 Рік тому

      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)

    • @andreikiryieuski364
      @andreikiryieuski364 Рік тому

      Java also gives TLE when a map of heaps is used.

  • @asparshraj9016
    @asparshraj9016 Рік тому +3

    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.

    • @HibiTeamQueso
      @HibiTeamQueso Рік тому +1

      Same, I passed 72/77 with only arrays

  • @yashaggarwal2949
    @yashaggarwal2949 Рік тому +1

    In my opinion it's a pretty good problem. I did solve it on my own but I had to see the hints.

  • @sy_alty
    @sy_alty Рік тому +1

    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.

    • @HelloWorld-z1h
      @HelloWorld-z1h 10 місяців тому

      Actually, you can just initailize a Sorted Set with a custom comparator function like this SortedSet(key=lambda x: (-x[0], x[1]))

  • @BirajDahal-z6u
    @BirajDahal-z6u Рік тому +2

    Cant we do hashMap[cuisine] --> mapped to priority queue [(rating, food)]?

    • @HardcoreJapanese
      @HardcoreJapanese Рік тому +3

      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.

    • @mkum2141
      @mkum2141 Рік тому +3

      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.

    • @BirajDahal-z6u
      @BirajDahal-z6u Рік тому

      @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]

    • @yang5843
      @yang5843 Рік тому

      @@mkum2141 You could add a list to nullify any existing (food+old food rating) so the heap skips those values

    • @BirajDahal-z6u
      @BirajDahal-z6u Рік тому

      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]

  • @vishalpanchidi4538
    @vishalpanchidi4538 Рік тому

    Absolute Genius

  • @ChrisBakare
    @ChrisBakare Рік тому

    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.

  • @Vancha112
    @Vancha112 Рік тому +1

    Hmm yeah I'll think i will just go with a naive approach 😅

  • @SatansSpatula
    @SatansSpatula 7 місяців тому

    You skipped the part of the problem about " If there is a tie, return the item with the lexicographically smaller name."

  • @masterbyte42
    @masterbyte42 Рік тому +3

    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)

    • @phatboislym
      @phatboislym Рік тому

      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?

    • @masterbyte42
      @masterbyte42 Рік тому +1

      @@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)

  • @tanishq8211
    @tanishq8211 Рік тому

    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...

  • @andreikiryieuski364
    @andreikiryieuski364 Рік тому

    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.

    • @NeetCodeIO
      @NeetCodeIO  Рік тому +1

      Searching a tree map is logn, whole searching a heap is o(n)

  • @yang5843
    @yang5843 Рік тому

    I don't think I'll be able to solve this in a 40 minute interview

  • @SlateCode
    @SlateCode Рік тому

    videoon medium or hard daily problems

  • @bundiderp5109
    @bundiderp5109 Рік тому

    I really feel like this is a hard problem...

  • @asktostranger8296
    @asktostranger8296 Рік тому

    Is this low level design??

  • @mkum2141
    @mkum2141 Рік тому

    neetgoat