2353: Design-a-Food-Rating-System
Medium

table of contents

I forgot to write pseudocode- my thinking process was quite messy; here is what i should have done…

The overarching theme is that we want to be able to retrieve the highest-rated food item for a given cuisine. To do this, we could simply just create a priority_queue for each cuisine.

The issue with this approach, is that we also want to be able to change the rating for any given food item. The issue is that we are unable to directly retrieve a given food item inside the priority_queue and change its rating.

However, a way we can bypass this issue, is to simply not edit the existing value inside the priority_queue at all. Instead, we can simply add our new rating for a given food into the priority_queue and keep track of the current rating for any food item in a separate unordered_map. Then, when we want to retrieve the highest-rated food item, we can use the unordered_map to check whether the rating is “real” or not. If it is not, then we can pop the top value, else, we can simply return that food item as the highest-rated food item.

To start off, since the priority_queue has a unique way of ordering the food items (higher-rated items first, with tie-breakers being broken by the lexicographically-smaller name), we first define a Info structure:

struct Info {
    string name;
    string cuisine;
    int rating;

    bool operator<(const Info& other) const {
        if (rating != other.rating) {
            return rating < other.rating;
        }
        return name > other.name;
    }
};

Then, we initialize foodInfo, which aims to create a mapping between a food’s name and its Info, and cuisineFoodRanking, which aims to create a mapping between a cuisine and a priority_queue used to keep track of its respective highest-rated food:

private:
    unordered_map<string, Info> foodInfo;
    unordered_map<string, priority_queue<Info>> cuisineFoodRanking;
};

When we first initialize FoodRatings, we want to initialize both unordered_map’s with their respective data:

FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
    for (int i = 0; i < foods.size(); ++i) {
        foodInfo.emplace(foods[i], Info(foods[i], cuisines[i], ratings[i]));
        cuisineFoodRanking[cuisines[i]].emplace(foods[i], cuisines[i], ratings[i]);
    }
}

For changeRating, we can simply update foodInfo with the new rating and update the new Info value into cuisineFoodRanking:

void changeRating(string food, int newRating) {
    foodInfo[food].rating = newRating;
    cuisineFoodRanking[foodInfo[food].cuisine].push(foodInfo[food]);
}

For highestRated, we just check whether the top value is valid or not (if the top rating matches the rating inside foodInfo), and repeatedly pop the top value until we have a valid top food:

string highestRated(string cuisine) {
    auto top = cuisineFoodRanking[cuisine].top();
    while (top.rating != foodInfo[top.name].rating) {
        cuisineFoodRanking[cuisine].pop();
        top = cuisineFoodRanking[cuisine].top();
    }
    return top.name;
}

code

struct Info {
    string name;
    string cuisine;
    int rating;

    bool operator<(const Info& other) const {
        if (rating != other.rating) {
            return rating < other.rating;
        }
        return name > other.name;
    }
};

class FoodRatings {
public:
    FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
        for (int i = 0; i < foods.size(); ++i) {
            foodInfo.emplace(foods[i], Info(foods[i], cuisines[i], ratings[i]));
            cuisineFoodRanking[cuisines[i]].emplace(foods[i], cuisines[i], ratings[i]);
        }
    }
    
    void changeRating(string food, int newRating) {
        foodInfo[food].rating = newRating;
        cuisineFoodRanking[foodInfo[food].cuisine].push(foodInfo[food]);
    }
    
    string highestRated(string cuisine) {
        auto top = cuisineFoodRanking[cuisine].top();
        while (top.rating != foodInfo[top.name].rating) {
            cuisineFoodRanking[cuisine].pop();
            top = cuisineFoodRanking[cuisine].top();
        }
        return top.name;
    }
private:
    unordered_map<string, Info> foodInfo;
    unordered_map<string, priority_queue<Info>> cuisineFoodRanking;
};

/**
 * Your FoodRatings object will be instantiated and called as such:
 * FoodRatings* obj = new FoodRatings(foods, cuisines, ratings);
 * obj->changeRating(food,newRating);
 * string param_2 = obj->highestRated(cuisine);
 */

complexity

time taken