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

貢獻者: 史迪奇-Stitch
模擬面試影片: 英語
 模擬面試影片-1 漢語
 模擬面試影片-2 漢語

🥸：interviewer
👾：interviewee

283. Move Zeroes

模擬面試過程

🥸：Hi Stitch, this is Nick from one of the company. Given an integer array, move all zeros to the end of it while maintaining the relative order of the nonzero elements. Note that you must do this in place without making a copy of the array. The size of this array should be no less than 1 and no greater than 10,000. The element should range from

- 2^{31}

2^{31} - 1

Here's a few examples:
Input: [0,1,0,3,4]
Output: [1,3,4,0,0]

Input:[2,3,4]
Output:[2,3,4]

Input:[0]
Output:[0]
Now you may start your answer.

👾：Ok, let me make sure. Uh, so I need to put 0s to the end of the array and without changing the relative order of another elements?
🥸：Correct.
👾：When you said:"Do this in place without making a copy of the array, does this mean to change the original array only.
🥸：Yes, "in place" is exactly what you mention.
👾：The first approach I'll be using is 2 pointer method. There will be two pointers i and c. One pointer i traverse the entire array, as soon as it encounters a non zero element, we insert the non zero element to the beginning of array. By doing so, we won't change the relative order of non-zero elements.The pointer(index c) tells where to insert the non zero element, as the entry is modified, c moves on to next position( increment by 1). The idea can be break down in two steps:

Step 1. i traverse through array, insert non zero element to the beginning where c is pointing to.

[0,1,0,3] , when i traverse through the array, if encounters 1, insert it to beginning. Then encounters 3, insert it to beginning right after 1. So the array becomes [1,3,0,3].

Step 2. Fill in zeros from index c to the end

From the 0 after 3, we'll need to fill zeroes the end.
So the final array becomes [1,3,0,0].

The procedure looks like this:

When i encounters non zero element
Put the non zero element in arr[c], c++
i++, repeat from step 1 until i reach the end of array.

👾：Does this sound reasonable to you?

🥸：Yes, you may start coding.
👾：

Method 1: Two pointers without swap

// Time complexity: O(n)
// Space complexity: O(1)
void moveZeroes(vector<int>& nums)
{
    int i = 0, c =0;
    for( ; i < nums.size(); i++) 
    {
        if(nums[i] != 0)
        {
            nums[count] = nums[i];//insert non zeroes to beginning
            c++;
        }
    }
    for( ; c < nums.size(); c++) //fill in zeroes
    {
        nums[c] = 0;
    }
}

🥸：Can you test it out?
👾：以[0,1,0,3,4]為例子，以滑鼠指出程式碼的i,c當下的值來說明。

steps
1	[0	1	0	3]
	i,c
2	[0	1	0	3]
	c	i
3	[1	1	0	3]
		i,c
4	[1	1	0	3]
		c	i
5	[1	1	0	3]
		c		i
6	[1	3	0	3]
			c	i
Fill in zeros starting from c
7	[1	3	0	3]
			c	i
8	[1	3	0	0]
				i,c

🥸：I see. Can you show the time and space complexity and explain?
👾：Time complexity is O(N) since we'll have to traverse through the entire array. Space complexity is O(1) since we're not using extra spaces.
🥸：Do you think there's a better way, with less operation to move the zeroes.
👾：Yes, the second approach, instead of moving the non zero to the beginning firstly then fill in the zeros afterward. Perhaps, we can do them simultaneously using the swap function. So this is very similar to the previous approach. Just that instead of using c to tell us where to insert non zero element, c (now j) is the element which we want to swap with arr[i]. So the operation goes like this:

The procedure looks like this:

When i encounters non zero element
swap( arr[i], arr[j]), j++
i++, repeat from step 1 until i reach the end of array.

By doing so, we can move zeroes to the back of array at the same time. What I'm concerned here is whether the i,j will be pointing at different non zero element, which makes swap accidentally changes the order of non zero element. Let's use two example to check:

steps
1	[1	2	0	3]
	i,j
2	[1	2	0	3]
	i,	j
3	[1	2	0	3]
		j i,
4	[1	2	0	3]
		i,	j
5	[1	2	0	3]
			j i
6	[1	2	0	3]
			j	i
7	[1	2	3	0]
				i, j

We find that, when i,j both points to non zero element, this algorithm enables them to be on the same position so swapping doesn't actually has effect on array element, which prevents accidental reordering from happening. Sir, do you have any thought on this algorithm?
🥸：It's reasonable, please start coding.
👾：Following code:

Method two: two pointers with Swap

void moveZero(vector<int>& nums)
{
    int i = 0, j =0;
    for( ; i < nums.size(); i++)
    {
        if(nums[i] != 0)
        {
            swap(num[j], num[i]);
            j++;
        }
    }
}

🥸：Show time/space complexity with explaantion and what is the difference between this and the previous approach?
👾：This approach has time complexity of O(N) since we need to traverse through array still, but this approach since we're using swap, the zero are moved to the end as non zero elements are insert to the beginning, which saves us operations to traverse from j(previous c) to the end to fill in zeros. It uses less operation due to the use of swap. For space complexity, it's O(1) since we're not using extra space.
🥸：I see, due to time costrains, we'll end the interview here, thank you for your attending, we'll contact you by the end of the week. Have a great day.

程式碼改進方案

在第二個方法中，我們可以發現當i, j都指向同個位置而且需要swap的時候(i指到non zero element)，應該可以直接跳過swap執行下去，免去swap但沒有任何影響的狀況。

自評檢討

說話的方式會讓人覺得沒有把握，不太確定的感覺
說話前或許可以想一響等等要說什麼，邊說邊想會造成第一項的問題
在寫code時邊說話容易犯錯而不自知
感覺花太多時間詳細講解著自己預計要怎麼做，但其實那些時間原本可以拿來寫code邊講解。通常應該是口語幾句自己要採取的方法，或帶個例子說明會長怎樣，之後就要根面試官確認自己的方向對否。由於這個模擬面試我們都是等到心中已經有答案的情況下自問自答，方法可能都定了，但實際面試時，應該要再三確認方向。有看到dcard說明其實面試官也很注重我們遇到不會的問題時的反應，一定要跟面試官討論。

69. Sqrt(x)

模擬面試過程

🥸：嗨，史迪奇，我是來自瓦拉公司的軟體工程師王凡，今天面試的第一道題是給你一個非負的整數，希望你實作出一個根號的function，這個function會吐出這個X的根號值。這個根號值如果帶有小數就把小數去掉，而且這個吐出來的數字也必須是個非負的數字。不可以使用任何內建的指數方式或是指數的operator。

Example

input: 4
output: 2

input: 8
output: 2 (round 2.828… to 2)
另外有個限制: 0

\leq

\leq 2^{31} - 1

，請開始你的回答。
👾：所以我的第一個想法就是，我就從零一直一路往上找到X，把每一個整數都走過一遍。為了方便解釋，我把它叫做 j 好了，我要找這個數字叫 j。我希望 j 的平方會小於X，可是 j + 1的平方。不大於X。那這時候我就找到我們要的數字 j。這樣子演算法聽起來有什麼問題嗎？
🥸：沒問題，那你可以開始實作了。
👾：

Method 1: Naiive approach

int sqrt( int x )
{
    int j = 0;
    for ( ; j<= x; j++)
    {
        if( (long) j * j == x) return j;
        else if ( (long)j * j < x && (long)(j+1)(j+1) > x) return j;
    }        
    return -1;
}

這個時間複雜度是O(N)因為我們需要從0一直往上找到X。複雜度是O(1)，因為我們沒有用到額外空間。
那我們可以來測一下，如果用0帶入的話，j從零開始自己相乘後得到0，所以等於X所以吐出零。如果要以帶路的話，發現在第2次進到或迴圈後也會回傳1。
🥸：好的沒問題，有看到你有些地方有用到(long)，但有些地方會用int你可以稍微解釋一下你的考量嗎?
👾：如果要使用比較少的記憶體，其實我應該一開始全部都使用int但是因為在jj部分，存取這個乘積的變數所需要的型別可能會超出2的32次方，例如j =

$2^{31} - 1$ 時，所以會產生integer overflow。於是這邊我就讓jj轉成有8×8=64個bits的type long。其他像x因為本身題目限制就是int能裝的最高位所以就int就好。
🥸：好的，那再往下走，你覺得你有任何改進程式效能的想法嗎?
👾：有的，我們可以回想現在的作法，就是用一個數字跟的平方就跟X做比較，但其實我們要搜尋的這個範圍(0到x)的整數本身就是排序好的，所以已可想見用binary search的方法去找加快。請問這個方向對嗎?
🥸：對，請繼續說明。
👾：好，所以現在呢？原本我要從0一直找到X。那現在我一開始就使用binary search去找零跟X中間的點，然後讓它的平方去跟X做比較。然後，如果得到的這個平方值小於X，代表說目標在我現在取的這個值的右邊，於是我就讓我搜尋範圍的下界變成是這個中間點的右邊開始，範圍的上屆還是X。好接下來，再從更新的下界跟上界取其中點的平方去跟X做比較，如果這次是大於X，那代表說下一個我要搜尋的目標應該在目前的左邊，所以我就要更改搜尋範圍的上屆變成是目前減1。藉由這樣的方式將搜索範圍變成一半，持續做到最後只剩下一個元素的時候，我們就要停止。所以直覺來看需要做的次數就會是

l o g_{2} (N)

，所以時間複雜度會是O(

l o g (N)

)。空間複雜度O(1)因為沒有使用額外空間。

使用例子來說明好了:下屆:l, 上界:r, 中間點:m, 當x = 8，預期結果為2。

steps	[0	2	3	4	5]
1	l	m			r
2*2< 8
2			l	m	r
4*4 >8
3			l,r,m
3*3 >8
4		r,m	l
stops when r < l
r is the expected output

這樣子的回答可以嗎？
🥸：沒問題，那請你開始實作。
👾：

Method 2: Using binary search


int sqrt( int x)
{
    int left = 0, right = x;
    while(1) // binary search
    {
        int mid = left + (right -left)/2; 
        if((long)mid * mid == x) return mid;
        else if((long)mid * mid < x) left = mid + 1;
        else right = mid -1;
        if( right < left ) return  right;
    }
}

🥸：為什麼你知道要return right? 並且為何停在當right < left 時?
👾：我們可以透過剛剛舉的表格中的例子發現，再r<l 的前一步發現都會先經過r = l，此時的m = r = l，如果m平方等於x那剛好吐出m，如果沒有，r跟l也只會差一個位置，說明我們的搜尋範圍已經壓到剩下這兩個數之一了，要round to the nearest integer所以選擇小的那個，也就是right。
🥸：好的這個回答很精細。那最後還想請你說說Binary Search的應用場景?
👾：Binary Search對於已經分類好的資料中去搜尋東西可以加快速度，在搜尋引擎，電腦檔案搜索，資料庫的檔案搜尋都可以加快搜尋速度。
🥸：沒問題，時間關係今天的面試就到這邊。謝謝你的參與，請繼續關注我們之後的信件。

程式碼改進方案

在Method 2中，將
$m i d = (r i g h t + l e f t) / 2$ 寫成
$m i d = l e f t + (r i g h t - l e f t) / 2$ 可以將right, 可以使得較不容易出現integer overflow。
Method2:int mid的宣告應該擺在while外就不會一直重複宣告。

自評檢討(面試)

寫code或回答時有很多不必要的停頓，要學習表達和邊講話邊code
interviewer習慣在思考的時候長時間往下看邊說話而不看interviewee，實際面試中這樣不太尊重面試官。
Method 1優化程式碼的部分感覺比較像避免發生錯誤而已
身為interviewee不停碎動，應該要穩一點
影片中interviewer的問題太少，絕大多數是要讓interviewee提出更好的辦法，應該要更多的細問(這部分可能是因為是自己設計問題，所以本來就知道interviewer會這麼問，在錄影片時interviewee自己就講出來了，要拿捏自己說的東西，免得說多了又不是interviewer要的，這部分要再拿捏。

11.Container with most water

模擬面試過程

🥸:你好史迪奇，我是王凡，瓦拉公司的軟體工程師，今天面試的第3道題是這樣的。給定一個長度為n的整數陣列height，代表再index i從0到n-1的位置有n條垂直的線長度為height[i]的線。每兩條線段加上X軸都可以視為一個容器，你要找到其中2條線段，使得他們與x軸一起形成的一個容器能夠容納最多的水，然後回傳這個容器的裝水量。注意，題目要求是不能傾斜這個容器。給一個例子，
intput: height = [1,8,6,2,5,4,8,3,7]
Output: 49
input陣列中的數字，就是下圖的鉛垂線的長度，可以看見其中兩條紅線便是能夠承載最多水量的容氣的兩邊，那便是8。並且該容器最多可以承載的水量就是49。

那這題有些限制，
n == height.length
2 <= n <= 105
0 <= height[i] <= 104

👾:第一個想法是。使用2個pointer，使用2個for迴圈下去把所有的2個邊都找過一遍。然後選出最多的。容量，那這麼做的效率實驗時間複雜度會是O(

n^{2}

)
🥸:沒問題，請開始實作。
👾:這題的時間複雜度是O(

^{2}

)，因兩個for迴圈都traverse過array，空間複雜度是O(1)，沒有使用額外空間。

Method 1: Brute force(2 for loops)

int maxArea(vector<int>& height) {
        int area = 0, res = 0;  
        for( int i = 0; i < height.size()-1; i++)
        {
            for (int j = i + 1; j < height.size(); j++)
            {
                area = min(height[i], height[j]) * (j - i);
                res = max(area, res);
            }
        }
        return res;
    }

🥸:是的，那你有什麼辦法降低他的時間複雜度嗎?

👾:所以題目要我使用算出最大容量，也就是使得底邊最大的情況下，並且希望兩個編當中短的納編越長越好，好我想要使用2個pointer，那麼因為容器兩邊應該是一左一右，所以選擇從兩邊開始往中間找，這樣一來可以使得最終如果兩個pointer碰到的時候，也只是traverse過一遍array，使得時間複雜度可以達到O(n)，那我現在要選擇，如何判斷每一步要動哪一個指標。我想先請問這樣的演算法的方向對嗎?
🥸:可以
👾:好，我觀察到因為容量限制由短邊所決定，並且每次將指標往中間靠，由於抵邊變短的情況下，容兩可能會縮小。如果長邊移動，遇到下一個更長的容量不會變，因為被短編所限制，如果遇到更短的，那就要看是否比另一個短邊短，如果比另一個短邊長，納容量不變，如果遇到的短邊比另一個短邊短，納容量右更小。所以移動長邊，得到的結果只有容量不變，或者變少。所以我移動短邊，至少還有容量變多的機會。
🥸:是否說可以說更詳細?
👾:如果我的短邊移動，遇到長邊，納容量就「有可能」變大，如果遇到短邊，納容晾衣錠縮小。粽上來看，如果要有可能使得容量變大只有移動短邊的可能。
🥸:好請繼續。
👾:納如果遇到兩個邊都一樣長，我想想。那無論誰動，於到更長的邊都不會改變容量，遇到更短的邊都會容量下降，都不會有因為這次移動錯邊而少了容量變多的可能。所以我就隨意選左邊動好了。

移動長邊

遇到更長的邊，容量不變因為受短邊限制
遇到更短的邊，容量維持(更短的邊比另一短邊長或相等)或下降(更短的邊比另一短邊短)

移動短邊

遇到更長的邊，容量可能上升
遇到更短的邊，容量必下降

兩邊等長

遇到更長的邊，容量仍下降因為底邊縮小
遇到更短的邊，容量必縮小

🥸:好，那請你實作看看。
👾:如下

Method 2: Two pointer, Greedy

兩個pointer: left, right，從array兩邊開始往中間靠近
指向短邊者往中間移動，只長邊者不動
計算容量，若容量比之前紀錄的都大，就更新回傳值
直到左右pointer碰再一起結束

    int maxArea(vector<int>& height) {
       int left = 0, right = height.size() - 1, res = 0, area = 0;
       while( left != right)
       {
           area = min(height[left], height[right]) * (right - left);
           res = max(res, area);
           if(height[left] > height[right])right -= 1;
           else if (height[left] < height[right]) left += 1;
           else left += 1;                  
       }
        return res;

    }

那時間複雜度是

O (n)

因為left, right pointer最後就是會總共traverse array一次。那空間複雜度部分O(1)，未使用額外空間。
🥸:好的，程式碼能夠更精簡嗎?
👾: 將if, else if改為else因為都做同樣動作。

Method 2:Two pointer, Greedy稍微更精簡版

int maxArea(vector<int>& height) {
       int left = 0, right = height.size() - 1, res = 0, area = 0;
       while( left != right)
       {
           area = min(height[left], height[right]) * (right - left);
           res = max(res, area);
           if(height[left] > height[right])right -= 1;
           else left += 1;                 
       }
        return res;

🥸:好的，那如果讓兩個pointer都從最左邊開始動是否可以，與從兩邊往中間靠近的差異?
👾:若都由左邊出發，假設一開始向右移動的pointer稱為right，一開始沒動的後來也會一在左邊的pointer叫left，right向右移動時，假設一開始如果left為長邊，right為短邊，短邊right向右移動，若遇到長邊容諒必上升，但如果遇到短邊，可能使容量更小，但底邊變大，因此容量的變化不向前一種方式有明確要移動的規則，更像是第一種的暴力解，全部試一遍才會知道。
🥸:剛剛你使用的由兩邊靠向中間那種決定下一步的方式是某種演算法的精神，你知道嗎?
👾:在當下選擇最有利的方法，每一步都這麼做，是貪婪演算法(Greedy Algorithm)。
🥸:沒錯，那由於時間關係，今天的面試就到這邊，謝謝。

改進方案

針對Method2，同樣動作歸類為同一類，可使得判斷少一步驟，剩if,else。

自評檢討(面試)

Interviewer:

Interviewer有給予提示
Interviwer再問Greedy algorithm納提的時候，感覺有點說太多提示。

Interviewee:

這部影片中有減少碎動，語氣聽起來比較堅定
用詞應該更精準的時候，例如「短邊是限制了『水深』，所以影響容量，如果只說影響容量，聽者可能沒有那麼直接能理解到」。
雖然解釋很細節，但也要注意時間
完全沒有跟interviewer討論到任何edge case，或相關限制，就直接進行說明approach，雖然有跟interviewer確定方向，但一開始應該稍微重複題目確保自己真的理解正確。
code寫錯要自己檢查，等到面試官提出來有點慘

第二次作業-他評01

針對 Interviewer 的檢討:

可以包裝一下題目
在引導 Interviewee 時，可以再更明確一點，例如希望對方優化的部分是程式碼、時間複雜度還是演算法，避免詢問兩次類似的問題
口語清晰
有詢問對方對此類型演算法的了解，不同於別人的問法很棒
18:31: Interviewee 沒考慮到的情況會適時的引導
對程式碼 pointer 變換是否依然可以執行的問題，可以避免面試者直接背答案的情況，問得很好!

針對 Interviewee 的檢討:

方法說明得很清楚
口語清晰
建議影片中 problem 2 程式碼做縮排，方便閱讀
後面有帶 testcase 做測試很棒!
6:11: 帶測試資料時建議不要突然丟出疑問句在自己回答，聽的人會以為在問自己

第二次作業 - 他評02

for interviewer

優點

咬字清晰
說明清楚
語速適中

可改進的地方

避免直接使用Leetcode題目原型，應加以變型
7:22: 請interviewee優化程式碼稍嫌籠統，可以針對時間複雜度或空間複雜度等，根據公司的需求提出優化的方向

for interviewee

優點

口齒清晰
闡述自己對題目的理解與初步使用的演算法時，有善用google document寫下pseudo code，有助於理解彼此的想法
3:36: coding時有自己先想到overflow的問題並加以解決

可改進的地方

2:17 開始coding時，語速會忽快忽慢，在說明時會加快，容易聽不懂，這中間也會有些卡頓，加上不少的「然後」就會給人一種interviewee很緊張的感覺（但也增加了模擬面試的真實性…？）
缺少 Repeat & Examples 的步驟，建議先確認自己對題目的理解正確再和interviewer討論Approach
6:51: 不宜讓滑鼠游標有這樣的晃動，對理解無益，遇到網路卡頓時更會造成負面效果

第二次作業 - 他評03

for interviewer

優點

將題目以書面呈現，減少口語上的認知落差
一步步帶領interviewee思考蠻好的

可改進的地方

沒有

for interviewee

優點

講解清楚，有用「我想一下」爭取時間

可改進的地方

模糊人物的部分，可以只模糊臉部，讓看影片的人可以看到肢體語言，因為在面試中也需要練習