# 2023 年「資訊科技產業專案設計」作業 1
> [模擬面試錄影-1](https://www.youtube.com/watch?v=U1ojxdzmT9w) (漢) 1. Two Sum
> [模擬面試錄影-2](https://www.youtube.com/watch?v=q3-dDTSpM6I) (漢) 11. Container With Most Water
> [模擬面試錄影-3](https://www.youtube.com/watch?v=A0QBc7ogT9o) (英) 226. Invert Binary Tree
>
> **interviewee** : 😷 郝主意 Goodidea
> **interviewer** : 🎃
## [1. Two Sum](https://leetcode.com/problems/two-sum/)
> `C++`
🎃: 題目是給你一個整數陣列`nums`，以及一個目標整數`target`，請你找出陣列`nums`中哪兩個數字的和會等於目標數字`target`，最後給出這2個數字在`nums`裡的index。 有任何問題可以提出。
> ==不應該直接講題目==。可以帶入某個環境
ex: 有個倉儲公司有一堆不同長度的盒子，某個倉儲任務是要將不同長度的盒子兩兩存放在指定長度的貨櫃內，在只考慮盒子長度的情況下，給定的貨櫃長度，希望你能找到剛好塞入貨櫃的組合以節省空間...之類的。==用引導的方式讓interviewer思考==，這樣才能知道他的想法。
😷: 如果有多個組合的和都等於目標數字是回傳任一一種組合嗎? 🎃: 是的。
😷: 找不到組合或是輸入為空陣列的話就回傳空? 🎃: 是的。
😷: 我舉例一下，若一組輸入是[1,2,3,4,5]，目標數字是4的話，我要輸出[0,2]，這樣理解對嗎? 🎃: 是的。
😷: 1:42 我初步的想法是用兩個for迴圈去找，第一個for迴圈是找第一個數字，第二個for迴圈是找第二個數字，這樣依序跑下去，把這2個數字加起來。然後去check是不是跟目標數值相等。
用這種方式一直去記錄並更新最大值。同時也要記錄產生最大值的那2個index是多少，最後回傳答案。
```cpp
vector<int> Sum(vector<int>& nums, int target) {
int n = nums.size();
for(int i=0; i<n; i++){
for(j=i+1; j<n; j++){
if (nums[i] + nums[j] == target) {
return {i, j};
}
}
}
return {};
}
```
> 應在自訂函式前先令
`vector<int> nums = {1,2,3,4,5}; `
`int target = 5;` 之類的，讓 interviewer 知道預計 input 的資料型態是什麼。 最後也應對這個vector套用自訂函式，如：`int ans = Sum(nums, target);`
🎃: 你覺得這段程式碼有哪些地方可以改進讓程式碼的運算效率提高？
😷: 目前這段程式碼有2個for迴圈，所以時間複雜度是 $O(n^2)$。如果要提高運算速度的話，我覺得可以從 **第6行** 運算式來改。
```
nums[i] + nums[j] == target
```
😷: 因為在第2個for迴圈裡面，每次在if判斷的時候，都會執行一個加法運算。如果在第一個for迴圈的時候，把這個加法運算改成用`target`減去第一個數值`nums[i]`並記錄他們的差`error`，再進到第2個for迴圈去跟`nums[j]`比較，就可以省下每次在第2個for迴圈裡if的加法運算時間。
```cpp
vector<int> Sum(vector<int>& nums, int target) {
int n = nums.size();
for(int i=0; i<n; i++){
int error = target - nums[i];
for(j=i+1; j<n; j++){
if (nums[j] == error) {
return {i, j};
}
}
}
return {};
}
```
## [11. Container With Most Water](https://leetcode.com/problems/container-with-most-water/)
> `python`
🎃: 題目是給你一個`n`長度的整數陣列`height`，請你在這個陣列裡找出2個高，使得這2個高圍出來的蓄水面積是最大值，最後回傳這個面積最大值是多少。
> ==不應該直接講題目==，可以帶入某個環境：
e.g., 有個水庫工程預計要在山坡建設，事前有評估從上游至下游每個地點的圍牆可建設高度，希望能找到最大的水庫蓄水範圍...之類的。==用引導的方式讓interviewer思考==。
😷: 水位的最高處是由所選的兩個`height`比較短的那條決定? 🎃: 是
🎃: 底是由所選的兩個位置的差值決定？ 🎃: 是
😷: 我舉例一下，若輸入是[5,1,2,3,4]，因為最大蓄水是頭尾的高而且水位是4，所以輸出4*4=16，這樣理解對嗎? 🎃: 是的。
🎃: 若準備好的話可以開始作答。
😷: 初步的想法是用2個for迴圈決定出2個點。再用這2個位置找值，並更新它的最大值。首先定義一個函式叫做max_area()，它的輸入就是一串陣列。
```python
# python
def max_area(height):
ans = 0
area = 0
for i in range(len(height):
for j in range(i+1,len(height)):
area = min(height[i],height[j]) * (j-i)
if area > ans:
ans = area
return ans
```
> 應在 def 函式前先令一個 array 叫 `height = [5,1,2,3,4]` 之類的，讓 interviewer 知道 input 的資料型態是什麼。 最後也應對這個 array 套用自訂函式，如： `max_area(height)`
🎃: 大概了解你的思路了。你用了2個for迴圈，時間複雜度應該蠻高的。你覺得有什麼方法可以改進它嗎？
😷: 2個for迴圈的時間複雜度是 $O(n^2)$，計算時間會有點久。如果要降低時間複雜度的話，我覺得可以從整個**陣列的兩端下去比較，慢慢往中間去尋找**。選的方式是從兩端比較矮的高度開始往內去尋找。當一邊的高度超越另外一邊的時候，則換另外一邊往內尋找。直到找到最佳解，這樣<font color="#a00">~~時間複雜度只剩 n~~</font>。
>* 6:55 講清楚 $O(n)$，別只講 $n$。
>* 講「從兩端下去找」雖然易懂但有點抽象，可==舉例補充==「分別設定一個index在array的頭和尾」。
```python
# python
def max_area(height):
left = 0
right = len(height-1)
ans = 0
area = 0
while left < right:
area = min(height[i], height[j]) * (j-i)
if area >= ans:
ans = area
if height[left] <= height[right]:
left += 1
else:
right -= 1
return ans
```
🎃: while迴圈內的i跟j是不是有問題?
😷: 我修正一下
> 12:00 打完沒看到bug還被interviewer抓到，==應避免==。
＃ 沒重新錄影是希望保留錯誤示範，而且這種情況是真的有可能發生。
```python
# python
def max_area(height):
left = 0
right = len(height-1)
ans = 0
area = 0
while left < right:
area = min(height[left], height[right]) * (right-left)
if area >= ans:
ans = area
if height[left] <= height[right]:
left += 1
else:
right -= 1
return ans
```
🎃: 有沒有辦法讓程式碼再更精簡一點?
😷: 原先是左邊或右邊每往內一次就計算一次蓄水面積，如果往內找時高度還比原先小、寬度又沒有比較寬，不可能有更大的面積。因此往內找的時候，找到更大的高度再計算面積就好。
> 這裡interviewee最後打的程式碼沒有更精簡，反而變更長、更醜，但目的是希望提高計算效率。==可以有自己的想法，但要先跟interviewer講，免得答非所問==。
```python
# python
def max_area(height):
left = 0
right = len(height-1)
ans = 0
area = 0
while left < right:
area = min(height[left], height[right]) * (right-left)
if area >= ans:
ans = area
if height[left] <= height[right]:
new_left = left + 1
while (new_left < right) and (height[new_left] < height[left]):
new_left += 1
if new_left == right:
break
else:
left = new_left
else:
new_right = right - 1
while (new_right > left) and (height[new_right] < height[right]):
new_right -= 1
if new_right == left:
break
else :
right = new_right
return ans
```
> 18:09 第17行是打到後來才補上的，有發現邏輯錯誤是好事，==但最好要避免這種情形==，不然可能會讓人覺得interviewee思路不周全。
## 面試過程3（英）---- [226. Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/)
> `C++`
🎃: Hello Goodidea, welcome to the interview. In today's interview, I will ask you a simple question. **The question is as following. I will give you a root of a binary tree, please invert the tree and return its root。**
> 0:11 不應該直接講題目。可以帶入某個環境，用引導、互動的方式套用這個Leetcode題目。
😷: If the input tree is `NULL`, should I return `NULL`? 🎃: Yes.
😷: Can I use `TreeNode*` as input?
🎃: Yes, of course u can use `TreeNode*` as input and <font color="#a00">~~you need to return a `TreeNode*` as well.~~</font>
> 1:07 針對interviewee的問題回答就好，==不應該跟interviewee講函式要回傳什麼==，感覺像有制式的答案，這樣會限制雙方思考跟互動的空間。
😷: My first thought is to use a recursion function. The **input** is a `TreeNode*`. There're 3 cases in this recursion funtion.
1. " If input is `NULL`, then return `NULL`. ""
1. " If input has no children, then return itself. "
1. " If input has children, then swap them. "
😷: Since it's a recusion funtion, it needs to invert(child_1) and invert(child_2). And finally, return input.
>* 上面說明的input的時候，都是一個`TreeNode*`的root。說明的時候別只講input，==改成講 “ input root ” 會更清楚==。
>* NULL就NULL，不要講成NULL space（不是線代）。
```cpp
Treenode* invert(Treenode* root) {
if (root == NULL) {
return NULL;
}
if ( root ->left == NULL && root->right == NULL) {
return root;
}
else{
Treenode* temp = root->left;
root->left = root->right;
root->right = temp;
}
invert(root->left);
invert(root->right);
return root;
}
```
## 自評
前兩個模擬面試模擬面試錄影用手機錄音的效果有點吵，第三個模擬面試錄影改用耳麥，清楚很多。
#### interviewer
* 三個面試內容都是給一個Leetcode題目，應改用帶入某個環境，用引導互動的方式套用這個題目，以避免看到題目就直接把刷過的Leetcode拿來用。
* 要準備測試用的數據來驗證。
#### interviewee
* 打程式前要先說明預計要用什麼語言寫(C++ or python)。
* 冗言贅字太多，像是：ㄜ..
* 最好測試一下程式碼
---
## HW2-他評01
### interviewer
- [ ] 可改進之處
* [6:48](https://youtu.be/U1ojxdzmT9w?t=408) 在改進方法這邊，時間複雜度也是$O(n^2)$ ，在提問時可以明確指出要降低時間複雜度
### interviewee
- [ ] 優點
* [1:48](https://youtu.be/U1ojxdzmT9w?t=108) 有用肢體語言輔助表達
* [4:26](https://youtu.be/q3-dDTSpM6I?t=266) 詳細描述程式碼
- [ ] 可改進之處
* [1:48](https://youtu.be/U1ojxdzmT9w?t=108) 在說明approach時，如果可以初步給一個程式框架，能讓interviewer更容易理解
* 可以在程式實作完成後，用先前example時所舉的例子做test
## HW2-他評02
### interviewer
- [ ] 優點:
* 口齒清晰
* 題目說明清楚
- [ ] 可改進之處:
* 前面可以在加點自我介紹
* 感覺可以回話有點少缺少一點互動感
### interviewee
- [ ] 優點
* 邊打程式有邊解釋有互動感
* 程式改進的部分非常清楚
## HW2-他評03
### 針對 Interviewer 的檢討:
* 可以包裝一下題目
* 口齒清晰
* 在第一題 Interviewee 優化時，沒有優化到時間複雜度可以引導 Interviewee
* 第三題可以再多一些互動，像是問 Interviewee 覺得Invert Binary Tree 會使用到的場景，有種 Interviewee 還沒火力全開就結束的感覺
### 針對 Interviewee 的檢討:
* 寫完程式碼後可以帶測資去驗證程式碼
* 第二題比較多判斷式的程式碼，建議在實作前和 Interviewer 說明你的程式流程，好處是判斷式一多有時候寫程式碼容易漏掉，若前面有先說明，比較容易發現哪裡漏掉；若這時候有邏輯漏洞，Interviewer 有可能會適當的補充，也能讓 Interviewer 比較容易理解你的程式架構
## HW2-他評04
### Interviewer:
- [ ] 優點
* 題目說明清楚，不只以口頭闡述，也有以文件輔助。
- [ ] 可改進之處
* 題目給法可以不要關鍵字題目名。
* 題目敘述也不要直接給原題，可以換成應用、延伸或者套上情境。
* 最後結尾「大概了解你程式碼的想法了」，之後卻結束了，給人一種尚未了解透徹的感覺，應該可以換個更堅定的語氣，並結束面試。
### Interviewee :
- [ ] 優點
* 舉例有時候是以反白的方式，很棒。
* 有確認例子、有確認作法後得到Interviewer回應才開始。
- [ ] 可改進之處
* 應有測試以滿足 REACTO
## HW2-他評05
### interviewer
- [ ] 優點:
* 聲音清楚
- [ ] 可改進之處:
* 回答問題可以增加互動
### interviewee
- [ ] 優點
* 反覆詢問題意，確認對題目的理解沒有出錯
* 可以邊打程式邊解釋很厲害
Sign in with Wallet
Connect another wallet