HW2 leetcode 0001. Two Sum

>貢獻者: 半條悟-satoru [影片](https://youtu.be/uKXPCErW4IA) # HW2 leetcode 0001. Two Sum ##### ${interviewer}$(改進：包裝題目) 你好，我是今天主持這場面試的人，文遠，那我們就開始面試。現在你正在挑戰一個遊戲，桌上有許多帶有價值的物品，你需要挑出恰巧兩個物品，用以通關遊戲。通關遊戲的規則是，這兩個物件的價值需要合計等於，一個神秘數字magic。那請你設計一個程式，給予一個儲存所有物品價值的vector，快速找出一個能通關的組合吧！ ##### interviewee 也就是說，比如我有一個vector內含[2,5,7,16,21,10]，如我螢幕上所示，且magic = 12，那麼預期得到的結果是[1,2]嗎？ ##### ${interviewer}$ 是的沒錯。 ##### interviewee 再比如說，我有一個vector內含[2,7,7,8,10,19]，如我螢幕上所示，且magic = 14，那麼預期得到的結果是[1,2]嗎？ ##### ${interviewer}$ 是的，這也正確。 ##### interviewee 桌上有許多物品，那麼請問我可以假設，肯定有至少一個方法可以通關遊戲，而且我也只需要找出一個，對吧？ ##### ${interviewer}$ 可以，你可以假設至少一組，找出一組即可。 ##### interviewee(改進：說明加上註解) 感謝，那我首先想到的方法是，以兩個for迴圈，遍歷這個vector，外圈for固定住第1個數，內圈for尋找index在第1個數之後的所有元素，並嘗試找出與他相加等於target的數。在找到配對的時候記錄下兩個for回圈當下的index，立刻return。 (大略說完後，一邊寫扣一邊配合註解並解說) ```cpp= #include <iostream> #include <string> #include <map> using namespace std; class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> ans; int n = nums.size(); for(int i = 0;i < n-1;i++){ for(int j = i+1 ; j < n ; j++ ){ if(nums[i]+nums[j] == target){ ans.push_back(i); ans.push_back(j); return ans; } } } return ans; } }; ``` ##### interviewee 我完成了，請問有什麼問題嗎？ ##### ${interviewer}$ 感覺相當不錯，那該怎麼評估這個會花上多久才能找出通關組合呢？ ##### interviewee 第一個迴圈從第0個到n-1，而第二個迴圈會做n-1次、n-2次、n-3次......所以這個方法的時間複雜度為$\mathcal{O}(n^2)$ ##### ${interviewer}$ 那我們是否有方法節省更多時間，讓你不需要檢查這麼多次呢？ ##### interviewee 或許可以用一個map並遍歷一次vector。每次看到元素的當下先以「target減當前元素值」，作為key來搜尋map是否已出現過與當前元素值可以相加乘target的數。如果有找到，則將map的index以及當前的index作為結果return，因為可以假設只有一組解。如果未找到，將當前值作為key、當前的index作為value新增到map中。 (大略說完後，一邊寫扣一邊配合註解並解說) ```cpp= #include <iostream> #include <string> #include <map> using namespace std; class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { map<int, int>::iterator ptr; // numlist前者是值作為key，後者是在nums中的index map<int,int> numlist; vector<int> ans; for(int i = 0;i < nums.size();i++){ //先搜尋target減當前的值 ptr = numlist.find(target-nums[i]); //代表找到了 if(ptr != numlist.end()){ ans.push_back(ptr->second); ans.push_back(i); return ans; } //沒找到則新增元素 numlist[nums[i]] = i; } return ans; } }; ``` ##### interviewee 我完成了，請問有什麼問題嗎？ ##### ${interviewer}$ 看起來也不錯，那這個方法為何節省了時間？ ##### interviewee 因為用map的方式，這使得vector內的值只被掃過一次即可明白解出現在何處，不必跑2次迴圈，時間複雜度變成了$\mathcal{O}(n)$。 ##### ${interviewer}$(改進：探討map) 那麼，既然使用到了map，map那內部是用什麼實作方法呢？ ##### interviewee 是紅黑樹，最有利的特徵是，資料用有序的方式儲存。 ##### ${interviewer}$ 在這題當中，順序似乎沒有什麼意義，我們能捨棄這點做出改善嗎？ ##### interviewer 我想到了，unordered_map在只需查找的情況下表現大多更加快速，因為用的是雜湊表。使用上則只需要將map換成unordered_map即可。 ```cpp= #include <iostream> #include <string> #include <unordered_map> using namespace std; class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int>::iterator ptr; // numlist前者是值作為key，後者是在nums中的index unordered_map<int,int> numlist; vector<int> ans; for(int i = 0;i < nums.size();i++){ //先搜尋target減當前的值 ptr = numlist.find(target-nums[i]); //代表找到了 if(ptr != numlist.end()){ ans.push_back(ptr->second); ans.push_back(i); return ans; } //沒找到則新增元素 numlist[nums[i]] = i; } return ans; } }; ``` ##### interviewee 我完成了，請問有什麼問題嗎？ ##### ${interviewer}$ 看起來不錯，沒有問題了，今天的面試就到此為止，感謝你的配合。 ##### interviewee 謝謝主持人，再見。 # 許願+自我檢討他人的檢評加上這次影片我學到以下重點。 ### 關於 interviewer * 題目須包裝 * 聲音清晰與否真的是因人而異 * 多引導討論程式碼的改進內容，問得深入點，考驗面試的人是否真的有料 ### 關於 interviewee * 要用自己不熟的環境，不能仰賴提示幫助 * 口條真的很重要，如何清楚闡述自己所想 * 註解！註解！註解！要寫註解阿RRRRRRRRRRRRR * 英文真的很爛，爛到大家都看的出來 * (許願)假設沒發現自己的code錯誤怎辦，被點出來怎辦？這種沒有實際跑程式碼就沒看出來的錯怎辦？或者寫錯了要更正怎麼辦？(這次拍的影片我自己有特別留嚴重跟輕微的錯誤，給老師舉例說明用) * vector初始化不是那樣寫 * main 裡面 cout << 印出的東西錯了 # 評價他人(第二次作業) :::spoiler ## 01 布萊德 bread ### 關於 interviewer - [ ] 優點 * 有將題目的敘述寫出來很好，傳達題目更加清晰。 - [ ] 可以改進的地方 * 可以在包裝或是改動一下題目，two sum題名也可以不用寫，否則容易便宜到刷題者。 * 聲音過小，在面試上會導致溝通不良。 ### 關於 interviewee - [ ] 優點 * 在撰寫的當下有配合說明，非常棒 - [ ] 可以改進的地方 * 回頭說明的時候建議以反白、選取的方式使人更加清楚在說明什麼部分。 * 可以更加具體的說為什麼改進了時間複雜度，比如資料從傳遞幾次降為幾次。 * 有想法之後建議化為註解，幫助自己掌握好接下來要實作的架構，也便於讓面試主持人知道。 * 最後沒有測試。reacTo ## 02 東尼 Tonny ### 關於 interviewer - [ ] 優點 * 以文件的方式敘述題目，傳達更清楚，很好。 * 有將題目包裝過，包裝後能有效避免刷題怪。 - [ ] 可以改進的地方 * 「同學你好」，這稱呼似乎不太對。 * 「讓我來講解一下這題的目標」感覺就可以了，用到「面對」似乎太過嚴肅。 * 不用整個畫面都糊掉。 ### 關於 interviewee - [ ] 優點 * 有將想法化成文字註解。 * 寫的時候也有一邊說明。 * 有測試階段很棒。 - [ ] 可以改進的地方 * 測試階段說明i j 在陣列哪個元素的時候，可以用不同的指示符號。 * 不用整個畫面都糊掉。 ## 03 呆呆獸 Slowpoke ### interviewer - [ ] 優點 * 舉出實作上可以應用的地方很棒。 * 向interviewee提出問題，交流是否有地方需要改進，互動良好。 - [ ] 可改進之處 * 有時候會有一小段字突然糊掉、聽不清楚。 * 第二題不需要特別說題目名稱關鍵字，這樣刷題者馬上就手癢想寫了XD。 ### interviewee - [ ] 優點 * 對答橋段良好，REACTO完整。 - [ ] 可改進之處 * 一邊寫一邊卻沒有說明，建議在撰寫的時候配合說明，可以清楚讓面試主持人知道在幹嘛。 * 承上，配合在各個程式片段下註解，更可以有效傳達自己的想法。 ## 04 沙西米 Sashimi ### 關於interviewer - [ ] 優點 * 不只以口頭說明的方式，以文件的方式給予題目。 * 有以互動的方式引導改進程式碼。 - [ ] 可改進的地方 * 題目建議變形、包裝過更優，避免刷題目者。 ### 關於interviewee - [ ] 優點 * 提出「問題」順便舉例，並打出字說明自己的例子。 * 最後有做到驗證測試部分 - [ ] 可改進的地方 * 提出程式碼想法、撰寫有口頭說明，卻沒有配合註解。 ## 05 郝主意 Goodidea ### Interviewer: - [ ] 優點 * 題目說明清楚，不只以口頭闡述，也有以文件輔助。 - [ ] 可改進之處 * 題目給法可以不要關鍵字題目名。 * 題目敘述也不要直接給原題，可以換成應用、延伸或者套上情境。 * * 最後結尾「大概了解你程式碼的想法了」，之後卻結束了，給人一種尚未了解透徹的感覺，應該可以換個更堅定的語氣，並結束面試。 ### Interviewee : - [ ] 優點 * 舉例有時候是以反白的方式，很棒。 * 有確認例子、有確認作法後得到Interviewer回應才開始。 - [ ] 可改進之處 * 應有測試以滿足 REACTO ::: # 評價他人(第四次作業) :::spoiler ## 01 曉榕-Dawn ### 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數影響什麼的缺點也得一併說明。 ## 02 月前龍馬-lonmu ### 關於 interviewer - [ ] 優點 - 問題包裝良好。 ### 關於 interviewee - [ ] 優點 - [03:41](https://youtu.be/Ire86ptjVtI?si=QGfTpsa5reqbMr8d&t=221)為止，REACTO的REA做得很完整，有適當舉例幫助了解，也有向主持人確認做法才開始實作。 - [ ] 可改進的地方 - [07:03](https://youtu.be/Ire86ptjVtI?si=wU7cpvaCmgOBvUqA&t=423)雖然你用反白標示出你在講什麼部分很好，但又配上滑鼠游標畫圈的動作，就扣分回來了，老師在上課有提到，應避免如此畫圈行為。 - 整個coding下來，雖然在文件最上面已經用註解表示全體流程，但建議在coding時還是要把這個區塊在做什麼，把註解寫在該區塊，會清楚點。 ::: ## 第四次作業-他人評論-01 ### 關於 interviewer - [ ] 優點 - 語速適中，咬字清楚 - [26:24](https://youtu.be/uKXPCErW4IA?feature=shared&t=1584)：跟interviewee討論可以優化的過程互動不錯 - [ ] 可改進的地方 - 前期跟interviewee的對話方式不太像老師希望的「討論」，比較像...質詢（？ ### 關於 interviewee - [ ] 優點 - 寫程式過程中講解得很詳細，還有用註解輔助說明 - [ ] 可改進的地方 - [5:32](https://youtu.be/uKXPCErW4IA?feature=shared&t=332)：「吃進去」的參數有點口語 - 整個過程說明得太詳細了，以正常的面試流程來說應該會讓interviewer沒辦法問到後面的問題，可以試著不用每個步驟都說明的很仔細，只講關鍵步驟即可 - [24:11](https://youtu.be/uKXPCErW4IA?feature=shared&t=1451)：在說明第二個方法的時候，可以把map裡面的key-value變化打出來，比起用講的會更好理解 ###### tags:資訊科技產業專案設計2023