# 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最高的食物並回傳。

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的資料型態如下：

type Rating = { food: string, rating: number };

並定義一個class來實現我們的heap，並實作以下功能；其中我們的heap，由於是complete binary tree故很適合用array來保存。

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的最後面，也就是樹中的最後一個子節點的位置，之後進行調整。

insert(node: Rating):void {
    this.heap.push(node);
    let idx = this.heap.length - 1;
    this.adjustUp(idx);
}

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。

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去做兩個變數的交換

[a, b] = [b, a] // Switch a and b

#### Update and adjust (down)
而`Update`則是用來修改某一個食物的rating，這個function一般不會出現在heap的資料結構中，一般的heap只會支援delete max(min)。

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。

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)$

getMax(): Rating {
    return this.heap[0];
}

最後將我們實作的Heap class拿到main function裡面作為存放rating的資料結構，就可以大大的提升效能

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最高的食物。