// 2353. Design a Food Rating System #include "leetcode.h" /* * design a food rating system that can do the following: modify the rating of a * food item listed in the system, return the highest rated food item for a type * of cuisine in the system. note that a string 'x' is lexicographically smaller * than string 'y' if 'x' comes before 'y' in the dictionary order, that is, * either 'x' is a prefix of 'y', or if 'i' is the first position such that * 'x[i] != y[i]', then 'x[i]' comes before 'y[i]' in alphabetic order. */ struct cuisine_hash; struct food_hash { char *food; struct cuisine_hash *cuisine; int rating; int idx; UT_hash_handle hh; }; struct cuisine_hash { char *cuisine; struct food_hash **foods; int foods_size; UT_hash_handle hh; }; typedef struct { struct food_hash *foods; struct cuisine_hash *cuisines; struct food_hash *food_entries; } FoodRatings; static char *str_clone(const char *s) { int n = strlen(s); char *const res = (char *const)malloc((n + 1) * sizeof(char)); memcpy(res, s, n + 1); return res; } static bool is_food_greater(struct food_hash *lhs, struct food_hash *rhs) { return lhs->rating > rhs->rating || (lhs->rating == rhs->rating && 0 > strcmp(lhs->food, rhs->food)); } FoodRatings *foodRatingsCreate(char **foods, int foodsSize, char **cuisines, int cuisinesSize, int *ratings, int ratingsSize) { FoodRatings *res = (FoodRatings *)malloc(sizeof(FoodRatings)); memset(res, 0, sizeof(FoodRatings)); res->food_entries = (struct food_hash *)malloc(foodsSize * sizeof(struct food_hash)); struct cuisine_hash *entry; for (int i = 0; i < foodsSize; i++) { HASH_FIND_STR(res->cuisines, cuisines[i], entry); if (!entry) { entry = (struct cuisine_hash *)malloc(sizeof(struct cuisine_hash)); entry->cuisine = str_clone(cuisines[i]); entry->foods = NULL; entry->foods_size = 0; HASH_ADD_KEYPTR(hh, res->cuisines, entry->cuisine, strlen(entry->cuisine), entry); } ++entry->foods_size; struct food_hash *food_entry = &res->food_entries[i]; food_entry->food = str_clone(foods[i]); food_entry->cuisine = entry; food_entry->rating = ratings[i]; } struct cuisine_hash *tmp; HASH_ITER(hh, res->cuisines, entry, tmp) { entry->foods = (struct food_hash **)malloc(entry->foods_size * sizeof(struct food_hash *)); entry->foods_size = 0; } for (int i = 0; i < foodsSize; ++i) { struct food_hash *food_entry = &res->food_entries[i]; entry = food_entry->cuisine; int idx = entry->foods_size++; while (idx && is_food_greater(food_entry, entry->foods[(idx - 1) / 2])) { entry->foods[idx] = entry->foods[(idx - 1) / 2]; entry->foods[idx]->idx = idx; idx = (idx - 1) / 2; } entry->foods[idx] = food_entry; entry->foods[idx]->idx = idx; HASH_ADD_KEYPTR(hh, res->foods, food_entry->food, strlen(food_entry->food), food_entry); } return res; } void foodRatingsChangeRating(FoodRatings *obj, char *food, int newRating) { struct food_hash *food_entry; HASH_FIND_STR(obj->foods, food, food_entry); struct cuisine_hash *const cuisine = food_entry->cuisine; int idx = food_entry->idx; const int prev = food_entry->rating; if (newRating > prev) { while (idx && is_food_greater(food_entry, cuisine->foods[(idx - 1) / 2])) { cuisine->foods[idx] = cuisine->foods[(idx - 1) / 2]; cuisine->foods[idx]->idx = idx; idx = (idx - 1) / 2; } cuisine->foods[idx] = food_entry; cuisine->foods[idx]->idx = idx; } else if (newRating < prev) { for (;;) { int to_move = idx, left = idx * 2 + 1, right = idx * 2 + 2; if (left < cuisine->foods_size && is_food_greater(cuisine->foods[left], cuisine->foods[to_move])) to_move = left; if (right < cuisine->foods_size && is_food_greater(cuisine->foods[right], cuisine->foods[to_move])) to_move = right; if (to_move == idx) break; cuisine->foods[idx] = cuisine->foods[to_move]; cuisine->foods[idx]->idx = idx; cuisine->foods[to_move] = food_entry; idx = to_move; } cuisine->foods[idx]->idx = idx; } } char *foodRatingsHighestRated(FoodRatings *obj, char *cuisine) { struct cuisine_hash *entry; HASH_FIND_STR(obj->cuisines, cuisine, entry); return entry->foods[0]->food; } void foodRatingsFree(FoodRatings *obj) { HASH_CLEAR(hh, obj->foods); struct cuisine_hash *del, *tmp; HASH_ITER(hh, obj->cuisines, del, tmp) { for (int i = 0; i < del->foods_size; ++i) free(del->foods[i]->food); free(del->foods); HASH_DEL(obj->cuisines, del); free(del->cuisine); free(del); } free(obj->food_entries); free(obj); } int main() { char *foods[] = {"kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"}; char *cuisines[] = {"korean", "japanese", "japanese", "greek", "japanese", "korean"}; int ratings[] = {9, 12, 8, 15, 14, 7}; FoodRatings *obj = foodRatingsCreate((char **)foods, ARRAY_SIZE(foods), (char **)cuisines, ARRAY_SIZE(cuisines), ratings, ARRAY_SIZE(ratings)); printf("%s\n", foodRatingsHighestRated(obj, "korean")); // expect: kimchi printf("%s\n", foodRatingsHighestRated(obj, "japanese")); // expect: ramen foodRatingsChangeRating(obj, "sushi", 16); printf("%s\n", foodRatingsHighestRated(obj, "japanese")); // expect: sushi foodRatingsChangeRating(obj, "ramen", 16); printf("%s\n", foodRatingsHighestRated(obj, "japanese")); // expect: ramen foodRatingsFree(obj); }