## 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023/)」作業 1
> 貢獻者: 優嬉兔-UCII
> [影片(漢語)](https://youtu.be/q6-oFMhfYX0)
> [影片(英語)](https://youtu.be/hQl42dTbkLc)
## Leetcode
* ## [509. Recursion_Fib](https://leetcode.com/problems/fibonacci-number/)
**測驗說明與問答**
*interviewer*: UCII你好，我們目前需要一些能夠優化資料查詢或代碼演算法的人才，所以想跟你做一些相關的測驗。你能舉出一些實作過的案例嗎?
*interviewee*: 好的。我有做過二元樹的類型問題，例如:計算費氏數列的末項值。
:::info
:::
*interviewee*: 我是用postorder的遞迴方式，讓所有節點最後都化為已知的前2項數值，再全部加總起來，也就是說，每個父節點都是2個子節點的和，到底層訪問完所有節點，再依次往上加總，到最終的根節點後，完成所有遞迴呼叫。
*interviewer*: 那麼這種方式的時間複雜度為何?
*interviewee*: 因為每次都會進行fib(n-1)與fib(n-2)兩次遞迴呼叫，所以時間複雜度為。
**Recursion_Fib with recursion**
```
int fib(int n){
if(n>1){
return fib(n-1)+fib(n-2);
}
else{
return n;
}
}
```
*interviewer*: 還不錯，編程的方式還蠻簡潔的。那有沒有recursion以外的解決方式呢?
*interviewee*: 有的。另一種解法就是iterative，和recursion一樣都是二元樹類型問題常見的兩大演算法。這次我把fib(0)、fib(1)換成prev1、prev2，再新增一個current，儲存prev1和prev2每次的總和，如此不斷迭代到計數器i=n為止。
*interviewee*: 而這個方式避免了遞迴的開銷，所以時間複雜度是，比前一個方式更加有效率。
**Recursion_Fib with iterative**
```
int fib(int n){
if(n<=1){
return n;
}
int prev1=0; // 起始數列的第一個數
int prev2=1; // 起始數列的第二個數
int current=0; // 當前計算的數
for(int i=2;i<=n;i++){
current=prev1+prev2;
prev1=prev2;
prev2=current;
}
return current;
}
```
* ## [206. LinkedList_Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/)
**測驗說明與問答**
*interviewer*: OK，那請問你還有做過其他這種呼叫尋址類型的題目嗎?
*interviewee*: 有，另一種類型就是鏈結串列。就像接下來這題，我要試著把一個單向鏈結串列做反轉。
:::info
:::
*interviewee*: 這題我所想到的最有效率的解法，時間複雜度也只有，並且必須只能走訪串列一遍就要反轉完成。所以我除了設置記錄開頭與結尾的2個pointer，curr與curr2外，還要再設一個備份節點之間路徑的指標backup。透過調整curr2讓curr轉向達成倒轉，最後回傳backup記錄的節點軌跡，得到反轉結果。
**LinkedList_Reverse Linked List**
```
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
if(head==NULL||head->next==NULL){
return head;
}
struct ListNode* backup=NULL;
struct ListNode* curr=head;
while(curr!=NULL){
struct ListNode* curr2=curr->next;
curr->next=backup;
backup=curr;
curr=curr2;
}
return backup;
}
```
*interviewee*: 中間的每個操作都只涉及指針的調整，沒有額外的迴圈或遞迴結構，所以每次為。
* ## [11. Array_ContainerWithMostWater(medium)](https://leetcode.com/problems/container-with-most-water/)
**測驗說明與問答**
:::info
:::
*interviewer*: 最後你能夠實作一個計算biggest container的function嗎?
*interviewee*: 這一題是要求找出容器能盛裝的最大水容積，而且要注意不能讓水溢出，所以若容器兩側長度不同，要以較短那一側為主(以它的長度為容積高)。
*interviewee*: 先初始化maxarea這個變數，最後要計算最大容量用。然後l、r分別為從陣列左右兩端開始找尋的index，按照上述不能使水溢出，接下來設有一個條件式布林判斷式，若height[l](左側柱)較高，容積為height[r]*(r-l)；反之為height[r]*(r-l)，然後area暫存每次計算出的可能容積。
**Array_ContainerWithMostWater**
```c
int maxArea(int* height, int heightSize){
int maxarea=0;
int l=0,r=heightSize-1;
while(l<r){
int area=height[l]<height[r]?height[l]*(r-l):height[r]*(r-l); //condition boolean formula, 'area=height[l]<height[r]' is condition, 'height[l]*(r-l)' is true result, 'height[r]*(r-l)' is false result
if(area>maxarea){
maxarea=area;
}
if(height[l]<height[r]){
l++;
}
else{
r--;
}
}
return maxarea;
}
```
*interviewee*: 只要每次有算出最大的area值，就立刻更新到maxarea，最後得出最大可能容積。而這次的時間複雜度為***O(3n)***，分別是while迴圈迭代n次，每次經過3個if-else條件判斷。仍然屬於級別。
* ## English Commentary
👩🦰: *interviewer* 👧: *interviewee*
### Problem1
👩: Hello UCII, we are currently in need of talent who can optimize data queries or code algorithms, so we would like to conduct some relevant assessments with you. Could you provide some examples of cases you've worked on in the past?
👧: Yes. I have worked on problems related to binary trees, such as calculating the final value of the Fibonacci sequence.
👧: I used a postorder traversal of recursive approach where each node is eventually simplified into the known values of the previous two terms in the sequence. This means that each parent node is the sum of its two child nodes. After visiting all nodes at the bottom level, I summed them up and continued this process upwards until reaching the root node, finished all recursive calls.
👩: So what is the time complexity of this method?
👧: Because two recursive calls to fib(n-1) and fib(n-2) are made each time, the time complexity is $O(n^2)$.
👩: That's good. The programming method is quite simple. And is there any solution other than recursion?
👧: Yes, I am. Another solution is iterative, which, like recursion, are two common algorithms for binary tree type problems. In this problem, I replaced fib(0) and fib(1) with "prev1" and "prev2", and added a new "current" to store the sum of prev1 and prev2 each time, and continued to iterate until the counter i=n.
👧: This method avoids time spending of recursion, so the time complexity is $O(n)$, more efficient than the previous solution.
### Problem2
👩🦰: OK. Have you done any other problems of this type of call addressing?
👧: Yes. I have done the question of linked list. Just like the next question, I'm going to try to reverse a one-way link sequence.
👧: This is the most efficient solution which I can think of this problem. It's time complexity also only $O(n)$. It must only visit the sequence once before reversing it. So in addition to setting the two pointers at the beginning and end of the record, "curr" and "curr2", I also need to set up an pointer "backup" for backup the path between the nodes. By adjusting "curr2", "curr" is turned to achieve the reversal, and finally the node path recorded by the "backup" is returned to obtain the reversal result.
👧: Each operation in the processing only involves pointer adjustment, no additional loops or recursive structures, so the complexity of each time is $O(1)$.
### Problem3
👩🦰: Finally, can you implement a function that calculates the biggest container?
👧: This question requires finding the maximum volume of water that the container can hold, and care should be taken not to allow the water to overflow. Therefore, if the lengths of the two sides of the container are different, the shorter side's length should be the height of volume.
👧: First, initialize the variable "maxarea", and finally calculate the maximum volume. Then "l" and "r" are the indexes searched from the left and right ends of the array respectively. Next, according to the above, the water cannot overflow. there is a condition boolean formula that if height[l] is higher, the volume is height[r]×(r-l); Otherwise, it is height[r]×(r-l), and then area temporarily stores the volume calculated each time.
👧: As long as the maximum area value is calculated each time, it is immediately updated to maxarea, and finally the maximum volume is obtained. And the time complexity is O(3n), which means the while loop iterates n times, and each time it passes 3 if-else conditional judge formulas. Still at the level of $O(n)$.
## 總體初步檢討
針對**interviewer**的檢討:
針對**interviewee**的檢討:
---
## 第二次作業-他評 01
### 關於 interviewer
- [ ] 優點
* 變成interviwee在向interviewer介紹自己的所學，跟其他人不同挺有趣的。
* 三題都錄雙語版本，真是辛苦了。
### 關於 interviewee
- [ ] 優點
* (漢語)
* [06:54](https://www.youtube.com/watch?v=q6-oFMhfYX0&t=414s): 有優化時間複雜度很棒。
* 演算法解說的圖片畫得詳細。
* (英語)
- [ ] 可改進的地方
* (漢語)
* [02:36](https://www.youtube.com/watch?v=q6-oFMhfYX0&t=156s): 題目上就有程式碼答案，是不是不太對XD?
* [07:55](https://www.youtube.com/watch?v=q6-oFMhfYX0&t=475s): 圖片畫得很詳細，但是如果能在解釋邏輯時，也看著圖片一行行稍微舉例一下就好。
* [12:03](https://www.youtube.com/watch?v=q6-oFMhfYX0&t=723s): `struct ListNode* curr2=curr->next;`宣告式子可以往前提到while外，`struct ListNode* curr2; while(curr != NULL){curr2=curr->next;...}`，可以減少重複宣告記憶體，稍微降低一點點點。(Leetcode結果: 8.52MB -> 8.49MB)
* (英語) 加強口說。
## 第二次作業-他評 02
### interviewer
- [ ] 優點
* 從面試者做過的相關經驗著手，而不是單純提問，可以引導面試者從有他經驗的問題開始了解想法
- [ ] 可改進的地方
* 建議影片上面試官與面試者還是要做一些區隔，例如上名子之類的
* 第一題Fib的部分可以在最後引導能不能再減少時間，進而提出建表的概念，因為fib數列是固定值，因此可以利用建表的方式讓數列只需做一次，之後查表即可，以此來減少時間成本，而不是每次都重新run一遍
### interviewee
- [ ] 優點
* 口齒清晰，且流程簡潔俐落
- [ ] 可改進的地方
* 建議example階段直接自行創造簡單的example與面試官進行確認，先行把範例做好不太符合現實
* 在撰寫程式碼時可以避免一段時間的沉默，可以一邊打程式碼一邊跟面試官分享自己的想法，目前都還停留在解說一段之後沉默直到一段打完在接下一段的狀況
* 在與面試官討論做過的經驗時可以包裝一下題目，從實務延伸到問題避免直接用演算法問題起頭，以免面試官產生「他只會刷提」的觀感
* REACTO中的test階段不太明顯，建議可以在撰寫完程式碼之後使用之前創造的example trace code 讓面試官了解整體的流程
## 第二次作業-他評 03
### interviewer
- [ ] 優點
* 語速自然，咬字清楚
- [ ] 可改進的地方
* 面試官與受試者區隔不明顯
* 面試官宜對問題進行包裝，將題目內容帶入應用情境之中
* 題意解說應更明確
* 與受試者互動偏少
### interviewee
- [ ] 優點
* 筆記演算法流程解釋清楚
- [ ] 可改進的地方
* 第一題演算法好像直接打在題目上了
* 程式碼撰寫時宜適時加入註解與說明
* 第三題在面試官說要撰寫計算biggest container的function後，應該再次確認題目要求
* REACTO落實不太明顯
* 應該花點時間解釋演算法運作原理
## 第二次作業-他評 04
### interviewer
- [ ] 優點
* interviewer一開始有透過interviewee相關的經驗著手，進而延伸至題目本身，轉折設計良好。
- [ ] 可改進的地方
* interviewer後續在進行延伸討論時問題太過直白，例如直接詢問時間複雜度等，可以提出一些可能的改進方向，待interviewee完成改進後，再橫向進行時間複雜度比較。
*
### interviewee
- [ ] 優點
* 口說速度勻稱，咬字清楚
* 有表格跟圖片搭配說明，能清楚理interviewee欲表達概念。
- [ ] 可改進的地方
* 第一題與第二題的連接方式設計不太合理，怎麼是interviewee提出自己接下來要做什麼題目。
* 影片中interviewee 與 interviewer區分不易，如果剪輯不易，建議可以在影片畫面角落加上不同貼圖來區分目前是哪一位在說話。
## 第二次作業-他評 05
### interviewer
- [ ] 優點
* 口齒清晰
- [ ] 可改進的地方
* 建議不要直接使用leetcode原題，可對題目做適當的包裝
* 對話內容有點太制式
### interviewee
- [ ] 優點
* 在書寫程式碼的過程中有搭配適度的解釋
- [ ] 可改進的地方
* 缺少test的環節
## 它評 06
**Interviewee**
- [ ] 優點
* [2:30](https://youtu.be/NV9trXRA03Y?t=2m30s)簡化問題的說法不錯
* [4:49](https://youtu.be/NV9trXRA03Y?t=4m49s) coding 邊講解很流暢
- [ ] 缺點
* [1:22](https://youtu.be/NV9trXRA03Y?t=1m23s) 應該要重複問題，確認
* [4:49](https://youtu.be/NV9trXRA03Y?t=4m49s)講解完解題思路後要問下考官想法，不要直接coding
* [10:49](https://youtu.be/NV9trXRA03Y?t=10m49s)講解完優化作法後，就算時間不夠，還是可以在share的畫面寫偽碼示意。
**Interviewer**
- [ ] 優點
* [0:55](https://youtu.be/lgNBDqEPq6g?t=0m55s):口齒非常清晰，問題清楚
- [ ] 缺點
* [3:22](https://youtu.be/NV9trXRA03Y?t=3m23s) 直接展示問題不好，可以用關鍵字替代來確認問題
* [10:49](https://youtu.be/NV9trXRA03Y?t=10m49s)沒有做好延伸問題和充分討論，可以追問推薦系統演算法那類型方向的想法
Sign in with Wallet
Connect another wallet