---
tags: info2023-homework1
---
# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者: 新鮮柿-Shizi
>👺: interviewer1
>👹: interviewer2
>🤡: interviewee
>
[影片1(漢題目1、2)](https://www.youtube.com/watch?v=K0tznWPiJGw)
[影片2(英題目3)](https://www.youtube.com/watch?v=ojbGrV7jwhQ)
《**以下為大略逐字稿,並非與影片完全相同**》
## [283. Move Zero](https://leetcode.com/problems/move-zeroes/?envType=study-plan-v2&envId=leetcode-75)
👺:
你好,歡迎你來面試我們公司,我是本公司的軟韌工程師Sam,沒問題的話就開始今天的面試。今天的部分一共有兩題,都在我傳給你的 Google Docs 裡面,那麼我大致講解一下題目,第一題,我希望你設計一個函式將一個array中所有等於零的元素移至array的末段。
🤡:
**Repeat:**
我想確認一下,當我將所有為零的元素移動到array的末段時,可以動到原本非零值的順序嗎?
👺:
不行,你必須保持原本非零元素的相對順序,對了我希望你使用不回傳值的函式。
🤡:
**Example:**
好的,那我想舉個例子確認一下我的理解是否正確。
輸入: `[0,1,0,3,12]`
輸出: `[1,3,12,0,0]`
👺:
沒錯!
🤡:
**Approach:**
那我大致說明我現在對此題目的想法,我會希望用一個for迴圈檢查整個array,當有元素等於零的元素時,用以計數的變數就會加一,反之,不等於零則將元素加入輸出的array中。最後再跑一個for迴圈,依據計數變數的值判斷要再加幾個零元素到輸出array的末段。
👺:
聽起來大致沒問題,那麼開始coding吧!
🤡:
**Code:**
```cpp
void moveZeroes(vector<int>& nums) {
vector<int> v;
int size = nums.size();
int count = 0;
for(int i=0; i<size; i++){
if(nums[i] == 0){
count ++;
}
else{
v.push_back(nums[i]);
}
};
for( int i = 0; i<count; i++){
v.push_back(0);
};
nums = v;
};
```
1. 先宣告一個vector v來儲存輸出元素。
1. 宣告一個int count用以計算零元素數量。
1. for迴圈檢查nums,如果元素等於零,`count++`,反之,將元素push_back到vector v中。
1. for迴圈push_back零到vector v中。
1. 因為使用void函式,不能直接迴傳,所以用v取代原本的array nums。
**Test:**
舉個例子,測試看看:
1. **輸入vector nums:** [2,1,0,3] **vector v:**[] **計數int count**: 0
2. **輸入vector nums:** [**2**,1,0,3] **vector v:**[2] **計數int count**: 0
3. **輸入vector nums:** [2,**1**,0,3] **vector v:**[2,1] **計數int count**: 0
4. **輸入vector nums:** [2,1,**0**,3] **vector v:**[2,1] **計數int count**: 1
5. **輸入vector nums:** [2,1,0,**3**] **vector v:**[2,1,3] **計數int count**: 1
count = 1,加一個零-----> **vector v:**[2,1,3,0]
👺:
看起來是還不錯,時間複雜度已經到了O(n+m)的等級了,不過我認為不管是再執行速度以及空間使用率都還能再更好,我想請問你是否還有其他方法嗎?
🤡:
**Optimization:**
我試試看用兩個旗標的方式,一個旗標用來走訪整個輸入array,另一個則用來標示要swap的元素位置。
```cpp
void moveZeroes(vector<int>& nums) {
int nonZeroIndex = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] != 0) {
swap(nums[i], nums[nonZeroIndex++]);//swap 完後加1
}
```
1. 宣告一個變數 nonZeroIndex用以標示要被swap的元素位置。
2. for迴圈走訪整個array,每當發現非零元素,與nonZeroIndex旗標位置元素swap。
3. 換完後,nonZeroIndex旗標往後移一個位置: `nonZeroIndex++`。
4. 最後為零的元素會因為沒被置換到前面的位置而自動趨於末段。
這個方法不僅減少了宣告次數,也減少了for迴圈迭代的次數,時間複雜度降至*O(n)*,並且程式碼也變得更加整潔。
## [48. Rotate Image](https://leetcode.com/problems/rotate-image/description/)
👺:
那接下來進入第二題,我也大致說明一下題目,我希望你將一個 $n \times n$ 的二維矩陣做順時針旋轉90度,並且必須in-place。
🤡:
**Repeat:**
將一個 $n \times n$ 的二維矩陣做順時針旋轉90度,並且必須in-place,我想問這裡的in-place的意思是否為在coding過程中不能另外宣告其他矩陣計算?
👺:
可以這麼說,也就是你只能藉由更改原本的矩陣來得到結果。
🤡:
**Example:**
OK,那我想舉個例子確認一下我的理解是否正確。
輸入: `[[1,2,3],[4,5,6],[7,8,9]]`
| 1 | 2 | 3 |
| --- | --- | --- |
| **4** | **5** | **6** |
| **7** | **8** | **9**|
輸出: `[[7,4,1],[8,5,2],[9,6,3]]`
| 7 | 4 | 1 |
| --- | --- | --- |
| **8** | **5** | **2** |
| **9** | **6** | **3** |
👺:
就是如此!
🤡:
**Approach:**
這題的話,我會想要將矩陣的上下做對換,以我剛剛的例子說明:
| 1 | 2 | 3 |
| --- | --- | --- |
| **4** | **5** | **6** |
| **7** | **8** | **9**|
==上下對調==
| 7 | 8 | 9 |
| --- | --- | --- |
| **4** | **5** | **6** |
| **1** | **2** | **3**|
接者,作轉置(也就是`matrix[i][j]` $\to$ `matrix[j][i]`):
| 7 | 8 | 9 |
| --- | --- | --- |
| **4** | **5** | **6** |
| **1** | **2** | **3**|
==轉置==
| 7 | 4 | 1 |
| --- | --- | --- |
| **8** | **5** | **2** |
| **9** | **6** | **3**|
即可獲得一個順時針旋轉90度的矩陣。
👺:
看起來沒問題,你可以開始coding了。
🤡:
**Code:**
```cpp
void rotate(vector<vector<int>>& matrix) {
int n = size(matrix);
for(int i = 0; i < n/2; i++){
for(int j = 0; j < n;j++){
int temp = matrix[i][j];
matrix[i][j] = matrix[n - i - 1][j];
matrix[n - i - 1][j] = temp;
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j <= i; j++){
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
```
1. 宣告 int n 儲存矩陣的size。
2. 跑一個雙層for迴圈做上下置換,因為對稱的上下置換,所以只需跑n/2次。
3. 再跑一個雙層for迴圈做轉置。
**Test:**
拿上面的例子來測試看看:
輸入: `[[1,2,3],[4,5,6],[7,8,9]]`
n = 3,第一個for迴圈:n/2 = 1,所以i只跑到1。
**第一個for迴圈:**
上下置換
i = 0:
* j = 0: matrix[0][0]、matrix[2][0] 對調。
* j = 1: matrix[0][1]、matrix[2][1] 對調。
* j = 2: matrix[0][2]、matrix[2][2] 對調。
i = 1:
* j = 0: matrix[1][0]、matrix[1][0] 對調。
* j = 1: matrix[1][1]、matrix[1][1] 對調。
* j = 2: matrix[1][2]、matrix[1][2] 對調。
**第二個for迴圈:**
轉置
i = 0:
* j = 0: matrix[0][0]、matrix[0][0] 對調。
i = 1:
* j = 0: matrix[1][0]、matrix[0][1] 對調。
* j = 1: matrix[1][1]、matrix[1][1] 對調。
i = 2:
* j = 0: matrix[2][0]、matrix[0][2] 對調。
* j = 1: matrix[2][1]、matrix[1][2] 對調。
* j = 2: matrix[2][2]、matrix[2][2] 對調。
👺:
看起來沒麼問題,雖然已到達本題理論上時間複雜度的上限O(n^2^),不過我發現有許多地方還能再改進,我想請問你是否有可以改進本code的想法?
🤡:
**Optimization:**
我發現有這個程式碼有幾個可以改進的地方:
1. 上下置換以及轉置時,有同位置元素對調的多於時間浪費。
2. 程式碼可以再精簡一些。
因此,我將程式碼改為:
```cpp
void rotate(vector<vector<int>>& matrix) {
int n = size(matrix);
for(int i = 0; i < n/2; i++){
for(int j = 0; j < n;j++){
if(i == n - i - 1){
break;
}
swap(matrix[i][j],matrix[n - i - 1][j]);
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
swap(matrix[i][j], matrix[j][i]);
}
}
}
```
1. 上下置換以及轉置時,有同位置元素對調的多於時間浪費。
改進方式:
再第一個for迴圈中增加一個判斷式: `if(i == n - i - 1){break;}`,以及把第二個for迴圈中 j <= i改為 j < i。
2. 程式碼可以再精簡一些。
改進方式:
改用swap()來實現元素位置對調。
👺:
大致OK,那今天的面試就結束了,如果有再通知您,第二階段面試將會使用英文面試,掰掰!!!
## [104. Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/)
👹:
Hello,my name is Luke and i'm the software engineer in this company.Today,I have one coding question want you to answer.The question is in the google doc which I sent to you.I breifly explain the question. I will give you a binary tree and you need to return it's maximum depth and the struct of treenode is also in the google doc.
```cpp
//Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
```
🤡:
**Repeat:**
OK! So,I need to find the maximum depth for the input binary tree.I have one quenstion: Is the root node included in the depth calculation?
👹:
Yes,it is.
**Example**
🤡:
I want to give an example to confirm whether my understanding is correct.
```
1
/ \
2 3
/
4
depth = 3
```
It's that right?
👹:
Yes,it is. So,do you have any idea for this question?
🤡:
**Approach:**
I would like to use DFS by recursion to solve this question.
👹:
OK,go ahead.
🤡:
**Code:**
```cpp
int maxDepth(TreeNode* root) {
if (root == NULL){
return 0;
}
return 1+ max(maxDepth(root->left), maxDepth(root->right));
}
```
I think it is the easiest understandable solution. Using recursive to check the maximum depth of left subtree and right subtree for all elements and add on one conditional statement if (root == NULL),then that means there's no elements in the binary tree.
**Test:**
🤡:
Let me give an example to test this code.
1
/ \
2 3
/
4
1. 1 + max(maxDepth(root->left), maxDepth(root->right)) root = 1
2. 1 + max(maxDepth(root->left), maxDepth(root->right)) root = 2 ; 1 + max(maxDepth(root->left), maxDepth(root->right)) root = 3
3. 1 + max(maxDepth(root->left), maxDepth(root->right)) root = 4
4. return 0
5. return 1
6. return 1+1
7. return 1+1+1
👹:
Mmmmmm.... I think using recursion is a little slow. Do you have another approach to reduce the time spent?
🤡:
**Optimization:**
I think i can try using iteration(BFS) to reduce the time spent.
```cpp
int maxDepth(TreeNode* root) {
if (root == NULL){
return 0;
}
queue<TreeNode*> q;
q.push(root);
int depth = 0;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
if (node->left){
q.push(node->left);
}
if (node->right){
q.push(node->right);
}
}
depth++;
}
return depth;
}
```
👹:
OK!The interview for today is done. We'll let you know if there's any news.Bye!!!
# 初步自我檢討
**針對interviewer:**
(漢)
* 有點太死氣沉沉。
* 講話卡卡的,比interviewee還卡。
* 題目描述不夠清晰。
(英)
* 英文口說還需要加強,講話講起來卡卡的,雖然說中文也卡卡的。
整體:
* 太過口語化。
* 有面試主導權沒有握在自己手上的感覺。
* OK真的說太多次了。
**針對interviewee:**
(漢)
* 說話不夠清晰。
(英)
* 英文口說還需要加強(書畫的換氣點、發音、語助詞使用過多)。
* 英文的術語要注意。
* 有些地方發音要注意像是**B**FS與**D**FS。
* 題目說明的地方樹的節點可以改成用ABC來做記號,比較不會搞混。
* TreeNode題目的N大寫,面試時未注意,以後要多注意細節。
* 改善的方法要說明一下程式碼。
* 迭代不一定會比較好,還容易出錯。
整體:
* 要記得介紹自己。
* 要心平氣和。
* 注意語助詞。
* 語調太過平淡。
* 有時候回答問題不夠精確。
# 他評區
## 第二次作業-他評01
### 關於interviewer
### 優點
* 說話清楚、聲音穩定。
* 英文通順。
### 可改進的地方
* 針對 Test 和 Optimize 的部分可以進一步詢問。
### 關於interviewee
### 優點
* 說話清楚、聲音穩定。
* 有將思考方向先當作註解寫在 google doc 上。
* 詢問並根據題目敘述舉出例子。
* 有測試寫出來的程式。
* 英文通順。
### 可改進的地方
* 可以詢問題目限制,像是參數和回傳值的型態、範圍。
* 影片中的縮排有時會少 } 、 ; 、 Tab 等等。
* 有忘記討論空間、時間複雜度的情形。
* 283. Move Zeroes
* [1:36](https://youtu.be/K0tznWPiJGw?t=96) 兩道題目可以分開,避免畫面混亂。
* 48. Rotate Image
* 可以測試 Optimization 的部分。
* 104. Maximum Depth of Binary Tree
* 可以多舉幾個例子
* 若有時間,可用例子將 BFS 的程式走一遍。
# 第二次作業-他評02
## interviewer
### 優點:
- 英文流利清楚
- 台風穩
### 可改進的地方
- 可以增加一些延伸變化題測面試者的反應
- [47:29]( https://www.youtube.com/watch?v=K0tznWPiJGw&ab_channel=%E3%80%8C%E8%B3%87%E8%A8%8A%E7%A7%91%E6%8A%80%E7%94%A2%E6%A5%AD%E5%B0%88%E6%A1%88%E8%A8%AD%E8%A8%88%E3%80%8D%E8%AA%B2%E7%A8%8B%28%E5%AD%B8%E5%93%A1%E5%B0%88%E5%8D%80%29?t=2849) 這邊請面試者在重複一次之前的話,可以改為問兩個方法的時間空間複雜度比較
## interviewee
### 優點:
- [7:04]( https://www.youtube.com/watch?v=ojbGrV7jwhQ&ab_channel=%E3%80%8C%E8%B3%87%E8%A8%8A%E7%A7%91%E6%8A%80%E7%94%A2%E6%A5%AD%E5%B0%88%E6%A1%88%E8%A8%AD%E8%A8%88%E3%80%8D%E8%AA%B2%E7%A8%8B%28%E5%AD%B8%E5%93%A1%E5%B0%88%E5%8D%80%29?t=424 ) REACT都有做到
- [37:03]( https://www.youtube.com/watch?v=K0tznWPiJGw&ab_channel=%E3%80%8C%E8%B3%87%E8%A8%8A%E7%A7%91%E6%8A%80%E7%94%A2%E6%A5%AD%E5%B0%88%E6%A1%88%E8%A8%AD%E8%A8%88%E3%80%8D%E8%AA%B2%E7%A8%8B%28%E5%AD%B8%E5%93%A1%E5%B0%88%E5%8D%80%29?t=2363) test階段詳細
- [40:25]( https://www.youtube.com/watch?v=K0tznWPiJGw&ab_channel=%E3%80%8C%E8%B3%87%E8%A8%8A%E7%A7%91%E6%8A%80%E7%94%A2%E6%A5%AD%E5%B0%88%E6%A1%88%E8%A8%AD%E8%A8%88%E3%80%8D%E8%AA%B2%E7%A8%8B%28%E5%AD%B8%E5%93%A1%E5%B0%88%E5%8D%80%29?t=2425) 改進方向明確
- [21:33](https://www.youtube.com/watch?v=K0tznWPiJGw&ab_channel=%E3%80%8C%E8%B3%87%E8%A8%8A%E7%A7%91%E6%8A%80%E7%94%A2%E6%A5%AD%E5%B0%88%E6%A1%88%E8%A8%AD%E8%A8%88%E3%80%8D%E8%AA%B2%E7%A8%8B%28%E5%AD%B8%E5%93%A1%E5%B0%88%E5%8D%80%29?t=1293) 這邊的approach講的恰到好處,讓面試者清楚知道你要怎麼做
### 可改進的地方
- [5:59](https://www.youtube.com/watch?v=ojbGrV7jwhQ&ab_channel=%E3%80%8C%E8%B3%87%E8%A8%8A%E7%A7%91%E6%8A%80%E7%94%A2%E6%A5%AD%E5%B0%88%E6%A1%88%E8%A8%AD%E8%A8%88%E3%80%8D%E8%AA%B2%E7%A8%8B%28%E5%AD%B8%E5%93%A1%E5%B0%88%E5%8D%80%29?t=359 ) 影篇中說因為node2 has no children, so it’ll return 0,
如果說完整是要在呼叫下一次遞迴maxdepth(node2->left)時發現此時root為null,return 0,所以maxdepth(node: 2) = 1,可能比較完整
- 英文題目,Move Zero沒有討論到時間空間複雜度
- [7:41]( https://www.youtube.com/watch?v=ojbGrV7jwhQ&ab_channel=%E3%80%8C%E8%B3%87%E8%A8%8A%E7%A7%91%E6%8A%80%E7%94%A2%E6%A5%AD%E5%B0%88%E6%A1%88%E8%A8%AD%E8%A8%88%E3%80%8D%E8%AA%B2%E7%A8%8B%28%E5%AD%B8%E5%93%A1%E5%B0%88%E5%8D%80%29?t=461 ) 對於使用iteration作為approach可以在多說明一些實際要做的事-
- [11:39]( https://www.youtube.com/watch?v=ojbGrV7jwhQ&ab_channel=%E3%80%8C%E8%B3%87%E8%A8%8A%E7%A7%91%E6%8A%80%E7%94%A2%E6%A5%AD%E5%B0%88%E6%A1%88%E8%A8%AD%E8%A8%88%E3%80%8D%E8%AA%B2%E7%A8%8B%28%E5%AD%B8%E5%93%A1%E5%B0%88%E5%8D%80%29?t=699 ) 寫程式當下可以邊講這一步在作什麼
- [15:03]( https://www.youtube.com/watch?v=K0tznWPiJGw&ab_channel=%E3%80%8C%E8%B3%87%E8%A8%8A%E7%A7%91%E6%8A%80%E7%94%A2%E6%A5%AD%E5%B0%88%E6%A1%88%E8%A8%AD%E8%A8%88%E3%80%8D%E8%AA%B2%E7%A8%8B%28%E5%AD%B8%E5%93%A1%E5%B0%88%E5%8D%80%29?t=903) 寫完程式碼後,這邊說舉個例子來解釋一下,或許說來測試一下比較好,就進入test階段了
- [43:58]( https://www.youtube.com/watch?v=K0tznWPiJGw&ab_channel=%E3%80%8C%E8%B3%87%E8%A8%8A%E7%A7%91%E6%8A%80%E7%94%A2%E6%A5%AD%E5%B0%88%E6%A1%88%E8%A8%AD%E8%A8%88%E3%80%8D%E8%AA%B2%E7%A8%8B%28%E5%AD%B8%E5%93%A1%E5%B0%88%E5%8D%80%29?t=2638) if( )當中的等號打成assign
## 第二次作業-他評03
### interviewer
- [ ] 優點
* 口齒清晰
- [ ] 可改進的地方
* [1:22](https://youtu.be/K0tznWPiJGw?t=82)可以將不同題目放在不同頁面。
* 互動較少,可以提問的多一點。
### interviewee
- [ ] 優點
* REACTO 做的很詳細!
* TEST 部分講解部分很清楚!
- [ ] 可改進的地方
* 如果邊打 code 邊說明不太順的話,可以先在寫之前講解一下你要怎麼做。
* [1:34](https://youtu.be/ojbGrV7jwhQ?t=94) 盡量避免扶臉,會給人一種面試很無聊的感覺。
## 第二次作業-他評 04
- [ ] 可改進的地方
* [0:30](https://youtu.be/ojbGrV7jwhQ?t=30): 針對 [104. Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/),開頭的 "I need to find the maximum depth" 很突兀,應該先描述應用場景 (最好跟公司專案有關),然後才講需求。打開 YouTube 字幕,觀察自動辨識出的單字和口說的差異。
* [詢問 ChatGPT](https://chat.openai.com/share/cfd83238-1a9f-487f-af49-cdcb0b676689),得到 "maximum depth of binary tree" 的應用場景,interviewer 也可利用本題目,跟 interviwee 討論更多已知的應用場景。
* Efficient Data Storage: In computer science, binary trees are commonly used to implement data structures like binary search trees (BST) or balanced binary trees (e.g., AVL or Red-Black trees). The maximum depth of such trees directly impacts their performance. A balanced tree with a lower maximum depth ensures that search, insertion, and deletion operations are more efficient, as the depth of the tree is a key factor in determining the time complexity of these operations.
* Algorithms and Searching: Algorithms like binary search and various tree traversal algorithms rely on understanding the depth of a binary tree. For example, binary search in a balanced binary search tree is a highly efficient way to search for an element, with a time complexity of O(log N) for a tree with N nodes. The logarithmic nature of this time complexity is due to the balanced tree structure and its limited depth.
* Database Indexing: In databases, B-trees and B+ trees are commonly used to index and manage large datasets. The maximum depth of these trees affects query performance. A shallower tree means faster access to data, which is crucial for efficient database operations.
* Network Routing: In computer networks, binary trees can be used to represent routing tables. A shallow tree means quicker routing decisions, reducing latency in data transmission.
* [0:39](https://youtu.be/ojbGrV7jwhQ?t=39): 對照看 YouTube 自動辨識的字幕,原本的 depth 被判定為 "death"。提問的 "Is root node included in depth calculation?" 可改為 "Is the root node **counted** in the maximum depth of a binary tree? 會更明確,而且這也是 REACTO 的 "Repeat" 階段。
* [0:54](https://youtu.be/ojbGrV7jwhQ?t=54): 不用說 "I want to give the example to confirm whether my understanding is correct.",若真的在意禮貌,可改說 "To validate my understanding of the requirements, I would like to go through some examples. Please advise if I make any mistakes."
* [1:11](https://youtu.be/ojbGrV7jwhQ?t=71): "like this binary tree" 聽起來很突兀,特別是前面你沒有發話,不易猜出到底是「像誰」。可改說 "Consider a binary tree constructed with 1 as the root node, to which we then add two children nodes, 2 and 3."。「口語化」很好
* [1:24](https://youtu.be/ojbGrV7jwhQ?t=84): 作為 interviewer 不該急著說 "That's right. Do you have any idea for this question?",這無助於溝通,可請對方準備其他案例,像是 [skewed binary tree](https://www.geeksforgeeks.org/skewed-binary-tree/),注意,原本的題目沒有要求要平衡 (balanced)
* [1:31](https://youtu.be/ojbGrV7jwhQ?t=91): 托腮講出 "I would like to use ..." 好嬌貴啊,"DFS with recursion" 無法完整解釋你如何解決問題,寧可多用幾句話來描述。例如: "Based on the definition, to find the depth, we should determine the path length from the root to the deepest leaf node, which may be in either the left or right subtree. In other words, the longest path from the root to the deepest leaf can traverse either the left or right child of the root. Therefore, the best approach is to calculate the depth of the left and right subtrees recursively. We take the maximum depth from either subtree and add 1 to obtain the depth of the tree.
* [1:41](https://youtu.be/ojbGrV7jwhQ?t=101): 注意手勢,看起來就像在耍帥 若有所思但又不針對隻字片語進行互動,就喪失討論的效果。
* [4:11](https://youtu.be/ojbGrV7jwhQ?t=251): 既然強調遞迴,可先寫遞迴式,也就是畫面中的敘述,然後再補上 max 和 `root == NULL` 等敘述
---