# 2023 年「資訊科技產業專案設計」作業 1
> 貢獻者: Huaxin
[video](https://hackmd.io/kl3nsNJvTgSYYZbSPjRjsw)
[27 Remove Element 模擬面試錄影(英)](https://youtu.be/_TKTRMeKKsE)
[114 Flatten Binary Tree to Linked List 模擬面試錄影(漢)](https://youtu.be/T60QqxKx-oc)
[876 Middle of the Linked List 模擬面試錄影(漢)](https://youtu.be/T7e4fpKFIAY)
## 自評-程式部分
* 比較擔心裡所想的，不一定能以程式很好的呈現出來，有一段落差在
## 自評-面試過程
* 表達很簡單的內容時，常常複雜化
* 說話表達並沒有這麼流利，需要透過錄影多練習自我表達，並透過影片發覺自己的問題點
* 英文口說時，很擔心因為說錯而被扣分，會想盡可能避免文法錯誤，但容易很卡
## 自評-嘗試改進部分
紀錄時間 : 2023/09/15
透過檢視他人檢討過程，也同時檢討自己自身的問題，[參考文件](https://hackmd.io/@sysprog/H1J64cMHt)
* 要避免自身思考過久，雙方沉默許久
* 盡量將正在思考的過程說明出來，讓面試官理解你對這一問題的思路是什麼
* 倘若該題存在 complecity 限制，在說明 approach 時也應該提到，為何該 approach 可以符合 complecity 限制。
* 自已過去在說明 approach 並不會主動說明 time complecity 和 space complecity 並帶入例子說明，關於這一點後續錄影我會補上
* 遇到短時間內無法想出解法的題目，可以主動告知面試官，我會安靜一兩分鐘思考
## [27. Remove Element](https://leetcode.com/problems/remove-element/description/)
🧔：interviewer 👶：interviewee
🧔: We have a problem. Given an integer array nums and an integer val. Please attempt to remove all occurences of val in nums and return the number of elements in nums which are not equal to val. The number which are not equal to val is k. Additionally, you need to consider that the first elemtents in nums are not equal to val.Don't concern the remaining elements.
### repeat
👶: I will receive an integer array and an integer val. Then return the count of k elements that are not equal to to val in the array. Also, the first k elements in the array are not equal to val, right?
🧔：That's right. note that all yout operations will be performed on the integer array you get.
### example
👶：
Okay, let me give you an example, assuming our input is below
input: [5,1,5,3], val 為 5
output: [1,3,,] , k 為 2
The two last elements in the integer array are not considered, and the order of my 1 and 3 can be rearranged. Is my understanding correct?
🧔：
Yes, it doesn't affect the final accuracy.
### approach
👶：
Here , I will use an integer to keep track of the current position in the array where the value is not val. This integer is used for inserting new elements that are not val and also for returning the final count of elements that are not val. Next, I will use a for loop to iterate through all elements in the integer array one by one. In this way, the time complecity is O(n), and the space complecity is O(1).
🧔：OKay, Start now.
### code
👶：
```c++=
int removeElement(vector<int>& nums, int val) {
int k= 0;
for(int i=0;i<nums.size();i++){
if(nums[i]!=val){
nums[k] = nums[i];
k++;
}
}
return k;
}
```
we declare an integer k ,and then use a for loop to iterate through each element. If the current element is not equal to val. we insert it starting from the first element of nums, and increment k to prepare for the next inserion position.
After the traversal, return the next available position for inserting elements that are not equal to "val."
### test
👶：
1. Suppose we have an array [1,5,1,6] and val is 1. At i=0, we check if nums[0] is not equal to 1. If it's not, we skip it. The current nums is [1,5,1,6].
2. At i=1, we check if nums[1] is not equal to 1. If it is,we insert nums[1] at position k=0, and then increment k. The current nums is [5,5,1,6]
3. At i=2, the nums is [5,5,1,6]
4. At i=3, the nums is [5,6,1,6]
5. Finally, we return k with a value of 2.
## [876. Middle of the Linked List](https://leetcode.com/problems/middle-of-the-linked-list/)
🧔：interviewer 👶：interviewee
🧔：給你單獨一個 linked list 的 head，請你返回該 linked list 的 middle node。
假設碰到兩個 middle node 麻煩請返回第二個 middle node。
### repeat
👶：我會拿到一個 linked list 的 head ，然後嘗試去找出 linked list 的 middle node 對嗎?
🧔：是的沒錯，注意若存在兩個 middle node 記得返回第二個。
### example
👶：例如有一個 linked list 為 5->8->9->10，此時中間存在兩個 middle ，最終我必須返回 node 9。
🧔：對。
### approach
👶：我想用兩個 pointer，分別名為 middle 和 final。以下為我的想法
* 一開始讓 middle = head，final = head
* 使用 while loop 並每次判斷 final 和 final->next 是否都存在
* /** while 內部**/
* middle 每一次走一步
* final 每一次走兩步
* 最後返回 middle pointer
關於時間複雜度為 O(N)，因為遍尋時間為線性，也就是 linked list 的長度。
空間複雜度為 O(1)，因為只用了兩個指標，為 constant。
🧔：好
### code
👶：
```c++=
ListNode* middleNode(ListNode* head) {
ListNode* final = head;
ListNode* middle = head;
while(final && final->next){
middle = middle->next;
final = final->next->next;
}
return middle;
}
```
1. 首先先宣告出兩個 pointer，然後它們指向 head
2. 建立一個 while loop 並每一次確認 final 和 final->next 是否同時存在
3. 接下來在每一次 while loop 中，middle 走一步，final 走兩步
4. 倘若發現 final 和 final->next 中任一個不存在便跳出 while loop
5. 最終返回 middle node
### test
👶：這裡我舉兩個不同長度 linked list 做說明，分別為 2->3->4，2->3->4->5
* Case 1 (2->3->4)
第一次 middle 走到 node 3，final 走到 node 4
第二次 判斷 `while(final && final->next)` 時，因 `final->next` 不成立跳出 while Loop, 返回 middle node
* Case 2 (2->3->4->5)
第一次 middle 走到 node 3，final 走到 node 4
第二次 判斷 `while(final && final->next)` 時成立，因為 `final->next` 存在，`final->next` 指向 null，因此 middle 走到 node 4，final 走到 null
第三次 跳出 while loop, 返回 middle node
🧔：如果嘗試把 while loop 的判斷式改成 `while(final)` 會發生什麼事
👶：我舉個例子好了，假設我們 linked list 為 2->5->7->9->10
第一次 middle 走到 node 5，final 走到 node 7
第二次 middle 走到 node 7，final 走到 node 10
第三次 middle 走到 node 9，final pointer 走第一步時並不會出錯，但在走第二步時便會碰到 access violation 的問題。
🧔：好
## [114. Flatten Binary Tree to Linked List](https://leetcode.com/problems/flatten-binary-tree-to-linked-list/description/?envType=study-plan-v2&envId=top-100-liked)
🧔：給你一個二元樹的 root，請你試著去攤平成一個 linked list，該 linked list 應該使用相同的 TreeNode class，其中右子樹會指向 list 的下一個節點並且左子樹為 null。
### repeat
👶：我會得到一個二元樹的 root，然後我要將該 tree 攤平成一個 linked list，其中右子樹會指向 list 的下一個節點並且左子樹為 null，對嗎?
🧔：是的。
### example
👶：假設我的 input 如下
```graphviz
digraph {
rankdir=TB
node [shape="block"]
node1 [label="1"]
node2 [label="2"]
node3 [label="3"]
node4 [label="4"]
// node5 [label="5"]
// node6 [label="6"]
null0 [shape=none, label="NULL"]
null1 [shape=none, label="NULL"]
null2 [shape=none, label="NULL"]
// null3 [shape=none, label="NULL"]
// null4 [shape=none, label="NULL"]
// {rank=same; null1; node5;}
node1->5->6->null0
5->null1
6->null2
node1->node2
node2->node3
node2->node4
}
```
然後最後 output 如下
```graphviz
digraph {
rankdir=TB
node [shape="block"]
// node5 [label="5"]
// node6 [label="6"]
null0 [shape=none, label="NULL"]
null1 [shape=none, label="NULL"]
null2 [shape=none, label="NULL"]
null3 [shape=none, label="NULL"]
null4 [shape=none, label="NULL"]
null5 [shape=none, label="NULL"]
null6 [shape=none, label="NULL"]
// {rank=same; null1; node5;}
1->2
1->null0
2->3
2->null1
3->4
3->null2
4->5
4->null3
5->6
5->null6
6->null4
6->null5
}
```
🧔：是的
### approach
👶：
* 嘗試寫一個 while loop
-> /** 每一次 loop **/
-> 取得 root 的 left 然後再往剛剛取得的 root->left 的 right 走到底
-> 將走到底節點的 right 指向 root 的 right
-> 再將 root 的 right 指向 root 的 left
-> 將 root 的 left 指向 null
-> 最後將 root 往 right 移動一步
🧔：那該方法的時間複雜度和時間複雜度是?
👶：該方法的時間複雜度取決於節點數量，所以為 O(n)，空間複雜度為O(1)
### code
👶：
```c++=
void flatten(TreeNode* root) {
TreeNode* curr = root;
while(curr){
if(curr->left){
TreeNode* p = curr->left;
while(p->right){
p = p->right;
}
p->right = curr->right;
curr->right = curr->left;
curr->left = NULL;
}
curr = curr->right;
}
}
```
1. 宣告出兩個 poiners，分別為 curr 和 p，curr 用來顯示當前 root 位置，p 則是表示 root 的左子樹中最右側的節點
2. 當 curr 的 left 存在時便嘗試取得，接著再嘗試取最右側的 right subnode 為 p。
3. 將 p 的 right child pointer 指向 curr 的 right subnode，再將 curr 的 right child poiner 指向 curr 的 left child pointer，最後將 curr 的 left child pointer 指向 null。
4. 然後將 curr 往 right subnode 移動
🧔：我看完後發現，你有個地方會重複記憶體分配和釋放，你的想法是 ?
👶：我觀察了我的程式碼並且比對您剛剛提到的想法，在 while loop 中會重複為 p 分配記憶體，造成額外的計算成本，可以將 p 在 while loop 前提前宣告，來改善此問題。
```c++=
void flatten(TreeNode* root) {
TreeNode* curr = root;
TreeNode* p = new TreeNode();
while(curr){
if(curr->left){
p = curr->left;
while(p->right){
p = p->right;
}
p->right = curr->right;
curr->right = curr->left;
curr->left = NULL;
}
curr = curr->right;
}
}
```
🧔：是的，因為當你 root 的 left 要處理的次數增加時，你的運算成本便會增加
### test
👶：這裡我們以下方例子做示範
step 1
```graphviz
digraph {
rankdir=TB
node [shape="block"]
// node5 [label="5"]
// node6 [label="6"]
null0 [shape=none, label="NULL"]
null1 [shape=none, label="NULL"]
null2 [shape=none, label="NULL"]
null3 [shape=none, label="NULL"]
null4 [shape=none, label="NULL"]
// null5 [shape=none, label="NULL"]
// null6 [shape=none, label="NULL"]
// {rank=same; null1; node5;}
1->2
3->null2
3->null3
4->null1
4->null4
1->5->6
5->null0
2->3
2->4
}
```
嘗試將 root 的左子樹的最右節點，node 4，指向 root 的右子節點，node 5
step 2
```graphviz
digraph {
rankdir=TB
node [shape="block"]
// node5 [label="5"]
// node6 [label="6"]
empty0 [shape=none, label=""]
null0 [shape=none, label="NULL"]
null1 [shape=none, label="NULL"]
null2 [shape=none, label="NULL"]
null3 [shape=none, label="NULL"]
// null4 [shape=none, label="NULL"]
// null5 [shape=none, label="NULL"]
// null6 [shape=none, label="NULL"]
// {rank=same; null1; node5;}
1->2
1->5->6
5->null0
2->3
3->null2
3->null3
2->4
4->5
4->null1
}
```
再將 root 的 right 指向 node 2，則 root 的 left 指向 null，然後 root 往右子節點移動
step 3
```graphviz
digraph {
rankdir=TB
node [shape="block"]
// node5 [label="5"]
// node6 [label="6"]
empty0 [shape=none, label=""]
null0 [shape=none, label="NULL"]
null1 [shape=none, label="NULL"]
null2 [shape=none, label="NULL"]
null3 [shape=none, label="NULL"]
null4 [shape=none, label="NULL"]
// null5 [shape=none, label="NULL"]
// null6 [shape=none, label="NULL"]
// {rank=same; null1; node5;}
1->null1
1->2
6->null0
6->null3
2->3
2->4
4->5->6
4->null2
5->null4
}
```
以下重複上面所述動作
step 4
```graphviz
digraph {
rankdir=TB
node [shape="block"]
node3 [label="3"]
// node6 [label="6"]
null0 [shape=none, label="NULL"]
null1 [shape=none, label="NULL"]
null2 [shape=none, label="NULL"]
null3 [shape=none, label="NULL"]
null4 [shape=none, label="NULL", rank=max]
null5 [shape=none, label="NULL"]
null6 [shape=none, label="NULL"]
{rank=same; null4; node3;}
1->null1
// 1->5->6
1->2
6->null0
6->null3
2->node3
2->null4
node3->null5
node3->4
4->5->6
5->null6
4->null2
}
```
step 5
```graphviz
digraph {
rankdir=TB
node [shape="block"]
// node6 [label="6"]
null0 [shape=none, label="NULL"]
null1 [shape=none, label="NULL"]
null2 [shape=none, label="NULL"]
null3 [shape=none, label="NULL"]
null4 [shape=none, label="NULL"]
null5 [shape=none, label="NULL"]
null6 [shape=none, label="NULL"]
1->null1
// 1->5->6
1->2
6->null0
6->null3
2->3
2->null4
3->null5
3->4
4->5->6
5->null6
4->null2
}
```
## 總體初步檢討
Sign in with Wallet
Connect another wallet