# 2353.Design a Food Rating System <span class="tag" data-diff="medium" />
{%hackmd RN5D4nggQRO8wzNqxuvlNw %}
## 題目
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.
Implement the `FoodRatings` class:
- `FoodRatings(String[] foods, String[] cuisines, int[] ratings)` Initializes the system. The food items are described by `foods`, `cuisines` and `ratings`, all of which have a length of `n`.
- `foods[i]` is the name of the $i^{th}$ food,
- `cuisines[i]` is the type of cuisine of the $i^{th}$ food, and
- `ratings[i]` is the initial rating of the $i^{th}$ food.
- `void changeRating(String food, int newRating)` Changes the rating of the food item with the name `food`.
- `String highestRated(String cuisine)` Returns the name of the food item that has the highest rating for the given type of `cuisine`. If there is a tie, return the item with the **lexicographically smaller** name.
Note that a string `x` is lexicographically smaller than string `y` if `x` comes before `y` in 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.
### Example 1:
#### Input
```
["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"]]
```
#### Output
```
[null, "kimchi", "ramen", null, "sushi", null, "ramen"]
```
#### Explanation
````
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"); // return "kimchi"
// "kimchi" is the highest rated korean food with a rating of 9.
foodRatings.highestRated("japanese"); // return "ramen"
// "ramen" is the highest rated japanese food with a rating of 14.
foodRatings.changeRating("sushi", 16); // "sushi" now has a rating of 16.
foodRatings.highestRated("japanese"); // return "sushi"
// "sushi" is the highest rated japanese food with a rating of 16.
foodRatings.changeRating("ramen", 16); // "ramen" now has a rating of 16.
foodRatings.highestRated("japanese"); // return "ramen"
// Both "sushi" and "ramen" have a rating of 16.
// However, "ramen" is lexicographically smaller than "sushi".
````
### Constraints:
- $1 \le n \le 2 \times 10^4$
- `n == foods.length == cuisines.length == ratings.length`
- `1 <= foods[i].length, cuisines[i].length <= 10`
- `foods[i]`, `cuisines[i]` consist of lowercase English letters.
- $1 \le ratings[i] \le 10^8$
- All the strings in `foods` are **distinct**.
- `food` will be the name of a food item in the system across all calls to `changeRating`.
- `cuisine` will be a type of cuisine of **at least one** food item in the system across all calls to `highestRated`.
- At most $2 \times 10^4$ calls **in total** will be made to `changeRating` and `highestRated`.
## 思路
最初的想法是建一個hash map來存每個食物的評分，由於他的食物會有不同的風味(cuisine)，並且題目的要求是要每個風味的最高分，所以在hash map的設計上，會將每個cuisine做各自的table來存放，另外為了在更新rating的時後能快速地找到該食物在哪一個cuisine table，所以額外maintain一張cuisineMap來記錄每個食物的風味。
最後在取得每種風味的最高評分時，則用`reduce`去找出table中rating最高的食物並回傳。
```typescript
class FoodRatings {
private tables: Record<string, Record<string, number>> = {};
private cuisineMap: Record<string, string> = {};
constructor(foods: string[], cuisines: string[], ratings: number[]) {
foods.forEach((f, i) => {
this.tables[cuisines[i]] = this.tables[cuisines[i]] ? this.tables[cuisines[i]] : {};
this.tables[cuisines[i]][f] = ratings[i];
this.cuisineMap[f] = cuisines[i];
});
}
changeRating(food: string, newRating: number): void {
this.tables[this.cuisineMap[food]][food] = newRating;
}
highestRated(cuisine: string): string {
if (!this.tables[cuisine]) return null;
const result = Object.entries(this.tables[cuisine]).reduce((max, curr) => {
if (curr[1] > max[1]) return curr;
if (curr[1] === max[1]) return max[0] < curr[0] ? max : curr;
return max;
}, ['', -1]);
return result[0];
}
}
```
<center><b>It works, but too slow.</b></center>
<br>
這的確是最簡單的做法，但如果這樣就這要解決了，就配不上他medium的難度了，果不其然，最後在其中一筆測資TLE了，仔細分析了一下上面的code，在 `changeRating` 的時候由於是直接修改hash map的值，所以理論上所需的時間複雜度是 $O(1)$ 所以最大的問題是出在 `highestRated` 的部分，在取得最高評分的食物時，需要loop過該風味底下的所有食物，才能找出最大值，所花費的時間複雜度是 $O(n)$，而且該結果並不會保存起來，等於每次call這個function的時候都需要重新找一遍，即便兩次function call之間rating並沒有改變。
### Heap
要解決這個問題，可以用 `heap` 這個資料結構來作為儲存rating的table
> heap 是一種完全二元樹(complete binary tree)，且當heap是max heap時，能保證父節點一定比左右子節點還要大
一般的heap在每次insert時，會調整tree以滿足上面的條件，而heap調整的作法是會一層一層往下(上)去進行比較與交換，故其時間複雜度與樹高有關所以是$O(logn)$。
:::info
由於binary tree每個node最多只會有2個children，所以第 $i$ 層最多會有 $2^i$ 個node，假設樹高為 $h$，全部有 $n$ 個node，則
$$(1+2^1+...+2^h)=2^{h+1}-1=n$$故$$h=log_2{(n+1)}-1=O(logn)$$
:::
我們先定義每個node的資料型態如下：
```typescript
type Rating = { food: string, rating: number };
```
並定義一個class來實現我們的heap，並實作以下功能；其中我們的heap，由於是complete binary tree故很適合用array來保存。
```typescript
class Heap {
private heap: Rating[] = [];
constructor(){}
private adjustDown(startIdx: number):void {...}
private adjustUp(startIdx: number):void {...}
insert(node: Rating):void {...}
update(food: string, rating: number): void {...}
getMax(): Rating {...}
}
```
以下依序來講每個method的實作：
#### Insert and adjust (up)
首先是`insert`，這個method會用來在初期建構Heap，他會接收一個node並插入到array的最後面，也就是樹中的最後一個子節點的位置，之後進行調整。
```typescript
insert(node: Rating):void {
this.heap.push(node);
let idx = this.heap.length - 1;
this.adjustUp(idx);
}
```
```graphviz
graph hierarchy {
node [color=black,shape=circle]
edge [color=black]
root -- n1;
root -- n2;
n1 -- n3;
n1 -- n4;
n2 -- n5;
n6[style=dashed]
n2 -- n6[style=dashed];
}
```
當呼叫`adjustUp`時，會從給定的node index`idx`去往上調整max heap，調整的方法為：檢查parent，若parent 小於 current node，則switch兩個node，而後再一直與parent進行比較，直到他小於parent或是已經到達root。
以上圖為例，insert n6之後，先與n2進行比較，若$n_6>n_2$則交換兩者，並再跟root比較；若否則停下來。交換後並不需要再跟n5比較，因為n2已經保證會比n5大了，若n6大於n2則必定會大於n5。
```typescript
private adjustUp(startIdx: number) {
let idx = startIdx;
while (idx > 0) {
const jdx = Math.floor((idx - 1) / 2);
if ( this.heap[jdx].rating > this.heap[idx].rating) break;
if (
this.heap[jdx].rating === this.heap[idx].rating
&& this.heap[jdx].food < this.heap[idx].food
) break;
[this.heap[idx] ,this.heap[jdx]] = [this.heap[jdx], this.heap[idx]];
idx = jdx;
}
}
```
:::info
在0-index的array中，第 $i$ 個node的parent其index是 $\lfloor{{i - 1}\over 2}\rfloor$
:::
在上述程式碼中，要注意題目的條件，若兩者rating相同，則name的文字順序較小者為大，另外在javascript中可以很簡單的用array decompose去做兩個變數的交換
```javascript
[a, b] = [b, a] // Switch a and b
```
#### Update and adjust (down)
而`Update`則是用來修改某一個食物的rating，這個function一般不會出現在heap的資料結構中，一般的heap只會支援delete max(min)。
```typescript
update(food: string, rating: number): void {
const idx = this.heap.findIndex((x) => x.food === food);
if (idx < 0) return;
this.heap[idx].rating = rating;
this.adjustUp(idx);
this.adjustDown(idx);
}
```
在update的時候，首先loop過heap找到要被更新的node index並更新該node，之後調整tree，`adjustUp`前面已經提過了，這裡就不再贅述，而另一個調整程式`adjustDown`則是從目標node往下調整，看左右兩邊的child是否比自身大，若是，則與較大者交換，直到2個children node都比自身小或是已經到了leaf node。
```typescript=
private adjustDown(startIdx: number) {
const currentNode:Rating = this.heap[startIdx];
let childIdx = startIdx * 2 + 1;
let done = false;
while (childIdx < this.heap.length && !done) {
if (this.heap[childIdx + 1]) {
if (this.heap[childIdx + 1].rating > this.heap[childIdx].rating) {
childIdx += 1;
} else if (
this.heap[childIdx + 1].rating === this.heap[childIdx].rating
&& this.heap[childIdx + 1].food < this.heap[childIdx].food
) {
childIdx += 1;
}
}
if (currentNode.rating > this.heap[childIdx].rating) {
done = true;
} else if (
currentNode.rating === this.heap[childIdx].rating
&& currentNode.food < this.heap[childIdx].food
) {
done = true;
} else {
[this.heap[Math.floor((childIdx - 1) / 2)], this.heap[childIdx]]
= [this.heap[childIdx], this.heap[Math.floor((childIdx - 1) / 2)]]
childIdx = childIdx * 2 + 1;
}
}
}
```
:::info
在0-index的array中，第 $i$ 個node的left child其index是 $2i + 1$，而right child的index是 $2(i+1)$
:::
在第3行，我們先選取left child，接著進入迴圈，檢查是否有children且比較還沒結束(`!done`)；在第7 ~ 16行，會檢查是否有right child且若right child比left child大的話，則選定其為比較的對象，接者開始進行比較；若此時current node的值已經比兩個children中最大者大了，則將done設為true來跳出迴圈，否則令其跟child交換，並將childIdx的指標指向互換後的left child。
雖然`update`看起來call了兩個調整程式，但其實只有一個會真的執行，因為update後，該node如果比parent大，就一定會比其children還要大，則在`adjustDone`的第一個回圈內就會被終止了；反之，若比children小，就會比parent還小，則`adjustUp`也不會執行。
#### GetMax
最後是`getMax`這個method，這是用來找出heap中最大值的function，由於heap的特性(parent一定大於child)，且在每次insert及update的時候都會調整以滿足該特性，故這個method非常簡單只要回傳`heap[0]`即可，時間複雜度是 $O(1)$
```typescript
getMax(): Rating {
return this.heap[0];
}
```
最後將我們實作的Heap class拿到main function裡面作為存放rating的資料結構，就可以大大的提升效能
```typescript
class FoodRatings {
private table: Record<string, Heap> = {};
private cuisineMap: Record<string, string> = {};
constructor(foods: string[], cuisines: string[], ratings: number[]) {
foods.forEach((f, i) => {
const rating: Rating = { food: f, rating: ratings[i] };
if (!this.table[cuisines[i]]) this.table[cuisines[i]] = new Heap();
this.table[cuisines[i]].insert(rating);
this.cuisineMap[f] = cuisines[i];
});
}
changeRating(food: string, newRating: number): void {
this.table[this.cuisineMap[food]].update(food, newRating);
}
highestRated(cuisine: string): string {
return this.table[cuisine].getMax().food;
}
}
```
在`table`這個變數中，我們一樣對每個cuisine建立一個Heap來存放rating，construct的時候，則呼叫`insert`來建構heap，`changeRating`時用Heap內建的update function去更新heap，最後在`highestRated`的時候用`getMax`來取得rating最高的食物。
Sign in with Wallet
Connect another wallet