# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者: 拍手-clap
> 🧔：interviewer
> 👶：interviewee
> [模擬面試-1 (中文)](https://youtu.be/xBcoqaVNP4g)
> [模擬面試 2 (中文)](https://youtu.be/eqqSNY4fdG0)
> [模擬面試-3 (英文)](https://youtu.be/kGyCmL_Qc-8)

## [148. Sort List](https://leetcode.com/problems/sort-list/)
### 面試過程
🧔 : 現在有一個 linklist 我希望你按照每一個 node 的值將他們由小到大做排序。

👶 : 好的，那這邊想確認一下，假設 input 為一個 [5,3,7,9,-1,3] 那我們的 output 會是 [-1,3,3,5,7,9] 其中 3 是代表 input 可能會有重複的數字，-1 代表可能有負數，這樣我理解有錯嗎?

🧔 : 沒有錯，你理解得很好。

👶 : 那這邊一開始會想先判斷 input 有幾個 node，如果沒有或只有一個的話，那可以直接將值傳回去，如果節點數大於1的話想採用 bubble sort 來完成排序。

🧔 : 聽起來不錯，你可以開始實作了。


👶 : 那我的程式時間複雜度會是 O(n^2)。

🧔 : 那你有辦法把時間複雜度控制在 O(logn)嗎?

👶 : 恩......(思考)，那我會將排序的方法由 bubble sort 改成 merge sort，這樣就可以滿足時間複雜度在 O(logn)。
🧔 : 聽起來很棒，你可以繼續實作了。

## [1282. Group the People Given the Group Size They Belong To](https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/?envType=daily-question&envId=2023-09-11)
### 面試過程

🧔 : 現在有個 array，裡面一個 index 就是一個人而 index 的值就是人在的團體有幾個人，例如 : [1,1,3,3,3]第0個人在一個人的團體裡，第二個人在三個人的團體裡，然後我需要你將團體給分類好，像上面的例子會變成 [[0],[1],[2,3,4]] 會有很多種答案只要給我其中一種就可以。

👶 : 那想先請問一下總人數有可能是空的嗎或是總人數有什麼上限?

🧔 : 總人數一定大於1且小於500。

👶 : 那想再請問有可能給的數值無法剛好分配成剛好的團體嗎?例如 array 給 [1,1,2] 但是第二個人沒有人跟他配對。

🧔 : 不會，array的值都是設訂好的，不會發生上面的情況。

👶 : 好的，那我想在確認一次題目，如果收到 array [3,2,1,3,2,3] 那麼第0個人在三個人的團體，第1個人在兩個人的團體後面以此類推，output 會產出 [[2],[1,4],[0,3,5]] 這樣我理解有錯嗎?

🧔 : 沒有錯，你理解的非常好。

👶 : 那我的想法是因為數值不一定是由小排到大，所以想要先排序，但是因為 index 代表一個人所以要跟數值綁定一起排序，所以我會先將數值跟index排序完後，再從排序完的結果一個一個按照他的數值取人，就可以得到答案了。

🧔 : 聽起來是沒甚麼問題，你可以開始實作了。


👶 : 目前整體的時間複雜度是 O(n^2) 因為排序採用的是bubble sort如果採用其他排序法可以縮短到 O(nlogn)，而空間複雜度是 O(n)。

🧔 : 那有時麼方法可以比 O(nlogn) 還要更快的嗎?

👶 : 恩......(思考)我想到可以用 hash table 來記錄這樣時間複雜度可以縮短到 O(n)。

🧔 : 聽起來不錯，你可以開始實作了。


## [100. Same Tree](https://leetcode.com/problems/same-tree/description/)
### 面試過程
🧔: I want yot to determine whether every value in two binary trees is the same. The input for this task will be the roots of the two binary trees.

👶 : So, if there are two binary trees with the structures [1,9,6,3,2] and [1,6,9,3,2], the return value will be false because even though both of them contain 6 and 9, in the first tree, 9 is in the left subtree, while in the second tree, 9 is in the right subtree. Therefore, the two binary trees are still not equal. Is this understanding correct?

🧔 : You are right, and your understanding is accurate.

👶 : We will first create a function with the purpose of checking whether the values at corresponding positions in two subtrees are equal. If they are not equal, the function will return false. If they are equal, the comparison will continue downward. The entire algorithm operates through recursion, starting from the root, comparing the left subtrees first, then the right subtrees, until all nodes have been compared. If all nodes are found to be equal, the function will return true.

🧔 : Sounds good! Let's begin the implementation.


👶 : Here, the time complexity of my algorithm will be O(n) because we need to visit all the nodes once.

🧔 : This is great,Thank you for participating in the interview. We will provide you with the results within the next two weeks. Have a wonderful day, and goodbye!

## 初步檢討
1.面試官部分缺少互動感
2.題目應該適當的包裝
3.缺少了test的部分
4.寫程式的速度可以加快
5.編寫程式時可以適當的加入註解

---

## 第二次作業-他評01
### 關於interviewer
- [ ] 優點
* 語速適中

- [ ] 可改進的地方
* [13:44](https://youtu.be/xBcoqaVNP4g?si=LdCX7CSUS5TqbNKd&t=824): 應該可以再延伸問題或是探討最佳化的寫法，而不是單純的要求他找出O(logN)方法。例如:提出改善的可能方案之類
* 這三題最後interviewee在interviewer完成後，interviewer可以給一些評論或是討論，讓interviewee知道自己是否正確或是有可以需要改進的地方。
* 缺了少請interviewee TEST的部分
* [20:22](https://youtu.be/eqqSNY4fdG0?si=efBlxI4bjBI1Te2R&t=1222): 在interviewee說明自己要用hashtable實作的時候，可以繼續追問為什麼用hashtable會更快或者hasttable的特性，藉此了解interviewee的想法
* 可以包裝一下題目(雖然我也不太會包裝==，但這有點在考試的感覺而不是面試
* 英文題目說明的太簡短，應該要主動舉個例子 在看interviewee是否了解題意
* 對 interviewee 的回饋偏少，大多都只回"聽起來不錯"，會讓對方覺得你很敷衍

### 關於interviewee
- [ ] 優點
* repeat和example的部分有做到，確認自己有了解題意

- [ ] 可改進的地方
* 打code速度要提升
* 建議事先詢問可用的程式語言
* [08:15](https://youtu.be/xBcoqaVNP4g?si=_1p7JJXYFd-8k-VF&t=495): 建議可以加點肢體動作來強化視覺效果
* [13:44](https://youtu.be/xBcoqaVNP4g?si=LdCX7CSUS5TqbNKd&t=824): 建議練習邊打code邊解釋為什麼這麼寫，而不是念自己打出來的東西
* [35:33](https://youtu.be/eqqSNY4fdG0?si=NFTZBRvJOkuuddXJ&t=2153): 建議講解時間複雜度的時候，可以分別上下兩段程式碼所需要的時間，而不是說因為用了hash table時間複雜度就為 $O(n)$，會讓人覺得你是背答案的
* 建議主動跑test case來說服interviewer這麼寫可以執行且得到想要的結果
* [05:23](https://youtu.be/kGyCmL_Qc-8?si=iO_4lz-FTZumINNa&t=323): 建議可以在code旁邊註解 類似 `//if p is null`

## 第二次作業-他評02
- [ ] 影片相關建議
* 中間轉場空白的時間可以縮短一些

### 關於interviewer
- 可以考慮先自我介紹一下，而不是一來就直接塞題目給面試者
- 最後結尾的時候也可以說一些下次可能會是什麼時候再來面試或者很感謝你今天來參與的這些話
### 關於interviewee
- 英文面試的時候後半段聲音都比較模糊模有辦法聽仔細說了什麼內容

## 第二次作業-他評03
### 關於interviewer
- [ ] 優點
* 口齒清晰。

- [ ] 可改進的地方
* 題目可以適度包裝，而非直接照抄leetcode。
* [0:01](https://www.youtube.com/watch?v=xBcoqaVNP4g&t=1): 建議標記出interviewer跟interviewee，方便看出現在的角色。

### 關於interviewee
- [ ] 優點
* [13:43](https://www.youtube.com/watch?v=xBcoqaVNP4g&t=823): 有做optimize的部分很不錯。

- [ ] 可改進的地方
* [4:05](https://www.youtube.com/watch?v=xBcoqaVNP4g&t=245): 少了一個分號。
* [13:28](https://www.youtube.com/watch?v=xBcoqaVNP4g&t=808): 少了test的部分，可以舉例來trace一下code。

## 第二次作業-他評04
### 關於interviewer
- [ ] 優點
* 音量適當，口齒清晰

- [ ] 可改進的地方
* 應該適度將 LeetCode 原題做變形

### 關於interviewee
- [ ] 優點
* interviewee 將 repeat 與 example 部分結合，節省時間，這一點值得嘉許
* 音量適當，口齒清晰

- [ ] 可改進的地方
* [1:31](https://www.youtube.com/watch?v=kGyCmL_Qc-8&t=91)：念錯字 comparison -> comparsion
* 解釋 Approach 的時候 可以在 Word 上作筆記（或註解）
* 寫 code 時可以邊寫程式邊講解，避免尷尬的沉默