Problem statement

A food app lists n dishes. Dish i is called foods[i], belongs to the cuisine cuisines[i] and has the rating ratings[i]. Write the class FoodRatings:

• FoodRatings(String[] foods, String[] cuisines, int[] ratings) stores the n dishes.
• void changeRating(String food, int newRating) sets the rating of the dish named food to newRating.
• String highestRated(String cuisine) returns the name of the dish with the highest rating in that cuisine. If several dishes share the highest rating, return the one whose name is lexicographically smallest.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["FoodRatings","highestRated","highestRated","changeRating","highestRated","changeRating","highestRated","changeRating","highestRated"]
[[["dosa","idli","biryani","korma","vada","pulao"],["south","south","mughlai","mughlai","south","mughlai"],[8,8,10,7,6,9]],["south"],["mughlai"],["biryani",5],["mughlai"],["vada",8],["south"],["dosa",1],["south"]]
Output: [null,"dosa","biryani",null,"pulao",null,"dosa",null,"idli"]
Explanation: dosa and idli tie at 8 in south, and "dosa" comes first. Once biryani drops to 5, pulao (9) leads mughlai. vada rising to 8 does not beat dosa (same rating, larger name); after dosa drops to 1, idli leads.

Example 2

Input: ["FoodRatings","highestRated","changeRating","highestRated","changeRating","highestRated"]
[[["pho"],["vietnamese"],[100000000]],["vietnamese"],["pho",1],["vietnamese"],["pho",3],["vietnamese"]]
Output: [null,"pho",null,"pho",null,"pho"]
Explanation: With a single dish in the cuisine it is always the answer, whatever its rating.

Constraints

• 1 <= n <= 2 * 10^4
• n == foods.length == cuisines.length == ratings.length
• 1 <= foods[i].length, cuisines[i].length <= 10
• foods[i] and cuisines[i] consist of lowercase English letters
• 1 <= ratings[i] <= 10^8
• All the strings in foods are distinct
• food is the name of a dish in foods; cuisine is a cuisine of at least one dish
• 1 <= newRating <= 10^8
• At most 2 * 10^4 calls are made in total to changeRating and highestRated

Hints for Design a Food Rating System

1. Hint 1

   Scanning every dish of a cuisine on each query is too slow when one cuisine holds most of the 2 * 10^4 dishes.

2. Hint 2

   Keep, per cuisine, its dishes ordered by (rating descending, name ascending). The answer is then the first element.

3. Hint 3

   A rating change must move the dish inside that order: in an ordered set, remove the old (rating, name) and insert the new one. With a heap, push the new pair and skip tops whose rating is out of date (lazy deletion).

How to solve Design a Food Rating System

Map each dish to its cuisine and current rating, and keep each cuisine's dishes in an ordered set keyed by (-rating, name). The highest rated dish is the set's first element; a rating change is a delete and an insert.

Approach

1. Build cuisineOf[food], rating[food], and for every cuisine an ordered set of (-rating, name) pairs.
2. changeRating(food, r): in cuisineOf[food]'s set remove (-rating[food], food), set rating[food] = r, insert (-r, food).
3. highestRated(cuisine): return the name of the first pair in that cuisine's set.
4. Heap alternative: push (-r, food) on every change and, when querying, pop tops whose stored rating differs from rating[food].

Why it works

Sorting by -rating first and by name second puts the highest rating first and, among equal ratings, the lexicographically smallest name first — exactly the required tie-break. Each set always holds one up-to-date pair per dish of its cuisine, because a change replaces that dish's pair.

Complexity

• Time — O(log n) per call (amortised O(log n) with the lazy heap); O(n log n) to build
• Space — O(n)

Pitfalls

• The tie-break is the smaller name, not the dish that came first in the input.
• If a comparator reads the current rating from a map, remove the dish from the set before updating its rating, or the set can no longer find it.
• Compare names by character codes (ordinal), not with a locale-aware comparison.

Reference solution

Python

import heapq

class FoodRatings:

    def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
        self.cuisineOf = {}
        self.rating = {}
        self.heaps = {}  # cuisine -> heap of (-rating, name); stale pairs are skipped later
        for f, c, r in zip(foods, cuisines, ratings):
            self.cuisineOf[f] = c
            self.rating[f] = r
            self.heaps.setdefault(c, []).append((-r, f))
        for h in self.heaps.values():
            heapq.heapify(h)

    def changeRating(self, food: str, newRating: int) -> None:
        self.rating[food] = newRating
        heapq.heappush(self.heaps[self.cuisineOf[food]], (-newRating, food))

    def highestRated(self, cuisine: str) -> str:
        h = self.heaps[cuisine]
        while -h[0][0] != self.rating[h[0][1]]:
            heapq.heappop(h)  # that rating has changed since
        return h[0][1]

Java

class FoodRatings {
    private HashMap<String, String> cuisineOf = new HashMap<>();
    private HashMap<String, Integer> rating = new HashMap<>();
    private HashMap<String, TreeSet<String>> sets = new HashMap<>();
    // Orders dish names by their current rating (high first), then by name.
    private Comparator<String> order = (a, b) -> {
        int ra = rating.get(a), rb = rating.get(b);
        return ra != rb ? Integer.compare(rb, ra) : a.compareTo(b);
    };

    public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
        for (int i = 0; i < foods.length; i++) {
            cuisineOf.put(foods[i], cuisines[i]);
            rating.put(foods[i], ratings[i]);
            sets.computeIfAbsent(cuisines[i], k -> new TreeSet<>(order)).add(foods[i]);
        }
    }

    public void changeRating(String food, int newRating) {
        TreeSet<String> s = sets.get(cuisineOf.get(food));
        s.remove(food); // while the comparator still sees the old rating
        rating.put(food, newRating);
        s.add(food);
    }

    public String highestRated(String cuisine) {
        return sets.get(cuisine).first();
    }
}

C++

class FoodRatings {
    unordered_map<string, string> cuisineOf;
    unordered_map<string, int> rating;
    unordered_map<string, set<pair<int, string>>> sets; // cuisine -> (-rating, name)
public:
    FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
        for (size_t i = 0; i < foods.size(); i++) {
            cuisineOf[foods[i]] = cuisines[i];
            rating[foods[i]] = ratings[i];
            sets[cuisines[i]].insert({-ratings[i], foods[i]});
        }
    }

    void changeRating(string food, int newRating) {
        auto& s = sets[cuisineOf[food]];
        s.erase({-rating[food], food});
        rating[food] = newRating;
        s.insert({-newRating, food});
    }

    string highestRated(string cuisine) {
        return sets[cuisine].begin()->second;
    }
};

JavaScript

// Each cuisine keeps [rating, name] pairs sorted by rating descending, then name ascending.
function frBefore(r1, n1, r2, n2) {
    return r1 > r2 || (r1 === r2 && n1 < n2);
}

function frPos(list, r, name) { // first position not before (r, name)
    var lo = 0, hi = list.length;
    while (lo < hi) {
        var mid = (lo + hi) >> 1;
        if (frBefore(list[mid][0], list[mid][1], r, name)) lo = mid + 1; else hi = mid;
    }
    return lo;
}

var FoodRatings = function(foods, cuisines, ratings) {
    this.cuisineOf = new Map();
    this.rating = new Map();
    this.lists = new Map();
    for (var i = 0; i < foods.length; i++) {
        this.cuisineOf.set(foods[i], cuisines[i]);
        this.rating.set(foods[i], ratings[i]);
        if (!this.lists.has(cuisines[i])) this.lists.set(cuisines[i], []);
        this.lists.get(cuisines[i]).push([ratings[i], foods[i]]);
    }
    this.lists.forEach(function(list) {
        list.sort(function(a, b) { return frBefore(a[0], a[1], b[0], b[1]) ? -1 : 1; });
    });
};

FoodRatings.prototype.changeRating = function(food, newRating) {
    var list = this.lists.get(this.cuisineOf.get(food));
    var old = this.rating.get(food);
    list.splice(frPos(list, old, food), 1);
    list.splice(frPos(list, newRating, food), 0, [newRating, food]);
    this.rating.set(food, newRating);
};

FoodRatings.prototype.highestRated = function(cuisine) {
    return this.lists.get(cuisine)[0][1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium
• Simple Bank System Medium