---
tags: 資訊科技產業專案設計作業
---
# 2022 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2022)」作業 1
> 貢獻者: 威爾 will
> [video1](https://www.youtube.com/watch?v=DfnONCAPgGo)、[video2](https://www.youtube.com/watch?v=XJInRbG92No)

🧔：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

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

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);
}

## [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 是否為對稱樹
👶：另外寫程式時還要注意到子樹是空的的情況

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

 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;
}

# info2022-homework2
### [面試檢討 - 他評 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 打字時盡量不要轉頭