Design a Food Rating System
Understanding the Problem
We need to build a data structure that manages food items, each belonging to a cuisine and having a rating. Two operations must be supported: updating a food's rating and querying the highest-rated food for a given cuisine (with lexicographic tiebreaking).
The challenge is the interplay between updates and queries. If we only needed queries, we could sort each cuisine's food list once and be done. Ratings change, so we need a structure that handles both efficiently. A linear scan of every food in a cuisine on each query works, but with up to 2 * 10^4 total calls it can be slow when a cuisine is large.
What we need is a per-cuisine ordered collection where we can find the maximum quickly and also update individual elements. A sorted set (TreeSet in Java, SortedSet in C#, std::set in C++, SortedList or BTreeSet elsewhere) gives this directly. In languages without a built-in ordered set, a heap with lazy deletion achieves the same time bounds.
Key Constraints:
n <= 2 * 10^4and at most2 * 10^4calls -> An O(k) scan per query, where k is the cuisine size, reaches O(n) per query when one cuisine holds all foods. With many queries that approaches 4 * 10^8 operations, so an O(log n) per-operation structure is the safer target.ratings[i] <= 10^8-> Ratings fit in a 32-bit signed int (max ~2.1 * 10^9), so no overflow concerns.- All food names are distinct -> Food names work as unique keys in hash maps.
foodandcuisinearguments are always valid -> No need to handle missing keys.
Approach 1: Brute Force (Linear Scan)
Intuition
Store each food's information in hash maps, and whenever we need the highest-rated food for a cuisine, scan through all foods of that cuisine and pick the best one. There is no ordering to maintain.
changeRating updates the food's rating in a hash map, which is O(1). highestRated iterates through every food in the given cuisine, comparing ratings and breaking ties by name. This scan is O(k), where k is the number of foods in that cuisine.
Algorithm
- In the constructor, build three hash maps:
foodToRating: maps each food name to its rating.foodToCuisine: maps each food name to its cuisine.cuisineToFoods: maps each cuisine to its list of food names.- For
changeRating(food, newRating): updatefoodToRating[food]tonewRating. - For
highestRated(cuisine): iterate through all foods incuisineToFoods[cuisine], track the one with the highest rating. If two foods have the same rating, pick the lexicographically smaller name.
Example Walkthrough
Code
- Time Complexity:
- Constructor: O(n), where n is the number of food items. We iterate once to populate all hash maps.
changeRating: O(1). Single hash map update.highestRated: O(k), where k is the number of foods in the given cuisine. In the worst case, all foods belong to one cuisine, so k = n.- Space Complexity: O(n) for storing all food information in hash maps.
Every highestRated call rescans the entire cuisine, repeating work that the previous query already did. The next approach keeps each cuisine's foods in sorted order so the highest-rated one is always available without a scan.
Approach 2: Sorted Set (Optimal)
Intuition
Instead of scanning every food on each query, maintain a sorted set per cuisine. Order entries by rating descending, then by name ascending for tiebreaking. The highest-rated food is then always the first element, so a query is O(1): peek at the front.
The work moves to changeRating. The set is ordered by rating, so an in-place value update would leave the entry in the wrong position. We remove the old entry, update the rating, then insert the new entry. Removal and insertion are each O(log k) in a balanced-BST-backed set, where k is the number of foods in that cuisine.
The languages with a built-in ordered set use it directly: TreeSet in Java, SortedSet in C#, std::set in C++, SortedList (from sortedcontainers, available on LeetCode) in Python, and BTreeSet in Rust. Go, JavaScript, and TypeScript have no built-in ordered set, so they reach the same time bounds with a heap and lazy deletion, described after the sorted-set code.
Algorithm
- In the constructor:
- Build a
foodToRatingmap and afoodToCuisinemap, same as before. - For each cuisine, create a
TreeSet(or equivalent sorted set) that orders entries by (-rating, name). This way the first element is always the highest-rated food (with lexicographic tiebreaking). - For
changeRating(food, newRating): - Look up the food's cuisine and current rating.
- Remove the entry (currentRating, food) from the cuisine's sorted set.
- Update
foodToRating[food]to newRating. - Insert the entry (newRating, food) into the cuisine's sorted set.
- For
highestRated(cuisine): - Return the first element of the cuisine's sorted set. This is the food with the highest rating (and smallest name on ties).
Example Walkthrough
Code
The sorted set's comparison key encodes both query rules at once: rating descending, then name ascending. So the first element is, by construction, the highest-rated food with the smallest name on ties. There is nothing to compute at query time.
The ordering of an entry depends on its rating, so an entry must be removed using its old key before the rating changes. If we updated foodToRating first, the set could no longer locate the old entry to remove it, leaving a stale duplicate. The order is: remove old key, update rating, insert new key.
The heap variant (Go, JavaScript, TypeScript) cannot remove an arbitrary entry cheaply, so changeRating pushes a new entry and leaves the old one in place. A query pops entries off the top while their stored rating disagrees with the current rating in foodToRating, stopping at the first entry that matches. That first matching entry is the true maximum, because any entry above it had a higher stored rating that is now outdated and gets discarded. Each entry is pushed once and popped at most once, so the work is amortized O(log n) per operation.
- Time Complexity:
- Constructor: O(n log n). Each of the n foods is inserted into a sorted set in O(log k), where k is that cuisine's size, summing to O(n log n) in the worst case.
changeRating: O(log n). One removal and one insertion in the sorted set, each O(log k) with k <= n. The heap variant is also O(log n) for the push.highestRated: O(1) for the sorted-set variant (read the first element). For the heap variant it is amortized O(log n), since each stale entry is popped at most once over the lifetime of the structure.- Space Complexity: O(n) for the hash maps and sorted sets. The heap variant can grow to O(n + q), where q is the number of
changeRatingcalls, because stale entries stay in the heap until a query pops them.