---
# System prepended metadata

title: 曉蓉2023-homework2

---

# 曉蓉2023-homework2
[TOC]

## 第一次作業中學到
- 多注意 REACTO framwork
    >Repeat: 重複提問，確認自己理解原本的要求
    **Examples: 針對題目條件，舉出符合的案例，不限於特例**
    **Approach: 說明自己打算採用的方案**
    Code: 撰寫程式
    Test: 若不能實際測試，那說明驗證程式的方案
- 代名詞要示意一下
- 面試者請自行提出時間空間複雜度分析
- tmp都可以念temp了

## 506 Relative Ranks
>[video](https://youtu.be/4fWx1P9DTjY)
>[題目網址](https://leetcode.com/problems/relative-ranks/)
**Interviewer**： 你好，曉蓉，歡迎來參加面試。 我們來解決一個關於程式耗能排名的問題。 假設我們有一台計算機，上面運行了多個不同的程式，每個程式消耗不同的能源。 這些程式在電腦上同時運行，我們希望為它們排名，以確定哪個程式消耗的能源最多，哪個程式消耗的最少。

規則如下：

1. 消耗能源最多的程式排名第一，並輸出標籤"Top"。
2. 消耗能源第二多的程式排名第二，並輸出標籤"Runner-Up"。
3. 消耗能源第三多的程式排名第三，並輸出標籤"Third"。
4. 剩下的程式，排名依它們的能源消耗依序遞增。

你的任務是寫一個程式，輸入是每個程式消耗的能源，輸出是每個程式的排名。 不要使用傳統的排名方式，按照上述規則產生排名。你需要寫一個C++函數 findRelativeRanks，它接收一個整數陣列 energy，表示程式消耗的能源。函數需要傳回一個字串向量，表示每個程式消耗的能源排名。

**曉蓉（Interviewee）**：我明白了，我們要根據得分來計算每個程式消耗的能源排名。 我想先確認幾件事。

**曉蓉（Interviewee）**： 需要寫一個函數 findRelativeRanks，它接收一個整數數組 energy，表示程式消耗能源，假設為 energy = [5,4,3,2,1]。 函數需要傳回一個字串向量，表示每個程式消耗能源排名。 排名規則是：第一位得標籤"Top"，第二位得標籤"Runner-Up"，第三位得標籤"Third"，然後從第四位開始，排名就是他們的排序。將分數進行排序，得出每位程式的排序依序為[1st, 2nd, 3rd, 4th, 5th]，所以輸出為["Top","Runner-Up","Third","4","5"]，對嗎?

**Interviewer**： 是的，曉蓉，你理解得很正確。 那麼，你有什麼想法如何解決這個問題呢？

**曉蓉（Interviewee）**： 我的想法是創建一個map的陣列，(耗能，順位)，來儲存原本的排序。接著對於原本的陣列做升冪排序，使用vector的sort搭配less<int\>()，再創建一個文字vector，對應的填入再該順位的程式得到的排序。

這個做法平均的時間複雜度為 O(nlogn)，n為輸入的程式數量，空間上需求比四個size為n的vector還大。

**Interviewer**： 很好，聽起來可行，你會怎麼優化他?

**曉蓉（Interviewee）**： 我認為可以在分配標籤和排序時避免多次訪問 scoreToIndex，可以直接在經過排序後的原本的energy位置上，直接給予排序，這樣可以減少一些額外的存取的耗能。

**Interviewer**： 非常正確，你的分析和優化建議都很好。 但你這個優化只會減少訪問 scoreToIndex，我想要你做時間複雜度上的優化。

**曉蓉（Interviewee）**： 在這個問題中，由於需要根據分數排名，並且分數是唯一的，所以快速排序（O(nlogn)）似乎是一個合理的時間複雜度。 不過，如果要進一步降低時間複雜度，可以考慮使用==線性時間複雜度==的方法。我打算使用線性時間複雜度的桶排序（Bucket Sort）

**曉蓉（Interviewee）**：  首先，遍歷分數數組，找出最高分和最低分，確定分數範圍。建立一個桶（Bucket）數組，桶的數量等於分數範圍的大小。將每個程式的耗能數值放入對應的桶中，桶的索引對應耗能數值。從最高分開始，遍歷桶數組，依序為程式分配標籤和名次。這種方法的==時間複雜度是O(n)==，因為在確定了耗能數值範圍後，分配到桶中和遍歷桶都是線性時間複雜度的操作。
```=
energy = [10,3,8,9,4]
max = 10, min = 3
range = 10-3+1 = 8
以range創建二維 Bucket: Bucket = [[] [] [] [] [] [] [] []]
從頭遍歷一次engry，push index進去bucket，10-min=7，所以第七個bucket的值為10在energy的index(=0)。
Bucket = [[] [] [] [] [] [] [] [0]]
3-min=0，所以第0個bucket的值為3在energy的index(=1)。
Bucket = [[1] [] [] [] [] [] [] [0]]
已次類推得到: Bucket = [[1] [4] [] [] [] [2] [3] [0]]

在從尾端給予名次，因為是耗能越大，排序越靠前。
result[0] = "Top"
result[3] = "Runner-Up"
result[2] = "Third"
result[4] = "4"
result[1] = "5"
```
**Interviewer**： 聽起來可行，請寫出程式碼。

```cpp=
vector<string> findRelativeRanks(vector<int>& energy) {
    int maxEnergy = *max_element(energy.begin(), energy.end()); //找最大
    int minEnergy = *min_element(energy.begin(), energy.end()); //找最小

    int range = maxEnergy - minEnergy + 1;

    vector<string> result(energy.size()); //儲存名次的vector
    vector<vector<int>> buckets(range);  //二維vector

    for (int i = 0; i < energy.size(); ++i) {
        buckets[energy[i] - minEnergy].push_back(i); 
    }

    int rank = 1;
    for (int i = range - 1; i >= 0; --i) {
        if (!buckets[i].empty()) {
            for (int j = 0; j < buckets[i].size(); ++j) {
                if (rank == 1) {
                    result[buckets[i][j]] = "Top";
                } else if (rank == 2) {
                    result[buckets[i][j]] = "Runner-Up";
                } else if (rank == 3) {
                    result[buckets[i][j]] = "Third";
                } else {
                    result[buckets[i][j]] = to_string(rank);
                    //把數字轉成字串
                }
                rank++;
            }
        }
    }
    return result;
}

```

**曉蓉（Interviewee）**： 這個版本的程式碼具有線性時間複雜度O(n)，但需要一些額外的空間來儲存桶數組。 然而，由於耗能數值是整數，桶的數量通常不會太多，因此空間開銷是有限的。


**Interviewer**： 很棒，優化做得很好，期待下次與你見面。

## 他評-01
### interviewer
- 待改進的地方
    - [4:05](https://youtu.be/4fWx1P9DTjY?si=IgYDSmbe0jLxMaIh&t=245) 如果 interviewer 就是想問有沒有更好的排序方式，可以直接提問:"請問你能不能想到時間複雜度比 O(n log n) 更少的排序方式?" 會更明確。
### interviewee
- 優點
    - [5:18](https://youtu.be/4fWx1P9DTjY?si=nzHAgOpoXxrb_Bmn&t=318) 講解 bucket sort 的部分清楚、流暢
- 待改進的地方
    - [5:10](https://youtu.be/4fWx1P9DTjY?si=avYcklpJFWY0wpeu&t=310) bucket sort 的時間複雜度只提到是線性，應針對 bucket 數量、程序數量、worst case等進行更多討論

## 他評-02
### interviewer
- 待改進的地方
    - [4:04](https://youtu.be/4fWx1P9DTjY?t=245) : interviewer 要求優化時應該對現有框架下有甚麼問題去做引導，比方說 interviewer 明顯是想要 interviewee 去改變 sorting 的部分，如果有做引導則可以減去時間。

### interviewee
- 優點
    - [15:43](https://youtu.be/4fWx1P9DTjY?t=943) : Test 的部分很清楚
- 待改進的地方
    - [5:18](https://youtu.be/4fWx1P9DTjY?t=318) : interviewee 應該說明為何使用 bucket sort 時間複雜度會減少，與他所帶來的風險，比方說 worst case 很糟糕之類的，主因是如果 bucket sort 真的都優過於常見的 quick sort 等等，應該會更常看到它。
    - [11:17](https://youtu.be/4fWx1P9DTjY?t=677) : 鏡頭擋住畫面，應當將視訊鏡頭置於不會擋到 code 的地方。

## 他評-03
### interviewer
- 待改進的地方
    - [4:05](https://youtu.be/4fWx1P9DTjY?t=245) : 有點單薄，可以明確表示想要哪方面的優化，同時給予被面試的人一點引導跟思考。

### interviewee
- 優點
    - [19:29](https://youtu.be/4fWx1P9DTjY?si=AwaVefq5rGJiZjGn&t=1169)為止，整段test實際推演bucket情形，使得講解很清楚。
    - 寫code的時候也有配合註解，code到哪，解說就到哪，很棒。
- 待改進的地方
    - [07:19](https://youtu.be/4fWx1P9DTjY?si=ETYYf4Kb_S7jvNj3&t=439)為止，如果可以再多推數個步驟，實際將優點，對比前面一個方法的改進之處提出會更完善。當然，會出現什麼樣的缺點，如何訂定bucket數，bucket數影響什麼的缺點也得一併說明。