# 2023年 資訊科技產業專案設計 作業1
> contributer: 哈囉-Hi
> video: [1](https://youtu.be/wCLCpmhdKxw), [2](https://youtu.be/nRBLQ3-U8Ww), [3](https://youtu.be/xccI0_yKEHU)
>
:man: imterviewer :woman_in_lotus_position: interviewee
## [Maximum Average Subarray l](https://leetcode.com/problems/maximum-average-subarray-i/?envType=study-plan-v2&envId=leetcode-75)
:man:: Hi , I'm Jo. Here's a question for you . Given an integer array **num** consisting of **n** elements , and an integer **k**. Find a contiguous subarray whose **length is equal to** **k** that has the maximum average value and return this value . Any answer with a calculation error less than **10^-5^** will be accepted
:woman_in_lotus_position: : You means that I got an array and an integer , then I need to do the calculation to find the continuous part that contains four elements?
:man:: Yeah , I think that's a great explaination .
:woman_in_lotus_position:: Well , I would like to use two for loop , one for the iteration of the entire array , the other for the calculation to sum up the elements in the subarray
:man: All right. It sounds reasonable.
:woman_in_lotus_position: : Ok , I would like to start with giving some examples
```
Input : nums = [1,12,-5,-6,50,3] , k = 4
there are three subarray
[1,12,-5,-6] , [12,-5,-6,50] , [-5,-6,50,3]
with the sum be
2 , 51 , 42
with avg be
0.5 , 12.75 , 10.5
```
:man:: I am wondering if there's a quicker solution?
:woman_in_lotus_position: : Umm...maybe I could use the sliding window to remove the first element in the current subarray and add the next element behind the last one in current subarray
>程式碼
1.original
```cpp
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
double Max = 0; //max for the biggest value
double part = 0; //part for the sum of each loop
//loop through the array to find the max
for(int i=0; i<= nums.size()-k ;i++){
part = 0;
for(int j=i; j<k ; j++){
part+= nums[j];
}
if(part>Max)
Max = part;
}
return Max/k;
}
};
```
2.sliding window
```cpp
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
double Max = 0; //max for the biggest value
double part = 0; //part for the sum of each loop
//loop through the array
for(int i=0; i<= nums.size()-k ;i++){
if(i==0){
for(int j=0; j<k ; j++){
part+= nums[j];
}
Max= part;
}
else{
// slide the calculation window
part = part - nums[i-1] + nums[i+k-1];
if(part > Max)
Max = part ;
}
}
return Max/k;
}
};
```
## [Search in a Binary Search Tree](https://leetcode.com/problems/search-in-a-binary-search-tree/?envType=study-plan-v2&envId=leetcode-75)
:man:: The next question is about Binary Search Tree . Now , you are given the **root** of a binary tree (BST) and an integer **val**. Please find the BST that the node's value equals **val** and return the subtree rooted with that node. If such a node does not exist , return **null**.
:woman_in_lotus_position: : Ok , so I am given a value and a root of a binary tree . Then , I need to search if there's any node that correspond to the value . If it exists , I should just output the root and the following node with preorder traversal .
:man:: All right , please go on.
:woman_in_lotus_position:: Let me try to do it with some examples
in this photo , we find the corresponding value 2 in the trees , and then output the value based on the root with preorder traversal
:man:: Yeah , it make sense
:woman_in_lotus_position: :Besides , since a BST would have bigger node in the left hand part , and smaller one in the right hand part , so we could use a if else to help it find the targer node quicker
>程式碼
```cpp
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if(root == NULL)
return NULL;
if (root->val == val)
return root;
else if (root->val >val)
return searchBST(root->left , val);
else
return searchBST(root->right , val);
}
};
```
## [Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/?envType=study-plan-v2&envId=leetcode-75)
:man::There is the final question . Given the **head** of a linked list . **Delete** the **middle node** , and return the **head** of the modified linked list. The **middle node** of a linked list of size **n** is the **[n/2]^th^** node from the **start** using **0-based indexing** , where **[x]** denotes the largest integer less than or equal to **x**.
:woman_in_lotus_position:: Ok , so I got a size **n** linked list , and I need to get rid of its middle node ?
:man:: Yeah , it sounds reasonable .
:woman_in_lotus_position: : All right , let me start with some examples.
this is the example for odd counts of elements
this is for even counts of elements
:man:: Then , how will you code this out
:woman_in_lotus_position: : I would start from named a new Listnode as front and tail , and assign the node of head to front , then iterate through head to find the size of this linkedlist . After that , I would go to that node before our target , then link it to the node behind our target , and thus delete the node . Besides , we should keep an eye on the case when size equals to 1 , we should just return NULL .
>程式碼
```cpp
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteMiddle(ListNode* head) {
ListNode* front;
ListNode* tail;
int size = 0;
front = head;
while(head != NULL){
size++;
head = head->next;
}
head = front;
for(int i=1 ; i<size/2 ; i++){
head = head->next;
}
if (size == 1)
return NULL;
else
tail = head->next->next;
head->next = tail;
return front;
}
};
```
## 初步檢討
:man: interviewer
+ **引導解題的方式不夠深入**
對於演算法的精進可以適度給予提示 ，或是引導interviewee去分析不同演算法的時間與空間複雜度，甚至是應用場景的細節
+ **延伸原本問題的技巧**
若是能跳脫原本問題的框架，以延伸的想法與interviewee互動，或許更能挖掘出自己想要的人才
:woman_in_lotus_position: interviewee
+ **寫程式時說話音量太小**
要保持interviewer聽得清楚的音量 ，或是盡量在coding前的解釋補充得更清楚 ，就不需再coding時分心解釋
+ **表達流暢度的精進**
會有過多語助詞以及窮詞的狀況，若能流利地表達能給interviwer自己是 well-prepared and confidence 的印象
---
## 第二次作業-他評 01
### 關於 interviewer
- [ ] 優點
* 咬字清楚
* 舉例簡潔
- [ ] 可改進的地方
* Part 3 [00:20](https://youtu.be/xccI0_yKEHU?t=20): 與其照著 LeetCode 原題來描述，不如針對應用場景，說明為何要找出單向鏈結串列中間的節點 (並釋放記憶體)
> 以 [FreeRTOS](https://wiki.csie.ncku.edu.tw/embedded/freertos) 來說，就用鏈結串列來表示動態建立的任務
* Part 3 [3:10](https://youtu.be/xccI0_yKEHU?t=190): 避免只說 "How will you code this out?"，這樣的互動太草率，應該回顧 interviewee 提出的方法後，在適當的分析後，才說 "reasnable"
* Part 3 [9:54](https://youtu.be/xccI0_yKEHU?t=594): 避免過早說 "That's all"，聽起來太敷衍，應該針對程式碼討論，掌握 REACTO 流程，特別是 Test 及 Optimization
* Part 3 [10:08](https://youtu.be/xccI0_yKEHU?t=608): 避免過早說 "Look forward"，這樣可能會帶來非必要的暗示，應該給予評論和延伸問題
### 關於 interviewee
- [ ] 可改進的地方
* Part 3 [1:53](https://youtu.be/xccI0_yKEHU?t=113): 作為 interviewee，不該直接提及 LeetCode 及其範例，應該要能夠呼應 REACTO 流程
* Part 3 [2:10](https://youtu.be/xccI0_yKEHU?t=130): 在 Google Docs (或者協作的頁面) 中，一邊解說案例，一邊寫下，屆時開發程式時，可對照運用
* Part 3 [2:18](https://youtu.be/xccI0_yKEHU?t=138): 採用 0-based indexing，依據範例應該是左邊 (或右邊) 起算的第 4 個節點，不該說 "the third node"。可用類似以下說法:
> In a singly-linked list, when we use 0-based indexing, the first node is considered to be at index 0, the second node at index 1, the third node at index 2, and so on.
> So, in the example: 1 -> 2 -> 3 -> 4 -> 5
> The first node (index 0) is 1.
> The second node (index 1) is 2.
> The third node (index 2) is 3.
* Part 3 [2:09](https://youtu.be/xccI0_yKEHU?t=129): 應區分 node 和 element
* A node is a fundamental building block of a linked list. It consists of two components:
- Data: This is the actual information or value that you want to store in the linked list.
- Reference (or Link): This is a pointer/reference to the next node in the sequence (in a singly-linked list) or both the next and previous nodes (in a doubly-linked list).
* An element in the context of a linked list generally refers to the actual data or value stored within a node. It's what you retrieve or manipulate when you work with the linked list.
> Elements are the meaningful pieces of information that you are storing and managing using the linked list data structure. [ChatGPT](https://chat.openai.com/share/98766992-f0e4-4b91-81d4-b1635ce06168)
* Part 3 [2:48](https://youtu.be/xccI0_yKEHU?t=168): 若及早定義 middle，並用偶數奇數來解釋，就可及早切入程式碼。`4 / 2 = 2` 的讀法是 "four divided by two equals two"
* Part 3 [3:26](https://youtu.be/xccI0_yKEHU?t=206): 字元太小，應適度放大，有利於後續討論。面試的場合通常不會用 LeetCode 網頁
* Part 3 [4:04](https://youtu.be/xccI0_yKEHU?t=244): `front` 和 `tail` 應該宣告在同一行，便於一面解說一面打字
* Part 3 [5:01](https://youtu.be/xccI0_yKEHU?t=301): "We might not... we cannot do the next progress" 聽起來過於武斷，究竟不記錄鏈結串列的長度到底會怎樣？
* Part 3 [5:22](https://youtu.be/xccI0_yKEHU?t=322): 避免頻繁地搖頭，可能會讓人誤會你在多個電腦螢幕之間切換視線，或者旁邊有人給你提示
* Part 3 [5:50](https://youtu.be/xccI0_yKEHU?t=350): 頻繁搖動滑鼠，很討厭，無助於溝通
* Part 3 [6:07](https://youtu.be/xccI0_yKEHU?t=367): "I forget that" 這句話不用說，應該強化 REACTO 流程，讓方法可對應到程式碼
* Part 3 [7:35](https://youtu.be/xccI0_yKEHU?t=455): 關於特例的討論，應該在 REACTO 的 Approach 階段提出
若用 [Linux 風格的 cicular doubly-linked list](https://hackmd.io/@sysprog/c-linked-list) 撰寫，優雅許多:
```c
/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *slow, *fast;
slow = fast = head->next;
for (; fast != head && (fast = fast->next) != head; fast = fast->next)
slow = slow->next;
element_t *element = list_entry(slow, element_t, list);
list_del(&element->list);
q_release_element(element);
return true;
}
```
## 第二次作業-他評 02
### interviewer
- [ ] 優點
* 用字簡潔
- [ ] 可改進的地方
* 介紹題目的時候，可以不完全把題目條件講清楚（測資範圍等），讓面試者自行思考極端情況、問清楚條件
* interviewee 完成題目後，可以請對方對演算法做分析，像時間複雜度，或是哪裡可以改進等 (Optimization)
### interviewee
- [ ] 優點
* 有把範例用註解寫下來
- [ ] 可改進的地方
* 注意 coding style，固定使用大/小寫當作變數開頭（可能有面試官會在意）
Sign in with Wallet
Connect another wallet