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

貢獻者: 姆咪-MUMI
🧔：interviewer 👶：interviewee
模擬面試錄影(漢)
模擬面試錄影(漢)
模擬面試錄影(英)

---

121. Best Time to Buy and Sell Stock

面試過程

🧔:你好，同學我是這次的面試官，我這裡有一道題目想請你作答。我會給你一串陣列裡面有「7,1,5,3,6,4」這六個數字，請你把它當作股票的價格，去尋找一段買賣時機來獲得最大收益。舉剛剛的例子在第二天買入股票，在第五天賣出，獲得最大收益為5；那如果你發現這一串陣列沒有任何收益的話，請你輸出為0
👶:我呢!一開始直覺上會想要用暴力法，類似這樣(開始用小畫家畫圖)，用兩層迴圈，假設i是他然後再找j(也就是i後面這一串數字)，和它相減來獲得這輪的最大收益(也就是max)。接著i找到下一個數字，依此類推，尋找整個陣列找到它的最大收益

方法一:暴力解

解題過程
👶:就像我一開始所說的我必須要跑兩層迴圈，會分別令n紀錄有幾個數字還有max_profit也就是我圖上的max。最外面那層i要檢查到每一個數字，接著裡面那層因為只要檢查i後面的數字，所以從i+1開始即可

class Solution{
public:
    int maxProfit(vector<int>& prices){
    int n=prices.size();
    int max_profit=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if((prices[j]-prices[i])>max_profit)
            max_profit=prices[j]-prices[i];
            }
        }
        return max_profit;
    }
};

🧔:那同學可以請你分析一下這段程式碼的時間複雜度嗎?
👶:因為要跑兩層迴圈，應該會很接近O(n^2)
🧔:可以請你找一個時間複雜度更低或更快的方法處理?
👶:直覺上除了剛剛的方法，其實還可以朝著Greedy還有dp的方法來解

方法二:DP

說明想法
👶:我們設兩個指標一個是最小值(min)一個是最大收益(max)，那我先假設它的min是這個，那我就和它後面的相減，來獲得max:-6。接著找到下一個最小值，一直去尋找它的最大收益。
解題過程
👶:就像我剛剛說的會有兩個指標(變數)，因為一樣要跑所有的數字，所以從0到prices的size，首先要先判斷它的最小值，接著去找它的最大收益

class Solution{
public:
    int maxProfit(vector<int>& prices){
        int profit=0;
        int min=INT_MIN;
        for(int i=0;i<prices.size();i++){
            if(prices[i]<min) min=prices[i];
            if((prices[i]-min)>profit) profit=prices;
        }
        return profit;
    }
};

---

53. Maximum Subarray

面試過程

🧔：感謝你的時間，接下來由我主持這場面試。這裡有一道題，就是經典的maximun subarray，題目描述如上。一個array中，它裡面有很多個subarray，那麼我要你找出這個subarry內元素的數值總和，並且這個總和要是最大值。
例如我給你一個array裡面元素有「-2,1,-3,4,-1,2」，而它的maximum subarray為「4,-1,2」，也就是你要output:5；那如果這個array中只有一個元素的話，直接輸出即可。
👶:好的，(打開小畫家)
一開始我看到這題，我會去假設它有兩個指標(i,j)，然後j就往後讓i一個一個去加，去找出這一輪loop的最大sum值(這是第一步)。而我的第二步，去移動這個i重複上面這個動作，依此類推，直到i移動到最後一個元素為止。

方法一:暴力解

👶:一開始會先宣告"res"為答案，初值為array第一個元素。開始跑for迴圈，就像剛剛畫的，我現在要讓i從頭跑到尾(0~nums.size())，因為我每一輪迴圈都要找它的sum，把它重製為0。接著開始實作第一步動作和後面相加並找出最大值，因為只要和後面相加，所以j從i開始

class solution{
    public:
    int maxsubarray(vector<int>& nums){
    int res =nums[0];//答案 初值為array第一個元素
    for(int i=0;i<nums.size();i++){
        int sum=0;
        for(int j=i;j<nums.size();j++){
            sum=sum+nums[j];
            res=max(res,sum);
            }
        }
        return res;
    }
};

🧔：然後同學可以請你分析一下你寫的這個code的時間複雜度嗎?
👶:由於它跑兩層迴圈為O(N^2)，N就是這個array的元素個數
🧔：那可不可以只跑這個陣列遍歷一次就可以了
👶:痾，我想一下喔。如果要這麼做，要朝著greedy還有dp的方向去思考

方法二:DP

👶:首先呢!會有兩種情形(一個是和前面subarray合併，另外一個是不要合併)，然後再取最大值
(開始用小畫家解釋)
那麼最後這個array的最大值就會是最大subarray的數值總和
(開始打code)
解題過程
👶:先令now_sum(紀錄目前這個subarray的數值總和，初值為第一個元素)，接著令max_sum(記錄這個array的最大subarray數值總和)，接著跑for迴圈。那麼就可以實作我剛剛說的–-now_sum就去判斷合併/不合併，max_sum去看這個subarray最大值
而我這個code它的時間複雜度就會是

$O(N)$，因為他只要跑一層迴圈，利用DP的概念去完成要求

class solution{
    public:
    int maxsubarray(vector<int>& nums){
    int now_sum=nums[0];
    int max_sum=nums[0];
        for(int i=1;i<nums.size();i++){
            now_sum=max(now_sum+nums[i],nums[i]);
            max_sum=max(now_sum,max_sum);
        }
        return max_sum;
    }
};

🧔：好的，同學。我這裡還有一個follow-up，不曉得你想不想挑戰看看?就是我希望你用divid & conquer來解這道題
👶:divid & conquer阿?!它整體的思維就是把一個很大的問題分成好幾個小問題，先把這個array一分為二，那我要去找出左右半邊最大subarray為多少?那麼我再去看看如果此時我把這兩個合併起來，那我最大的subarray還是右半邊的5

方法三:divid & conquer

說明策略
👶:我會有lmax(主要記錄左半邊的maximum subarray)、rmax(主要記錄右半邊的maximum subarray)、還有ml和mr(這兩個是從m這個位置的元素往左/右的最大值)
解題過程
👶:一開始我的function會多兩個變數(left和right)。如果left>right代表它跑過頭，return;那如果沒有，就先找到m的位置，接著就令剛剛說的ml和mr，然後是左半邊最大值lmax右半邊最大值rmax，lmax從left到m-1/rmax從m+1到right。接著去求ml的值，用之前的想法往左累加並找出maximun，mr也是;最後去找出左半邊和右半邊哪個最大，再去比較mr+ml+m哪個更大

class solution{
    public:
    int maxsubarray(vector<int>& nums,int left,int right){
    if(left>right) return INT_MIN;
    
    int m =(left+right)/2;
    int ml=0,mr=0;
    int lmax=maxsubarray(nums,left,m-1);
    int rmax=maxsubarray(nums,m+1,right);
    
    for(int i=m-1,sum=0;i>=left;i--){
        sum+=nums[i];
        ml=max(ml,sum);
        }
    for(int i=m+1,sum=0;i<=right;i++){
        sum+=nums[i];
        mr=max(mr,sum);
        }    
     return max(max(lmax,rmax),ml+mr+nums[m]);   
    }
};

---

2441. Largest Positive Integer That Exists With Its Negative

面試過程

🧔：
Hello, thank you for waiting. I will be conducting this interview. I have a question for you:
The question is as follows: I will provide you with an array, and your task is to find a pair of elements within this array, where one element is positive and the other is negative, and then find the maximum value among them.
For example, given the array [-1, 2, -3, 3], you should output 3 because it satisfies the criteria. If no such pair is found in the array, please output -1.Additionally, there are no elements equal to 0 in this array.

👶:Well~ Initially, since the order of positive and negative numbers in the array is not guaranteed, it's probably positive one is in front of negative one.Or negative one is in front of positive one.

說明策略

👶:I think I will use nested loops to check. However, since there are no zeros in the array,a number pairing with itself won't occur. So, I can start the loop from 0.

方法一:Brute Force

解題過程

👶:I will start by using the 'ans' variable as my answer and initialize it to -1. Next, my first loop will iterate through the entire array. The second loop will do the same. Then, I'll check if 'nums[i]' is greater than 0 and if 'nums[i]' is equal to it's negative(nums[j]). If both of these conditions are met, I'll update the value of 'ans' using the 'max' function

class solution{
public:
    int findMaxk(vector<int>& nums){
        int ans = -1;
        for(int i=0;i<nums.size();i++){
            for(int j=0;j<nums.size();j++){
                if(nums[i]>0 && nums[i]==-nums[j])
                ans=max(ans,nums[i]);
            }
        }
        return ans;
    }

};

🧔：Is there a way to simplify this code?
👶: Yes, there is a way to simplify it. You can start the loop from i+1, without considering the order, and you don't need to distinguish between nums[i] and nums[j].

方法二:改進Brute Force內的步驟

class solution{
public:
    int findMaxk(vector<int>& nums){
        int ans = -1;
        for(int i=0;i<nums.size();i++){
            for(int j=i+1;j<nums.size();j++){
                if(nums[i]==-nums[j])
                ans=max(ans,abs(nums[i]));
            }
        }
        return ans;
    }

};

👶: By Doing this,it reduce the second loop's execution by half.
🧔：Is there a faster approach?
👶: Well, let me think…
🧔：When it comes to data lookup, what comes to your mind?
👶:I might think the binary tree
🧔：However, if the data size is too large, this number can be quite high. There is a method that can achieve search in O(1) time.
👶:oops,hashtable

說明策略

👶:here are two types of hashtables: hashset and hashmap. Since we only need to check for existence, I would choose hashset.Because a set doesn't allow duplicate elements,it only stores unique elements

方法三:Hashtable

解題過程

👶:First, I'll insert the values from the array into a hashtable. Then, I'll check if this hashtable contains a pair of elements that meet the criteria. If it does, I'll update the 'ans' value using the 'max' function.
Because I only need to determine its existence or not, using the count function is sufficient

class solution{
public:
    int findMaxk(vector<int>& nums){
        unordered_set<int> htable;//hashset for exist
        for(int i=0;i<nums.size();i++)
        htable.insert(nums[i]);
        
        int ans = -1;
        for(int i=0;i<nums.size();i++){
        if(nums[i]>0 && htable.count(-1*nums[i]))
            ans=max(ans,nums[i]);
        }
        return ans;
    }

};

👶:This approach trades space for time. The minimum space complexity would be O(N) from O(1) since we need to store elements.But the time complexity will be O(n)(for insert) from O(nlogn),and search time for O(1)
.

---

初步檢討

針對 interviewer 的檢討:

• 第一部影片interviewer不應該自稱面試官的…，以及用array來稱呼陣列會比較精準
• interviewee 宣稱完成程式碼，interviewer應有必要的檢驗和討論
• 英文口說需要再加強…像是來唸稿的，不像對話
• interviwee講解時，interviewer應該適度地去打斷提出發問，討論一些議題，如這麼做需要考慮什麼，來檢視是否真的知道interviewee在打什麼。
• 提問時，避免只拋出「時間複雜度」這樣的問題，可能 interviewee 憑藉猜測或背誦做答，可改為要求 interviewee 解釋並簡介並對應到程式碼該怎麼執行，去做到足以鑑別一個人能力
• 避免只是說「能寫得更精簡嗎？」，卻沒有給予方向和思維，這不是好的「互動」

針對 interviewee 的檢討:

• 程式撰寫時適當的空格、註解，提高簡潔度和可讀性
• 回答問題時有點太過直接，會讓人覺得自己是來解考古題的。
• interviewer要開始撰寫程式時，應該告知要用什麼語言
• interviewer在interviewee講解題目時，要去用REACTO的repeat仔細確認題意，如果突然微調題目，會GG
• 英文口說需要再加強…
• 解釋改善的方法時，應該順道解釋為何減少執行次數
• 在解釋想法的時候盡量精簡講"核心思想"，避免冗言贅字
• 提出改進方法後不要馬上實作，要先和 interviewer 討論

他評01

優點

• 咬字清晰，對聽者很友善^ ^
• interviewee 使用手寫的介面描述想法很讚，可以很快速的讓人理解。
• interviewee 邊寫程式碼邊解說，沒有冷場~
• (LeetCode 53) 5:36: interviewee 將要討論的多種情況寫下來，方便參考，很棒！

可改進的地方

• 影片中的程式碼有點糊。
• interviewer 可以有更多的應用情境假設。
• (LeetCode 121) 4:32: 建議 interviewee 可以在寫完程式碼後，主動先分析時間及空間複雜度，會有比較好的印象。
• (LeetCode 121) 8:36: 解法二缺乏複雜度分析。
• 小小建議，(LeetCode 53) 9:33: interviewer 希望可以試試看 divid & conquer 的解法，不過 DP 的解法好像就已經夠快了，除非在這題，divid & conquer 有什麼特別的優點，或是有什麼特別的情境需求(我目前沒有想到)，才需要要求額外的解法，畢竟 interviewer 應該是希望改進程式碼，而不是使用多種方法解題?(應該吧
• (LeetCode 2441) 1:21: 在說解題想法前，缺少重複提問及舉例來確認提議。
• 題目 1443 ，我覺得最後的解法還有一些多餘的步驟可以改進，不需要兩個 for 迴圈，一個寫入，一個判斷並找 max，這兩個動作可以同時進行，以下是我的修改建議。

class Solution {
public:
    int findMaxK(vector<int>& nums) {
        int ans = -1;
        unordered_set<int> htable;//hashset for exist
        for(int i=0;i<nums.size();i++){
            if (htable.count(-nums[i])) { 
                ans=max(ans, abs(nums[i]));
            }
            else {htable.insert(nums[i]);}
        }
        return ans;
    }
};

第二次作業-他評02:

Interviewer

優點

• 語速正常，咬字清楚，聲音也適中
• 有跟Interviewee互動，漸進式的引導
• 題目有利用實際問題包裝，較好理解並沒那麼快讓人聯想到經典題目

可改進的地方

• 題目建議獨立放大剪輯出來，題目的字太小太糊看不太清楚

Interviewee

優點

• 語速正常，咬字清楚
• 有畫圖解釋讓人易於理解
• 有解釋到時間和空間複雜度的分析

可改進的地方

• 程式碼偏糊，不好觀看
• 缺乏R的部份，都是直接從E開始

第二次作業-他評03:

Interviewer

優點

• 可以不用以面試官自稱，畢竟之後有可能會共事。
• 有與面試員互動，嘗試引導面試員想到解法

可改進的地方

• Maximum subarray可以不把題目直接亮出來，嘗試描述情境讓面試員不會直接想到解法。
• 英文5:36Data是得塔(中文空耳)

Interviewee

優點

• 有使用小畫家，但我不確定面試時能不能用

可改進的地方

• 可以重述R的部分，一部分是當你面對新題目是重述題目可以增加思考時間以及注意到細節。
• A(Approach)的部分是可以看面試官是否接受你的做法，假設你做的方向不如預期，他可能會就打斷你，或是給方向才進行C(Code)

第二次作業-他評04:

Interviewer

可改進的地方

• 0:47：Interviewer 與 Interviewee 之間的切換不夠明顯，使人在第一次聽時有些錯愕。

Interviewee

優點

• 在 coding 能清楚說明為什麼這麼做並拿出範例佐證。

可改進的地方

• 0:47：跳過了 Repeat 與 Example 這個步驟。
• 5:23：雖然有用圖說明 DP 算法如何執行，但在細節上解釋的稍顯不足，會使聽感不佳，比方說為何我們能知道最小值是 1 是因為 7 與 1 相減得出 -6，這邊應該加以說明理由，使聽者能更容易進入狀況。

第二次作業-他評05:

Interviewer

優點

• 在暴力解完之後，有提出減少時間複雜度的優化。

可改進的地方

• 00:02盡量不要使用"面試官"自稱，可以說我是XX公司的XX工程師。

Interviewee

優點

• 有邊寫邊說明在寫什麼。

可改進的地方

00:56 05:20 在舉例說明時，可以直接打在word上比較清楚，不用再開一個小畫家。
04:40 回答時間複雜度時可以有自信一點，不用說"應該會很接近" O(n^2) ，可以直接說因為使用兩個for迴圈，所以時間複雜度是O(n^2)。

第二次作業-他評06:

Interviewer

優點

• 有小小嘗試包裝題目
• 0:01 說"由我來主持這場面試" 不錯，畢竟面試官可能之後是同事或是職位比面試低的人

可改進的地方

• intervierer及intervieree的切換有點模糊
• 互動有點少

Interviewee

優點

• 有畫圖來表達
• 讓人感覺能力很強

可改進的地方

• REACTO要再加強。

第二次作業-他評07:

Interviewer

優點

嘗試引導面試者去思考更好的解法

可改進的地方

在面試者提出解法時，面試官其實可以要求面試者針對測資一起搭配著說明，也能一同驗證該解決方案是否可行

Interviewee

優點

針對你的121. Best Time to Buy and Sell Stock我覺得你的 DP 想法很不錯，嘗試使用兩個指標紀錄最小值及最大收益

可改進的地方

後來我嘗試使用您的想法遇到一些問題，以下為我參考您的想法

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        int min = INT_MIN;
        for(auto price : prices){
            if(price < min) min = price;
            if((price - min) > profit) profit = price - min;
        }
        return profit;
    }
};

會產生以下問題

Line 8: Char 23: runtime error: signed integer overflow: 7 - -2147483648 cannot be represented in type 'int' (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:17:23

我認為是 price - min 時造成 overflow，超過有號整數能表示的範圍了

以下為，改進版本

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        int min = prices[0];// 原先是 int min = INT_MIN;
        for(auto price : prices){
            if(price < min) min = price;
            if((price - min) > profit) profit = price - min;
        }
        return profit;
    }
};

我舉個例子說明，您的測資為[7,1,5,3,6,4]

在 price = 7 時，min = 7， profit = price - min = 0; max profit = 0
在 price = 1 時，min = 1， profit = price - min = 0; max profit = 0
在 price = 5 時，min = 1， profit = price - min = 4; max profit = 4
在 price = 3 時，min = 1， profit = price - min = 2; max profit = 4
在 price = 6 時，min = 1， profit = price - min = 5; max profit = 5
在 price = 4 時，min = 1， profit = price - min = 3; max profit = 5
最後返回 max profit = 5

第二次作業-他評08:

• 面試者和面試官對話中間正常會留點停頓，影片感覺很像看稿唸出來。

Interviewer

優點

• 5:33: 有誘導面試者是否能夠想到更好的方法。

可改進的地方

• 4:55: 可以提到空間複雜度，還有影片中看起來面試者還在打字，面試官就已經打算要做後續討論了。
• 5:13: 面試者沒有說明時間複雜度，可以先問他，再詢問是否有更快的作法。

Interviewee

優點

• 1:05, 0:53, 1:00: 用小畫家解釋作法。

可改進的地方

• 6:10: 圖好像沒有特別標記min和max值在執行的時候會怎麼跑。
• 6:55: INT_MIN打反了，而且應該是INT_MAX。
• 4:43: 圖上直接打叉對解釋要用的作法沒有什麼意義。
• 9:30:
  $O(n)$寫得像
  $O(h)$，其實可以不用再切到小畫家，直接用打字的就好。