aboutsummaryrefslogtreecommitdiff
path: root/design_food_rating_system.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-09-16 21:57:46 -0600
committerJack Sangdahl <[email protected]>2025-09-16 21:57:46 -0600
commitff1952c4a397b91945686c74e8e86e4dd4c4e7d2 (patch)
treecfdbca26f6787d801ac4742cfdb1ff85458189d4 /design_food_rating_system.c
parentb7cd5b2d6cb9a619e68bc518a369b5461cc72097 (diff)
downloadleetcode-ff1952c4a397b91945686c74e8e86e4dd4c4e7d2.tar.gz
leetcode-ff1952c4a397b91945686c74e8e86e4dd4c4e7d2.zip
2353. design a food rating system
Diffstat (limited to 'design_food_rating_system.c')
-rw-r--r--design_food_rating_system.c165
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);
+}