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

埃默里-Emery
video(eng)
video(漢_1)
video(漢_2)

🧔：interviewer (灰帽子)
👶：interviewee (黃帽子)

自評 && 嘗試改進部分(整體)

自評_Interviewer

1. 前面應該可以加上一些『場面話』，再進入問問題的部分
2. 較為缺乏REACTO 的test 部分，所扮演的Interviewer 會直接進入討論優化的部分。
3. 可以再將題目再包裝的更精巧，可以與公司業務相關或是一個特定情境
4. 雖然會給interviewee一些優化提示，不是直接說『降低時間複雜度』，讓他可以有線索improve，但感覺可以多用引導的方式讓他自己想到優化方法。
5. 應該要多注意interviewee的程式犯的錯
   例如9:24的"unordered_map"，或是4:56 的主函式的solve()的input與宣告的不同。

自評_Interviewee

1. 講解時缺乏致肢體動作，只有靠語言可能會有誤解的困擾
2. 需要練習邊打code邊講解
3. 在approach 的時候，會講得很抽象，容易造成理解困難，感覺可以舉一些例子邊用顏色或反白來解釋程式如何進行的
4. 語速過快，以及咬字和發音可以更清楚。可能會在訊號不好或是有延遲的情況下造成更多的討論/理解困難

283. Move Zeroes

題目描述

給定一個整數陣列nums，將所有0元素移動到陣列末尾，同時保持非零元素的相對順序。

面試對話&程式碼解說

🧔：Hello, Emery. I have a question and I'm hoping you can help me find a solution.
Today we received an array filled with product numbers, all of which are non-negative integers.
However, among these numbers, products with a number of 0 are defective. I'm looking for a way to move the elements with a value of 0 to the end of the array without affecting the order of normal products.
👶：
OK, so, I will receive an array consisting of integers, and I need to move the elements with a value of 0 to the end of the array without changing the order of the other non-zero elements.
🧔：Yes, that's correct.
👶："let me take a simple example?"
[1,5,4,0,2,0] → [1,5,4,2,0,0]

Is this the correct result?
🧔：In this example, the result is correct. Now, please propose your solution strategy?

👶：I would start by creating a blank array A of the same length n as the given array. Additionally, I'll initialize a left pointer l with an initial value of 0 and a right pointer r with an initial value of n minus one .

Next, I'll set up a for loop to iterate through the given array. For each element, if the value is non-zero, I'll place it in the L position of the blank array A. If the value is 0, I'll place it in the R position of the array A. Finally, I'll move l or r.
🧔：
Sounds like this can solve the problem. Please present your solution using code.

方案一 : 雙指標(Using Extra Space)

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        
        int n=nums.size();
        int r =0;
        int l =n-1;
        vector<int>tem(n);
        for(int i=0;i<n;i++){
            if(nums[i]!=0){
                tem[r]=nums[i];
                r++;
            }
            else{
                tem[l]=nums[i];
                l--; 
            }
        }
        for(int i=0;i<n;i++){
            nums[i]=tem[i];
            }
        return;
    }
};

👶：First, initialize the values of r and l. Then, create a loop to check each element if it's 0.
If it's not 0, place it at position l and increment l by 1.
If it's 0, place it at position r and decrement r by 1. Finally, return the array.
This time complexity is O(N), and the space complexity is also O(N).

🧔：This approach indeed solves this problem. However, if there is a requirement to reduce space complexity, meaning not using additional memory allocation, how would you design it?

👶：
If there is a requirement to reduce space complexity, meaning we cannot create an additional blank array but instead need to modify the original given array,
I would start by initializing two pointers, i and j, both set to 0.

Then, I would use a while loop with the condition that both pointers i and j are less than the length n of the given array.

Inside the loop, I would implement a conditional statement: if the value at the j-th position of the given array is non-zero and i is not equal to j, then swap the values at positions i and j, and increment both i and j by 1.
However, if the value is zero, increment only j by 1.

The principle behind this approach is to allow j to scan the entire array, while i remains at the position of the first element or the leftmost 0 in the array.
By swapping elements, we can move the 0s to the end of the array.
🧔：This approach ensures that zeros can be moved to the end regardless of their initial positions.
I noticed you added the condition i not equal to j to reduce unnecessary swaps.
It's clear that you want to minimize unnecessary operations.
However, this approach has a potential issue. If the first element is non-zero or there are no zeros in the entire array, it will result in an infinite loop. So, I would like to ask you to make some adjustments to address this issue.
👶：
Yes, I only considered reducing the number of swaps and didn't think about this issue.
I will adjust by moving the condition i not equal to j inside the check for the j-th position value being non-zero.
Additionally, if i is equal to j, I will also increment both i and j by 1.
🧔：
Yes, this modification will address the issue mentioned above.
Could you please present it using code?

方案二 : 雙指標(In-Place)

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int i=0,j=0;
        while(i<nums.size() && j<nums.size()){
            if(nums[j]!=0){
                if (i!=j)
                swap(nums[i++],nums[j++]);
                else {i++;j++;}
            }
            else{
                j++;
            }
        }
    }
};

👶：
Sure. First, Initialize i and j. Then, create a while loop with the condition that i and j do not exceed the array length.
Inside the loop, check the j position value of array.
If it's not zero, further check if i is equal to j.
If they are different, swap the values at the i-th and j-th positions in the array, and increment both i and j by 1.
If i and j are the same, it means there's no need for a swap, but still, increment both i and j by 1.
Finally, if the j position value in the array is 0, only increment j by 1.
🧔：
Well done, thank you. I have another question. I'd like to hear how would you solve it.

面試過程檢討

Interviewer

Interviewee

219. Contains Duplicate II

題目描述

給定一個整數數組 nums 和一個整數 k，如果數組中有兩個不同的索引 i 和 j 且 nums[i] == nums[j] 且 abs(i - j) <= k，則返回 true。

面試對話&程式碼解說

🧔：今天有一個陣列nums，裡面裝有整數，並且給定一個整數k，想請你幫我確認這個陣列中是否有兩個一樣的element，並且他們的索引值相差小於k。如果是就返回true，反之返回false
👶：好的，讓我確認一次問題。我需要在一個陣列中找到是否存在兩個索引值差小於整數k。那請問整數k 與陣列的長度範圍為何?另外我是否需要找到每一組符合條件的組合，還是找到一組就可以return true 了
🧔：陣列的長度在1到10000之間，而k值則是會落在0到10000之間
另外，只需要找到一組符合條件的就可以返回true了。
👶：我了解了，那讓我舉幾個例子。
[4,5,6,4,5] k=3 返回true ， [4,2,8,6,4] k=2 則返回false
這樣的例子是符合題意的嗎?
🧔：是的，你所舉的例子都和要求相符，接著請你說明你打算如何解決這個問題。
👶：好的，我會使用兩個for 迴圈，外圈索引值i會從到陣列長度L-1
並且以陣列中每個值為起點，用第二個迴圈往前找k個數，若是有相同的element，就 return true。若是雙層迴圈跑完都沒找到符合條件的數，則return false。
🧔：是的，這會是最直觀的做法，但請你要考慮一些邊界條件，例如陣列中只有一個element，若是沒有其他問題的話，就請你用程式來呈現你的解決方法。

方案一 : 暴力解(雙層迴圈)

class Solution {
public:
 bool containsNearbyDuplicate(vector<int> & nums, int k) {
    int l=size(nums);
    for(int i=0;i<l-1;i++){
       for (int j=i+1;j<l;j++){
          if((j-i)>k) break;
          if(nums[i]==nums[j]) return true;
       }
    }
    return false;
  }
};

👶：外圈index i從0找到nums倒數第二個數，內圈index j從i+1找到最後一個element，首先先判斷j-i是否大於k，式的話代表找超過k 個數了，就跳出內層迴圈
若雙層迴圈跑完還沒有找到，就return false。
🧔：是的，這樣是可以解決這個問題，而且也包含了特殊的情況，但就像你所說的時間複雜度為O(n *k)，所以當n和k很大時，運行時間會非常長。
想請你想想看有沒有方法可以不使用到雙層迴圈去找到符合要求的數字組合呢?
例如可以先找是否存在重複的element，接著針對位置做判斷。
👶：我想到的方式是將nums 中的element 做排序，這樣相同的整數就會容易找到。
但這樣會打亂原本的順序，就不知道相距是否小於k。所以我會採用vector 裡的pair 資料類型，將value 和index都存下來，再對value 做排序，這樣就可以找到相同的element並且保留index。
🧔：你所描述的方法，可以解決不雙層迴圈，那就請你用程式來呈現你這個方法，並討論為什麼會比第一個方法還要快

方案二 : (用 sorted pair 查找 )

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
       pair<int, int> p[nums.size()];
       for (int i = 0; i < nums.size(); i++){
            p[i].first = nums[i];
            p[i].second = i;
       }
       sort(p, p + nums.size());
       for (int i = 0; i < nums.size() - 1; i++){
           if (p[i].first == p[i + 1].first){
               if(abs(p[i].second - p[i + 1].second) <= k)
                    return true;
           }
       }   
        return false;
    }
};

👶：雖然只使用到兩個單層迴圈，但因為過程中有使用到sort ，所以時間複雜度仍然是O(nlogn) ，並且因為創建了pair 所以空間複雜度等級為O(n)。
🧔：根據你的程式碼以及討論，可以證明這個方法在運行時間上比第一個方法快。
但還是請你想想看有沒有不需要做排序，在第一遍檢視陣列時就可以找到相同element 的距離呢?

👶：是的，在剛剛用pair方法實作時，有想到其實不需要將每個值記錄下來做排序。
我會使用更直觀的unordered map，並用迴圈從第一個element開始記錄。
其中key 為nums[i]，而value 則為索引值i，並在填入map前，檢查這個key 是否存在了，若是存在了，代表這個值已經出現過了，馬上檢查這一次出現的索引值i跟map 中相同key 的value，若是相減小於k就可以返回true。若是沒有，則將索引值i取代原本的value，因為這個key 有可能會再後面再出現。
若是整個迴圈跑完還未找到，就返回false。
🧔：從你所描述的架構來看，因為不需要排序，所以運行時間可以更少，請你用程式來呈現你這個方法。

方案三 : (unordered map 查找)

class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
    int l=size(nums);
    unordered_map<int, int> mp;
    for(int i=0;i<l;i++){
       if(mp.count(nums[i])){
          if(i-mp[nums[i]]<=k) return true;
          mp[nums[i]]=i;
       }
       else mp[nums[i]]=i;
    }
    return false;
}
};

面試過程檢討

Interviewer

Interviewee

55. Jump Game

題目描述

給定一個整數數組 nums。 您最初位於數組的第一個索引處，數組中的每個元素代表您在該位置的最大跳躍長度。

如果可以到達最後一個索引，則返回 true，否則返回 false。

面試對話&&程式碼解說

🧔：假設你是負責規劃路線的工作，今天每一站之間固定為1km並排列成一直線
但每一站有一個限制，限制接下來你至多能走幾km，而這個限制會以非負整數陣列的方式呈現。而你需要告訴我，是否有任何方式可以從第一站抵達最後一站。
👶：好的，讓我整理一下問題。今天我會拿到一個陣列，每一個位置上都會一個整數，代表接下來可以前進幾個位置。然後我需要判斷是否有方法可以從第一個位置走到最後一個位置。
🧔：是的，因為題目的可能性很多樣，你可以舉例來確認題意
👶：好，今天如果陣列是
[1,0,1,2] 因為一開始只能走1步，所以只能走到第二個位置，而數值是0
所以不能再前進，只能返回false
若是陣列是[2,0,1,3,0,1] 可能的路線可以從2跳到1跳到3跳到1就返回true。
🧔：你舉的兩個例子都符合題意，並且若是陣列中沒有0，答案就一定是true，因為不存在無法前進的情況。若是對題目沒有問題，你可以試著先提出你想到的任何做法跟我討論
👶：這個題目的難處在於，在選擇走幾步之前，並不會知道接下來的限制步數，所以並不會知道最佳走法。
我會採用遞迴的方式，把從每一個位置出發作為一個子問題，去看從這一個位置出發是否能抵達最後一個位置，就對這個子問題返回true，若是從這個位置出發的所有走法都無法抵達，就對這個子問題返回false
🧔：是的，遞迴是解決這個問題很直觀的做法。請你用程式呈現你的解決方法。

方案一 : 遞迴

bool solve(int i,vector<int>& nums) {
        if(i>=nums.size()-1) return true;
        for(int step=1; step<=nums[ind];step++) {
            if(solve(i+step,nums)==true) return true;
        }
        return false;
    }
bool canreach(vector<int>& nums) {
     return solve(0,nums); 
}

🧔：看起來符合你所敘述的解決方法，但如果只是用這樣的遞迴方式，會有太多重複的子問題，會大大的增加運行時間。你可以嘗試修改這個遞迴的方法，透過記錄解決過的子問題，使程式更有效率嗎?
👶：這樣的話，可以利用Dynamic Programming的方式，另外創建一個陣列dp，初始值都設為-1，用來存放已經解決的子問題方便查找。
遇到已經解決過的子問題，可以直接返回答案。
🧔：是的，這樣可以改善遞迴會計算重複子問題的缺點。
請你用程式呈現你的解決方法

方案二: Dynamic Programming

bool solve (int i,vector<int>& nums, vector<int>&dp){
    if( i >= nums.size()-1) return true; 
    if( nums[i]== 0 ) return false;   
    if( dp[i] != -1 ) return dp[i];
    for(int step=1; step <= nums [i]; step ++){ 
        if( i+step < nums.size() && solve (nums, i+step ,dp))
        return dp[i]=1;
    }
        return dp[i]=0;
    }
bool canreach(vector<int>& nums) {
     vector<int>dp(nums.size(),-1);
     return solve(0, nums,dp);
}

👶：這樣因為將子問題的結果存下來做查找，改善了重複解決問題，所以時間複雜度是O(n)
而因為額外創建一個陣列，所以空間複雜度是O(n)
： 是的，這樣會比起遞一個方法還要快上許多。
但這邊要請你想想看，有沒有方法可以在不創建額外陣列的情況下，完成這個任務
例如，可以想想要怎麼判斷最遠可以走到哪個位置，而什麼情況是無法繼續前進了。
👶：若要是去判斷最遠可以走到哪個位置，可以嘗試使用貪婪演算法。
也就是去計算每個位置可以走到的最遠的位置，並且保留最大的結果，看到最後是否可以走到最後一個位置
🧔：貪婪演算法是一個很適合用來解決這個問題的方式，請你用程式實體化你的解法

方案三:

bool canreach(vector<int>& nums){
int maxi=0 , n=nums.size();
for(int i=0;i<n;i++){
    if (maxi < i) return false;
    maxi=max(maxi,i+nums[i]);
}
return true;
}

👶：若是最遠能抵達的位置maxi比我正在計算的位置還要小，就代表最遠無法抵達正在計算的位置所以就return false，接著會將maxi 更新到目前的最大值，可以抵達的最遠的位置。
若是到迴圈結束後還沒有return false ，代表有辦法抵達最後一個位置，所以就return true
雖然時間複雜度等級還是O(n)，但實際的計算量會比前一個用遞迴的方式還要少
並且空間複雜度等級只有O(1)

🧔：是的，這是一個很理想的解決辦法。謝謝你今天參加面試

面試過程檢討

Interviewer

Interviewee

第二次作業-他評 01

interviewer

• 感覺在一開始interviewer介紹題目的時候背景就可以有題目出來，讓interviewee更好理解題目，不知道為何到後面才出現題目。
• 可以多為你的題目設定情境，像是我們是某某公司，平常可能會做甚麼，所以想考考你有關甚麼內容的解決能力等。

interviewee

• 在repeat的階段很完整，而且也能考量到題目可能需要那些限制或是需求來做提問，增加討論性
• 可惜比較缺乏test的部分，感覺可以在後面說明時間複雜度和空間複雜度的時候去做test的部分，然後利用一開始在example提出的測試來驗證你的程式碼是否有誤。

第二次作業-他評 02

interviewer

• 優點

• 有針對完成的程式碼提出回應，並且引導面試者提出更好的解法。

• 可改進的地方

• 00:10:可以想想情境題，比如說這題可以假設在做市場調查，我們想知道在K個小時(索引值)內有沒有兩個人以上買過這個商品(元素)

interviewee

• 優點

• 整體在寫程式時都很順暢，讓面試官可以很清楚現在做到哪裡了。

• 可改進的地方

• 00:26:在回答面試官問題時，把想法打在電腦上感覺會讓面試官比較好確認你的理解是否正確

第二次作業 - 他評03

for interviewer

• 優點
  • 敘述清楚，雖然一開始沒有顯示題目，但從口頭敘述就可以理解題目
• 可改進的地方
  • 影片裡interviewer眼睛都會往左看
  • Leetcode 55有經過包裝，很棒！但建議可以再更深入，例如為什麼要從第一站到最後一站？可以與公司的業務連結（旅遊業、交通業…）

for interviewee

• 優點
  • 語速平穩適中
  • 邊coding邊說明很流暢
• 可改進的地方
  • 3:58 時間複雜度應完整說出「『Big-O』 n乘以k」

第二次作業-他評 04

interviewer

• 優點
  • 口齒清晰，音量、速度適中。
• 可改進的地方
  • 00:10 描述問題時，可以在word或google document上寫下關鍵字，稍後可讓interviewee較易了解題目。
  • 04:22 在提出要減少時間複雜度後，可以等interviewee卡住或是主動詢問後，再做提示。

interviewee

• 優點
  • 在開始寫程式前，有先確認題目的邊界。
  • 縮排排得很清楚，程式碼看起來很舒服👍。
  • 除了提出使用vector的pair優化時間複雜度外，也有進行說明為什麼這樣比較好。
• 可改進的地方
  • 02:22 05:10 可以將程式碼包裝在一個class或是function內，這樣後續在使用上能清楚知道function的作用以及回傳的資料型態。