貢獻者: 輝瑞-BNT
video
REACTO
- Repeat problem -> 順便理解題目
- Examples -> 解釋範例測資
- Approach -> 講大概的解法
- Coding -> 開始解題
- Testing -> 將測資代入上一步驟的實做
- Optimize -> 討論優化可能
Two Sum
題目要求: 給定一個陣列和 target
,要找出哪兩個 element 的總和可以剛好為 target
EX1:
Solution
思路: 因為題目說一定會有解,所以我們只需要迭代 nums
,檢查是否經過元素 target
- nums
Complexity
因為 hash 操作為 ,而需要遍歷長度為 n 的陣列,所以時間複雜度為
缺失:
- 忘記在寫程式前,於 code block 內用稍後將實做的方法來試跑測資 (方便面試官理解我方法的運作流程)
延伸題 3Sum
Problem link
Valid Parentheses
題目要求: 檢查由 ('(', '{', '[', ')', '}', ']') 組成的字串是否合法,除了要成對,順序也要對
EX1:
Solution
思路: 用 stack 來紀錄成對的狀況
Complexity
因為 stack 的 pop 和 push 都是 ,所以本題的時間複雜度為
Medium: Top K Frequent Elements
題目要求: 在陣列 nums
中找出最頻繁出現的 k 的元素
EX1:
Solution
思路: 透過 hash map 紀錄不同 elements 出現的頻率,接著透過 priority queue 來排序,並取出 top K 的 node。
Complexity
- time complexity of insertion:
- iterate at most N times
所以解法的時間複雜度為
reference: priority queue, customize pq comparator
更好的方法 (bucket sort)
第三次作業-他評
- 建議使用 Google Docs,減少工具輔助以應對各式情況
- 說明解法前應向 interviewer 確認題目內容
- 編寫前應增加範例說明及演示
- 編寫程式碼時都有使用打字來輔助說明
第三次作業-他評2
- 6:48 這裡提到說延伸 2-SUM 解法的複雜度會是 ,並解釋不使用這方法的原因是因為無法在解決答案重複的問題。這邊應該可以解釋得更清楚些,因為如果將每一組答案正規化後置入 hashset 就可以解決這問題。真正的問題是在於 2-SUM 的 解法是建立於該問題只須回傳一組解的前提下。若改為回傳所有解,其複雜度為 ,所以延伸的 3-SUM 解會是 。
第三次作業-他評3
interviewer
優點
- 0:06 實作第一題時,沒有直接說明題目名稱,而是講解完題目要求後舉例說明,方便interviewee快速進入狀況
- 23:06 coding完成後和interviewee討論程式碼,真的有在互動
interviewee
優點
缺點
- 23:28 花了將近一分鐘在驗證每段程式的時間複雜度,未來時間可能要稍微分配一下
第三次作業-他評4
面試過程檢討
總體
- 人物分類薄弱,比較難看出Interviewer跟Interviewee的差別,且口吻上也比較無差異性
- 口語表達較為薄弱,聽起來有點缺乏自信
- 依照課堂需求應該使用如Google document來增加撰寫程式碼的困難度。
- Interviwer 跟 Interviewee 比較缺乏攻防與問答。
- 是不是應該要有三題才對,但是只有兩題。
Interviewer
- 題目講解快速,沒有浪費過多時間舉例而浪費面試時間。
- 直接說『你的答案看起來是對』不太精確,且像是在敷衍。
- 講到延伸問題 3Sum 的時候,可以說仔細一點input 資料的型態,例如:有沒有重複值?;是否有排序過?;資料的大小等等。
Interviewee
- 解題概念清楚,能很快讓人知道意思。但也有可能讓人認為是在死背。
- 4:14 講到為了避免編譯器報錯所以最後要回傳,可能可以講仔細一點為什麼要這樣?
- 時間複雜度的部分可以在講的仔細一點,例如說明比較跟暴力法的差別。
- 7:15講到沒有辦法在 n 平方的複雜度就解決所以要新的方法,聽起來有點不合邏輯,可以在說明清楚。
- 有一些口頭禪可以稍微改進(或是可以剪接剪掉)例如:像這樣,對
- 講解 3Sum 的實作還有條件判斷很清楚,一聽就懂。
第三次作業-他評5
總體
- 應使用 Google doc 或者文字編輯器(e.g. Vim、NotePad++)來增加程式碼撰寫的困難度。
- 沒有回答 Valid Parantheses,我猜是忘了回答。
Interviewer
- 題目講解快速,沒有用過多時間舉例而浪費面試時間。
- 3Sum 部分,我覺得 input 資料型態要說明正多細節,例如:是否有重複值?是否有排序過?input 資料長度等等。
- 直接說「你的答案看起來是對的」有夠敷衍。
Interviewee
- 解題概念相當清楚,而且在跟 Interviewer 講解時的描述能力不錯(特別是 3Sum 部分)。
- 講解解題概念同時開始打程式碼,節省時間之外,也讓 Interviewer 可以同時了解 Interviewee 的想法。
- 4:02提到為了避免編譯器出現 compile error 所以要回傳 一個空的
vector
,需要說明為什麼要這麼做。
- 7:15提到用 O(n^2) 複雜度效率很低,所以需要換一個思路,我認為需要說明清楚。
第三次作業-他評6
Interviewer
0:21 避免直接將 LeetCode 的題目「英翻中」
4:14 沒有針對「防止他編譯錯誤」這句話進行提問
5:13 未對 unordered_map find 函式執行時間複雜度為 的說法要求進一步的解釋
16:34 在 interviewee 寫完程式碼後,沒有針對其中的部分進行更進一步的討論或總結
19:09 可以要針對 unordered_map 元素的初始值進行詢問
23:15 「很明顯的你時間就是有慢到」這句話雖然很口語化,但是並不精準,可能會讓 interviewee 覺得你不專業
Interviewee
1:42 沒有完整講述自己的 approach 就開始寫程式碼,會讓 interviewer 有誤會背題目的可能性
4:26 盡量以手動驗證的方式,避免過於依賴手邊編輯環境的功能來檢視程式碼的正確性
6:23 實際情況應該不會有「如題目名字」一樣的思路可以參考,應避免使用這樣的詞彙來描述解題手法
16:31 在沒有檢查邊界條件的前提下,僅透過執行預設的 Test Case 就宣稱程式碼「看起來沒有問題」
17:20 沒有進行 REACTO 中的 "R" 以及 "E" 的步驟
17:22 可以進一步詢問 interviewer 輸入陣列中的數值範圍,如果數值範圍不大,不使用 map 就可以實作
第三次作業-他評7
Interviewer
- 第一題two sum未告知interviewee題目有唯一解的限制
- 23:12"有慢到" 太口語了
Interviewee
- 有邊coding邊講解,Great。
- 沒有詢問interviewer關於唯一解的問題,感覺像是背起來題目
- 沒有Repeat interviewer的問題
- 講解時都沒有舉例子
- "看起來"、"應該" 口頭禪需要改掉
- 4:58 這裡不只有access,還有hash map的搜尋時間
- 6:21 不需要附和覺得這題是延伸題
- 31:00 說 比 好是從何得知的,應該說明一下。 若稍微代換一下 = ,則如何與比較
第三次作業-他評8
Interviewer
- 可以盡量避免直接拿leetcode頁面進行面試,它所提供的參數也許會限制住面試者的想法。
- 第一題延伸題interviewee實作完成後,可以再多提出一些問題或是評論。
- 第二題說到: 時間有慢到,口語化但在面試的過程中應該可以換個說法
Interviewee
- 想法很清楚,也有邊coding邊說明想法
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
- 第一題有講說為了要避免編譯器會報錯所以最後還是要回傳,可以的話盡量再多說明一點為什麼
- 第一題延伸題,對於 為什麼沒辦法在O(N^2)的複雜度有效的判斷答案是否重複 的想法可以再多解釋。
- 第二題自己也說有點慢,那最好可以說明一下是因為在coding時用到什麼東西所導致。
整體
- 應對interviewer和interviewee做更仔細的分類,服裝、鏡頭、語氣皆一致。
- 第一題有唯一解的限制,interviewer未說出、interviewee也沒有問到這個問題。
第三次作業-他評 9
整體
在打字與講解上的時間掌握得當,若在講解的過程加入更多的例子會更好
Interviewer
- LeetCode 1 - Two Sum
- 建議的點:
1:37 這邊看到 interviewee 開始使用 unordered_map
的時候,或許可以問說是否可以先不使用這個 container 來完成原本這題目,而不使用 container 完成題目的時間複雜度為何這樣
- LeetCode 15 - Three Sum
- LeetCode 347 - Top K Frequent Elements
- 建議的點:
覺得可以在 interviewee 寫 code 的過程中去問(不過就要做更多剪接了),不然在呈現上很像是讓 interviewee 都先把 code 寫完之後,再開始問剛剛寫了什麼,在過程中或許可以加入更多的討論(為何不那樣寫?多了一個限制的話目前的 code 要怎麼改?)
Interviewee
- LeetCode 1 - Two Sum
- 優點:
講解過程清楚,也使用到了 container 來完成題目
- 建議的點:
若在使用 unordered_map
container 前,主動的粗略講一次不用到該 container 要怎麼做,時間複雜度為何,或許會更好唷。這邊可能會直覺使用 brute-force 方法用 2 個 for 迴圈找,但因為這樣太慢了,所以可以改成 binary search 的方法找,這樣的延伸都可以使得在回覆上的內容更豐富唷
- LeetCode 15 - Three Sum
- 優點:
6:42 將此題較難的題目與上一題較簡單的題目做連結(不過跳出時間複雜度是 n^2
這邊太快了,可以加一下回圈怎麼跑搭配 2sum 的時間複雜度後,推得為 n^2
)。另外,能在一開始就想到如何針對 “重複的答案” 有解答且提出想法
- 建議的點:
13:00 這邊在講解避開重複的數值時,因為 while
裡頭又包 while
,若 interviewer 這邊沒跟上的話,很難直接從 code 得知你的想法,建議能加個簡單例子輔以說明
13:42 這邊有點怪XD先寫了第二個條件之後才回去寫第一個條件,這樣感覺不太自然(的確應該也演練蠻多次的),覺得這邊就是講到什麼就加什麼條件即可
- LeetCode 347 - Top K Frequent Elements
- 優點:
能夠提出兩個版本,第二個版本針對第一個版本的缺點再去改進
- 建議的點:
24:06 這邊講 “priority queue 的 push 就是 logn” 應該還可以再講多一些(額外提到像是 heapify),或許會更好唷。另外,後面有用到 k
以及 n
來講解,口頭上有講到分別代表什麼意思,不過這邊自己也是回放回去聽才記起來,或許可以在註解後面補上 k=map size 之類的,會更清楚
25:28 ~ 26:01 這段完全 get 不到想表達的內容(可能慧根不夠),可能對你來說是消化後用很精簡的方式講出,但是以聽的角度來說(至少我自己)是聽不太懂改用 bucket 能帶來的效益,這邊如果要講解的話就蠻需要例子來輔助了~
第三次作業-他評 10
interviewee 優點
interviewee 可改進的地方
- 解釋自己的做法時,不要只用講的,可以用寫一些註解來闡釋做法或是寫一些例子(REACTO),讓面試官可以更好更快的理解。
- 解題的過程中,盡量不要突然不說話,把所想的事情給說出來,可以講一些更細節的事情。
- 如果一開始就沒有想要打中文,輸入法可以一開始就調成全英文。
- 9:19 對於
i
程式碼盡量放入初始化值,雖然程式會幫你歸0,和這不是一個好習慣。
- 在闡述作法時,可以多一點多元的思考,即使知道最 Optimized 的解法,可以先講一些基礎解法,再提出最 Optimized 的解法,這樣看起來比較不像是在被題目。
interviewer 優點
interviewer 可改進的地方
- 關鍵台詞有點多
- 用 leetcode 寫,然後用 leetcode run code 來判斷程式碼對不對有點奇怪,白板題主要是在看想法,而不是程式碼完全的正確性。
- 可以加入一些 follow up ,來讓整個測驗更有鑑別度。
- 可以請 interviewee 帶入一些例子來討論,尤其是 special cases
第三次作業-他評 11
interviewee
00:10 建議使用google doc,leetcode 太好用了
01:00 可以一邊舉例一邊簡單打數字或方法,讓 interviewer 更清楚,只用聽的較難完全理解你的意思
01:38 應該先跟 interviewer 討論方法和 corner case,討論佔大部分時間,程式碼實作佔少部分
04:16 Interviewee 應該用自己的舉例去看程式對不對,面試沒有測資可以跑
18:28 interviewee 應避免用 “可能”、“類似” 等用語
interviewer
00:25 建議應該是 interviewee 來舉例,interviewer 講解題目就好
16:59 應由 interviewee 自己舉例
23:23 可以直接問有沒有其他改進方法
24:10 可以再追問為什麼 push 的 time complexity = O(logn)