# **2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FS11ooE4Rh)」作業 2**
---
## **對其他同學的正反批評**
### [曉榕 Dawn - 他評04](https://hackmd.io/py_SEUfHQ0mzy_lcdaZSOQ?both)
### 優點
- 口齒清晰，說話速度適中。
- 說明這麼寫的原因和優底是什麼。
### 可改進的地方
- interviewe不用逐字讀題目
- interviewee在舉例階段時可以將想法打在word上，更能一目了然。
---
### [靈魂程式手 mock - 他評02](https://hackmd.io/pBfvjKMqTH6jKDGxmUtgwA?both)
### 優點
- interviewer在說明題目時，使用圖檔以及將重要的地方框起來，可以讓interviewee更快了解題意。
### 可改進的地方
- 注意說話的音量，不要被鍵盤和滑鼠聲蓋過。
- 在完成暴力解後，可以對題目做一些變化。
---
### [泰迪熊 Teddy - 他評03](https://hackmd.io/uoX35YelQ9OSUBuVh2I1Hw?both)
### 優點
- 有先將字串的constraints詢問清楚。
- 有將舉的例子寫在google document上，可以讓雙方都看得很清楚。
- 有先提出想到的特例👍。
### 可改進的地方
- 可以對題目進行一些變化，像是將s插入t中，可以組成幾種新字串。
- "="和"=="在程式語言中代表意義不同。
---
### [姆咪 MUMI - 他評05](https://hackmd.io/vJ_f1RagRoa0XDdANiY29Q?both)
### 優點
- 在暴力解完之後，有提出優化的作法。
- 邊寫程式邊說明目前在寫什麼，讓interviewer有更多互動的機會。
### 可改進的地方
- 回答問題時減少使用"應該"，自信作答。
---
### [埃默里 Emery - 他評04](https://hackmd.io/IcL6COXQT9WAjdKid6po9w?both)
### 優點
- 在提出優化的方法後，也有進一步說明為什麼這樣比較好。
- 縮排排的很好，看起來很舒服。
- 開始寫程式前先確認題目的constraints。
### 可改進的地方
- interviewee可以等interviewer主動求助或是卡住時再給提示。
- 程式碼可以用一個class或function包裝起來，後續在使用上能清楚知道function的作用以及回傳的資料型態。
---
## **我從中學習到**
- 在寫程式碼時，除了說明接下來要寫的東西有哪些，也可以進一步說明這麼寫的好處是什麼。
- 在寫leetcode時，可以多想想如何改成變化題。
- 在舉例時，可以將想到的特例或是邊界先提出來。
- 在暴力解完題目後，可以想看看有沒有其他優化時間複雜度或空間複雜度的做法。
- 在說明完如何優化後，可以更進一步說明為什麼這樣比原本的好。
---
[21. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/description/)
---
>[video](https://youtu.be/Fo9UBmmS6LE)
🐻: interviewer
🐰: interviewee
---
🐻: 同學你好，我是水果公司的軟體工程師，在看過你的簡歷後，對你很感興趣，所以今天想和你聊聊，這邊我會用一個情境舉例，請你依照這個情境設計出相符的程式。
🐻: 假設今天運動品牌H舉辦了一個跑步比賽，第一名會有價值1萬元的該品牌商品獎勵，第二名會有價值5000元的商品獎勵，第三名會有價值3000元的商品獎勵，參加比賽的每個人根據跑步名次都會有價值不等的商品獎勵，但是在消息發布之後，由於參加的人數眾多，主辦方決定將參賽者分成男生組和女生組，等比賽結束後再一起統計每人的成績。
🐻: 想請問如果你是主辦方，會怎麼設計一個能夠計算所有人成績的程式?
🐰: 我想請問第一名是指男女組成績一起算出來，最終只有一個第一名，還是男生組、女生組各有一個第一名?
🐻: 男女組成績一起算，只有一個第一名。
🐰: 好的，那麼請問成績的數值範圍是?
🐻: 成績以秒為單位，可接受的範圍是0~10800s。
🐰: 好的，那麼請問男女組成績是已排序還是未排序的?
🐻: 是已排序的。
🐰: 好的，那我想先說我對這個情境的理解。
🐰: 比賽分成男生組和女生組，最終的名次是男生和女生一起比較得出。
🐰: 舉例來說，男生組是A組，女生組是B組，成績是...，output是...
```
Input:
A = [1,2,3,4,6]
B = [2,3,6,8,9,10]
Output:
[1,2,3,3,4,5,5,8,9,10]
```
🐰: 請問我對情境的理解正確嗎?
🐻: 正確，再來我想聽看看你的設計構想。
🐰: 我想使用兩個lists來表示男生組和女生組，從兩個lists的頭開始比較，一直比較到有一個lists比較完成，沒有比較完的list的部分再接到output list的後面。
🐻: 聽起來沒問題，可以開始實作。
🐰:
```cpp=
class Solution {
public:
ListNode* mergeTwoLists(ListNode* listA, ListNode* listB) {
//創建一個dummy node指向output list的head
ListNode* dummy = new ListNode(0);
ListNode* current = dummy;
//比較l1和l2的node
while (listA != nullptr && listB != nullptr) {
if (listA->val < listB->val) {
current->next = listA;
listA = listA->next;
}
else {
current->next = listB;
listB = listB->next;
}
current = current->next;
}
if (listA != nullptr) {
current->next = listA;
}
else {
current->next = listB;
}
return dummy->next;
}
};
```
🐻: 請你使用這個範例進行測試
```
A = [1,2,5,6,8]
B = [2,3,3,3,4,7]
```
🐰: (開始測試)
🐻: 好的，這個程式可以解決男女分組的問題，那麼我想再做一個假設，如果因為當天報名的人數過多，主辦方將原本的男女各一組，改成男女混合5~8人一組，共有K組，你會怎麼設計?
🐰: 我先說一下我對這個假設的理解
```
Input:
lists = [[1,3,5,6,7], [2,4,6,7,7,7], [5,7,9,10,22,35,84]]
Output:
[1,2,3,4,5,5,6,7,7,7,7,7,9,10,22,35,84]
```
🐻: 理解正確，請說明你的設計構想。
🐰: 我想使用priority_queue做一個minHeap，將vector<ListNode*>作為底層容器類型，再定義一個使用大於的compare函數。
🐰: 將input的lists的head node加入minHeap中，進行自動排序。
🐰: 此時的minHeap會選出最小的head node，將它放入output list中。
🐰: 被選中最小的head node會從minHeap中pop out，並放入同一個list的下一個node和其他lists的head node進行比較，一直持續到minHeap裡面沒有任何node為止。
🐻: 好的，請開始實作。
🐰:
```cpp=
class Solution {
public:
//自定義compare函數(預設是maxHeap，這裡要用minHeap所以改成>)
struct CompareNodes {
bool operator()(const ListNode* left, const ListNode* right) const {
return left->val > right->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
//使用priority_queue進行排序
priority_queue<ListNode*, vector<ListNode*>, CompareNodes> minHeap;
for (ListNode* list : lists) {
if (list) {
minHeap.push(list);
}
}
//創建一個dummy node指向output list
ListNode* dummy = new ListNode(0);
ListNode* current = dummy;
//不停循環直到minHeap裡面的node都被取出
while (!minHeap.empty()) {
ListNode* minNode = minHeap.top();
minHeap.pop();
current->next = minNode;
current = current->next;
//當前這個pop出最小值的list是否還有其他node
if (minNode->next) {
minHeap.push(minNode->next);
}
}
return dummy->next;
}
};
```
🐻: 好的，看起來程式碼沒有問題，請問這個程式碼的時間和空間複雜度是多少?
🐰: 這題的時間複雜度取決於兩個因素，分別是將所有lists的head node加入minHeap的過程以及從minHeap中取出node重新插入的過程。
🐰: 因為lists的總數為K，所以將所有lists的head node加入minHeap的時間複雜度是O(KlogK)。
🐰: 而從minHeap取出node重新插入的過程，最壞的情況會是每個node都會被插入和彈出一次，因此時間複雜度會是O(NlogK)，其中N是所有lists的node總數，所以這個程式碼的時間複雜度為O(NlogK)。
🐰: 而空間複雜度的部分，因為這個minHeap最多同時包含K個節點，因此空間複雜度是O(K)。
🐰: 除了minHeap之外只使用像是dummy node這種常數級別的輔助空間，所以這部分的空間複雜度是O(1)。
🐰: 整個程式碼的空間複雜度為O(K)。
🐻: 這個部分說明得很清楚，程式碼的運作也沒有問題，之後有消息會再進行通知，今天的面試就到此結束，謝謝你的參與。
## 他評01
- interviewer的檢討:
- [0:00](https://www.youtube.com/watch?v=pez6PnEcLT4&t=0) 過於直接的把Leetcode題目抄下來，即使要用抄的也應該用口語一點的方式把題目和限制條件講清楚而非直接念題目。例如：「這邊有一個array，裡面有數個integer，然後我會給你一個target number，希望你可以幫我找出是否在array中有兩個不同的數相加會等於這個target number，對於這部分有什麼問題嗎？」
- interviewee的檢討:
- 影片可以不要剪掉思考的過程，空白的地方也可以增加雙方的互動。
- [2:25](https://www.youtube.com/watch?v=pez6PnEcLT4&t=145) 說「等於」就好，不需要說「等於等於」
Sign in with Wallet
Connect another wallet