---
tags: info2023-homework1
---
# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> [模擬面試錄影(漢)](https://youtu.be/sqPCM6ESEZg)
> [模擬面試錄影(漢)](https://youtu.be/-ul6w3t3rgw)
> [模擬面試錄影(英)](https://www.youtube.com/watch?v=QEG4Gdv7aho)
>
> interviewer: :bearded_person:
> interviewee: :monkey_face:
## [101.Symmetric Tree](https://leetcode.com/problems/symmetric-tree/)
> [video](https://youtu.be/sqPCM6ESEZg)
### 題目描述
給定一棵二元樹，檢查它是否是其自身的鏡像（即圍繞其中心對稱）。
```cpp
例如，這個二元樹是對稱的：
1
/ \
2 2
/ \ / \
3 4 4 3
但這個不是：
1
/ \
2 2
\ \
3 3
```
### 程式碼解說
已知樹節點資料結構如下：
```cpp
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode():val(0), left(nullptr), right(nullptr) {}
};
```
#### ***方案一 : Recursion***
```cpp
class Solution {
public:
bool isSymmetric(TreeNode *root) {
if (!root) return true;
return isSymmetric(root->left, root->right);
}
bool isSymmetric(TreeNode *left, TreeNode *right) {
if (!left && !right) return true;
if (left && !right || !left && right || left->val != right->val){
return false;
}
return isSymmetric(left->left, right->right)
&& isSymmetric(left->right, right->left);
}
};
```
最快想到的方法就是用遞迴解決，因為程式碼可讀性高，而且相對容易撰寫。
首先確定根節點是否存在，接著透過遞迴持續比對將所有子節點，直到走訪所有節點。
比對方法左右子樹節點是否一有一無，或者是值不相同。
比對時需注意“左子樹右節點”是和“右子樹左節點”比對，以此類推。
優點：可讀性高，容易撰寫和維護。
缺點：當在binary tree很大時，運行遞迴需維護的stack可能會無法負荷。
時間複雜度最差就是O(n)，因為必須要比完所有的節點才知道是否對稱。
#### ***方案二 : Queue***
```cpp
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (!root) return true;
queue<TreeNode*> q1, q2;
q1.push(root->left);
q2.push(root->right);
while (!q1.empty() && !q2.empty()) {
TreeNode *node1 = q1.front(); q1.pop();
TreeNode *node2 = q2.front(); q2.pop();
if (!node1 && !node2) continue;
if((node1 && !node2) || (!node1 && node2)) return false;
if (node1->val != node2->val) return false;
q1.push(node1->left);
q1.push(node1->right);
q2.push(node2->right);
q2.push(node2->left);
}
return true;
}
};
```
不用遞迴的話，就要自己透過一些資料結構來紀錄節點資訊了。
我選擇用兩個queue來紀錄兩邊的節點，並加以比對。
需注意的是while loop的結束條件是queue為空，與遞迴時不一樣，當子節點皆為nullptr時還是需要繼續比對，因為有可能是左子樹的左子點為空但右子點不同的情形
時間複雜度一樣最差就是O(n)，因為必須要比完所有的節點才知道是否對稱。
## [39.Combination Sum](https://leetcode.com/problems/combination-sum)
> [video](https://youtu.be/-ul6w3t3rgw)
### 題目描述
給定一組不重複的候選數字 (candidates)和一個目標數(target)，請找出候選數字中加總和達到目標數的所有組合。
其中可以從候選數字中無限次地選擇同個數字。
所有數字（包括目標數）都是正整數。
```cpp
範例：
Input: candidates = [2,3,6,7]
target = 7,
A solution set is:
[
[2,2,3],
[7]
]
```
### 程式碼解說
#### ***方案 : Recursion DFS***
```cpp
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ans;
vector<int> cur;
std::sort(candidates.begin(), candidates.end());
dfs(candidates, target, 0, cur, ans);
return ans;
}
void dfs(vector<int>& candidates, int target, int s, vector<int>& cur, vector<vector<int>>& ans) {
if (target == 0) {
ans.push_back(cur);
return;
}
for (int i = s; i < candidates.size(); ++i) {
if (candidates[i] > target) break;
cur.push_back(candidates[i]);
dfs(candidates, target - candidates[i], i, cur, ans);
cur.pop_back();
}
}
};
```
用遞迴做深度優先搜尋如上圖，使用cur來紀錄每次搜尋過程，一但符合target，就存到ans中。
而在此之前，可以先排序候選數字 (candidates)，這樣搜尋過程中遇到候選數字 (candidates）大於target的情況，就能確保後面的數字都大於target，不用再繼續找下去。且遞迴也可以從最小開始找起。如此一來就能找出所有可能組合解。
## [70.Climbing Stairs](https://leetcode.com/problems/climbing-stairs/)
> [video](https://www.youtube.com/watch?v=QEG4Gdv7aho)
### 題目描述
Imagine you're climbing a staircase with 'n' steps, and you can either climb 1 step or 2 steps at a time. how many different ways can you reach the top?
```cpp
Example:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
* 1 step + 1 step
* 2 steps
```
### 程式碼解說
#### ***方案一 : Recursion***
```cpp
int climbStairs(int n) {
if(n==1) return 1;
if(n==2) return 2;
return climbStairs(n-1)+climbStairs(n-2);
}
```
This recursive function will make two recursive calls for each input 'n' except for the base cases when 'n' is 1 or 2.
Therefore, the number of recursive calls grows exponentially with 'n' because each call branches into two more calls.
So The time complexity can be expressed as O($2^n$), where 'n' is the input size (number of steps).
This is a fairly high time complexity and will lead to very high computational costs when the number of stairs is large.
#### ***方案二 : Dynamic Programming***
```cpp
int climbStairs(int n) {
if (n <= 1) return 1;
vector<int> climb_ways(n);
climb_ways[0] = 1;
climb_ways[1] = 2;
for(int i=2; i<n; i++){
climb_ways[i] = climb_ways[i-1]+climb_ways[i-2];
}
return climb_ways[n-1];
}
```
This algorithm uses a for loop to iterate through 'n' steps to calculate the number of ways to reach each step.
In the loop, it performs constant-time operations for each step.
Therefore, the time complexity of this dynamic programming solution is O(n), where 'n' is the input size (number of steps).
# 第二次作業-他評01
## interviewer
### 優點
- 面試過程輕鬆不會太上對下
### 可改進的地方
- 可以將變數限制交給面試者來詢問，一方面看看他是否有在思考邊界條件，另一方便也可以促進溝通
- 面試者的答案都全肯定，建議面試官可以明知故問，給面試者解釋的機會，也可更加理解對面試者的想法
- 建議可以用實際例子來包裝問題
## interviewee
### 優點
- 懂得適時求助面試官給予引導
- 口齒清晰
### 可改進的地方
- 可以把程式碼放在REACTO中的最後一步，coding階段可以先思考最直觀且最暴力的解法，給面試官一個「我可以在短時間內優化」的印象
- repeat(R)階段與example(E)階段同時並行，建議先理解題目意圖再進行舉例
# 第二次作業-他評02
## interviewer
### 優點
- 與 interviewee 的互動很好
- 發問精簡，也有引導 interviewee 優化
### 可改進的地方
- 題目可再做些包裝
## interviewee
### 優點
- 依循 REACTO 流程，有將 Approach 充分討論
- 邊講解例子邊寫出來，讓人容易理解
### 可改進的地方
- 英文解說有點卡卡的
# 第二次作業-他評03
## interviewer
### 優點
- [13:18](https://youtu.be/sqPCM6ESEZg?si=igU6goXCf72nlWEy&t=798):針對程式碼有提供具體的問題，增加討論的空間。
### 可改進的地方
- 若可以用一些生活的例子或是情境來包裝題目會更好。
## interviewee
### 優點
- 整個面試的過程很自然而且很流暢，說明也很清楚。
### 可改進的地方
- [00:56](https://youtu.be/sqPCM6ESEZg?si=7-QywUbm-qumvW0y&t=56):在打例子時我覺得可以稍微說明或是說點話，讓空氣不要太安靜
# 第二次作業-他評04
## interviewer
### 優點
### 可改進的地方
- [14:53](https://youtu.be/QEG4Gdv7aho?si=7506IuDzullVuipj&t=14m53s): 結尾應該要說面試結束之類的客套話。
## interviewee
### 優點
- 解釋方法步驟清楚。
- [8:40](https://youtu.be/-ul6w3t3rgw?si=XTT4ByFhovayfeaJ&t=8m40s): `&`是講專業術語不是and。
### 可改進的地方
- 不應該用有自動補齊的工具。
- 打錯的字有點太多。
- 可以適度反白解釋會更清楚。
- [4:50](https://youtu.be/sqPCM6ESEZg?si=NIbKlNbs6QHyi6l3&t=4m50s): 應該是樹的結構，而且理論上應該要先宣告`struct`再寫主程式。
- [8:25](https://youtu.be/-ul6w3t3rgw?si=XTT4ByFhovayfeaJ&t=8m25s): `start`變數取名為`start_index`或`start_pos`會更清楚，或者在主程式的時候可以先寫註解解釋。
- [13:55](https://youtu.be/-ul6w3t3rgw?si=XTT4ByFhovayfeaJ&t=13m55s): 因為是直接用內建的C++函式，所以是Introsort，排序最佳、平均、最壞時間複雜度都是$O(nlogn)$。
- [13:30](https://youtu.be/QEG4Gdv7aho?si=7506IuDzullVuipj&t=13m30s): 可以將$i<n$的部分反白，會更清楚為何要多一個if的條件判斷。
Sign in with Wallet
Connect another wallet