921. Dish Rating Board

Medium3.5 points estimatedDesignHash TableHeapOrdered Set4 hints
RPby Rohit Parihar

A food-court app ranks stalls' signature dishes. Build the class DishRatings. The constructor receives three equal-length arrays: foods (all names distinct, lowercase), cuisines and ratings; the dish foods[i] belongs to cuisine cuisines[i] and has rating ratings[i].

  • changeRating(food, newRating) sets a new rating for an existing dish.
  • highestRated(cuisine) returns the name of the dish of that cuisine with the highest current rating. If several dishes share that rating, return the lexicographically smallest name. The cuisine always has at least one dish.

Aim for O(log n) amortized per call, not a scan over all dishes.

Example 1

Input:
operations = ["DishRatings","highestRated","changeRating","highestRated","changeRating","highestRated","highestRated"]arguments = [[["laksa","pho","satay","tomyum","ramen"],["malay","viet","malay","thai","jap"],[40,55,40,70,65]],["malay"],["satay",45],["malay"],["tomyum",10],["thai"],["jap"]]
Output:
[null,"laksa",null,"satay",null,"tomyum","ramen"]
Explanation:

Laksa and satay tie at 40 so laksa (alphabetically first) wins; after satay rises to 45 it leads; tomyum is the only thai dish so it stays the answer even at rating 10.

Example 2

Input:
operations = ["DishRatings","highestRated","changeRating","highestRated","changeRating","highestRated","changeRating","highestRated"]arguments = [[["moussaka","souvlaki","gyro","spanakopita"],["greek","greek","greek","greek"],[30,30,30,30]],["greek"],["moussaka",29],["greek"],["gyro",31],["greek"],["gyro",30],["greek"]]
Output:
[null,"gyro",null,"gyro",null,"gyro",null,"gyro"]
Explanation:

All four tie at 30 so gyro (alphabetically first) leads; lowering moussaka changes nothing; gyro at 31 leads; back at 30 the order falls back to alphabetical.

Constraints

1 ≤ foods.length ≤ 1000

1 ≤ ratings[i], newRating ≤ 100000

Names and cuisines are lowercase letters or digits, length 1 to 12

At most 3000 calls in total

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time
O(log n) amortized per call
Space
O(n + calls)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.