# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 暱稱: 呆呆獸 Slowpoke
> 👨💼： Interviewer
> 🙋♂️： Intreviewee
## [**27. Remove Element (Easy)**](https://leetcode.com/problems/remove-element/?envType=study-plan-v2&envId=top-interview-150)
> [錄影](https://youtu.be/Sh17ndeEbgY)
### 模擬面試過程
👨💼： 今天的面試，我們希望你能夠實作 Remove Element，這個算法可以幫助我們快速地清理數據，我們會給你一段整數 array 跟一個指定的整數 K，希望你能將所有等於 K 的值排列在 array 的最前面，並回傳不等於 K 的數量，array 內的其他數值以及 array 的大小並不重要。要注意的是，所有動作必須要 in-place。
👨💼： Array 的長度為 0~100，數值大小介於 0~50。
🙋♂️： 我想舉個例子確認一下題意。
``` cpp
Input: nums = [1,3,2,2,3], K = 3
Output: 3, nums = [1,2,2,_,_]
```
🙋♂️： 請問這個例子正確嗎?
👨💼： 沒有問題。
🙋♂️： 我的想法是使用一個 for 迴圈去看過每一個數值，如果不等於 K，就會把他往前放，所以我會再添加一個指標來記錄上次往前放的位置。
👨💼： 了解，你可以開始進行實作了。
``` cpp
int removeElement(vector<int>& nums, int K) {
int ptr = 0;
for (int i=0; i<nums.size(); i++){
if (nums[i] != K){
nums[ptr] = nums[i];
ptr++;
}
}
return ptr;
}
```
🙋♂️： 由於只有一層 for 迴圈，所以時間複雜度為 $O(N)$。
👨💼： 程式碼沒問題。
👨💼： 但你的程式看似有一些多餘的步驟，比如在你的舉例當中，1 會寫入 1 自己的位置，你有什麼解決辦法嗎?
🙋♂️： 那我另一個指標應該要從 array 的後面開始找，如果前面的指標遇到等於 K 的數字，就要跟後面指標交換，接著更新指標位置，直到前後指標重合。
``` cpp
int removeElement(vector<int>& nums, int K) {
int i=0;
int j = nums.size()-1;
while (i<=j){
if (nums[i] == K){
nums[i] = nums[j];
j--;
}
else{ i++; }
}
return j+1;
}
```
👨💼： 看起來沒什麼問題，我們再舉個例子測試一下。
``` cpp
Input: nums = [1], K = 1
Output: 0, nums = [_]
```
👨💼： Okey，沒有問題。
👨💼： 但在現實情境中，有時候我們會希望資料經過刪除後，同時資料所占用的空間也變少。對應到這個題目，我們希望在 Remove Element 後， capacity 也可以降低，你會怎麼修改呢?
🙋♂️： 我會使用 C++ 中 copy 跟 swap 的特性來完成，首先將原本的 array 複製一份到新的空間，這個步驟配置剛剛好的容量，接下來使用 swap 來改變記憶體位置。
``` cpp
int removeElement(vector<int>& nums, int val) {
int i=0;
int j = nums.size()-1;
while (i<=j){
if (nums[i] == val){
nums[i] = nums[j];
j--;
}
else{ i++; }
}
int result = j+1;
nums.erase(nums.begin()+result, nums.end());
vector<int>(nums).swap(nums);
return result;
}
```
## [**15. 3Sum (Medium)**](https://leetcode.com/problems/3sum/?envType=study-plan-v2&envId=top-interview-150)
> [錄影](https://youtu.be/O28WIYcjKZw)
### 模擬面試過程
👨💼： "3Sum" 是一個經典的算法問題，稍加改良後，能夠應用在資料庫查詢或金融交易分析中。在這個問題中，輸入會是一串整數，我們希望找出所有不重複的三個數字組合，使它們的總和等於零，請注意你的答案不能有重複的組合。
👨💼： 總共有 3 ~ 3000 個數值，數值的大小介於 $-10^5$ ~ $10^5$
🙋♂️： 請問 input 和 output 的資料型態, 我可以假設是 C++ 中的 vector 嗎？
👨💼： 可以這樣假設。
🙋♂️： 好的，為了更好的理解題目，我想舉個例子確認一下。
``` cpp
輸入： [-1,0,1,2,-1,-1,-1,2]
輸出： [[-1,-1,2],[-1,0,1]]
```
🙋♂️： 請問這樣有符合題意嗎?
👨💼： 這樣有符合。
🙋♂️： 那如果找不到符合條件的解，是不是回傳空的 vector 即可?
👨💼： 對。
🙋♂️： 我最初步的想法，是使用三層迴圈去找到所有解，並使用集合去儲存這些解以避免重複，不過這個演算法的時間複雜度是 $O(N^3)$，非常沒有效率，所以我會想使用雙指標來解決這個問題。首先，先對所有數值做升冪排序，接著使用一層 for 迴圈，每次固定一個值，剩下兩個值使用雙指標去選出來。
👨💼： 了解，你可以開始進行實作了。
``` cpp
vector<vector<int>> threeSum(vector<int>& nums) {
int length = nums.size();
set<vector<int>> result_set = {};
sort(nums.begin(), nums.end());
for (int i=0; i<length-2; i++){
int left = i+1;
int right = length -1;
while (left < right){
if ((nums[i] + nums[left] + nums[right]) > 0) { right--;}
else if ((nums[i] + nums[left] + nums[right]) < 0) {left++;}
else {
result_set.insert({nums[left], nums[i], nums[right]});
left++;
}
}
}
vector<vector<int>> result(result_set.begin(), result_set.end());
return result;
}
```
🙋♂️： 排序的時間複雜度為 $O(N\log N)$，迴圈跟雙指標的時間複雜度為 $O(N^2)$，所以這個演算法的時間複雜度為 $O(N^2)$。
👨💼： 你目前的演算法有用到集合，插入元素的時候，會需要維護的成本，如果不要使用集合，你有什麼想法嗎?
🙋♂️： 有的，重複的組合是由於相同的數值被選擇多次造成的，我們可以利用排序過後的特性，當連續出現相同數值時，可以直接跳過，來避免選到重複的組合。
``` cpp
vector<vector<int>> threeSum(vector<int>& nums) {
int length = nums.size();
vector<vector<int>> result = {};
sort(nums.begin(), nums.end());
for (int i=0; i<length-2; i++){
int left = i+1;
int right = length -1;
while (left < right){
if ((nums[i] + nums[left] + nums[right]) < 0) {left++;}
else if ((nums[i] + nums[left] + nums[right]) > 0) { right--;}
else {
result.push_back({nums[left], nums[i], nums[right]});
while (left < right && nums[left] == nums[left+1]) {left++;}
while (left < right && nums[right] == nums[right-1]) {right--;}
left++;
}
}
while (i < length-2 && nums[i] == nums[i+1]) {i++;}
}
return result;
}
```
## [**637. Average of Levels in Binary Tree (Easy)**](https://leetcode.com/problems/average-of-levels-in-binary-tree/?envType=study-plan-v2&envId=top-interview-150)
> [錄影](https://youtu.be/W66rCiuSKDk)
### 模擬面試過程
👨💼： Now I want to discuss a question about binary trees, "Average of Levels in Binary Tree" The number of nodes in the tree is in the range [1, 100]. Please follow the definition below for the structure of the binary tree.
``` cpp
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
};
```
🙋♂️： Could the node values be float?
👨💼： Let's assume they are integers.
🙋♂️： Okey. I want to provide an example to help me understand the question.
```graphviz
digraph graphname{
node[shape=circle]
{
A[label=3]
B[label=9]
C[label=20]
D[label=NULL, shape=plaintext]
E[label=NULL, shape=plaintext]
F[label=15]
G[label=7]
}
A->B;A->C;
B->D;B->E;
C->F;C->G;
}
```
🙋♂️： In this example, I need to return [3, 14.5, 11]. Did I get it right? Even though the input values are integers, the output values might be float.
👨💼： Yes, your understanding is right.
🙋♂️： For this question, my initial idea is to use DFS to visit each node and use a table to keep track of the total sum and the number of nodes at each level. Finally, we can calculate the average.
``` cpp
void dfs(TreeNode* root, int level, vector<pair<double, int>>& sum_levels) {
if (!root) return;
int k = root->val;
if (sum_levels.size() <= level) { sum_levels.push_back({k,1}); }
else{
sum_levels[level].first += k;
sum_levels[level].second++;
}
dfs(root->left, level+1, sum_levels);
dfs(root->right, level+1, sum_levels);
}
vector<double> averageOfLevels(TreeNode* root) {
vector<pair<double, int>> sum_levels;
vector<double> result;
dfs(root, 0, sum_levels);
for (int i=0; i<sum_levels.size(); i++){
double sum = sum_levels[i].first;
int num = sum_levels[i].second;
result.push_back(sum/num);
}
return result;
}
```
🙋♂️： Since DFS visits each node only once, the time complexity is $O(\lvert V\rvert)$, and the space complexity is also $O(\lvert V\rvert)$ because, for imbalanced trees, the depth of recursion could be equal to the number of nodes.
👨💼： It looks good, but in some cases, I might only want to calculate the average for a specific level. With your method, I would still have to traverse the entire tree. Do you have a way to improve this issue?
🙋♂️： I want to use BFS to visit each node layer-by-layer and calculate the average for nodes on the same level. This way, we can compute averages in the order we want.
``` cpp
vector<double> averageOfLevels(TreeNode* root) {
vector<double> result;
queue<TreeNode*> node_queue;
node_queue.push(root);
while (!node_queue.empty()) {
double sum = 0;
int size = node_queue.size();
for (int i=0; i<size; i++) {
TreeNode* node = node_queue.front();
sum += node->val;
node_queue.pop();
if (node->left != NULL) {node_queue.push(node->left);}
if (node->right != NULL) {node_queue.push(node->right);}
}
result.push_back(sum/size);
}
return result;
}
```
🙋♂️： The time complexity and space complexity are both $O(\lvert V\rvert)$. This is because BFS visits each node only once, and in the worst case, all nodes might be stored in the queue.
### 總體檢討
* 說話太糊，咬字不清楚，需要平常多注意。
* 聲音太小，語氣不夠肯定。
* 對話中太多 "嗯"，要改
* 英語口說要加強
- [ ] 針對 interviewer 的檢討
* 可以針對程式碼，進行更多的測試。
- [ ] 針對 interviewee 的檢討
* 打程式碼的時候，應該要配合階段性解說，讓 interviewer 更加清楚程式碼的脈絡。
* 會有過長的沉默時間，應蓋要盡量的講出 "預計要做" 或 "正在做" 的事。
---
## 他評01
- [ ] 優點
* 聲音柔和
* 第一題interviewer指出interviewee程式碼的問題並請其改正，有良好的互動性。
* 說明自己的想法後再開始實作。
* interviewee提出問題增進和interviewer的互動性。
- [ ] 可改進的地方
* 語氣可以更強這樣感覺起來更有自信。
* 聲音和背景音融合在一起，不容易聽清楚，也許說大聲點或是語氣有抑揚頓挫會更好。
* 那個打字一直出現的「拍噠」聲音聽起來好燥==
* 打程式碼的時候可以邊打邊說明程式碼的用途，不然好安靜。
* 第二題可以不用說出3sum，直接進入情境題。
## 他評02
### Interviewer
- [ ] 優點
* 說明題目很清楚
* 英文口說不錯
- [ ] 可改進的地方
* 也許一開始就可以說明情境，把完整的題意更清楚的說明。
### Interviewee
- [ ] 優點
* 在寫程式過程中，思考蠻清楚的。只要配上解釋應該就會好很多
* 寫程式中其實都沒卡頓，我認真覺得蠻厲害的
* 英文口說蠻好的
* 覺得可以再把整個思路講得更清楚一些
* 程式看起來很簡潔明瞭
- [ ] 可改進的地方
* 在撰寫程式碼過程中可以邊說明，不然過多留白會蠻尷尬的
* 可以跟面試官討論一下是否可以用C++
* [10:02](https://youtu.be/Sh17ndeEbgY?si=5wrniHEYgYDjDjx5&t=602): 為什麼Erase過後還要重新配置空間呢? C++的erase是真的會把size縮小的吧? 如果我理解錯誤有沒有參考資料plz。 Sundew [這是我的認知](https://www.geeksforgeeks.org/vector-erase-and-clear-in-cpp/)。[查資料又查到一個很有趣的](https://stackoverflow.com/questions/347441/erasing-elements-from-a-vector) 這邊小弟去實驗stackoverflow std::remove+vector.erase 的結果 
* 第二部[2:58](https://youtu.be/O28WIYcjKZw?si=w5bl14quGE-3CyW8&t=178): 也許講話要大聲一點可能比較清晰? 我自己背景也會有噪音所以是有後製把噪音去掉，看有沒有人有推薦麥克風，可以改善雜音太多的問題，我是用Iphone耳機
* 第三部[0:26](https://youtu.be/W66rCiuSKDk?si=4MT0MY0l-2W49Skq&t=26): 題目上已經給int了 還是意思是return value..
## 他評03
### Interviewer
- [ ] 優點
* 提問的時候有指出需要改進的地方。
* 英文口說咬字很清晰。
- [ ] 可改進的地方
* 文字可以稍微大一點。
* 提問環節時互動可以再多一點。
## Iterviewee
- [ ] 優點
* 程式撰寫的時候很流暢。
- [ ] 可改進的地方
* 可以在邊撰寫程式邊說明，或是在寫某一行條件時候 (像是 while 的中止條件) 可以先講解後再寫。
* DFS 的時間複雜度，可以說明 $V$ 的定義是節點數。
## 他評04
### Interviewer
- [ ] 優點
* 清楚說明出題目的與可應用的地方
* 面試互動完整
- [ ] 可改進的地方
* 可以將題目直接套入情境之中
* 可以多給予點題目的解釋
### Iterviewee
- [ ] 優點
* 遵循Reacto，與面試官互動良好
* 程式撰寫流暢
* 時間複雜度分析清楚
- [ ] 可改進的地方
* 程式撰寫時空白時間太長，宜適當加入註解與說明
* 第三題主體想法是DFS，可以先從這部分先進行撰寫與說明
## 他評05
### interviewer
- [ ] 優點
* 有使用情景為什麼需要做這個東西
* 有另外舉一個input測試interviewee
- [ ] 可改進之處
* 如果interviewee寫程式走火入魔了完全沒解說，可以主動提出一些問題打破尷尬
### interviewee
- [ ] 優點
* 有使用例子與interviewer確認自己的理解是否正確
* 有先用較差的時間復雜度再優化
- [ ] 可改進之處
* 沉默時間太長，在coding的時候應該伴隨著講解
## 他評06
### interviewer
- [ ] 優點
* 舉出實作上可以應用的地方很棒。
* 向interviewee提出問題，交流是否有地方需要改進，互動良好。
- [ ] 可改進之處
* 有時候會有一小段字突然糊掉、聽不清楚。
* 第二題不需要特別說題目名稱關鍵字，這樣刷題者馬上就手癢想寫了XD。
### interviewee
- [ ] 優點
* 對答橋段良好，REACTO完整。
- [ ] 可改進之處
* 一邊寫一邊卻沒有說明，建議在撰寫的時候配合說明，可以清楚讓面試主持人知道在幹嘛。
* 承上，配合在各個程式片段下註解，更可以有效傳達自己的想法。
Sign in with Wallet
Connect another wallet