diff options
Diffstat (limited to 'design_food_rating_system.c')
-rw-r--r-- | design_food_rating_system.c | 165 |
1 files changed, 165 insertions, 0 deletions
diff --git a/design_food_rating_system.c b/design_food_rating_system.c new file mode 100644 index 0000000..46d51cc --- /dev/null +++ b/design_food_rating_system.c @@ -0,0 +1,165 @@ +// 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); +} |