Design a Food Rating System
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Foods have a cuisine and a rating. Support changeRating(food, newRating) and highestRated(cuisine) (ties: the lexicographically smaller food name).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Which heap order puts the highest rating first, and the smaller name first on ties?
- Hint 2How can you know that a heap entry is outdated?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Each cuisine has a leaderboard board where the best dish stands at the top. When a dish's rating changes you do not search the board to rub the old entry out; you just add a fresh entry with the new rating. When someone asks for the best dish of a cuisine you look at the top entry: if its rating differs from the dish's current rating on the master list, that entry is outdated, so you discard it and look at the next one, until the top entry is up to date.
- The obvious way
Scan all foods of the cuisine on each query: O(n).
- The key insight
Keep rating_of[food], cuisine_of[food] and a min-heap per cuisine holding (-rating, name). changeRating: update rating_of and push a new entry. highestRated: while the top entry's rating differs from rating_of, pop it; then return the top entry's food.
- The algorithm
- Build rating_of, cuisine_of and a heap per cuisine.
- changeRating: store the new rating, push a fresh entry.
- highestRated: pop outdated top entries.
- Return the top entry's food name.
Watch it run
Examplefoods: kimchi 9 K, miso 12 J, sushi 8 J, moussaka 15 G, ramen 14 J, bulgogi 7 K
highestRated(korean): kimchi 9 beats bulgogi 7: kimchi. highestRated(japanese): ramen 14 beats miso 12 and sushi 8: ramen.
kimchi, ramen
Where people slip
- Never delete from the middle of a heap; compare the top with the master rating instead (lazy deletion).
- Ties: negative rating then the NAME ascending gives the smaller name first.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
import heapq
class FoodRatings:
def __init__(self, foods, cuisines, ratings):
self.rating_of = {} # master list: current rating of each food
self.cuisine_of = {}
self.boards = {} # cuisine -> heap of (-rating, name)
for food, cuisine, rating in zip(foods, cuisines, ratings):
self.rating_of[food] = rating
self.cuisine_of[food] = cuisine
heapq.heappush(self.boards.setdefault(cuisine, []), (-rating, food))
def changeRating(self, food, newRating):
self.rating_of[food] = newRating
heapq.heappush(self.boards[self.cuisine_of[food]], (-newRating, food)) # old entry stays; it is now stale
def highestRated(self, cuisine):
board = self.boards[cuisine]
while -board[0][0] != self.rating_of[board[0][1]]:
heapq.heappop(board) # outdated entry: throw it away
return board[0][1]Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.