---
tags: info2022
---
# 2022 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2022)」作業 1
> 胖達-Panda
> 🐶：interviewer
> 🐼：interviewee
> [模擬面試錄影(漢)](https://youtu.be/-eGgh2GsOFc)
> [模擬面試錄影(漢)](https://youtu.be/RC5Wn5U6bgM)
> [模擬面試錄影(英)](https://youtu.be/Aeqlc4_77NA)
## [15. 3sum](https://leetcode.com/problems/3sum/)
### 模擬面試過程
🐶：題目會給你一組數值，希望你把所有的組合找出來，組合有都是三個數值所組成，三個數值的總和為 $0$。請注意你的答案不能有重複的組合。
🐶：輸入最少有 $3$ 個數值，最多有 $3000$ 個。數值的值大小最小為$-10^5$,最大為$10^5$。
🐶：請問你對題目有疑問嗎？
🐼：有，我想請問輸入的數值有經過排序嗎？
🐶：沒有，題目預設輸入的數值沒有經過排序。
🐼：好的，爲了確認我對題目的理解，我想用一個例子説明
```cpp
輸入： [-1,0,1,-1,2,-5]
輸出： {[-1,0,1],[-1,-1,2]}
```
🐼：請問我有理解錯題目嗎？
🐶：沒有，你可以開始寫你的程式了。
🐼：在寫程式之前，我想先講一下我的想法。
🐼：最直觀的解法是用三個迴圈，把所有組合列舉出來，然後用一判斷式判斷三個數值的總和是否為$0$。
🐼：至於重複的組合，我們可以先把輸入的數值進行排序，然後用 $set$ 把答案存起來，防止加入重複組合。
### 暴力解法（3個迴圈）
```cpp
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());
}
```
🐶：你用三個迴圈把所有組合列舉出來是可以解決我們的題目。但以實務層面來説，輸入資料十分大時，程式的效能會很差。請問你有辦法解決嗎？
🐼：的確，用三個迴圈的時間複雜度是 $n^3$。我的想法是用排序過的數值所提供給我們的資訊，先用一個迴圈把第一個數值選出來，然後用雙指標把第二，三個數值給找出來。
### 利用快慢指標走訪
```cpp
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(n^2)$。
🐶：很好，那如果我們今天不能對輸入的數值做排序，你有辦法解決問題嗎？
🐼：那我們可以用Hash Table來做，但空間複雜度也會增加。
### 初步檢討
針對 interviewer 的檢討:
* 可以更深入對演算法的時間複雜度和空間複雜度做討論
* 應該對第一段的程式碼提出質問，因爲沒有測試過
針對 interviewee 的檢討:
* 說話的聲量不定，會忽大忽小 (尤其打code時説話會很小聲)
* 說話用語可以再準確點 （vector array 要 分清楚）
* 少用助語詞（舉例哪裡說 那，啊，啦，之類比較多）
* 最好用test case 來驗證程式
* 分析時間複雜度和空間複雜度時要用 $O(n^3)$ 不要只講 $n^3$
* 第一段的程式碼要測試
### 同儕檢討
針對 interviewer 的檢討
* [0:00](https://youtu.be/-eGgh2GsOFc): 避免說「這是我們面試的題目」這樣的開場，可改說「考慮到 ___ 情境，我們有時會想要得知連續記憶體空間內的資料分布，舉例來來說，我們想知道是否有其中三個元素總和為 0 的可能，以及發生三者總和為 0 的組合有幾個」
* [1:28](https://youtu.be/-eGgh2GsOFc?t=88): 舉例時，避免頻繁使用滑鼠游標，在視訊會議中，滑鼠游標的移動可能會落後，甚至某些系統無法正確展現滑鼠游標，可改為選取標注的方式
針對 interviewee 的檢討
* [3:16](https://youtu.be/-eGgh2GsOFc?t=196): 顯然有個好用的 container / 資料結構是答題的重要切入點，但應向 interviewer 確認是否可用 C++ STL，若不可用 STL (有些 interviewer 就想看應徵者的基本功和臨場反應)，當然連帶也就不可用 `vector`
*
延伸閱讀: [3sum|4sum|ksum](https://leetcode.com/problems/4sum/discuss/732885/3sum4sumksum)
---
## [112. Path Sum](https://leetcode.com/problems/path-sum/)
> [模擬面試錄影](https://youtu.be/vcccBHvvoJw)
### 模擬面試過程
🐶：題目會給你一個二元樹的根節點 $root$ 和 目標數 $targetSum$。希望你可以找出根節點到葉節點的路徑，葉節點為沒有子節點的節點。
🐶：請注意路徑的所通過的節點值總和為 $targetSum$ 時回傳 $true$,否則回傳 $false$。
🐶：二元樹的節點定義你可以參考這裏。
```cpp
/**
* 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) {}
* };
*/
```
🐶：請問你對題目有疑問嗎？
🐼：目前沒有，那我想用這裏的例子來驗證我對題目的理解。
$targetSum=22$
🐼：我另外再自己舉例説明。
```plain text
1
/ \
2 3 targetSum=5 false [] false
```
🐼：請問我有理解錯題目嗎？
🐶：沒有，你可以開始寫你的程式。
🐼：在寫程式之前，我想先講一下我的想法。
🐼：我會先判斷節點是否為葉節點，如果不是的話就把目標數減掉節點的值，把減完的數值和子節點的值存到佇列。遇到葉節點時會比對減完的數值和子節點的值是否相同。佇列爲空時演算法結束。
### 迴圈解法
```cpp
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;
}
```
🐶：你這邊使用了迭代的做法，請問你可以用遞迴的方式處理嗎？
🐼：可以，其實用遞迴和迭代的慨念差不多，但程式碼會簡潔很多。
### 遞迴解法
```cpp
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的應用
### 同儕檢討
程式碼的調整:
```c
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 早期就該聲明你的策略
延伸閲讀:
* [DFS](https://alrightchiu.github.io/SecondRound/graph-depth-first-searchdfsshen-du-you-xian-sou-xun.html)
* [BFS](https://alrightchiu.github.io/SecondRound/graph-breadth-first-searchbfsguang-du-you-xian-sou-xun.html)
---
## [9. Palindrome Number](https://leetcode.com/problems/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
```cpp
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.
### 轉換成字串
```cpp
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.
```cpp
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
```cpp
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.
```cpp
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時説話會很小聲)
* 第一段的程式碼要測試，負數輸入會有問題自己沒發現
* 第二段程式碼的測試發現有問題時沒有改第一段程式碼
相關閲讀材料:
* [Palindrome 演算法筆記](https://web.ntnu.edu.tw/~algo/Palindrome.html)
* [Palindrome 應用](https://www.itm-conferences.org/articles/itmconf/pdf/2020/02/itmconf_icacc2020_03006.pdf)
* [2021 年模擬面試](https://hackmd.io/@sysprog/S18FUpCBK)
Sign in with Wallet
Connect another wallet