2023 年「資訊科技產業專案設計」作業 1

貢獻者: Huaxin
Remove Element 模擬面試錄影(英)
Flatten Binary Tree to Linked List 模擬面試錄影(漢)
Middle of the Linked List 模擬面試錄影(漢)

自評

程式部分

比較擔心裡所想的，不一定能以程式很好的呈現出來，有一段落差在

[ ]面試過程

表達很簡單的內容時，常常複雜化
說話表達並沒有這麼流利，需要透過錄影多練習自我表達，並透過影片發覺自己的問題點
英文口說時，很擔心因為說錯而被扣分，會想盡可能避免文法錯誤，但容易很卡

嘗試改進部分

透過檢視他人檢討過程，也同時檢討自己自身的問題，參考文件
要避免自身思考過久，雙方沉默許久
- 盡量將正在思考的過程說明出來，讓面試官理解你對這一問題的思路是什麼
倘若該題存在 complecity 限制，在說明 approach 時也應該提到，為何該 approach 可以符合 complecity 限制。
自已過去在說明 approach 並不會主動說明 time complecity 和 space complecity 並帶入例子說明，關於這一點後續錄影我會補上
遇到短時間內無法想出解法的題目，可以主動告知面試官，我會安靜一兩分鐘思考

27. Remove Element

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

👶：

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

👶：

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].
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]
At i=2, the nums is [5,5,1,6]
At i=3, the nums is [5,6,1,6]
Finally, we return k with a value of 2.

876. 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

👶：

ListNode* middleNode(ListNode* head) {
    ListNode* final = head;
    ListNode* middle = head;
    while(final && final->next){
        middle = middle->next;
        final = final->next->next;
    }
    return middle;
}

首先先宣告出兩個 pointer，然後它們指向 head
建立一個 while loop 並每一次確認 final 和 final->next 是否同時存在
接下來在每一次 while loop 中，middle 走一步，final 走兩步
倘若發現 final 和 final->next 中任一個不存在便跳出 while loop
最終返回 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

🧔：給你一個二元樹的 root，請你試著去攤平成一個 linked list，該 linked list 應該使用相同的 TreeNode class，其中右子樹會指向 list 的下一個節點並且左子樹為 null。

repeat

👶：我會得到一個二元樹的 root，然後我要將該 tree 攤平成一個 linked list，其中右子樹會指向 list 的下一個節點並且左子樹為 null，對嗎?

🧔：是的。

example

👶：假設我的 input 如下

然後最後 output 如下

🧔：是的

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

👶：

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

宣告出兩個 poiners，分別為 curr 和 p，curr 用來顯示當前 root 位置，p 則是表示 root 的左子樹中最右側的節點
當 curr 的 left 存在時便嘗試取得，接著再嘗試取最右側的 right subnode 為 p。
將 p 的 right child pointer 指向 curr 的 right subnode，再將 curr 的 right child poiner 指向 curr 的 left child pointer，最後將 curr 的 left child pointer 指向 null。
然後將 curr 往 right subnode 移動

🧔：我看完後發現，你有個地方會重複記憶體分配和釋放，你的想法是 ?
👶：我觀察了我的程式碼並且比對您剛剛提到的想法，在 while loop 中會重複為 p 分配記憶體，造成額外的計算成本，可以將 p 在 while loop 前提前宣告，來改善此問題。

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

嘗試將 root 的左子樹的最右節點，node 4，指向 root 的右子節點，node 5
step 2

再將 root 的 right 指向 node 2，則 root 的 left 指向 null，然後 root 往右子節點移動
step 3

以下重複上面所述動作
step 4

step 5

總體初步檢討

針對interviewer的檢討:

Terrible english spelling, horrible to be honest
英文題目的部分, 應該至少有一個文件是寫題目敘述的, 題目長一點用講的誰會記得
是的！沒錯！講得非常生動, 迅速降低面試的緊張氣氛, 非常值得學習

針對interviewee的檢討:

在middle of linked list這題當中, 敘述approach的部分我認為表達清楚, 不過若能夠在表達的同時在文件上同時寫下一些幫助理解的文字, 可以讓整段思路更清楚的表達, 例如middle走一步, final走兩步就可以寫下來
都還沒把程式寫出來就突然自動說出時間複雜度, 感覺有背答案的嫌疑
白板提的程式不需要提交大小寫可能不用太在意, 不斷回頭去改變大小寫對於對於面試過程的流暢性不好
只有用test case來證明程式正確, 在一開始提出解法的時候也沒有說為什麼使用的解法可以找到正解
例如使用fast pointer來解middle of linked list的時候就可以算一點數學解釋為何middle最後會停在linked list中間

他評01

優點

英文口說部分咬字非常清楚!
對於樹的問題，有畫圖來解說，表達得很清楚。

可以改進的地方

(Middle of the Linked List) 03:02: 口誤，應為 final 為一次走兩步。
(Middle of the Linked List) while 迴圈的終止條件可以在撰寫之前來講解，讓面試官更清楚你是先思考後再撰寫程式碼。

他評02

優點
REACTO 做得不錯
在講解的時候表達滿清楚的
可以改進的地方
interviewer和interviewee之間的切換可以適當的留白

他評03

優點

再驗證程式可行性時有透過範例逐步將演算法運作的過程打在畫面上，能夠幫助interviewer理解。

可以改進的地方

英文面試開始時可以說明一下問題的應用場景，取代開頭直接說 "We have a problem"。

2023 年「資訊科技產業專案設計」作業 1

自評

27. Remove Element

repeat

example

approach

code

test

876. Middle of the Linked List

repeat

example

approach

code

test

114. Flatten Binary Tree to Linked List

repeat

example

approach

code

test

總體初步檢討

他評01

他評02

他評03

Read more

從 CPU cache coherence 談 Linux spinlock 可擴展能力議題

淺談 Microkernel 設計和真實世界中的應用

並行程式設計: 概念

並行程式設計: Lock-Free Programming