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

貢獻者: 泰迪熊 Teddy
video: 1, 2, 3

🥸：interviewer 🙂：interviewee
🥸：泰迪熊先生你好，我是Tim，歡迎你參加我們的面試，我們已經有經面試的google文件傳到您的信箱，請你打開第一題。

392. Is Subsequence

🥸：我先說明一下題目，這題會提供兩個字串s和t，你需要實作一個function，判斷s是否為t的子字串，如果是回傳true，不是就回傳false。如果一個字串是另一個字串的子字串，代表他可以從原字串中刪去一些字母來生成，並且其他剩下的字母順序不變。
🙂：那我想請問一下這兩個字串有可能是空字串嗎?並且會區分大小寫嗎?
🥸：兩個字串可以為空字串，然後你只需要考慮小寫的情況就可以了。

Repeat

🙂：那這題是要判斷輸入的字串s和t，s是不是t的子字串，子字串的定義是可以透過原字串刪去一些字母產生，並且其他字母的順序不可以改變。

Examples

🙂：那我舉個例子

1. s = "abc", t = "ahbgdc"  
  要回傳true，因為s可以透過把t中的h、g、d等字母刪除後得到。
2. s若改為"acb",t = "ahbgdc"
  要回傳false，因為他更動了字母的順序。

🙂：我這樣的理解是正確的嗎?
🥸：沒錯，請繼續。

Approach

🙂：那這題我會想用for迴圈迭代的方法，使用兩個pointer，用來記錄迭代的位置。然後我會先考慮有哪些狀況是可以不用進行迭代，直接回傳答案。

1.s為空字串時不管t是什麼，s都必為子字串，回傳true。
2.當s不是空字串但t是空字串時，s不可能是t的子字串，所以要回傳false。
3.s的長度大於t的長度時也必須回傳false。

🙂：如果不是上面三種情況才開始迭代t字串，每次移動一個字元，同時t的pointer也往前一個字，如果發現和s的pointer指的字一樣的字元，才把s的pointer也往前一個字元，這樣可以保證我們是照著t字串的順序找所有s中的字母。那我們的停止條件是迭代完整個t時，s的pointer是指到最尾端的時候，也就是s中全部的字元都可以在t中被找到，就可以回傳true。反之s的pointer指在尾端之前，我們就回傳false，代表s中有字母沒有被找到。時間複雜度的話是O(m)，m代表t的長度，因為我們只會迭代t字串一次，空間複雜度是O(1)，因為只使用兩個額外的變數來記錄。

🥸：ok，那請你實作看看

Code

    bool isSubsequence(string s, string t) {
        if(s=="")
            return true;
        if(t==""||s.length()>t.length())
            return false;
        int i=0;
        for(int j=0;j<t.length();j++){
            if(t[j]==s[i])   
                i++;           
            
        }
        if(i<s.length())
            return false;
        else
            return true;   
        
    }

Test

🙂：接著我舉個例子驗證

s="abc",t="axybc"兩個都不是空字串,i=0,j=0
接著進入for loop
j=0 s[0]==t[0]=>i+1=1
j=1 s[1]!=t[1]=>i=1
j=2 s[1]!=t[2]=>i=1
j=3 s[1]==t[3]=>i=2
j=4 s[2]==t[4]=>i=3 
比較i==s.length()=3
return true

Optimization

🥸：你的程式碼看起來是可以正確運作的，但是在for迴圈那邊看起來是一定會迭代整個t字串，是不是可以更加改進，讓某些情況下程式可以更快結束。
🙂：好的我理解你的意思了，那我想可以提早結束的情況會是在於當s字串的所有字母很早就被找完了，就可以提早返回true，那這邊我會多加一個判斷條件判斷，s字串的指標是否已經達到s字串的長度，就提早返回true讓程式可以更節省時間。
🥸：OK，那我們進入下一題。

自我檢討與改進

Interviewee

1.講話會卡頓需要練習表達得更順暢
2.在舉第二個例子的時候陣列的index要用變數表示還是要用數值表示要統一一下，兩個交叉用很混淆。

Interviewer

1.講解題目遇到定義，可以給個例子，不然有點難懂。
2.問的問題可能太容易了。

238. Product of Array Except Self

🥸：這題會提供一個整數陣列nums，希望你能回傳另一個陣列其中第i個位置儲存的是除了nums[i]以外的其他數字的乘積，不可以使用任何除法運算，並且時間複雜度須在O(n)以下。
🙂:那我想請問一下陣列裡面的乘積會不會超出一般32 bits整數的範圍
🥸：不會，你不需要考慮超過的情況。

Repeat

🙂:好的，題目是一個整數陣列nums，要回傳另一個陣列並且位置i要存的值是原本陣列中除了第i個位置以外其他數字相乘的結果，並且不可以使用除法運算，時間複雜度要在O(n)以下。

Examples

🙂:舉例來說，假如輸入A陣列為[1,2,3,4]那輸出將會是[24,12,8,6]。
🥸：沒錯，請繼續。

Approach

🙂:那這題我會想到的作法是每次計算i位置的答案時把nums陣列從i分成兩半，並用兩個額外的陣列取名叫prefix和suffix，其中prefix會儲存位置i左方的乘積，而suffix則是儲存i右方的乘積，用for迴圈迭代計算，最後再把兩者對應項相乘存到answer陣列裡面。
🙂:以上面的例子做示範的話

    [1 2 3 4] i從1開始
    prefix=1 1 2 6
    suffix=24 12 4 1
    接著只要把prefix和suffix中的對應項相乘就是答案 
    answer:24 12 8 6

🙂:不過我們可以觀察到i+1的prefix，其實就是前一個prefix值乘上位置i的數值，因此每次計算prefix不需要再從陣列開頭計算，因為之前的所有prefix都已經紀錄在陣列中，suffix也要這樣做可以減少重複的計算，所以應該要從最尾端開始往前計算，最後只要把兩個陣列用相反的順序相乘就可以了。所以我們只需要走訪整個陣列一次就可以計算出所有prefix，而suffix也是反向走訪一次，最後在兩個陣列相乘，也是走訪陣列一次，所以時間複雜度會是O(n)。空間複雜度的部分由於我額外用了三個大小為n陣列儲存因此也是O(n)。
🥸：那請你實作看看。

Code

    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int>prefix(n),suffix(n),answer(n);
        
        prefix[0]=1;
        suffix[0]=1;
        for(int i=0;i<n-1;i++){
            prefix[i+1]=prefix[i]*nums[i];
            suffix[i+1]=suffix[i]*nums[n-i-1];
        }
        for(int i=0;i<n;i++){
            answer[i]=prefix[i]*suffix[n-i-1];
        }
        return answer;
    }

Optimization

🥸:ok，但你上面的程式在輸出的answer陣列以外，額外又用到了兩個陣列，想請問你能不能再降低記憶體使用?
🙂:好的，我想可以用answer陣列代替之前prefix陣列的功能，把所有prefix直接存入answer[i]中，接著把suffix從陣列改為只用一個變數，這個變數會隨著i改變計算對應的suffix，同時乘上answer內儲存的prefix值。

    以同樣例子來說明，假設我們prefix已經算好儲存在answer中
    [1 2 3 4]
    answer=[1 1 2 6] 
    接著用一個變數s=1代表suffix，
    反向的乘上answer陣列，每乘完一項就把suffix更新成下一個的suffix
    也就是
    s=1  [1 1 2 6]=>s=4
    s=4  [1 1 8 6]=>s=12
    s=12 [1 12 8 6]=>s=24
    s=24 [24 12 8 6]  

🙂:這樣一樣是走訪陣列2次，時間複雜度不變，但是額外使用的儲存空間會降低到只剩一個變數，因此可以降低記憶體使用。
🥸：那你可以快速的實作出來嗎?
🙂:好的

    vector<int> productExceptSelf(vector<int>& nums) {
        int suffix=1; 
        int n=nums.size();
        vector<int>answer(n);
        answer[0]=1;
        for(int i=0;i<n-1;i++){
            answer[i+1]=(answer[i]*nums[i]);
        }
        for(int i=n-1;i>=0;i--){
            answer[i]*=suffix;
            right*=nums[i];
        }
        return answer;
    }

🥸：看起來ok，那我們的面試就到這邊謝謝你。

自我檢討與改進

Interviewee

1.在講解approach的時候前面雖然用鍵盤打字舉例，但是後面講解的時候又變成只用鼠標在說明，很不清楚。

Interviewer

1.第二個問題問得太直接了，應該用婉轉一點的方式讓面試者自己觀察。

104. Maximum Depth of Binary Tree

🥸：Hi Teddy.I'm Nick.Let's start today's interview.You can use google document to type your answer.And here's the probelm.
🥸：Given the root of a binary tree, return its maximum depth.A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Repeat

🙂:So,the problem is given a binary tree and I need to find its maximum depth.The maximum depth here is defined as the number of nodes along the longest path from the root down to the farthest leaf node.

Examples

🙂:I'll take an example to make sure I understand correctly.

        3
       / \
      9  20
         /\
       15  7

🙂:In this example because the longest path passing through nodes 3,20 and 15. So the maximum depth of this tree is 3.
🥸：Correct,go ahead.

Approach

🙂:To solve this problem,I'll use the recursive version of depth first search algorithm since the algorithm will go down to the leaf node first ,it is easy to calculate depth.And it will traverse all nodes so we can compare the depth of every branch.
🙂:The base case is when we go beyond the leaf nodes which is null then we should return 0.And the depth of leaf nodes will be 1.
🙂:The recursive thinking is the maximum depth of parent node is the larger value of the maximum depth of left subtree and right subtree and plus one. So we recursively call the function to calculate the depth of subtrees and return the larger number.
🙂:When finish the DFS traversal,we also get the maximum depth.Since DFS traverse the tree once,so the time complexity is O(n),n is the number of nodes.And space complexity is O(h) because we need a recursive stack with h spaces,h is the height of tree.

Code

    struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
    }
    int maxDepth(TreeNode* root) {
        if(root==NULL)
            return 0;
        int leftmax=maxDepth(root->left)+1;
        int rightmax=maxDepth(root->right)+1;
        return max(leftmax,rightmax);
    }

Test

🙂:I'll have another example to check my program.

         7(3)
       /   \
      9 (2) 6 (1)
     / 
    5 (depth=1)   
   /
  NULL(return 0)

🥸：Your code looks great.Here's one more question.
Since you use the DFS algorithm to solve this problem,can you try the breadth-first search algorithm?
🙂:Ok,for binary tree BFS is also the level-order traversal. It will traverse the tree until the last level.When we pass through one level,the depth also increase by 1.
As long as we finish BFS,we get the maximum depth.

int maxDepth(TreeNode* root) {
        if(root==NULL)
            return 0;
        queue<TreeNode*>q;
        int Depth=0;
        q.push(root);

        while(q.size()){
            int l=q.size();
            for(int i=0;i<l;i++){
                TreeNode* k=q.front();
                q.pop();
                if(k->left!=NULL)
                    q.push(k->left);
                if(k->right!=NULL)
                    q.push(k->right);
            }
            Depth++;
        }
        return Depth;
    }

🙂:Because we traverse all nodes ,the time complexity is O(n).And space complexity is also O(n),because the queue needs to store all leaf nodes at the last level which is at most 1/2* n.
🥸：Ok sounds great.That's today's interview.Thank you.

參考資料

https://leetcode.com/problems/maximum-depth-of-binary-tree/solutions/1125292/c-dfs-bfs-4-approaches-time-o-n-space-o-h/?envType=study-plan-v2&envId=top-interview-150

自我檢討與改進

Interviewee

1.英文表達和流暢度要加強
2.在講解approach遞迴條件的部分感覺可以用例子說明而不是直接打程式，再加上英文表達不好可能造成面試官不好了解意思。
3.聲音在後半段變小
4.breadth-first search跟depth-first search想要講縮寫可能要先跟面試官提一下。

Interviewer

1.第二個問題很容易猜到，也偏背誦，應該可以轉個問法，或換一題
。

第二次作業-他評01

關於interviewer

優點

• 說話清楚、聲音穩定。
• 有說明題目

可改進的地方

• 可以適時變更題目限制。

關於interviewee

優點

• 說話清楚、聲音穩定。
• 有實現 REACTO 步驟。
• 詢問 corner case，並根據題目敘述舉出例子。
• 有說明時間和空間複雜度。
• 字體大小適中。
• 104. Maximum Depth of Binary Tree
  • 有定義 TreeNode 結構。

可改進的地方

• 392. Is Subsequence
  • 可以確認兩個字串的長度範圍，避免超出 int 範圍。
• 238. Product of Array Except Self
  • 5:57 productexceptself 的可讀性不太好，詳細可參考變數命名法。
• 104. Maximum Depth of Binary Tree
  • 需要詢問節點數量，節點數量會影響程式的實作 (e.g. 適不適合遞迴…) 和回傳值。
  • 8:28 舉例方法使得二元樹的結構難以閱讀。

第二次作業-他評02

關於interviewer

優點

• 講話速度穩定、咬字清楚

可改進的地方

• 題目可經適當包裝，避免 interviewee 背答案

• 238 . Product of Array Except Self

  • 9:02 直接指出可優化記憶體的使用。時間允許的話，可以先問 interviwer 有沒有自己覺得可以優化的地方，沒有想出來再行引導。

• 104 . Maximum Depth of Binary Tree

  • 6:00 講完空間複雜度後，可再進一步追問 Binary Tree 的高度範圍（延伸閱讀：Relationship between number of nodes and height of binary tree）
  • 8:43 BFS 的作法用在這題沒有比較簡短、也沒有比較快，可改問為什麼這題使用 DFS 會比較直觀

關於interviewee

優點

• 講話速度穩定、咬字清楚
• 主動詢問題目邊界值
• 適當省略縮排減少打字時間（392. Is Subsequence 6:56）
• google document 行距、字體適中，文字易讀性高

可改進的地方

• 238 . Product of Array Except Self
  • 10:35 游標的位置遮擋到打字區域，影響閱讀

第二次作業-他評03

interviewer

優點

• 提示for迴圈可以提早結束，而非直接給答案，讓interviewee再思考看看。

可改進的地方

• 12:56可以對題目進行一些變化，像是將s插入t中，可以組成幾種新字串。

interviewee

優點

• 有先將字串的constraints詢問清楚。
• 有將舉的例子寫在google document上，可以讓雙方都看得很清楚。
• 有先提出想到的特例👍。

可改進的地方

• 07:11 撰寫程式碼時，注意s = ""和s == ""所代表的意義不同，如果在if寫s = ""會直接將s清空，不是口語表達中的s為空字串。