---
# System prepended metadata

title: JSERV - HW1

---

# JSERV - HW1

## Question 1 中文

### **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 ## Question 2 中文

## Question 2 中文

### **53. Maximum Subarray**

[https://leetcode.com/problems/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

## Question 3 英文

### **62. Unique Paths**

[https://leetcode.com/problems/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 講錯，每加一輪是跟最大值去做比較
- 英文口說需加強