# 2022 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2022/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FBJLSJ3ggi)」作業 1
> 心宿二 - Alpha Scorpii
> 🐼 : interviewer
> 🐶 : interviewee

> [模擬面試錄影(漢)](https://youtu.be/-mT27NHWI54)
> [模擬面試錄影(英)](https://youtu.be/MZ0aGVBmw6o)

## [226. Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/)

### 同儕檢討
#### interviewer
1. [0:02](https://youtu.be/-mT27NHWI54?t=2) 這邊使用「面試官」這個詞並不恰當，因為面試中並不是上下級關係可能會被記仇，可以使用「很榮幸可以由我來主持這場面試」等等字眼代替。
2. [0:09](https://youtu.be/-mT27NHWI54?t=9)這邊只單純講出請反轉二元樹並回傳樹根，這樣的問題可能有點太過抽象，可能可以舉出例子。
3. [0:11](https://youtu.be/-mT27NHWI54?t=11) 反轉的方式沒有說明清楚，會讓interviwee不知道該怎麼進行反轉。
4. [0:12](https://youtu.be/-mT27NHWI54?t=12) 有些專有名詞利用英文來說明會比較被多數人直接理解，像是樹根可以直接用root node。
5. [10:22](https://youtu.be/-mT27NHWI54?t=622) 這個問題問得很好，可以看出interviwer對於自己的程式是否完全理解而不是硬背。
6. [0:02](https://youtu.be/-mT27NHWI54?t=2) 在中文中避免使用「面試官」這個詞，Interviewer與Interviewee應是平等地位。
7. [0:06](https://youtu.be/-mT27NHWI54?t=6) 第一次聽到的「回傳它的樹根」會覺得有點模稜兩可，使用「回傳它的樹根節點」似乎比較精確。

#### interviewee
1. [0:24](https://youtu.be/-mT27NHWI54?t=24) 如果對題目不清楚，自己舉例子可能會跟題目要求有差別，覺得應該詢問清楚比較好
2. [7:11](https://youtu.be/-mT27NHWI54?t=431) 這邊有對很多情況來去討論出不同的空間複雜度很好，代表你對於整體架構有很深的理解。
3. [0:53](https://youtu.be/-mT27NHWI54?t=53) Interviewee敘述是說「也就是把Root節點的左、右子節點交換」，但應該是所有節點的左、右子節點交換，Interviewer應該要修正他。
4. [5:43](https://youtu.be/-mT27NHWI54?t=343) 「分析複雜度」應比「介紹複雜度」好。
5. [10:12](https://youtu.be/-mT27NHWI54?t=612) 有特別的followup蠻好的。
6. [1:20](https://youtu.be/-mT27NHWI54?t=80) Interviewer從沒有提過Full binary tree，舉完例子以後卻想詢問Interviewer「除了Full binary tree以外」的case，有點多餘。Interviewee可以直接確認 : 是不是將Binary tree中所有Node的左子樹與右子樹互換。
7. [1:50](https://youtu.be/-mT27NHWI54?t=110) 在REACTO中的E應該舉一些Corner case，例如：「input的節點會不會為空」、「若只有一個節點，便是回傳該節點嗎？」。
3. [4:12](https://youtu.be/-mT27NHWI54?t=252) 應是「Node的定義」非二元樹的定義。
4. [5:50](https://youtu.be/-mT27NHWI54?t=353) 可以直接說「節點交換成本的複雜度是常數」，後面那串有點多餘。
5. [6:50](https://youtu.be/-mT27NHWI54?t=410) （我也不是很確定）一個節點便會宣告一個暫存變數，這樣空間複雜度(Without function call stack)應該是$O(N)$非$O(1)$。
6. [7:22](https://youtu.be/-mT27NHWI54?t=442) 樹的高度的英文應該是height of the tree，非tree height。

### 自我檢討
1. Example 沒有確認邊界條件, 如 input 節點是否為空
2. [7:03](https://youtu.be/-mT27NHWI54?t=423) "隨著節點數的改變, 用到的空間的成本還是固定的" 是錯的, 應該改成 "對每個節點來說, 交換其左右子節點的時間成本不變", 接到 "翻轉整顆二元樹需要走訪每一個節點一次, 因此總時間成本與節點數成正比"。
3. [8:28](https://youtu.be/-mT27NHWI54?t=508) 時間複雜度的部份可以用不等式來表示非 full binary tree 的節點數與樹高的關係, 如 $2^{h-1} <= n <= 2^h - 1$, 再推出 $log(n) + 1<= h <= log(n+1)$, 於是得到 $h = \Theta{(log(n))}$。
4. [13:01](https://youtu.be/-mT27NHWI54?t=781) pseudocode 的 loop 前沒有 push root 節點。
5. 或許可以把字體換成 monospace。

## [21. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/) and [23. Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/)

### 同儕檢討
#### Interviewer
1. [19:06](https://youtu.be/-mT27NHWI54?t=1146) 這裡可以說"你可以開始進行實作了"，因為主導權應該在interviwer身上，所以不是合用疑問的方式。

#### Interviewee
1. [23:18](https://youtu.be/-mT27NHWI54?t=1398) 這裡講解時間複雜度利用了程式來一起進行解說，讓人很容易就可以理解，很讚。

## [50. Pow(x, n)](https://leetcode.com/problems/powx-n/)

### 同儕檢討
#### Interviewer

#### Interviewee
1. [1:15](https://youtu.be/MZ0aGVBmw6o?t=75) RE理解題目的這兩部份表達的滿清楚的，此用minus如用negative感覺會更好
2. [2:37](https://youtu.be/MZ0aGVBmw6o?t=157) 這裡有講到naive method，如是想表達最直覺的做法或許可以改成the most straightforward method會比較不容易誤導。這邊說明approach的部分很流暢，透過舉例說明選擇方法而非暴力法的原因也讓人可以清楚知道所選方法好在哪裡
3. [7:51](https://youtu.be/MZ0aGVBmw6o?t=471) 在寫程式前補充說明奇數條件的部分也滿順且清楚的
4. [13:18](https://youtu.be/MZ0aGVBmw6o?t=798) 這部分在說明程式performance的部分，有自己提到用bitwise去improve判斷奇偶數以及後面在講space complexity的部分有提到function call stack的空間部分滿好的，如果我是面試官聽到這兩個部分會覺得滿加分的