Track Dish Ratings and Report the Top-Rated Dish in Each Cuisine

A rating tracker keeps a rating for every dish on a menu, and each dish belongs to exactly one cuisine. Ratings change over time, and at any moment the tracker must report the highest-rated dish within a given cuisine. In the interview this was written as a class (a constructor, a method that changes a rating, and a method that reports the top dish of a cuisine) together with the candidate's own test cases; here the class is driven by a single function that replays a list of operations. ### Function Signature ```python def run_dish_ratings(foods: list[str], cuisines: list[str], ratings: list[int], operations: list[list[str]]) -> list[str]: ``` ### Rules - Dish `foods[i]` belongs to cuisine `cuisines[i]` and starts with rating `ratings[i]`. A dish's cuisine never changes. - The operations are applied in order. Each one is either: - `["change", food, new_rating]`: set the rating of dish `food` to the integer written in decimal in the string `new_rating`. Setting a dish to its current rating is allowed and changes nothing. - `["highest", cuisine]`: report the name of the dish in `cuisine` with the highest current rating. If several dishes share that rating, report the name that is smallest in lexicographic order: compare character by character, and a name that is a proper prefix of another comes first, so `"pie"` comes before `"pierogi"`. - Return the reports of all `"highest"` operations, in the order those operations appear. Return an empty list if there are none. ### Constraints - `1 <= len(foods) <= 2 * 10^4`, and `len(cuisines) == len(ratings) == len(foods)` - Every dish name and cuisine name has 1 to 10 lowercase English letters. Dish names are distinct; many dishes can share a cuisine. - `1 <= ratings[i] <= 10^9`. Every `new_rating` is the decimal string of an integer in the same range, with no sign and no leading zeros. - `1 <= len(operations) <= 2 * 10^4` - Every `"change"` names a dish in `foods`, and every `"highest"` names a cuisine that appears in `cuisines`. - All values fit in a 32-bit signed integer. ### Examples **Example 1** ```text Input: foods = ["tacos", "pho", "burrito", "ramen", "nachos"] cuisines = ["mexican", "vietnamese", "mexican", "japanese", "mexican"] ratings = [7, 9, 8, 6, 8] operations = [["highest", "mexican"], ["change", "tacos", "10"], ["highest", "mexican"], ["change", "tacos", "5"], ["highest", "mexican"], ["change", "burrito", "3"], ["highest", "mexican"], ["highest", "japanese"]] Output: ["burrito", "tacos", "burrito", "nachos", "ramen"] ``` The Mexican dishes start at tacos 7, burrito 8 and nachos 8, and the tie at 8 goes to `"burrito"`. Tacos then rises to 10 and leads. After it drops to 5, burrito and nachos tie at 8 again and `"burrito"` wins. After burrito drops to 3, nachos leads with 8. Ramen is the only Japanese dish. **Example 2** ```text Input: foods = ["pierogi", "pie"] cuisines = ["comfort", "comfort"] ratings = [5, 5] operations = [["highest", "comfort"], ["change", "pierogi", "6"], ["highest", "comfort"], ["change", "pie", "6"], ["highest", "comfort"]] Output: ["pie", "pierogi", "pie"] ``` `"pie"` is a proper prefix of `"pierogi"`, so it wins both ties; in between, pierogi leads alone with 6.