Design a Food Rating System

MediumDesign · Hash Map + Ordered Set🧩 Data Structure Design LeetCode #2353 ↗Updated Oct 30, 2026

Problem

Build FoodRatings(foods, cuisines, ratings), where food i has a unique name, a cuisine and a rating. Support changeRating(food, newRating) and highestRated(cuisine), which returns the name of the best-rated food of that cuisine; ties go to the lexicographically smallest name.

Input

foods=[kimchi,miso,sushi,moussaka,ramen,bulgogi] cuisines=[korean,japanese,japanese,greek,japanese,korean] ratings=[9,12,8,15,14,7]; highestRated(korean)

Outputkimchi

InputhighestRated(japanese); changeRating(sushi,16); highestRated(japanese)Outputramen, sushi

InputchangeRating(ramen,16); highestRated(japanese)Outputramen (tie, smaller name)

1 ≤ n ≤ 2·10⁴ · 1 ≤ ratings[i] ≤ 10⁸ · names ≤ 10 lowercase letters · ≤ 2·10⁴ calls · queried food/cuisine always exists

Try it yourself

Java

class FoodRatings {
    public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
        
    }

    public void changeRating(String food, int newRating) {
        
    }

    public String highestRated(String cuisine) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Group foods by cuisine and keep each group sorted by (rating desc, name asc). A rating change is just remove → update → re-insert in that one group, and the answer is the group's first element.

PatternData Structure Design

Instinct Implement a class whose methods must all hit a time bound (often O(1)) - write each method's target cost, then glue a hash map to a structure that keeps order.

Memory hack Finder plus keeper - a hash map finds it fast, a list/heap/array keeps the order, and every method updates both.

Open the Data Structure Design guide →

Approaches

Brute ForceScan Every Food on Each Query

Time change O(1), query O(n)Space O(n)

Keep two maps: food → rating and food → cuisine. A rating change is a single map write. highestRated walks all foods, filters by cuisine, and keeps the best one using the rating-then-name rule.

Java

class FoodRatings {
    private final Map<String, Integer> rating = new HashMap<>();
    private final Map<String, String> cuisineOf = new HashMap<>();
    public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
        for (int i = 0; i < foods.length; i++) {
            rating.put(foods[i], ratings[i]);
            cuisineOf.put(foods[i], cuisines[i]);
        }
    }
    public void changeRating(String food, int newRating) {
        rating.put(food, newRating);
    }
    public String highestRated(String cuisine) {
        String best = null;
        for (Map.Entry<String, Integer> e : rating.entrySet()) {
            String food = e.getKey();
            if (!cuisineOf.get(food).equals(cuisine)) continue;
            int r = e.getValue();
            if (best == null || r > rating.get(best)
                    || (r == rating.get(best) && food.compareTo(best) < 0)) {
                best = food;
            }
        }
        return best;
    }
}

Simple and cheap to update, but every query touches all n foods.

BetterPer-Cuisine Max-Heap with Lazy Deletion

Time O(log m) amortizedSpace O(n + updates)

One priority queue per cuisine ordered by rating desc, then name asc. A change pushes a new entry instead of editing the old one. On a query, pop tops whose stored rating no longer matches the live rating — they are stale.

Java

class FoodRatings {
    private final Map<String, Integer> rating = new HashMap<>();
    private final Map<String, String> cuisineOf = new HashMap<>();
    private final Map<String, PriorityQueue<Map.Entry<String, Integer>>> heaps =
        new HashMap<>();
    public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
        for (int i = 0; i < foods.length; i++) {
            rating.put(foods[i], ratings[i]);
            cuisineOf.put(foods[i], cuisines[i]);
            heaps.computeIfAbsent(cuisines[i], c -> new PriorityQueue<>((a, b) ->
                    !a.getValue().equals(b.getValue())
                        ? Integer.compare(b.getValue(), a.getValue())
                        : a.getKey().compareTo(b.getKey())))
                 .offer(Map.entry(foods[i], ratings[i]));
        }
    }
    public void changeRating(String food, int newRating) {
        rating.put(food, newRating);
        heaps.get(cuisineOf.get(food)).offer(Map.entry(food, newRating)); // old one goes stale
    }
    public String highestRated(String cuisine) {
        PriorityQueue<Map.Entry<String, Integer>> heap = heaps.get(cuisine);
        while (!heap.peek().getValue().equals(rating.get(heap.peek().getKey()))) heap.poll();
        return heap.peek().getKey();
    }
}

Fast in practice, but stale entries pile up and a query may pop many of them.

OptimalPer-Cuisine TreeSet (Remove & Re-insert)

Time O(log n) per opSpace O(n)

Each cuisine owns a TreeSet of food names whose comparator reads the live rating map. To change a rating, remove the food while its old rating is still stored, update the map, then add it back. The best food is always first().

Java

class FoodRatings {
    private final Map<String, Integer> rating = new HashMap<>();
    private final Map<String, String> cuisineOf = new HashMap<>();
    private final Map<String, TreeSet<String>> byCuisine = new HashMap<>();
    public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
        for (int i = 0; i < foods.length; i++) {
            rating.put(foods[i], ratings[i]); // must exist before the set compares it
            cuisineOf.put(foods[i], cuisines[i]);
            byCuisine.computeIfAbsent(cuisines[i], c -> new TreeSet<>((a, b) -> {
                int ra = rating.get(a), rb = rating.get(b);
                return ra != rb ? Integer.compare(rb, ra) : a.compareTo(b);
            })).add(foods[i]);
        }
    }
    public void changeRating(String food, int newRating) {
        TreeSet<String> set = byCuisine.get(cuisineOf.get(food));
        set.remove(food); // locate it using the OLD rating
        rating.put(food, newRating);
        set.add(food);
    }
    public String highestRated(String cuisine) {
        return byCuisine.get(cuisine).first();
    }
}

Guaranteed O(log n) per call with no stale data — the expected answer.

Pro tip

Never change a key the TreeSet is ordered by while it is inside the set — always remove, mutate, re-insert.

At a glance

Level	Approach	Time	Space
Brute Force	Scan Every Food on Each Query	`change O(1), query O(n)`	`O(n)`
Better	Per-Cuisine Max-Heap with Lazy Deletion	`O(log m) amortized`	`O(n + updates)`
Optimal	Per-Cuisine TreeSet (Remove & Re-insert)	`O(log n) per op`	`O(n)`

Common pitfalls

Updating the rating before removing from the TreeSet — the removal silently fails.
Comparing boxed Integer ratings with == (breaks above 127).
Forgetting the name tie-break, so equal ratings return an arbitrary food.

Interview tips

Clarify that names are unique and queried cuisines always exist.
Present the lazy heap first, then explain why an ordered set avoids stale entries.
Walk through the tie example to show the comparator's second key.

Pattern

Hash map + ordered set per group → “best item in a category” with frequent score updates.

My notes saved in this browser