# 曉蓉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數影響什麼的缺點也得一併說明。