# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者：矮鴨-Oopsy
> [模擬面試錄影: 漢語](https://youtu.be/llIIVtr5QKs)
> [模擬面試錄影: 英語](https://youtu.be/vMwGwKPJCzA)
:::info
在模擬面試錄影裡interviewer和interviewee會使用不同馬賽克區分。
interviewer的馬賽克為「我就爛」頭貼。
interviewee的馬賽克是一隻鴨子。
>👨🏻💼：interviewer
>🦆：interviewee
以下流程並非逐字稿，實際對談內容請以模擬面試錄影為主。
:::
## 1. Two Sum
👨🏻💼：嗨矮鴨你好，很高興你來參加我們公司的面試，我是今天的面試官Jason。
🦆：Jason你好！
👨🏻💼：之前在信中有跟你確認過會使用C\++來實作今天的問題，正確嗎？
🦆：沒錯，我今天會以C\++來實作。
👨🏻💼：好，那我就開始說明問題。我會給你一個整數的序列，並且給你一個目標值，請你幫我找出這個序列裡面有哪兩個整數相加會剛好等於目標值，並回傳他們在原始序列裡的位置。
### R
🦆：好的，所以我會拿到一筆資料，裡面都是整數，然後我要從裡面找出兩個整數，相加剛好等於目標值，並且回傳他們的位置，這樣理解沒錯嗎？
👨🏻💼：沒錯。
🦆：好，那有幾個問題想先確認，首先，序列裡會存在複數組符合要求的整數嗎？例如1+4=5，2+3=5這樣？
👨🏻💼：可以假設沒有這種情況，每一組序列最多只會有一組符合要求的整數。
🦆：了解，那剛剛使用「至多一組」來描述，是否代表需要將無解的情況考慮進去呢？
👨🏻💼：對喔，需要考慮無解的狀況。
🦆：好的，那序列裡面的整數能重複使用嗎？例如序列裡面只出現一個3，然後目標值是6，那3+3=6可以算是一組解嗎？
👨🏻💼：不行喔！序列裡的每個整數都只能使用一次。
### E
🦆：好的，那我舉個例子來再次確認理解是否正確。
```
Input:
nums = [2,7,11,15]
target = 9
Output: [0,1]
```
🦆：Input會有兩個，第一個是整數序列，我這邊用nums來表達，然後假設裡面有四個整數，分別是2,7,11,15。第二個input是目標值，我把它稱作target，假設是9。以這組資料作為input，可以找到2+7等於目標值9，所以會回傳他們兩個在序列裡的位置，也就是0跟1，這樣正確嗎？
👨🏻💼：沒錯，你對這個問題的理解是正確的，那請你開始描述你會怎麼解這個問題。
### A
🦆：我目前直覺想到的是使用雙層for迴圈去解，第一層的迴圈會使用index i，從序列的開頭開始跑到序列倒數第二格位置，然後第二層迴圈再從i+1的位置開始往後尋找是否有整數跟i這個位置的整數相加會等於目標值。
👨🏻💼：聽起來沒問題，那就開始coding吧。
### C
```cpp
vector<int> twoSum(vector<int>& nums, int target) {
for(int i=0;i<nums.size()-1;i++) {
for(int j=i+1;j<nums.size();j++) {
if(nums[i]+nums[j]==target) return {i,j};
}
}
return {-1,-1};
}
```
🦆：首先定義一個函式twoSum()，參數有兩個，就是剛才提過的整數序列跟目標值，而回傳就是找到的兩個整數的位置。
🦆：第一層迴圈index用i，從nums的開頭開始，每次往後找一個，直到nums.size()-1結束，因為找到一組至少需要兩個，最後一個整數不會再往後找了。
🦆：第二層迴圈的index用j，從i+1開始，因為要從i的位置開始往下找有沒有相加等於target的整數。一樣每次往後一格，直到nums的尾巴結束。
🦆：迴圈裡面就是寫判斷條件，如果nums\[i\]和nums\[j\]相加等於target就return他們的index，也就是i跟j。
🦆：最後如果迴圈全部跑完都沒有找到相加等於target的整數，就回傳\[-1,-1\]。
### T
🦆：用前面舉的例子來跑看看，然後我把位置換一下比較能演示到過程，序列依序為11,2,7,15。
🦆：在i=0時，第二層迴圈會依序測試11+2,11+7,11+15，都不等於target的9。
🦆：在i=1時，第二層迴圈測試到2+7等於target的9，因此回傳\[1,2\]並結束。
👨🏻💼：很好，你的方法是正確的，請你分析一下這個做法的時間複雜度。
🦆：外層迴圈跟內層迴圈的執行次數上界都是nums的長度，所以會是$O(n^2)$。
👨🏻💼：對，可是這個方法其實還蠻沒有效率的，你有想到其他更快的解法嗎？試看看能不能降到$O(n)$。
### O
🦆：（思考）如果是$O(n)$的話，我如果先把nums裡面的整數放到一個hash table裡面，這邊會需要耗時$O(n)$，但是後面要找特定整數的index就只需要$O(1)$的時間。接著只需要用一個迴圈，去計算每個整數要加上多少才會等於target，再去hash table找對應的值就可以了！這邊也只需要$O(n)$。
👨🏻💼：沒錯，這樣就可以降到$O(n)$了，那請你把他實作出來吧。
```cpp
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;
for(int i=0;i<nums.size();i++) {
map[nums[i]]=i;
}
for(int i=0;i<nums.size();i++) {
int complement = target - nums[i];
if(map.find(complement)!=map.end() &&
map.find(complement)->second!=i) {
return {i, map[complement]};
}
}
return {-1,-1};
}
```
🦆：首先用一個unordered_map來存放整數跟他的index，將整數當成key值，對應的value則是index。
🦆：迴圈就只需要跑過整個nums一次，在這邊我宣告complement代表target扣掉nums\[i\]的值，接著就只需要去判斷unordered_map裡面是否存在跟complement相同的key值，如果有的話就可以回傳他的value跟i值。
👨🏻💼：看起來沒有問題，不過我從你的實作方式裡看到可以更有效率的做法，你有發現嗎？
```cpp
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;
for(int i=0;i<nums.size();i++) {
int complement = target - nums[i];
if(map.find(complement)!=map.end() &&
map.find(complement)->second!=i) {
return {i, map[complement]};
}
map[nums[i]]=i;
}
return {-1,-1};
}
```
🦆：有，我大概懂了，其實不用一開始特地把nums的值存放到unordered_map裡面，可以在執行迴圈的時候再放進去就好。
🦆：在輪到某個nums\[i\]的時候，先去檢查已經放入unordered_map的整數是否有他的complement，如果沒有的話就表示他不存在complement或是他的complement還沒放進來，這時候再把nums\[i\]放進去unordered_map就可以了。
👨🏻💼：沒錯，你回答得很好，那我們就進下一題囉。
## 53. Maximum Subarray
👨🏻💼：第二題我會提供你一個陣列，裡面都是整數，請你找到相加總和最大的子陣列。
### R
🦆：好的，所以我會得到一個陣列，裡面存的值都是整數，然後要找到一個子陣列，讓裡面的數字相加總和最大，這樣理解正確嗎？
👨🏻💼：沒錯。
🦆：好，那我確認一下，這邊的子陣列必須是連續的子陣列嗎？
👨🏻💼：是的。
### E
🦆：好的，那我舉個例子來再次確認理解是否正確。
```
Input:
nums = [5,4,-1,7,8,-3]
Output: 23
```
🦆：假設今天的輸入陣列是這樣，那我能找到的最大子陣列應該會是\[5,4,-1,7,8\]，然後會輸出他們的總和23對嗎？
👨🏻💼：沒錯，你對這個問題的理解是正確的，那請你開始描述你會怎麼解這個問題。
### A
🦆：我目前直覺想到的是使用雙層for迴圈去解，第一層的迴圈會依序把陣列的每一個值當作開頭，然後第二層迴圈再從開頭往後去累加，並且每加一個值就檢查是否為最大，這樣就可以跑過所有情況並且算出最大子陣列了。
👨🏻💼：聽起來沒問題，那就開始coding吧。
### C
```cpp
int maxSubArray(vector<int>& nums) {
int maxSum = INT_MIN;
for(int i=0;i<nums.size();i++) {
int currentSum = 0;
for(int j=i;j<nums.size();j++) {
currentSum+=nums[j];
if(currentSum>maxSum) maxSum = currentSum;
}
}
return maxSum;
}
```
🦆：輸入一樣叫做nums，然後宣告一個整數變數maxSum並初始化成一個很小的數值，用來存放計算出來的最大值，在最後return maxSum就可以了。
🦆：第一層迴圈index用i，從nums的開頭開始，每次往後一格，直到nums的最後一個值結束。在這層我宣告一個整數變數currentSum，每次要進入第二層迴圈以前都會assign為0，用處是相同開頭的子陣列在計算數值時可以利用前面累加的結果。
🦆：第二層迴圈index用j，從i開始，每次往後一格，直到nums的最後一個值結束。每一次都會先把nums\[j\]加到currentSum，代表累加nums\[i\]到nums\[j\]之間的所有值。之後會檢查累加的數值是否為最大，如果是就更新maxSum。
### T
🦆：用前面舉的例子來跑看看
```
5
5+4
5+4+(-1)
5+4+(-1)+7
5+4+(-1)+7+8
5+4+(-1)+7+8+(-3)
4
4+(-1)
4+(-1)+7
4+(-1)+7+8
4+(-1)+7+8+(-3)
(-1)
(-1)+7
(-1)+7+8
(-1)+7+8+(-3)
7
7+8
7+8+(-3)
8
8+(-3)
(-3)
```
🦆：最後輸出maxSum就完成了。
👨🏻💼：沒錯，你的方法是正確的，請你分析一下這個做法的時間複雜度。
🦆：外層迴圈跟內層迴圈的執行次數上界都是nums的長度，所以會是$O(n^2)$。
👨🏻💼：沒錯，但這個方法其實還蠻沒有效率的，你有想到其他更快的解法嗎？
### O
🦆：（思考）剛才把過程全部列出來的時候我有發現，其實每個i在執行累加的重複性很高。既然題目要求的是最大值，可以在執行累加的時候就先判斷前面加過的數值是否有辦法讓總和增加，如果不行就直接從現在的i開始加，後面也不需要再加上i以前的數值了。這樣迴圈執行一次就可以了，時間複雜度應該會下降成$O(n)$
👨🏻💼：聽起來可行，不過你講的有點模糊，還是直接實作吧！
```cpp
int maxSubArray(vector<int>& nums) {
int maxSum = nums[0];
int currentSum = nums[0];
for(int i=1;i<nums.size();i++) {
currentSum = max(currentSum+nums[i],nums[i]);
maxSum = max(maxSum, currentSum);
}
return maxSum;
}
```
🦆：我先把maxSum的初始化修改成nums\[0\]，因為maxSum有可能就是nums\[0\]，所以這樣給值不會有問題，而且這樣迴圈就能從i=1開始。currentSum也初始化成nums\[0\]。
🦆：迴圈改成i=1開始，一樣每次前進一格，直到nums的結尾。先比較currentSum+num\[i\]和num\[i\]誰大，如果是前者就代表前面累加的數值到後面還有用，後者就代表前面累加的數值沒有用，可以直接從num\[i\]再開始加就好。然後再比較maxSum跟currentSum誰大，假設currentSum比較大就更新maxSum。
🦆：用前面舉的例子再跑看看
```
currentSum=5
maxSum=5
currentSum=9
maxSum=9
currentSum=8
maxSum=9
currentSum=15
maxSum=15
currentSum=23
maxSum=23
currentSum=20
maxSum=23
```
👨🏻💼：沒錯，這樣就比上一個方法快上不少了。不過你的方法變數其實可以更精簡，你要試看看嗎？
```cpp
int maxSubArray(vector<int>& nums) {
int maxSum = nums[0];
for(int i=1;i<nums.size();i++) {
nums[i] = max(nums[i-1]+nums[i],nums[i]);
maxSum = max(maxSum, nums[i]);
}
return maxSum;
}
```
🦆：有我想到了，其實迴圈在執行的時候，nums\[i\]前面的陣列空間已經沒有用處了，所以可以把currentSum直接記錄到陣列上就好，不需要額外宣告這個變數。
👨🏻💼：沒錯，你表現的不錯喔！那今天的面試就到這裡結束，下一次的面試全程都會用英文溝通，會再寄信通知你時間。
🦆：好的，謝謝！
## 141. Linked List Cycle(英)
👨🏻💼：Hello, I'm your interviewer Jason.
🦆：Hello Jason.
👨🏻💼：Okay.Let's get started. I will give you a linked list, and you have to check if there exist a cycle in it.
### R
🦆：Okay. So I will get a linked list, and my mission is to determine if this linked list has a cycle in it, is it correct?
👨🏻💼：Yes.
🦆：It seems that the linked list in this problem is a singly-linked list.Can I assume that the node's structure is like this?
```cpp
struct ListNode {
ListNode *next;
};
```
👨🏻💼：Yes, you can assume that.
🦆：There are only two conditions in this problem. One is that this list contains a single cycle, meaning the last node's pointer points to some node inside the list. The other condition is that this list doesn't have a cycle, and the last node's pointer simply points to NULL. Is that correct?
👨🏻💼：Yes, it's correct.
### E
🦆：Okay, let me give some examples to confirm if my understanding is correct.
```
Input:
1->2->3->4->NULL
Output:
False
Input:
1->2->3->4->2
Output:
True
```
🦆：In the first case, node number 4 points to NULL, so there is no cycle in the list. The output should be false.
🦆：In the second case, node number 4 points to node number 2, so there is a cycle in the list. The output should be true.
🦆：Am I right?
👨🏻💼：Yes. Let's talk about your approach.
### A
🦆：Sure. I will give each node a boolean value to keep track of whether it has been visited. False represents the node has not been visited yet, and True represents that it has already been visited.
🦆：I will use a pointer to travel through the whole linked list, and if the pointer visits a node that has already been visited, then we find a cycle.
👨🏻💼：Sounds good. You can start coding.
### C
```cpp
bool hasCycle(ListNode *head) {
unordered_map<ListNode *, bool> visited;
while(head!=NULL) {
visited[head] = true;
if(visited[head->next]==true) return true;
head = head->next;
}
return false;
}
```
🦆：I create a function hasCycle, and the parameter is a pointer points to the list's beginning, and I will call it head.This function will return a boolean value, which will be true if we found a cycle.
🦆：I will use a while loop to travel through the linked list. It will ended when the head pointer points to the NULL.
🦆：And I have to use an unordered_map to keep track of each node's status. I will call the map visited.
🦆：Inside the while loop, since the node pointed by the head pointer is being visited, the node's status will change from unvisited to visited, which means that its boolean value is set to true.
🦆：Later on, I will check if its next node has been visited. If so, then just return true.If not, the head pointer can move on to the next node.
### T
```
1->2->3->4->2
```
🦆：Now I'm going to check whether the function works or not.When the head pointer reach node number 2, its status will change to visited. And when the head pointer visited node number 4, it will check the next node's status, which is true because the next node is node number 2. Then the function will return true.
### O
👨🏻💼：Yeah. It works. And it's obviously to figure out the time your function costs, which is $O(n)$. However, you use $O(n)$ in memory space, since you need to store n pairs of key and value in your unordered_map. And I want to know if you can solve this problem using constant memory?
🦆：(thinking)Well, I don't have any idea right know. Can you give me some hints?
👨🏻💼：Of cource. Try using more than one pointers.
🦆：Ah, I see. I can use two pointers with different speed. The first pointer, fast, will move two nodes in each iteration.The second pointer, slow, will move one node in each iteration. If there exist a cycle, the fast pointer will enter it first, and the slow pointer will enter it later. Since the fast pointer move faster in each iteration, it will eventually catch up the slow pointer. Once they point at the same node in the cycle, our function can return true.
👨🏻💼：Yes, your approach makes sense. You can code it now.
```cpp
bool hasCycle(ListNode *head) {
ListNode *slow = head;
ListNode *fast = head;
while(fast!=NULL && fast->next!=NULL) {
slow = slow->next;
fast = fast->next->next;
if(fast==slow) return true;
}
return false;
}
```
🦆：In this way, we can solve this problem using constant memory.
👨🏻💼：Yes. Well done.
## 檢討
### 中文題目
- 2:30 原本已經有規劃好範例，第一題在做Example的時候為了要講規劃好的範例把原本已經舉例的東西刪掉，有點突兀。
- 3:23 發音問題，「倒數第二**gur**」。
- 因為平常講話的習慣，很常在說明的時候用字不精確，例如第一題跟第二題在提到vector裡面的資料時，會用「裡面那些人」、「後面那些人」去稱呼。
- 在解第二題的時候一直講「跟前面一樣」，例如「跟前面一樣用雙層for迴圈」或是「跟前面一樣用nums來宣告」，但根本不需要去強調跟前面用的資料結構或方法相同，反而只會讓句子變得很雜亂而已。
- 一邊coding一邊說明的講話方式很怪，一個句子會講到一半停下來專注在coding，等完整打完才補完整個句子，聽的人根本不知道我想表達什麼。可以調整成先說明再打或是想辦法讓斷點不要那麼怪。
- 手有點忙，常常莫名其妙就開始亂揮（只要沒有在coding或思考的時候就會），但對於解釋題目或做法幫助不大，可以改成在google文件上打範例進行說明。
- 在解釋雙層迴圈運作的時候有點抽象，可以嘗試改成用i等於多少、j等於多少的方式去舉例會更清楚。
- 講話的時候有個壞習慣，講到一半會因為在腦裡想到更好的表達方式，就把原本講到一半的話重新修改再講出來，聽起來完全不是完整的句子。
- 描述迴圈的運行時用「跑幾次」不太精確，可以改成用iteration或迭代描述。
- 語助詞太多，例如「呃」、「那」、「好」
- 不習慣用google文件打程式碼，coding的時候會卡卡的，要習慣不去依賴便利的code editor。
- 在討論的時候並沒有提到資料的總數是n，所以並不能直接講時間複雜度是$O(n)$，而是要用類似$O(nums.size())$或是在討論過程中跟面試官說明把該數值假設成$n$。
- 在思考REACTO流程的時候講話會停頓，而且眼神其實會亂飄（因為在想步驟），需要把這個過程更熟練，不然很突兀。
### 英文題目
- 發音有待加強，很多字都會糊掉。
- 沒辦法把想講的話馬上說出來，會經過一段「先轉換成英文再表達出來」的時間差，導致講話斷斷續續的。
- 如果還沒確定（翻譯）好下一句話要講什麼就貿然開口，發音就會暴走，例如3:43的\"You can start **kill-ding**\"
- 在思考REACTO流程的停頓變得更明顯了，因為多了轉換成英文的時間。
- 一邊講英文一邊coding好像更容易打錯字。
- 6:20 的地方超慘，因為想不到該怎麼表達直接語無倫次了10秒左右，看起來超像根本搞不清楚下一步要打什麼。以後再遇到這種情況，寧願空個幾秒確認要講什麼再開始講。
- 7:40 發音問題，\"...cycle inside **this list**...\"後面的this跟list聽起來根本一樣。
- 8:10 Test講得很亂，把一個很簡單的步驟講得很亂很雜，需要多練習英文。
- 10:43 發音問題，\"I can use two **points@&%er**...\"裡面的pointer發音很慘。
- 11:30 其實我想講的是fast每次都會追上slow一個node，所以可以證明一定會遇到而不會錯過，但我英文講不出來，只能簡單說明會追上。
- 13:20 在說明while迴圈的判斷條件有講錯，因為fast每次會往後兩格，所以本來就要往後檢查兩格，而不是為了變快才這樣寫。
- 結尾結束的倉促，因為我的英文能力已經耗盡了，真的需要多多練習。
---
## 第二次作業-他評01
### 關於 interviewer
- [ ] 優點
* 咬字清楚
- [ ] 可改進的地方
* 問題設計避免直接拿 leetcode 題目來問，可經過設計包裝、加上使用情境較佳
* 直接問時間複雜度比較單薄，可結合後面的改善方案一併發問
* [26:13](https://youtu.be/llIIVtr5QKs?si=Ny1mMOFO2merWaZ0&t=1573): 如果覺得 interviewee 的講法有點模糊，可以適時打斷對方、或是針對不理解的地方發問（和對方溝通）
* [29:48](https://youtu.be/llIIVtr5QKs?si=CpPvhNdI8kUoKzQ_&t=1788): 比起直接提出「變數可以更精簡」，不如先讓 interviewee 自己思考優化方法，再進行引導會比較好
### 關於 interviewee
- [ ] 優點
* 咬字清楚、很有朝氣
* 有遵循 REACTO 步驟，詳細發問與舉例
* 不確定的地方會主動向 interviewer 尋求幫助 （141. Linked List Cycle [10:23](https://youtu.be/vMwGwKPJCzA?si=z4e2V8h4QL5xueKL&t=623)）
- [ ] 可改進的地方
* [1:26](https://youtu.be/llIIVtr5QKs?si=ue3BWeyqWp97_K9E&t=86), [19:50](https://youtu.be/llIIVtr5QKs?si=m3iKtHrZg85tn311&t=1190): 慣用的語助詞滿多的，其中「齁」、「嘛」最讓人在意（過於本土味）
* [3:10](https://youtu.be/llIIVtr5QKs?si=RO32coiy1aefG-1O&t=190), [18:10](https://youtu.be/llIIVtr5QKs?si=quJNC1sWeZgFVAzJ&t=1090) 如果本來就知道更好的解法的話，可以跳過雙層迴圈的實作，因為很顯然不是最佳解
* [9:24](https://youtu.be/llIIVtr5QKs?si=VKIay1irEpFn10-_&t=564) 要爭取思考時間的時候，也許重複問題、說出自己的思路會比直接說「我想一下」更好
* (Linked List Cycle) Linked List 的不同節點是可以擁有相同數值的，所以應該先設定好本題不會有相同數值的節點，否則輸入 `1->2->3->4->2` 也無法看出有沒有 cycle
## 第二次作業-他評02
### 關於 interviewer
- [ ] 優點
* [29:51](https://youtu.be/llIIVtr5QKs?t=28m51s): 很認真的在看code，會詢問interviewee是否可以更精簡
* 會幫助interviewer，面試氣氛良好。
- [ ] 可改進的地方
* 可以把題目打在文件上面，以免interviewee忘記題目內容
* [29:51](https://youtu.be/llIIVtr5QKs?t=28m51s): 應該詢問是否有更精簡儲存資料的方式，問變數更精簡可能會讓interviewee會錯意。
* [10:17](https://youtu.be/vMwGwKPJCzA?t=10m17s): constant memory可以換另一種說法，the space complexity is constan之類的。
### 關於 interviewee
- [ ] 優點
* [0:54](https://youtu.be/llIIVtr5QKs?t=0m54s): 換句話說的重覆interviewer的問題會讓interviewer感覺你有理解。
* [1:06](https://youtu.be/llIIVtr5QKs?t=1m06s): 把問題說出來增加與interviewer互動的機會，也interviewer知道你有理解問題，並正在釐清的過程
* [3:24](https://youtu.be/llIIVtr5QKs?t=3m24s): 有增加手勢，讓對話不會太無趣
* 講話流暢，包括英語發音都很順暢
* [10:24](https://youtu.be/vMwGwKPJCzA?t=10m24s): 會主動提出需要給予更多hint，不讓自己卡住。
- [ ] 可改進的地方
* [18:27](https://www.youtube.com/watch?v=llIIVtr5QKs?t=18m27s): 可以將方法寫在文件檔裡面，方便interviewer了解interviewee再說甚麼，之後interviewee實做過程中也可以回去看
* [13:53](https://youtu.be/vMwGwKPJCzA?t=13m53s): 可以藉機說明一下走一步走兩步的原理，才不會原先想不到，突然被提示一下就有憑空想到的感覺，為什麼不用快指針速度快三倍，而只是快兩倍，是否有不相遇的問題，可以多一些探討會更好。
## 第二次作業-他評03
### 關於 interviewer
- [ ] 優點
* 說話清楚
* 語速適中
- [ ] 可改進的地方
* 題目可以給予文件以便於interviewee確認與討論
### 關於 interviewee
- [ ] 優點
* 搭配一些手勢去說明
* 邊界確認很清楚
* REACTO步驟都有做到
Sign in with Wallet
Connect another wallet