資訊科技產業專案設計HW2

作業二

HW2影片連結

: interviewer
: interviewee

模擬面試過程

104. Maximum Depth of Binary Tree

:你好，公司請我來了解你的情況，並協助你更認識公司，假設你現在是我們公司技術團隊的一員，負責優化使用者的搜尋體驗，我們平台上的住宿按照選項、地理位置分類，你可以想像有一個巨大的地圖，當使用者放大一個特定區域時，他們可以看到更小的區域，這些小區域又可以進一步的放大來顯示更小的區域，一直這樣類推下去。現在為了更好的服務我們的使用者，我想要你根據他們再查看區域的深度，來優化推薦的住宿選項。假設他們在研究一個具體的小區域，可以優先推薦這個區域的住宿，如果他們只是在瀏覽大區域，可以推薦大區域內幾個最受歡迎的住宿選項。你要完成的工作是，設計一個演算法或函式，給定使用者正在查看的區域，這個函式要可以返回這個區域裡我們地理分類系統的深度。

: 開始寫程式之前我想簡介一下我的軟體開發經驗，我主要是以前端為主，主要負責網頁設計跟架構網站，專案的部分我有做異常值檢測的雲端運算服務，是前端跟後端的結合，前端寫一個pivottable檢測異常值，並做ANOVA分析，再連接後端的資料庫，構成一個雲端運算系統。

: 好，那我大致了解你的情況了，沒有需要補充的話可以回答剛剛那個情境的可能解決方案了。

: 好，那我想確認我有沒有理解錯這個題目。解設我有一個二元數，它的根結點是3，左子節點是9，右子節點是20，20也有左子節點13，右子節點15。我要回傳這個二元樹的最大深度是多少。

: 對，你的理解是對的，請繼續你的解釋。

: 如果我的理解沒有錯的話，我想可用遞迴來解決這個問題。詳細方法是找到一個node，得到這個node的left child和right child的最大深度，並取得這兩個數值中的最大值+1，就會是這個node的maximum depth。
以上面的例子來說，要得到20這個node的maximum depth，就是取13跟15的maxamum depth的最大值，也就是1，再加上1得到2，就是20這個node的maximum depth。
再透過遞迴就可以歷遍整個Binary Tree，就可以得到這個Binary Tree的maximum depth了。

: 對，你的理解是對的，但你用遞迴的話會遇到一個問題，就是你要判斷這個節點是否為空。那如果你想好要怎麼寫code的話，可以開始寫你的code了。

:

int maxDepth(TreeNode* root){
	if(!root) return 0;
	int maxLeft = maxDepth(root->left);
	int maxRight = maxDepth(root->right);
	return max(maxLeft, maxRight) + 1;
}

: 好，這程式沒什麼問題，那我想問你一下這個程式的時間跟空間複雜度是多少?

: 時間複雜度是它所有節點的個數，因為它要歷遍整個binary tree，空間複雜度的部分，因為它是recursive stack，所以是level的個數。

: 那我們今天的面試就到這邊，感謝你的時間。

他評-01

interviewer

• 優點
  • 0:08 題目包裝得很新穎。
• 可改進的地方
  • 0:43 優先推薦的部分的說明較多餘，與作答無關，有點冗長。
  • 3:52 實作後如果 interviewee 忽略空節點判斷再提醒即可。
  • 6:21 可再針對作法引導優化。

interviewee

• 可改進的地方
  • 1:15 interviewer 問完問題之後，突然說明自己的開發經驗很突兀。應針對問題做回答，或者將自己過去的開發經驗連結到題目上，如:相關的開發經驗、作法為何、如何應用在此問題上等。
  • 2:05 並未提及題目是如何連結到二元樹，進展過快。應針對題目敘述做討論，並與 interviewee 確認，如:"分類系統應包含xx結構，因此將它視為一個二元樹"、"若為二元樹的形式，則分類系統的深度即為二元樹的深度"。
  • 6:11 可針對節點個數、深度、worst case 等狀況進行更多討論。

簡介對其他同學的檢討狀況(總述)

檢討同學: 鮪魚 竹間 喬喬 蔡中文 柯基

interviewer

優點

• 0:01 這位同學的開場讓整個面試的環境很舒服，不會讓人覺得這個面試是面試官在施展官威的地方。
• 大多數同學都能對interviewee的情況給予適時的回應

缺點

• 大多數人都沒有將題目包裝，而是直接用leetcode的原題進行問答。
• 有些人會有口齒不清的情況，導致題意傳達不清。

interviewee

優點

• 大多數人都能cover到REACTO的步驟。
• 有記得舉例子解釋題目。
• 和interviewer多溝通交換想法。

缺點

• 在邊打程式邊解釋的時候會有空白期，會讓interviewer感到乏味。
• 會有過多冗詞贅字的情況。 例如:然後… 恩… 厄…
• 一開始忘記解釋題目確認想法及舉例子
• 打字太慢

從中學習到什麼

透過看到其他同學的面試過程，學到了其他人所具備但我所不具備的能力，像是interviewee可以提出更好的程式撰寫方式來提升效率，interviewer可以更好的和interviewee溝通，並在講述題目的時候能適度的包裝題目來減少讓interviwee直接看出是經典題而直接被答案來應付interviewer的情況。但我也能辨識出自己的優點，像是口條，溝通節奏以及REACTO步驟的執行完整度等等。

第 4 次作業-他評簡介

第一位檢討同學:

月前龍馬-lonmu
video

針對interviewer的檢討

• 0:04: 避免講「我有個問題想請你解一下」，可以改成說「首先我們考慮 ___ 的情境」，因為面試的關鍵是溝通，題目只是媒介。
• 0:10: 有適度的包裝題目，來避免interviewee直接背題目答案的情形發生。
• 3:35: 這邊說「實踐你的想法」，蠻不錯的，因為通常大家都會說「請你開始寫程式碼」，這種說法會讓interviewee感到比較舒服。
• 10:12: 說話有點結巴，且最後再說完時間複雜度時，後面有一個類似"呃"的怪聲，可能會讓interviewee沒辦法適度的了解題目，可以盡量避免這種沒有發音好的情況在問問題時發生。
• 11:18:說:「需要合併的資料不是只有兩個客戶的話，是多個客戶要一起合併成一個linked list的話。」
• 這邊的"不是"的"不"講得很小聲，容易讓interviewee以為是要合併兩個客戶。在第一句結束時可以省略說"的話"，在第一句和第二句中間也可以加上 "而是"，來讓題目更容易被intervewee聽懂。

針對interviewee的檢討

• 0:28: 有適度的和interviewer溝通，做到repeat & example的步驟，而不是劈頭就直接開始打程式，在確認題意的同時又有跟interviewer互動到，可以讓interviewer留下好印象，讓Interviewer覺得之後和你一起工作是可以和你順利溝通的。
• 5:19: 有新增註解，可以幫助自己和interviewer更了解程式撰寫的邏輯，之後再檢查時也可以較快的判斷程式的正確性。
• 7:20: 這邊說「我想確認一下我的程式碼有沒有問題」，之後便空出了快30秒的空白時間，這段時間可以再稍微複述一下程式，避免讓interviewer不知道在這段時間不知道要做什麼事。
• 7:52: 有確實做到蠻多人都沒有做到的Test的步驟，來驗證程式碼的可執行性，是一個不錯的示範。
• 10:27: 這裡頻繁的移動滑鼠以及反白文字，這樣畫面會看起來很雜，也會讓interviewer看的眼花撩亂，盡量避免做出這種不必要的多於動作，來讓interviewer可以專注於interviewe想要表達的內容上。

第二位檢討同學:

埃默里 Emery
video

針對interviewer的檢討

• 0:07: 開場方式舒服，用 "問題" 取代 "題目"，用"討論" 取代 "考" ，這些用詞選擇會讓interviewer跟interviewee在這場面試中，更像是同事在討論公司正在面對的問題，並提出可行的解決方案，比較不像是一種上對下的關係，這樣會讓interviewee在整體的面試體驗上更為良好。
• 0:15: 有用包裝的方式來陳述題目，但在google document上卻放了原題的題目，這樣就失去了包裝題目不讓interviewee背答案的用意，google document在一開始還是保持乾淨就好。
• 0:26: linked list的發音不太正確，在影片中聽起來像linking list，與實際的發音有出入，可以改善發音方式。
• 7:00: 沒有跟interviewee說他剛剛的做法是否為正確，應該要先說他的想法是對的再請他開始實作程式碼。
• 11:17:不知道是不是剪輯問題，在interveiwee結束講解後，interviewer應該講話來結束整個面試，講諸如:感謝你今天的時間等等的話語做收尾，但影片中卻沒有出現此段落。

針對interviewee的檢討

• 0:33: 有和interviewer確認題目以達到在面試中強調的 "溝通" 效果。
• 1:48: 開始寫程式後語速跟打字速度稍慢，如果沒辦法講得很快的話，可以加快打字速度。
• 5:18: 有實際測試來驗證這個程式碼的邏輯是否錯誤，這是大多數面試的人容易忽略的過程。
• 10:48: 這邊可以等到interviewer題問再講解效率跟空間複雜度，突然開始講解會有點突兀，也減少了跟interviewer溝通的機會。