DSA problem
Design a Food Rating System
Design a system that tracks foods organized by cuisine, supports rating updates, and returns the highest-rated food per cuisine on demand. The constructor receives parallel arrays foods, cuisines, and ratings of equal length n. changeRating(food, newRating) updates a food's rating. highestRated(cuisine) returns the name of the food in that cuisine with the highest rating; ties are broken by lexicographically smaller name.
The naive solution scans every food in a cuisine on each highestRated call — O(n) per query. With up to 10^4 cuisines and 2·10^4 changeRating calls, that is too slow. The fix is to maintain, per cuisine, an ordered structure where the best food is always at one end. A standard choice is a TreeSet (Java) / SortedSet (Python via SortedList) / std::set (C++) keyed by (-rating, food) — so the lexicographic minimum of the set is also the highest-rated food, with ties broken alphabetically.
The other required state is a hash map food -> (cuisine, rating). When changeRating is called, we need to find the food's current cuisine and rating in O(1) to know which set entry to remove. We then remove the old (-oldRating, food) from the cuisine's set, insert (-newRating, food), and update the food's rating in the map.
highestRated(cuisine) peeks at the first element of the cuisine's sorted set in O(log n) and returns its food name. changeRating is also O(log n) because of the set remove and insert. The space is O(n) for the food map and the union of cuisine sets, each of which is just a partition of the same n foods. This is a textbook "indexed priority queue" — what you reach for whenever you need a heap that also supports random key updates.
Examples
foods=["kimchi","miso"], cuisines=["korean","japanese"], ratings=[9,12]; highestRated("korean")"kimchi"foods=["kimchi","ramen","sushi"], cuisines=["k","j","j"], ratings=[9,14,8]; highestRated("j")"ramen"foods=["a","b"], cuisines=["c","c"], ratings=[5,5]; changeRating("b",10); highestRated("c")"b"Constraints
- 1 <= n <= 2 * 10^4
- n == foods.length == cuisines.length == ratings.length
- 1 <= foods[i].length, cuisines[i].length <= 10
- foods[i], cuisines[i] consist only of lowercase English letters.
- 1 <= ratings[i] <= 10^8 and changeRating + highestRated combined ≤ 2 * 10^4 calls.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.