---
tags: 資訊科技產業專案設計作業
---
# 資訊科技產業專案設計課程作業 2
> 貢獻者: 威爾 will
> [模擬面試錄影(漢)](https://youtu.be/Z7pXNUo50No)
> [模擬面試錄影(漢)](https://youtu.be/LbsDUHjpxxE)
> [模擬面試錄影(英)](https://youtu.be/6FbfxWwfqho)
🧔：interviewer 👶：interviewee
## [230. Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst/)
### 測驗說明與問答
🧔：希望 will 可以實作一個 function，輸入一個二元搜索樹(BST)，這個 function 可以找出裡面第 k 小的元素。
👶：好的您的問題是給我一個二元搜尋樹，然後我要想辦法找出裡面由小到大排在第 k 位的點的值嗎?：
🧔:是的，沒錯!
👶:那首先對這個問題提出一些案例
```
Example 1:
Input:
k = 1
BST: 3
/ \
1 4
\
2
Output: 1
Example 2:
Input:
k = 3
BST: 5
/ \
3 6
/ \
2 4
/
1
Output: 3
```
👶：另外假設至少有一個點。
👶：我剛開始想到的方法是用遞迴解，以 inorder 的方式走訪整顆二元搜尋樹，因為 inorder 會按照二元搜尋樹的點由小到大走，因此我只需要再走的時候順便做 K 值的計算就可以找到答案
🧔：這樣的時間複雜度是如何？
👶：由於需要遞迴的訪問每一個節點執行函數，故時間複雜度為$O(n)$
### Kth Smallest Element in a BST
```c=
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
void inorder(struct TreeNode* node, int* k, int* ans)
{
if (node) {
inorder(node->left, k);
if (--*k == 0) {*ans = node->val;return;}
inorder(node->right, k);
}
}
```
🧔：如果這個 BST 很常被更改(插入/刪除)，且你也很常需要找到第 k 小的元素該怎麼辦？
👶：我的想法是在 ```struct TreeNode``` 中多加一個成員叫做 ```count``` 用來紀錄這個點的左右子樹的點數再加上自己(1)的總節點數，這麼一來每當 BST 在新增或刪除時也更新 ```count``` 的前提下，時間複雜度可以是$O(h)$，```h``` 代表樹高
### Follow up
```c=
struct tTreeNode{
int val;
int count;
struct tTreeNode* left;
struct tTreeNode* right;
};
void kthSmallest(struct tTreeNode* root, int k, int* ans)
{
int leftcount = root->left ? root->left->count : 0;
if (leftcount+1 == k) {*ans = root->val; return;}
else if (leftcount+1 > k) kthSmallest(root->left, k, ans);
else kthSmallest(root->right, k - leftcount - 1, ans);
}
```
### 同學互評
針對 interviewer 的檢討：
[00:00](https://youtu.be/LbsDUHjpxxE) 不要自稱自己是面試官比較好，就説你負責這次的面試。
[00:11](https://youtu.be/LbsDUHjpxxE) 如果提供題目及例子，並稍微講解一下會比較好。不然interviewee 可能會不懂你的問題。
針對 interviewee 的檢討：
* 盡量少講語助詞。
* 寫完 code 可以試著代入測資測試。
* 在被問到很常被更改的問題時，提出了更改原本的資料結構的想法，感覺可以的話應該是希望不要動到本來的基本結構，去其他方法會比較好一點。
## [101. Symmetric Tree](https://leetcode.com/problems/symmetric-tree/)
### 測驗說明與問答
🧔：在第二題我給你一個二元樹，請你檢查這棵樹是否為左右對稱(Symmetric)。
👶：沒問題，所以我會有一棵二元樹，然後我要檢查這棵樹是否左右對稱。
🧔：是的，沒錯
👶：好的那麼要處理這個問題，比如說下面這個例子
```
下面這顆是 symmetric tree
1
/ \
2 2
/ \ / \
3 4 4 3
```
👶：我一開始想到的方案是利用遞迴的方式來解，比如說看到 root 的左右節點(2, 2)簡稱為左節點跟右節點，這邊可以判斷(1)左節點的左子樹跟右節點的右子樹是否對稱、(2)左節點的右子樹與右節點的左子樹是否對稱，來判斷這顆 BT 是否為對稱樹
👶：另外寫程式時還要注意到子樹是空的的情況
```c=
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
bool isSYM(struct TreeNode* L, struct TreeNode* R)
{
if (!L && !R) return true;
else if (!L || !R) return false;
if (L->val == R->val) {
return isSYM(L->left, R->right) && isSYM(L->right, R->left);
}
else return false;
}
bool isSymmetric(struct TreeNode* root)
{
return isSYM(root->left, root->right);
}
```
🧔：好的，那麼接下來想請問有沒有非遞迴的方式
👶：我的想法是用兩個 ```queue```分別存 root 的左右子樹的點，把每次走到的點 pop 出去，然後 push 進它的左右子點。來達成iteration 的解法
👶：舉例來說
```
1 queue1 queue2 判斷兩個queue head 有沒有相同
/ \ 有就把他們pop掉，然後push他們的左右子點進來
2 2 [2] [2] 這邊要注意到兩個 queue push 左右子點的順序要對稱
/ \ / \
3 N 4 3 [3, NULL] [3, 4]
```
👶： C 語言因為沒有 queue 結構，所以這邊我要用 linked list 來實作簡單的 queue
```c=
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct qnode{
struct TreeNode *node;
struct qnode *next;
};
void insert(struct qnode *tail, struct TreeNode *tnode)
{
struct qnode *n = malloc(sizeof(struct qnode));
n->node = tnode;
n->next = NULL;
tail->next = n;
}
bool isSymmetric(struct TreeNode* L, struct TreeNode* R)
{
struct qnode* L_head = &(struct qnode){struct TreeNode* L, NULL};
struct qnode* R_head = &(struct qnode){struct TreeNode* R, NULL};
struct qnode* L_tail = L_head;
struct qnode* R_tail = R_head;
while (L_head && R_head) {
struct TreeNode* L = L_head->tnode;
struct TreeNode* R = R_head->tnode;
if (!L && !R) {
L_head = L_head->next;
R_head = R_head->next;
continue;
}
else if (!L || !R) return false;
else {
if (L->val != R->val) return false;
else {
insert(L_tail, L->left);
L_tail = L_tail->next;
insert(L_tail, L->right);
L_tail = L_tail->next;
L_head = L_head->next;
insert(R_tail, R->right);
R_tail = R_tail->next;
insert(R_tail, R->left);
R_tail = R_tail->next;
R_head = R_head->next;
}
}
}
return true;
}
```
### 同學互評
針對 interviewer 的檢討：
* [0:00](https://www.youtube.com/watch?v=Z7pXNUo50No) 題目還是給個example會比較好。
* [4:11](https://www.youtube.com/watch?v=Z7pXNUo50No) 除了問時間複雜度，空間複雜度也可以問一下。
* [0:00](https://www.youtube.com/watch?v=Z7pXNUo50No) 題目講解過於簡潔，避免 interviewee 理解錯誤，或理解太慢。且應該至少給予 true 跟 false 的範例各一個。可以在最後增加敘述「也請自行定義二元樹的結構」之類的話。
* [9:52](https://youtu.be/Z7pXNUo50No?t=590) 「那我大概知道了」像是 interviewer 也不完全了解 interviewee 的作法。若真的有不清的應該要繼續討論問清楚，若都清楚的應該要給更肯定的回應。接著
* 影片結束應該還要再帶給 interviewer 做評論，結束的有點倉促，可以對於第二個實作方式有更進一步的討論。
針對 interviewee 的檢討：
* 解説的時候盡量不要花太多次滑鼠。
* [3:56](https://youtu.be/Z7pXNUo50No?t=236) 影片中說的時間複雜度是錯的，不是 $O(h-1)$ 喔，有兩個點要注意，一、減一是不必要的，因為當 h 夠大時，減一可以忽略不計。二、每層要做判斷的數量不同，所以不可能是 $O(h)$。應該從每個節點拜訪的次數分析，時間複雜度是 $O(n)$，$n$ 為節點數量
* [10:18](https://youtu.be/Z7pXNUo50No?t=618) 開始，在講解 BFS 時，不需要刪掉 DFS 的部分，直接在底下實作即可。
* [22:32](https://youtu.be/Z7pXNUo50No?t=1352) 這邊的 continue 是不必要的。
* [27:22](https://youtu.be/Z7pXNUo50No?t=1642) insert 這個 function 可以改成回傳新增的 qnode，這樣在使用時，可以直接用回傳值去更新 tail，程式也會更簡潔。(tail 用 double pointer 去更改也是有相同效果的)
example :
```clike!
struct qnode* insert(struct qnode* tail, struct Treenode* tnode){
struct qnode* q_node = malloc(sizeof(qnode));
q_node->tnode = tnode;
q_node->next = NULL;
tail->next = q_node;
return q_node; // 回傳 tail 應該要指向的位置
}
// 每次使用時可以少打一行
L_tail = insert(L_tail, L->left)
```
## 同儕檢討(他評)
### [面試檢討 - 他評 01](https://hackmd.io/@sysprog/HJmh9FlGs)
* 優點
* 有重複問題和舉例討論。
* 口齒清楚
* 缺點
* 過場的時候可以用字幕標記 interviewer 和 interviewee
* [2:20](https://www.youtube.com/watch?v=8o5xDyZW-L0#t=2m20s) interviewee 在說想法時可以搭配打字舉例說明會比較好懂
* [2:52](https://www.youtube.com/watch?v=8o5xDyZW-L0#t=2m52s) interviewer 在這邊可以把題目從 32 bits 改成 8 bits 之類的，可以避免冗長的打程式過程
* [3:20](https://www.youtube.com/watch?v=-MmBAeRkeDc#3m20s) interviewee 可以先問能不能用標準函式庫
### [面試檢討 - 他評 02](https://hackmd.io/@sysprog/SyxXzTYgGi)
* 優點
* 口試清楚，對答流暢
* 缺點
* [0:10](https://www.youtube.com/watch?v=eG_ckTWiW8s#0m10s) 記得不要講面試官
* [0:29](https://www.youtube.com/watch?v=eG_ckTWiW8s#0m29s) interviewer 在說明題目時可以打一些範例來讓 interviewee 更能理解題目
* [0:56](https://www.youtube.com/watch?v=eG_ckTWiW8s#0m56s) interviewee 跳過 repeat，直接進到 approach 的部分了
* [9:28](https://www.youtube.com/watch?v=eG_ckTWiW8s#9m28s) 寫完可以先問問看 interviewer 的意見，之後再試著最佳化，比較有互動感
### [面試檢討 - 他評 03](https://hackmd.io/Jg0pMfMtSDmUeNjvhOT7wA?both)
* 優點
* interviewee 有停頓下來思考，不會讓人誤以為是背答案
* 口齒清楚
* 缺點
* [0:02](https://www.youtube.com/watch?v=Wy88DIP9j1o#0m02s) 記得不要講面試官
* [0:11](https://www.youtube.com/watch?v=Wy88DIP9j1o#0m11s) interviewer 說明題目時可以搭配打字讓 interviewee 更好理解
* [3:54](https://www.youtube.com/watch?v=Wy88DIP9j1o#3m54s) interviewer 提問時不應說能快點嗎，可以提出一個時間複雜度給 interviewee 思考
### [面試檢討 - 他評 04](https://hackmd.io/@sysprog/BJ_179gfo)
* 優點
* Interviewer 說明簡單明瞭，也有用圖來表達範例，讓 interviewee 更好理解
* Interviewee 有先向 interviewer 確認對題目的理解，然後再提出自己的想法
* Interviewee 口齒清楚，表達也很流暢
* Interviewee 有做到在撰寫程式碼的同時講出自己的想法
* 缺點
* Interviewer 可以向 interviewee 討論複雜度，然後再討論有沒有其他的 approach
* [2:12](https://www.youtube.com/watch?v=a8EAkMWPkB8#t=2m12s) 不是叫空子樹，要叫做這棵樹為空(空集合)
### [面試檢討 - 他評 05](https://hackmd.io/EIw2WNFWQ2OI0cVfJqRGmA?view)
* 優點
* Interviewer 的說明簡單明瞭，也有用圖來表達範例，讓 interviewee 更好理解
* Interviewer 可以向 interviewee 討論複雜度，然後再討論有沒有其他的 approach
* Interviewee 有先向 interviewer 確認對題目的理解，然後再提出自己的想法
* Interviewee 有做到在撰寫程式碼的同時講出自己的想法
* 缺點
* [5:16](https://www.youtube.com/watch?v=2614P2z1bg8#t=5m16s) Interviewee，Auto-Complete 記得要關掉
* [9:37](https://www.youtube.com/watch?v=2614P2z1bg8#t=9m37s) Interviewee 可以用快慢指標來最佳化
* Interviewee 打字時盡量不要轉頭
Sign in with Wallet
Connect another wallet