---
tags: info2022-homework1
---
# 2022 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2022)」作業 1
> 貢獻者: 無逸煩-Kris
> [模擬面試錄影(漢)](https://youtu.be/rgm9fmFExp0)
## [27. Remove Element](https://leetcode.com/problems/remove-element/)
### Interviewer
你好，我是xxx的工程師，沒問題的話我們就開始面試，我這邊有一道題目，題目是這樣的，我會給你一個陣列和一個值K，你要做的就是移 除所有陣列裡的K，陣列裡其他的元素的相對位置是可能改變的，要注意的就是你不能改變陣列的大小，並且你要將剩下的元素移到陣列的前面，你可以不用去處理陣列後方的空間，並且你要回傳剩下的元素個數
### Interviewee
**Repeat** :
所以是我會拿到一個陣列跟一個K，我要找到並移除陣列裡的K，然後將剩下的數字移到陣列前方，並回傳剩下的數字個數，並且剩下的數字不需要維持原有順序對嗎?
### Interviewer
沒錯，重要的是你不能更改陣列的大小，所有動作必須要原有陣列內進行(in-place)
### Interviewee
**Examples** :
好的，那我舉個例子，我今天拿到一個
input : [2,2,3,5,4,2] , k = 2
output : [ 3, 4, 5, *,* ]
我後面2位的數字不影響正確
同時我的354是可以改變順率的意思，請問我的理解是正確的嗎?
### Interviewer
沒錯，後面的不會影響作答
### Interviewee
**Approach** :
好的，我會採取的作法是， 1. 我會用2個指標，一個從頭開始為i，一個從尾開始為j 2. i負責找K，j負責找不為K，兩者都找到時就交換 3. i+1, j-1，重複1，直到ij交會
### Interviewer
OK，那我們開始coding吧
### Interviewee
**Code** :
```cpp
int RemoveElement(vector<int>& nums, int val){
int i = 0, j = nums.size()-1, remain_num = 0;
while(i<=j){
if(nums[i] != val){
i++;
remain_num++;
continue;
}
if(nums[j] == val){
j--;
continue;
}
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
remain_num++;
i++; j--;
}
return remain_num;
}
```
1. 我首先會宣告2個i,j，分別從頭跟尾開始遍歷整個陣列，以及宣告一個remain_num來計算回傳值
2. 我的終止條件是ij交會，也就是i<j，再來我用兩個while來找到我要的位置，i找K，j找非K得位置，
3. i每+1一次，remain_num也要+1，因為代表i找到了一個其他數字，而當j找到不為K的時候，也代表一個其他數字，所以j跳出迴圈，remain_num也要加一，再來i j找到，就進行交換並將i+1,j-1
4. 重複1，直到i j 交會
### Interviewee
**Test** : 舉例來說，我今天有一個陣列是
2 2 3 5 4 2 , K = 2
- i = 0, j = 4，ij互換，i+1, j-1
4 2 3 5 2 2
- i = 1, j = 3，ij互換，i+1, j-1
4 5 3 2 2 2
- i = 2, i = 2 在下一次 i = 3, j = 2 此時 i < j不滿足就會跳出
### Interviewer
好的，這邊我想請問一個問題，關於你的remain_num，是不是有其他的改進方法?
### Interviewee
OK，我想到了，因為我的i會比j早得到，且我的i必定是K的起點，也就是結束的時候，從index i 開始之後都是2，假設i是2，前面有2個數字，所以我可以直接回傳i
```cpp
int removeElement(vector<int>& nums, int val) {
int i = 0, j = nums.size()-1;
while(i<=j){
if(nums[i] != val){
i++;
continue;
}
if(nums[j] == val){
j--;
continue;
}
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
i++; j--;
}
return i;
}
```
回傳i即為剩餘數字個數，i的位置結束之時必為2的起始，也剛好是前面數字的個數
**Example ：** 6 3 4 2 2 2 2 i = 3跳出，回傳值為3
---
## **[53. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/)**
### Interviewer
好的，那我這邊還有另一個問題，我給你一個整數陣列，找到一個連續子陣列他的和為最大，並回傳和的值
### Interviewee
**Repeat :**
好，所以我今天有一個陣列，我要找到她之間的連續一段的和是最大的，並回傳他，是這個意思嗎?
### Interviewer
沒錯
### Interviewee
是要連續的一段子陣列對嗎?
### Interviewer
沒錯
### Interviewee
**Examples :**
所以我今天假如有一個陣列為 [2, -5, 6, 8, -1, 2]
我挑到的子陣列就會是[6, 8, -1, 2] 並回傳15 ，對嗎?
### Interviewer
沒錯
### Interviewee
**Approach :**
我的想法是用3個for loop去檢查所有的subarray，
第一個for跑 i = 0 到 n
第二個for跑 j = i 到 n
第三個是把 I到J的值都加起來
### Interviewer
好的，那我們開始coding吧
### Interviewee
**Code :**
```cpp
int MaxSubarray(vector<int>& nums){
int maxSum = nums[0];
for(int i = 0; i < nums.size(); i++){
for(int j = i; j<nums.size(); j++){
int curSum = 0;
for(int k = i; k < j; k++){
curSum += nums[k];
}
if(curSum > maxSum)
maxSum = curSUm;
}
}
return maxSum;
}
```
### Interviewer
好的，你看完這個code，有沒有發現curSum是不是重複算了好幾次一樣的東西，你覺得應該要怎麼改善?
### Interviewee
我知道了，我的curSum不需要每次都重新算一次，我的第三個for loop可以只做下一次的加即可，也就是這樣改，這樣我的big O就可以降到O(n2)
```cpp
int MaxSubarray(vector<int>& nums){
int maxSum = nums[0];
for(int i = 0; i < nums.size(); i++){
int curSum = 0;
for(int j = i; j<nums.size(); j++){
curSum += nums[j];
if(curSum > maxSum)
maxSum = curSUm;
}
}
return maxSum;
}
```
### Interviewer
那有沒有可能複雜度可以降到O(n)? 有沒有可能走過一遍陣列就可以拿到最大值? 你可以想看看當我從陣列頭開始家的時候，我要怎麼去決定要捨棄那些數字，如果加到負的的意義是甚麼?
### Interviewee
我這邊的做法是，我會遍歷一遍陣列，並記錄下目前的和跟最大的和，目前的和就是紀錄我for loop走過的值相加，如果加到負的，目前的和就重新計算一次，因為負的值是沒有貢獻的可以直接丟掉，否則就繼續加，並每一次去更新我的最大的和
### Interviewee
```cpp
int MaxSubarray(vector<int>& nums){
int curSum = 0, maxSum = nums[0] // curSum就是我要一次次去加的值，而maxSum是記錄我全部的最大值
for(int i = 0; i < nums.size(); i++){
if(curSum < 0)
curSum = 0; //如果curSum < 0 表示前面幾個數字的和為負， //對答案是沒有貢獻的，就可以直接丟掉
curSum += nums[i];
maxSum = max(curSum, maxSum); //確認是不是要更新最大值
}
return maxSum;
}
```
**Test :** 舉例來說，我今天有一個陣列是 3 -6 5 -3 6 curSum = 0, maxSum = 3, 以i做for loop
- i = 0, curSum = 3, maxSum = 3
- i = 1, curSum = 0(3-6 = -3,改0), maxSum = 3
- i = 2, curSum = 5, maxSum = 5
- i = 3, curSum = 2, maxSum = 5
- i = 3, curSum = 8, maxSum = 8
---
## **[62. Unique Paths](https://leetcode.com/problems/unique-paths/)**
### **Code :**
```cpp
class Solution {
public:
int uniquePaths(int m, int n) {
int path[m][n];
for(int i=0; i<m; i++)
path[i][0] = 1;
for(int i=0; i<n; i++)
path[0][i] = 1;
for(int i=1; i<m; i++)
for(int j=1; j<n; j++)
path[i][j] = path[i-1][j] + path[i][j-1];
return path[m-1][n-1];
}
};
```
# 檢討
### 程式部分
- 面試時不可以開啟語法提示，讓畫面看起來好亂
- 要善用註解，可以用註解的方式去寫Test case，以及用註解去區分程式的部分，可以先將妳要實作的功能分為幾部分，並分別加上註解，讓面試官更明白你的程式流程
- 會有過長的沉默時間，可以稍微講一下等等要實作的方法，或是目前正在做的事
- 語助詞太多
- 打字速度可以降低，不要一直打錯字
- 邊寫程式邊講話還是會有點卡卡的
- 第三題的部分，對陣列的初始化可以改寫成
```cpp
vector<vector<int>> path(m, vector<int>(n,1)) //宣告m*n vector 元素皆為1
```
會比用兩個for loop去初始化更簡潔一點
### 交談過程
- 在講解自己的方法中，最好是能夠透過test case說明，我再聽一次覺得自己講的其實沒有那麼好懂，如果搭配範例來解釋，會讓面試官更好理解
- 等到面試官確實了解你的方法，在開始進行coding
- 第一題的時候，講解方法時沒有提到remain_num，在寫程式時會有點突然
- test講解的部分不能用自己懂的方式去講，要以導師能懂的方式來說明，包括remain_num為甚麼要+1等等，以及終止條件的說明
- 20:38 講解新的方法時，應該先說明要用到的變數，再開始講解
- 22:00 講錯，每加一輪是跟最大值去做比較
- 英文口說需加強
# 第二次作業-他評01
## 關於interviewer
### 優點
+ [9:40](https://youtu.be/rgm9fmFExp0?t=574) 追問的問題給予適當的引導，卻又不過度限制思考空間，可以很好的了解對方的思考方式。
### 可改進的地方
+ 雖然拍攝起來可能有點麻煩，但講解題目的時候提供一個可以閱讀的畫面，能讓人比較清楚知道題目的問題。
+ [0:02](https://youtu.be/rgm9fmFExp0?t=2) 開頭用**面試**取代**考試**可能比較不會讓人感到壓力。
+ [11:19](https://youtu.be/rgm9fmFExp0?t=679) 這裡講解題目的時候，陣列沒有講到是什麼型態，整數?字元?或者是整數的話有無負數等等資訊，也說到要找**最大**、**連續**，這裡指的是存放的元素，還是陣列的index，這些對於理解問題都有很大的影響。
+ [19:25](https://youtu.be/rgm9fmFExp0?t=1165) 這裡可以先提出最佳解為O(N)，並了解面試者有無下手目標，讓面試者有思考的空間或是提出自己的觀點，可以更進一步了解面試者的思考邏輯。
## 關於interviewee
### 優點
+ 說明想法的時候搭配動作更加生動讓人好理解。
+ 解題過程邏輯清晰。
+ [7:15](https://youtu.be/rgm9fmFExp0?t=435) test的方式逐行表示實際運行的結果讓人更加清楚程式的正確性。
### 可改進的地方
+ [2:09](https://youtu.be/rgm9fmFExp0?t=129) 這裡在方法提到用兩個指標，會讓人預期要使用pointer的方式，但後面宣告的變數並非指標變數，有點讓人confused。
+ [11:08](https://youtu.be/rgm9fmFExp0?t=668) 這裡說"這就是他的修改"，會讓人感覺好像是背答案，但問題本身也許就沒有標準答案，建議可以改說"這是我做的修改"，把結果歸功於自己想到的方法。
## 其他補充
+ 此問題回答中的最佳解O(N)即為經典演算法[Kadane’s Algorithm](https://www.interviewbit.com/blog/maximum-subarray-sum/)
+ 偶爾打code的時候會有些murmur，那些聲音會讓人為了知道你有沒有要傳達甚麼訊息而去仔細聽，但卻聽得很辛苦。
+ [14:49](https://youtu.be/rgm9fmFExp0?t=889) 你說比size小，聽起來以為你說三小 :laughing:
Sign in with Wallet
Connect another wallet