Try   HackMD

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

胖達-Panda
🐶:interviewer
🐼:interviewee

模擬面試錄影(漢)
模擬面試錄影(漢)
模擬面試錄影(英)

15. 3sum

模擬面試過程

🐶:題目會給你一組數值,希望你把所有的組合找出來,組合有都是三個數值所組成,三個數值的總和為

0。請注意你的答案不能有重複的組合。
🐶:輸入最少有
3
個數值,最多有
3000
個。數值的值大小最小為
105
,最大為
105

🐶:請問你對題目有疑問嗎?
🐼:有,我想請問輸入的數值有經過排序嗎?
🐶:沒有,題目預設輸入的數值沒有經過排序。
🐼:好的,爲了確認我對題目的理解,我想用一個例子説明

輸入: [-1,0,1,-1,2,-5]
輸出: {[-1,0,1],[-1,-1,2]}

🐼:請問我有理解錯題目嗎?
🐶:沒有,你可以開始寫你的程式了。
🐼:在寫程式之前,我想先講一下我的想法。
🐼:最直觀的解法是用三個迴圈,把所有組合列舉出來,然後用一判斷式判斷三個數值的總和是否為

0
🐼:至於重複的組合,我們可以先把輸入的數值進行排序,然後用
set
把答案存起來,防止加入重複組合。

暴力解法(3個迴圈)

vector<vector<int>> threeSum(vector<int>& nums){
  sort(nums.begin(),nums.end());
  const int n =nums.size();
  set<vector<int>> ans;
  for(int i=0;i<n;++i)
      for(int j=i+1;j<n;++j)
          for(int k=j+1;k<n;++k)
              if(nums[i] + nums[j] + nums[k] == 0)
                        ans.insert({nums[i] , nums[j] , nums[k]});
return vector<vector<int>>(nums.begin(),nums.end());
}

🐶:你用三個迴圈把所有組合列舉出來是可以解決我們的題目。但以實務層面來説,輸入資料十分大時,程式的效能會很差。請問你有辦法解決嗎?
🐼:的確,用三個迴圈的時間複雜度是

n3。我的想法是用排序過的數值所提供給我們的資訊,先用一個迴圈把第一個數值選出來,然後用雙指標把第二,三個數值給找出來。

利用快慢指標走訪

vector<vector<int>> threeSum(vector<int>& nums){
  sort(nums.begin(),nums.end());
  const int n =nums.size();
  vector<vector<int>> ans;
  if(nums.front()>0||nums.back()<0) return{};
  for(int i=0;i<n;++i){
  if(nums[i]>0) break;
  if(i && nums[i]==nums[i-1]) continue;
   int j=i+1;
   int k=n-1;
   while(j<k)
    {
       if( nums[j]+nums[k]<-nums[i]) ++j;
       else if(nums[j]+nums[k]>-nums[i]) --k;
       else{
                 ans.push_back({nums[j],nums[k],nums[i]});
                 while(j<k && nums[j]==nums[j+1]) ++j;
                 while(j<k && nums[k]==nums[k-1]) --k;
                 ++j;--k;
           }
    }
return ans;
}

🐼:這樣時間複雜度是

O(n2)
🐶:很好,那如果我們今天不能對輸入的數值做排序,你有辦法解決問題嗎?
🐼:那我們可以用Hash Table來做,但空間複雜度也會增加。

初步檢討

針對 interviewer 的檢討:

  • 可以更深入對演算法的時間複雜度和空間複雜度做討論
  • 應該對第一段的程式碼提出質問,因爲沒有測試過

針對 interviewee 的檢討:

  • 說話的聲量不定,會忽大忽小 (尤其打code時説話會很小聲)
  • 說話用語可以再準確點 (vector array 要 分清楚)
  • 少用助語詞(舉例哪裡說 那,啊,啦,之類比較多)
  • 最好用test case 來驗證程式
  • 分析時間複雜度和空間複雜度時要用
    O(n3)
    不要只講
    n3
  • 第一段的程式碼要測試

同儕檢討

針對 interviewer 的檢討

  • 0:00: 避免說「這是我們面試的題目」這樣的開場,可改說「考慮到 ___ 情境,我們有時會想要得知連續記憶體空間內的資料分布,舉例來來說,我們想知道是否有其中三個元素總和為 0 的可能,以及發生三者總和為 0 的組合有幾個」
  • 1:28: 舉例時,避免頻繁使用滑鼠游標,在視訊會議中,滑鼠游標的移動可能會落後,甚至某些系統無法正確展現滑鼠游標,可改為選取標注的方式

針對 interviewee 的檢討

  • 3:16: 顯然有個好用的 container / 資料結構是答題的重要切入點,但應向 interviewer 確認是否可用 C++ STL,若不可用 STL (有些 interviewer 就想看應徵者的基本功和臨場反應),當然連帶也就不可用 vector

延伸閱讀: 3sum|4sum|ksum


112. Path Sum

模擬面試錄影

模擬面試過程

🐶:題目會給你一個二元樹的根節點

root 和 目標數
targetSum
。希望你可以找出根節點到葉節點的路徑,葉節點為沒有子節點的節點。
🐶:請注意路徑的所通過的節點值總和為
targetSum
時回傳
true
,否則回傳
false

🐶:二元樹的節點定義你可以參考這裏。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

🐶:請問你對題目有疑問嗎?
🐼:目前沒有,那我想用這裏的例子來驗證我對題目的理解。

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

targetSum=22

🐼:我另外再自己舉例説明。

   1
/      \
2      3    targetSum=5   false              []   false

🐼:請問我有理解錯題目嗎?
🐶:沒有,你可以開始寫你的程式。
🐼:在寫程式之前,我想先講一下我的想法。
🐼:我會先判斷節點是否為葉節點,如果不是的話就把目標數減掉節點的值,把減完的數值和子節點的值存到佇列。遇到葉節點時會比對減完的數值和子節點的值是否相同。佇列爲空時演算法結束。

迴圈解法

bool hasPathSum(TreeNode* root, int targetSum)
{
	if (!root) return false;
    queue<pair<TreeNode*, int>> q;
    q.push({root,targetSum-root->val});
    while (!q.empty()) {
        TreeNode *node=q.front().first;
        int sum = q.front().second;q.pop();
        if (!node->left && !node-> right && (sum==0)) return true;

        if (node->left)
            q.push({node->left,sum-node->left->val});
        if (node->right)
            q.push({node->right,sum-node->right->val});
    }
    return false;
}

🐶:你這邊使用了迭代的做法,請問你可以用遞迴的方式處理嗎?
🐼:可以,其實用遞迴和迭代的慨念差不多,但程式碼會簡潔很多。

遞迴解法

bool hasPathSum(struct TreeNode* root, int sum)
{
    if (!root)
        return false;
    if (!root->left && !root->right && root->val == sum) /* must be leaf */
        return true;
    return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}

//Test Case:
//    1
// /    \
// 2     3    targetSum=5 

初步檢討

針對 interviewer 的檢討:

  • 可以更深入對演算法的時間複雜度和空間複雜度做討論
  • 應該對第一段的程式碼提出質問,因爲沒有測試過
  • 可以問一下有關應用場景的問題

針對 interviewee 的檢討:

  • 說話的聲量不定,會忽大忽小 (尤其打code時説話會很小聲)
  • 第一段的程式碼要測試
  • 要討論一下BFS和DFS的應用

同儕檢討

程式碼的調整:

bool hasPathSum(struct TreeNode *root, int sum)
{
    if (!root) return false;

    sum -= root->val;
    if (!root->left && !root->right)
        return (sum == 0);
    return hasPathSum(root->left, sum) || hasPathSum(root->right, sum);
}

針對 interviewee 的檢討:

  • 應理解 DFS 和 BFS,並在 REACTO 早期就該聲明你的策略

延伸閲讀:


9. Palindrome Number

模擬面試連結: 9. Palindrome Number(英)

模擬面試過程

🐶:In this question, you are given an integer x, return true if x is a palindrome integer.
🐶:An integer is a palindrome when it reads the same backward as forward.
🐶:For example, 121 is a palindrome while 123 is not.
🐶:Do you have any questions about this question?
🐼:I think no. I want to use one example to check my understanding about this question

10 false 123321 true

🐼:Am I correct about this quetion?
🐶:Yeah, I think you are right. You can start codding now.
🐼:Before I start my coding, I want to explain my appoach to this problem.
🐼:I will first change the input number into string format.Then, I will reverse the string and check if it is same.

轉換成字串

bool isPalindrome(int x)
{
    string s= to_string(x);
    return s==string(rbegin(s), rend(s));
}

🐶:So your first appoach is to change the integer to string format. Can you solve the problem by not changing it to string?
🐼:Yes, we can check the number digit by digit.

121 % 10 =1 sum=1 // 1st iter
12 % 10 =2 sum=1*10+2=12 // 2nd iter
1 %10 =1 sum=12*10+1=121 // 3rd iter

Digit by Digit

bool isPalindrome(int x){
	int temp = x;
	long sum =0 ;
            while(x){
                            sum=sum*10+ x%10;
			x=x/10;
                         }
  return sum==temp;
}
 
//Test Case:
//-121 % 10 =-1  sum = -1
//-12 % 10 =-2    sum = -1*10-2=-12
//-1 %10=-1 sum=-12*10-1=-121

🐼:Seems that I fail to deal with negative numbers.

bool isPalindrome(int x){
	int temp = x;
	long sum =0 ;
	if(x<0) return false;
            while(x){
                        sum=sum*10+ x%10;
			            x=x/10;
                    }
  return sum==temp;
}

初步檢討

針對 interviewer 的檢討:

  • 沒有對演算法的時間複雜度和空間複雜度做討論
  • 應該對第一段的程式碼提出質問,負數輸入會有問題
  • 可以問一下有關應用場景的問題

針對 interviewee 的檢討:

  • 說話的聲量不定,會忽大忽小 (尤其打code時説話會很小聲)
  • 第一段的程式碼要測試,負數輸入會有問題自己沒發現
  • 第二段程式碼的測試發現有問題時沒有改第一段程式碼

相關閲讀材料: