Design a Food Rating System - Practice Coding Problems

Design a Food Rating System - Problem

Array Hash Table String Design Heap (Priority Queue) Ordered Set Medium

Design a food rating system that supports the following operations:

Modify the rating of a food item in the system
Return the highest-rated food item for a specific cuisine type

Implement the FoodRatings class:

FoodRatings(String[] foods, String[] cuisines, int[] ratings) - Initializes the system with food items, their cuisines, and initial ratings
void changeRating(String food, int newRating) - Changes the rating of the specified food item
String highestRated(String cuisine) - Returns the name of the highest-rated food for the given cuisine. If there's a tie, return the lexicographically smaller name

Input & Output

Example 1 — Basic Operations

$ Input: operations = [["FoodRatings", ["kimchi", "miso", "sushi"], ["korean", "japanese", "japanese"], [9, 12, 8]], ["highestRated", "japanese"], ["changeRating", "sushi", 16], ["highestRated", "japanese"]]

› Output: ["miso", "sushi"]

💡 Note: Initially miso (12) > sushi (8) for japanese cuisine. After updating sushi to 16, sushi (16) > miso (12).

Example 2 — Lexicographic Tiebreaker

$ Input: operations = [["FoodRatings", ["apple", "banana"], ["fruit", "fruit"], [5, 5]], ["highestRated", "fruit"]]

› Output: ["apple"]

💡 Note: Both have rating 5, so return lexicographically smaller: apple < banana.

Example 3 — Single Item Cuisine

$ Input: operations = [["FoodRatings", ["pizza"], ["italian"], [10]], ["highestRated", "italian"]]

› Output: ["pizza"]

💡 Note: Only one item in italian cuisine, so return pizza.

Constraints

1 ≤ n ≤ 2×10⁴
1 ≤ foods[i].length, cuisines[i].length ≤ 10
1 ≤ ratings[i] ≤ 10⁸
At most 2×10⁴ calls to changeRating and highestRated

Visualization

Tap to expand

Understanding the Visualization

Input

Foods with cuisines and ratings

Operations

Support rating updates and highest-rated queries

Output

Return best food per cuisine (lexicographic tiebreaker)

Key Takeaway

🎯 Key Insight: Hash maps provide O(1) food access while heaps maintain sorted order per cuisine for fast queries

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Meta 12

The key insight is combining hash maps for O(1) food lookups with priority queues for efficient cuisine-based queries. The optimal approach uses a hash map to store food metadata and separate max-heaps per cuisine. Time: O(log k) per query, Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Linear Search Each Time	O(n)	O(n)	Store all data in arrays and search linearly for each query
Hash Map + Priority Queue	O(log k)	O(n)	Use hash maps for O(1) lookups and heaps for efficient highest-rated queries

Linear Search Each Time — Algorithm Steps

Step 1: Store foods, cuisines, ratings in parallel arrays
Step 2: For changeRating, find food and update its rating
Step 3: For highestRated, scan all foods to find best in cuisine

Visualization

Tap to expand

Step-by-Step Walkthrough

Store Data

Keep parallel arrays for foods, cuisines, ratings

Search Linear

For each query, scan through all foods

Find Best

Return food with highest rating in cuisine

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_FOODS 1000
#define MAX_NAME_LEN 50

typedef struct {
    char foods[MAX_FOODS][MAX_NAME_LEN];
    char cuisines[MAX_FOODS][MAX_NAME_LEN];
    int ratings[MAX_FOODS];
    int count;
} FoodRatings;

FoodRatings* createFoodRatings(char foods[][MAX_NAME_LEN], char cuisines[][MAX_NAME_LEN], int* ratings, int count) {
    FoodRatings* fr = malloc(sizeof(FoodRatings));
    fr->count = count;
    for (int i = 0; i < count; i++) {
        strcpy(fr->foods[i], foods[i]);
        strcpy(fr->cuisines[i], cuisines[i]);
        fr->ratings[i] = ratings[i];
    }
    return fr;
}

void changeRating(FoodRatings* fr, char* food, int newRating) {
    for (int i = 0; i < fr->count; i++) {
        if (strcmp(fr->foods[i], food) == 0) {
            fr->ratings[i] = newRating;
            return;
        }
    }
}

char* highestRated(FoodRatings* fr, char* cuisine) {
    int bestRating = -1;
    static char bestFood[MAX_NAME_LEN];
    bestFood[0] = '\0';
    
    for (int i = 0; i < fr->count; i++) {
        if (strcmp(fr->cuisines[i], cuisine) == 0) {
            if (fr->ratings[i] > bestRating || (fr->ratings[i] == bestRating && strcmp(fr->foods[i], bestFood) < 0)) {
                bestRating = fr->ratings[i];
                strcpy(bestFood, fr->foods[i]);
            }
        }
    }
    return bestFood;
}

int main() {
    // Simplified example
    char foods[3][MAX_NAME_LEN] = {"kimchi", "miso", "sushi"};
    char cuisines[3][MAX_NAME_LEN] = {"korean", "japanese", "japanese"};
    int ratings[3] = {9, 12, 8};
    
    FoodRatings* fr = createFoodRatings(foods, cuisines, ratings, 3);
    char* result = highestRated(fr, "japanese");
    printf("[\"%s\"]\n", result);
    
    free(fr);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each highestRated query scans all n foods

✓ Linear Growth

Space Complexity

O(n)

Three arrays storing n food items

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Linear Search Each Time — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler