How do I efficiently handle updates to food ratings in this problem?

Efficiently handle updates by adjusting the rating in the hash map and updating the priority queue with the new rating for the relevant cuisine.

What is the key data structure for solving this problem?

The key data structure is a hash map to store food ratings and a priority queue to track the highest-rated foods by cuisine.

How should I handle ties in food ratings?

In case of a tie, return the food item that is lexicographically smaller, as specified in the problem statement.

Can I optimize the query for the highest-rated food?

Yes, by using a max-heap (priority queue), you can efficiently get the highest-rated food for any cuisine in O(log n) time.

What are the time and space complexities for this problem?

The time complexity for each operation is O(log n) due to heap operations, and the space complexity is O(n) for storing the data.

#2353

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

设计食物评分系统

设计一个支持下述操作的食物评分系统：修改系统中列出的某种食物的评分。返回系统中某一类烹饪方式下评分最高的食物。实现 FoodRatings 类： FoodRatings(String[] foods, String[] cuisines, int[] ratings) 初始化系统。食物由 f…

数组哈希表字符串设计堆（优先队列）

题目描述

设计一个支持下述操作的食物评分系统：

修改系统中列出的某种食物的评分。
返回系统中某一类烹饪方式下评分最高的食物。

实现 FoodRatings 类：

FoodRatings(String[] foods, String[] cuisines, int[] ratings) 初始化系统。食物由 foods、cuisines 和 ratings 描述，长度均为 n 。
- foods[i] 是第 i 种食物的名字。
- cuisines[i] 是第 i 种食物的烹饪方式。
- ratings[i] 是第 i 种食物的最初评分。
void changeRating(String food, int newRating) 修改名字为 food 的食物的评分。
String highestRated(String cuisine) 返回指定烹饪方式 cuisine 下评分最高的食物的名字。如果存在并列，返回 字典序较小 的名字。

注意，字符串 x 的字典序比字符串 y 更小的前提是：x 在字典中出现的位置在 y 之前，也就是说，要么 x 是 y 的前缀，或者在满足 x[i] != y[i] 的第一个位置 i 处，x[i] 在字母表中出现的位置在 y[i] 之前。

示例：

输入
["FoodRatings", "highestRated", "highestRated", "changeRating", "highestRated", "changeRating", "highestRated"]
[[["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], [9, 12, 8, 15, 14, 7]], ["korean"], ["japanese"], ["sushi", 16], ["japanese"], ["ramen", 16], ["japanese"]]
输出
[null, "kimchi", "ramen", null, "sushi", null, "ramen"]

解释
FoodRatings foodRatings = new FoodRatings(["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], [9, 12, 8, 15, 14, 7]);
foodRatings.highestRated("korean"); // 返回 "kimchi"
                                    // "kimchi" 是分数最高的韩式料理，评分为 9 。
foodRatings.highestRated("japanese"); // 返回 "ramen"
                                      // "ramen" 是分数最高的日式料理，评分为 14 。
foodRatings.changeRating("sushi", 16); // "sushi" 现在评分变更为 16 。
foodRatings.highestRated("japanese"); // 返回 "sushi"
                                      // "sushi" 是分数最高的日式料理，评分为 16 。
foodRatings.changeRating("ramen", 16); // "ramen" 现在评分变更为 16 。
foodRatings.highestRated("japanese"); // 返回 "ramen"
                                      // "sushi" 和 "ramen" 的评分都是 16 。
                                      // 但是，"ramen" 的字典序比 "sushi" 更小。

提示：

1 <= n <= 2 * 10⁴
n == foods.length == cuisines.length == ratings.length
1 <= foods[i].length, cuisines[i].length <= 10
foods[i]、cuisines[i] 由小写英文字母组成
1 <= ratings[i] <= 10⁸
foods 中的所有字符串 互不相同
在对 changeRating 的所有调用中，food 是系统中食物的名字。
在对 highestRated 的所有调用中，cuisine 是系统中 至少一种 食物的烹饪方式。
最多调用 changeRating 和 highestRated 总计 2 * 10⁴ 次

lightbulb

解题思路

方法一：哈希表 + 有序集合

我们可以使用哈希表 $\textit{d}$ 来存储每种烹饪方式下的食物，其中键是烹饪方式，值是一个有序集合，有序集合的每个元素是一个二元组 $(\textit{rating}, \textit{food})$ ，按照评分从高到低排序，如果评分相同，则按照食物名字的字典序从小到大排序。

我们还可以使用哈希表 $\textit{g}$ 来存储每种食物的评分和烹饪方式。即 $\textit{g}[\textit{food}] = (\textit{rating}, \textit{cuisine})$ 。

在构造函数中，我们遍历 $\textit{foods}$ 、 $\textit{cuisines}$ 和 $\textit{ratings}$ ，将每种食物的评分和烹饪方式存储到 $\textit{d}$ 和 $\textit{g}$ 中。

在 $\textit{changeRating}$ 函数中，我们首先获取食物 $\textit{food}$ 的原评分 $\textit{oldRating}$ 和烹饪方式 $\textit{cuisine}$ ，然后更新 $\textit{g}[\textit{food}]$ 的评分为 $\textit{newRating}$ ，并从 $\textit{d}[\textit{cuisine}]$ 中删除 $(\textit{oldRating}, \textit{food})$ ，并将 $(\textit{newRating}, \textit{food})$ 添加到 $\textit{d}[\textit{cuisine}]$ 中。

在 $\textit{highestRated}$ 函数中，我们直接返回 $\textit{d}[\textit{cuisine}]$ 的第一个元素的食物名字即可。

时间复杂度方面，构造函数的时间复杂度为 $O(n \log n)$ ，其中 $n$ 是食物的数量。其余操作的时间复杂度为 $O(\log n)$ 。空间复杂度为 $O(n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class FoodRatings:

    def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
        self.d = defaultdict(SortedList)
        self.g = {}
        for food, cuisine, rating in zip(foods, cuisines, ratings):
            self.d[cuisine].add((-rating, food))
            self.g[food] = (rating, cuisine)

    def changeRating(self, food: str, newRating: int) -> None:
        oldRating, cuisine = self.g[food]
        self.g[food] = (newRating, cuisine)
        self.d[cuisine].remove((-oldRating, food))
        self.d[cuisine].add((-newRating, food))

    def highestRated(self, cuisine: str) -> str:
        return self.d[cuisine][0][1]


# Your FoodRatings object will be instantiated and called as such:
# obj = FoodRatings(foods, cuisines, ratings)
# obj.changeRating(food,newRating)
# param_2 = obj.highestRated(cuisine)

speed

复杂度分析

指标	值
时间	O((n + m) \log n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Look for efficient management of both hash maps and priority queues.
question_mark
The ability to handle tie cases by lexicographical order is a key part of this solution.
question_mark
The candidate should optimize updates to the rating system to ensure the solution can handle large inputs.

warning

常见陷阱

外企场景

error
Failing to update the heap correctly after changing a food's rating.
error
Not handling lexicographical order correctly in case of ties when querying the highest rated food.
error
Using inefficient data structures that result in poor performance when handling large inputs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Extending the system to support multiple cuisines and more complex rating updates.
arrow_right_alt
Adding additional features such as filtering by food category or cuisine.
arrow_right_alt
Handling edge cases such as empty inputs or invalid cuisine names.

help

常见问题

外企场景

继续练习

#1912 设计电影租借系统 #2349 设计数字容器系统 #2336 无限集中的最小数字