---
tags: info2022-homework1
---
# 2022 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2022)」作業 1
> 噠噠特工-LonelyBoy
> [模擬面試錄影(漢)](https://youtu.be/qPCbeHqyeyM)
> [模擬面試錄影(漢)](https://youtu.be/AeG7K2gU214)
> [模擬面試錄影(英)](https://youtu.be/8FgfWqh54OE)
## [73. Set Matrix Zeroes](https://leetcode.com/problems/set-matrix-zeroes/)
因為題目就有提供範例，所以一開始直接使用題目的範例去做example，然後在approach的時候也利用題目給的例子去幫助說明。
```cpp=
void setZeroes(vector<vector<int>>& matrix) {
vector<int> x;
vector<int> y;
for(int i=0; i<matrix.size(); i++){
for(int j=0; j<matrix[i].size(); j++){
if(matrix[i][j]==0){
if(!count(x.begin(), x.end(), i)){
x.push_back(i);
}
if(!count(y.begin(), y.end(), j)){
y.push_back(j);
}
}
}
}
for(int i=0; i<x.size(); i++){
for(int j=0; j<matrix[i].size(); j++){
matrix[x[i]][j] = 0;
}
}
for(int i=0; i<y.size(); i++){
for(int j=0; j<matrix.size(); j++){
matrix[j][y[i]] = 0;
}
}
//end
}
```
上面是本來我自己做這題最一開始的解法，但後來自己在計算複雜度時發現 O(m\*n\*(m+n)) 有點太高。後來就做了一些修改，這邊把我原本遇到的問題設計成面試流程。
```cpp=
void setZeroes(vector<vector<int>>& matrix) {
vector<int> x(matrix.size());
vector<int> y(matrix[0].size());
for(int i=0; i<matrix.size(); i++){
for(int j=0; j<matrix[i].size(); j++){
if(matrix[i][j]==0){
x[i] = 1;
y[j] = 1;
}
}
}
for(int i=0; i<x.size(); i++){
for(int j=0; j<matrix[i].size(); j++){
if(x[i]==1){
matrix[i][j] = 0;
}
}
}
for(int i=0; i<y.size(); i++){
for(int j=0; j<matrix.size(); j++){
if(y[i]==1){
matrix[j][i] = 0;
}
}
}
//end
}
```
最後有第二個follow up，是在寫完這題時去看答案發現有能降低空間複雜度到 O(1) 的方法，在這邊設計成第二個follow up。
### 自評
* 有些講解的部分會太細，其實後面一點的code就會寫到，但前面的時候就會一直急著代後面的觀念，應該配合後面的code一起講解也會比較清楚。
* 有些觀念有點從太底層講起了，其實面試官都會這些觀念，不要搞得好像在"教"他一樣。
* 影片裡面其實function我是定義成"solution"，這不太好，應該命名的精確一點。
* 一開始第二個follow up沒有甚麼想法的時候應該再丟更多討論而不是直接承認自己不會。
### 同儕檢討
#### interviewer
- [00:01](https://youtu.be/qPCbeHqyeyM?t=1) 盡量不要用面試官自稱，可以用自己的英文名字代替，或是說今天由我來主持這場面試。
- [00:49](https://youtu.be/qPCbeHqyeyM?t=49) 對in place algorithm的說明有點奇怪，應該是強調要在原本的資料結構內操作，而不是回傳一個新的空間。
- [15:28](https://youtu.be/qPCbeHqyeyM?t=928) 直接問能不能把時間複雜度優化成O(m*n)很怪，詢問能不能再提供其他思路來降低時間複雜度會比較好。
#### interviewee
- [01:25](https://youtu.be/qPCbeHqyeyM?t=85) 詢問例子或舉例的時候可以嘗試把example打出來，而不是用鼠標轉圈圈的方式。
- [03:34](https://youtu.be/qPCbeHqyeyM?t=214) 寫程式時口齒清晰。
- [03:34](https://youtu.be/qPCbeHqyeyM?t=214) 盡量不要跨頁寫程式，這樣看不到完整的，需要一直上下拉。
- [12:01](https://youtu.be/qPCbeHqyeyM?t=721) Interviewee好像沒有發現到他的寫法已經不符合 [in-place algorithm](https://en.wikipedia.org/wiki/In-place_algorithm)。
---
## [121. Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)
反問了題目講解不夠清楚的地方，並對edge case題目沒有給例子。自己舉了例子來確認自己的理解。
```cpp=
int maxProfit(vector<int>& prices) {
int min = 10001;
int max_profit = 0;
for(int i=0; i<prices.size(); i++){
if(prices[i]<min){
min = prices[i];
}
else if(prices[i]-min>max_profit){
max_profit = prices[i] - min;
}
}
return max_profit;
}
```
套用自己一開始舉的例子來test the program。
最後講解空間以及時間複雜度，並解釋原因。
### 同儕檢討
#### interviewer
- [00:04](https://www.youtube.com/watch?v=AeG7K2gU214?t=4) 時，interviewer不該自稱為面試官。
- [01:40](https://www.youtube.com/watch?v=AeG7K2gU214?t=100) 時，interviewer應在一開始講解題目時，就先把input的constraint說明清楚，而不是後續interviewee慢慢詢問。
- [12:25](https://www.youtube.com/watch?v=AeG7K2gU214?t=745) 時，提問時，避免只拋出「時間複雜度是什麼等級？」這樣的問題，這樣對話欠缺上下文，可能 interviewee 憑藉猜測或背誦做答，從而喪失鑑別度。
- 後續可以再多問題目的變形，像是：
1. 可以有不限次數的交易進行，那最大獲益為何？
2. 有限制次數的交易進行(如：最多Ｋ次)，那最大獲益為何？
#### interviewee
- [12:25](https://www.youtube.com/watch?v=AeG7K2gU214?t=745) 時，interviewee可以在coding完，自己去分析時間與空間複雜度。
- [12:50](https://www.youtube.com/watch?v=AeG7K2gU214?t=770) 時，掃過一次for迴圈，這裡應該為時間複雜度才對。
### 自評
* 做這題的時候雖然可能影片看不出來，但我其實內心有點背了答案了，都知道下一行要打甚麼了，可能比較沒辦法真的練到思考能力。
* 不要急著一直發話，一發話讓我有點沒有時間思考程式問題。
* 面試官可以表現得呈穩一點。
* 在一開始就先確認好題目的範圍限制，不要先急著打程式。
* 打字配合講解速度，不要有時候講很久又有些時候打很快。
---
## [94. Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/)
自己畫了一個binary tree，來講解recursive method的step，並有列出每個step。
```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) {}
* };
*/
vector<int> inorderTraversal(TreeNode* root) {
inorder(root);
return answer;
}
vector<int> answer;
void inorder(TreeNode* current){
if(current!=NULL){
inorder(current->left);
answer.push_back(current->val);
inorder(current->right);
}
}
```
### 自評
* 用英文解釋recursive還需要加強。
* 很少用英文在講解code有些專業術語(特別是動詞)，很容易用的不夠精確。
* 可以讓面試官問一個follow up: "有沒有不用recursive的方法?"，來考驗面試者的能力。
* 面試者可以最後再用一開始的例子test自己的code，但用英文trace recursive的code真的頗有挑戰性。
* 不要一直打錯字，顯得自己程式能力很生疏。
---
## [104. Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/)
> [模擬面試錄影](https://youtu.be/sd2SuF743PI)
題意
> Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
>
> Given binary tree [3, 9, 20, null, null, 15, 7],
> ```
> 3
> / \
> 9 20
> / \
> 15 7
> ```
> return its depth = 3.
Depth-first-search vs. Breadth-first-search
策略：若子節點 left 或 right 存在，則遞增 depth，並判斷 left 或 right 是否存在子節點，遞迴直到最深層。
考慮以下:
```
A
/ \
B C
/ \
D E
```
> Tree depth = 3
* node~A~ 的深度 = 1~自身~ + max(node~B~ 深度, node~C~ 深度)
* node~B~ 沒有子節點 $\to$ node~B~ 的深度 = 1
* node~C~ 有子節點 node~D~ 和 node~E~ $\to$ node~B~ 的深度 = 2
* node~A~ 的深度 = 1 + 2 = 3
遞迴實作:
```c
static inline int max(int x, int y) { return x > y ? x : y; }
int maxDepth(struct TreeNode *root)
{
if (!root) return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
```
應用案例: [find(1)](https://man7.org/linux/man-pages/man1/find.1.html)
Sign in with Wallet
Connect another wallet