Highest-rated food per cuisine under rating updates with a lexicographic tie-break

A rating tracker is created from a list of foods. Each food belongs to one cuisine and has an integer rating. The tracker then processes a sequence of operations in order: an update sets one food's rating to a new value, and a query asks for the highest-rated food of a cuisine at that moment. Return the answers to all queries. The report describes the task as similar to a well-known design problem: a class with a constructor, an update method and a query method, written together with the candidate's own test cases. This version expresses the same behaviour as one function over a list of operations and fixes the exact rules below. ### Function Signature ```python def run_rating_tracker(foods: list[str], cuisines: list[str], ratings: list[int], operations: list[list[str]]) -> list[str]: ``` ### Rules - Food `foods[i]` belongs to cuisine `cuisines[i]` and starts with rating `ratings[i]`. Food names are distinct, and a food's cuisine never changes. - `["change", food, r]` sets the current rating of `food` to the integer written in decimal in the string `r`. It produces no output. The new rating may be higher than, lower than or equal to the old one. - `["highest", cuisine]` outputs the name of the food with the highest current rating among the foods of `cuisine`. If several of them share that rating, it outputs the lexicographically smallest of their names. - A query reflects every change that comes before it in `operations` and none that come after it. Queries never modify the tracker, so repeating a query with no change in between gives the same answer. - Return the outputs of all `"highest"` operations in the order they occur, or an empty list if there are none. ### Constraints - `1 <= n <= 2 * 10^4`, where `n = len(foods) = len(cuisines) = len(ratings)`. - Every food name and cuisine name consists of 1 to 10 lowercase English letters. - `1 <= rating <= 10^8` for initial and changed ratings; `r` has no sign and no leading zeros. - `1 <= len(operations) <= 2 * 10^4`; each operation is either `["change", food, r]` or `["highest", cuisine]`. - Every `change` names a food in `foods`, and every `highest` names a cuisine that appears in `cuisines`. - Lexicographic order is ordinary string comparison: compare letter by letter, and a name that is a prefix of another comes first. ### Examples **Example 1** ```text Input: foods = ["pho", "banhmi", "tacos", "burrito", "goi"] cuisines = ["vietnamese", "vietnamese", "mexican", "mexican", "vietnamese"] ratings = [7, 9, 8, 8, 9] operations = [["highest", "vietnamese"], ["highest", "mexican"], ["change", "pho", "10"], ["highest", "vietnamese"], ["change", "pho", "3"], ["highest", "vietnamese"]] Output: ["banhmi", "burrito", "pho", "banhmi"] ``` "banhmi" and "goi" share the top Vietnamese rating of 9, and "banhmi" is smaller; "burrito" and "tacos" tie at 8. After "pho" rises to 10 it leads, and after it drops to 3 the tie between "banhmi" and "goi" decides again. **Example 2** ```text Input: foods = ["dal", "naan", "korma"] cuisines = ["indian", "indian", "indian"] ratings = [5, 5, 4] operations = [["change", "dal", "2"], ["highest", "indian"], ["change", "naan", "1"], ["highest", "indian"], ["highest", "indian"], ["change", "dal", "5"], ["highest", "indian"]] Output: ["naan", "korma", "korma", "dal"] ``` After "dal" drops to 2, "naan" (5) leads. After "naan" drops to 1, "korma" (4) leads, and the repeated query returns it again. Raising "dal" back to 5 puts it on top. **Example 3** ```text Input: foods = ["zeppole", "arancini"] cuisines = ["italian", "italian"] ratings = [6, 3] operations = [["highest", "italian"], ["change", "arancini", "6"], ["highest", "italian"], ["change", "zeppole", "6"], ["highest", "italian"]] Output: ["zeppole", "arancini", "arancini"] ``` Raising "arancini" to 6 creates a tie that it wins by name; setting "zeppole" to its current rating changes nothing.