噠噠特工-LonelyBoy
模擬面試錄影(漢)
模擬面試錄影(漢)
模擬面試錄影(英)
因為題目就有提供範例,所以一開始直接使用題目的範例去做example,然後在approach的時候也利用題目給的例子去幫助說明。
上面是本來我自己做這題最一開始的解法,但後來自己在計算複雜度時發現 O(m*n*(m+n)) 有點太高。後來就做了一些修改,這邊把我原本遇到的問題設計成面試流程。
最後有第二個follow up,是在寫完這題時去看答案發現有能降低空間複雜度到 O(1) 的方法,在這邊設計成第二個follow up。
自評
- 有些講解的部分會太細,其實後面一點的code就會寫到,但前面的時候就會一直急著代後面的觀念,應該配合後面的code一起講解也會比較清楚。
- 有些觀念有點從太底層講起了,其實面試官都會這些觀念,不要搞得好像在"教"他一樣。
- 影片裡面其實function我是定義成"solution",這不太好,應該命名的精確一點。
- 一開始第二個follow up沒有甚麼想法的時候應該再丟更多討論而不是直接承認自己不會。
同儕檢討
interviewer
- 00:01 盡量不要用面試官自稱,可以用自己的英文名字代替,或是說今天由我來主持這場面試。
- 00:49 對in place algorithm的說明有點奇怪,應該是強調要在原本的資料結構內操作,而不是回傳一個新的空間。
- 15:28 直接問能不能把時間複雜度優化成O(m*n)很怪,詢問能不能再提供其他思路來降低時間複雜度會比較好。
interviewee
反問了題目講解不夠清楚的地方,並對edge case題目沒有給例子。自己舉了例子來確認自己的理解。
套用自己一開始舉的例子來test the program。
最後講解空間以及時間複雜度,並解釋原因。
同儕檢討
interviewer
- 00:04 時,interviewer不該自稱為面試官。
- 01:40 時,interviewer應在一開始講解題目時,就先把input的constraint說明清楚,而不是後續interviewee慢慢詢問。
- 12:25 時,提問時,避免只拋出「時間複雜度是什麼等級?」這樣的問題,這樣對話欠缺上下文,可能 interviewee 憑藉猜測或背誦做答,從而喪失鑑別度。
- 後續可以再多問題目的變形,像是:
- 可以有不限次數的交易進行,那最大獲益為何?
- 有限制次數的交易進行(如:最多K次),那最大獲益為何?
interviewee
- 12:25 時,interviewee可以在coding完,自己去分析時間與空間複雜度。
- 12:50 時,掃過一次for迴圈,這裡應該為時間複雜度才對。
自評
- 做這題的時候雖然可能影片看不出來,但我其實內心有點背了答案了,都知道下一行要打甚麼了,可能比較沒辦法真的練到思考能力。
- 不要急著一直發話,一發話讓我有點沒有時間思考程式問題。
- 面試官可以表現得呈穩一點。
- 在一開始就先確認好題目的範圍限制,不要先急著打程式。
- 打字配合講解速度,不要有時候講很久又有些時候打很快。
自己畫了一個binary tree,來講解recursive method的step,並有列出每個step。
自評
- 用英文解釋recursive還需要加強。
- 很少用英文在講解code有些專業術語(特別是動詞),很容易用的不夠精確。
- 可以讓面試官問一個follow up: "有沒有不用recursive的方法?",來考驗面試者的能力。
- 面試者可以最後再用一開始的例子test自己的code,但用英文trace recursive的code真的頗有挑戰性。
- 不要一直打錯字,顯得自己程式能力很生疏。
模擬面試錄影
題意
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Given binary tree [3, 9, 20, null, null, 15, 7],
return its depth = 3.
Depth-first-search vs. Breadth-first-search
策略:若子節點 left 或 right 存在,則遞增 depth,並判斷 left 或 right 是否存在子節點,遞迴直到最深層。
考慮以下:
Tree depth = 3
- nodeA 的深度 = 1自身 + max(nodeB 深度, nodeC 深度)
- nodeB 沒有子節點 nodeB 的深度 = 1
- nodeC 有子節點 nodeD 和 nodeE nodeB 的深度 = 2
- nodeA 的深度 = 1 + 2 = 3
遞迴實作:
應用案例: find(1)