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

貢獻者: 無逸煩-Kris

模擬面試錄影(漢)

27. 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 :

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

我首先會宣告2個i,j，分別從頭跟尾開始遍歷整個陣列，以及宣告一個remain_num來計算回傳值
我的終止條件是ij交會，也就是i<j，再來我用兩個while來找到我要的位置，i找K，j找非K得位置，
i每+1一次，remain_num也要+1，因為代表i找到了一個其他數字，而當j找到不為K的時候，也代表一個其他數字，所以j跳出迴圈，remain_num也要加一，再來i j找到，就進行交換並將i+1,j-1
重複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

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

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 :

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)

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

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

Code :

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，以及用註解去區分程式的部分，可以先將妳要實作的功能分為幾部分，並分別加上註解，讓面試官更明白你的程式流程
會有過長的沉默時間，可以稍微講一下等等要實作的方法，或是目前正在做的事
語助詞太多
打字速度可以降低，不要一直打錯字
邊寫程式邊講話還是會有點卡卡的
第三題的部分，對陣列的初始化可以改寫成

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 追問的問題給予適當的引導，卻又不過度限制思考空間，可以很好的了解對方的思考方式。

可改進的地方

雖然拍攝起來可能有點麻煩，但講解題目的時候提供一個可以閱讀的畫面，能讓人比較清楚知道題目的問題。
0:02 開頭用面試取代考試可能比較不會讓人感到壓力。
11:19 這裡講解題目的時候，陣列沒有講到是什麼型態，整數?字元?或者是整數的話有無負數等等資訊，也說到要找最大、連續，這裡指的是存放的元素，還是陣列的index，這些對於理解問題都有很大的影響。
19:25 這裡可以先提出最佳解為O(N)，並了解面試者有無下手目標，讓面試者有思考的空間或是提出自己的觀點，可以更進一步了解面試者的思考邏輯。

關於interviewee

優點

說明想法的時候搭配動作更加生動讓人好理解。
解題過程邏輯清晰。
7:15 test的方式逐行表示實際運行的結果讓人更加清楚程式的正確性。

可改進的地方

2:09 這裡在方法提到用兩個指標，會讓人預期要使用pointer的方式，但後面宣告的變數並非指標變數，有點讓人confused。
11:08 這裡說"這就是他的修改"，會讓人感覺好像是背答案，但問題本身也許就沒有標準答案，建議可以改說"這是我做的修改"，把結果歸功於自己想到的方法。

其他補充

此問題回答中的最佳解O(N)即為經典演算法Kadane’s Algorithm
偶爾打code的時候會有些murmur，那些聲音會讓人為了知道你有沒有要傳達甚麼訊息而去仔細聽，但卻聽得很辛苦。
14:49 你說比size小，聽起來以為你說三小
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →