# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023-homework1)」作業 1
> 貢獻者: 乙二-Two
> 👒: interviewer
> ◼️: interviewee
>
> 影片中戴帽子的是面試官，沒戴的是面試者
> [模擬面試錄影：第一題](https://youtu.be/QSURofCESyI)
> [模擬面試錄影：第二題](https://youtu.be/TSlRlgfC744)
> [模擬面試錄影：第三題](https://youtu.be/rh_INj4dS44)
## [217. Contain Duplicate](https://leetcode.com/problems/contains-duplicate/)
👒: 你好，歡迎來到本公司的面試，你今天的題目是寫一個函式，傳入一個整數陣列，如果有重複的數字就回傳 True，否則就回傳 False。
◼️: 好的，所以題目就是如果整數陣列有重複的值就回傳 True，否則就回傳 False。
👒: 是的。
◼️: 那請問陣列的長度會界於什麼之間？
👒: 會介於一到十的五次方之間。
◼️: 好的，那麼我來舉一下例子，如果陣列是 1,2,3,4,5 就會回傳 False，而如果是 1,2,3,3 之類的陣列，就會回傳 True，請問我的理解對嗎？
👒: 是的。
◼️: 好的，那我來講一下我會怎麼解決這個問題。最單純的解法就是使用兩層迴圈，外層迭代每個值，內層從那個數字開始往後找是否有重複的值。
◼️: 但是這樣子的演算法，它的時間複雜度是 O($n^2$)，而這樣子，我覺得是太慢了。
◼️: 我目前想到更有效率的解法是，先排序整個陣列，再尋找兩兩之間的數字是否相同。
👒: 好的，那麼你的迴圈開始和結束的條件會是什麼？
◼️: 會從 i=0 開始，如果 n 是陣列長度，會在 n-2 結束，因為會和下一個值比較。
👒: 好的。
◼️: 那麼我現在就開始來寫程式
```python
def contain_duplicate(nums):
nums.sort() # O(nlogn)
#O(n)
for i in range(len(nums)-1):
if nums[i]==nums[i+1]:
return True
return False
```
◼️: 這整個演算法的效率會是 O(nlogn)，會比原本的演算法更快。
👒: 好的，那麼請你輸入一些陣列來測試，我們來看一下結果。
◼️: 好。（測試 [1,2,3,4]、[1,2,3,3]、[1] 等的結果）
👒: 好的，那麼你對於這個演算法，你覺得有沒有什麼辦法可以讓它更快一點。
◼️: 我覺得這邊可以使用一個 hash map 紀錄已經找過的值，讓搜尋變成 O(1) 的時間複雜度，讓整體時間會變成 O(n)
👒: 那麼，你會怎麼修改這段程式碼呢？
```python
def contain_duplicate(nums):
exists={}
for num in nums:
if exists.get(num,False):
return True
exists[num]=True
return False
```
👒: 好，那麼你可以再跑一次測試嗎？
◼️: 好，這邊的結果是一樣的，時間複雜度會變成 O(n)，時間複雜度會比原本更快。
👒: 好，謝謝。
### 初步檢討
- Interviewee
- 2:05 附近，應該講相鄰的兩個數字，解釋會比較清楚。
- 5:45 附近，edge case 講＂邊緣＂的 case 會很難馬上理解，直接講英文會好一點。
- 7:32 附近，照著執行順序寫出程式，而不是寫完以後在前面加東西會比較好。
- Interviewer
- 應該提出更多問題，而不是只是對面試者說「好的」，才能有更多的交流。
- 解說題目時，直接講十萬而不是十的五次方會更好理解。
- 測試的時候，測資應該讓面試者自己提出，來看看對方會不會想到 edge case。
- 結束面試的時候，應該要更親切一點。
- 打招呼的時候應該講對方的名字。
## [20. Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)
👒: Hello, welcome to our interview, today, you will be writing a function.
👒: This function will accept a string, and you need to return whether the string is a valid parenthesis.
👒: A valid parenthesis must follow three rules
1. Evey open brackets must be closed by the same type of brackets
2. Open brackets must be closed in the correct order
3. Every closed bracket has a corresponding open bracket of the same type.
◼️: So, I will need to write a function that accepts a string and return a boolean value, to return if the string is valid parenthesis.
◼️: That is, every open brackets is closed by the brackets that is in the correct type and in correct order, am I right?
👒: Yes
◼️: And, what character will the string contain?
◼️: Will it contain multiple types of parenthesis? And, will it contain any other characters that aren't parenthesis?
👒: No, the string will only contain opening and closing parenthesis, square brackets, and curly brackets, and no other characters.
◼️: Ok, and what will the length of the string be? Will it be zero or a large integer that will cause overflow?
👒: No, it will be between 1 and 10000.
◼️: Ok. So, let me give a few examples and you can check if they're correct.
◼️: Strings with one character are not valid because they're missing an opening or closing bracket.
◼️: This ( \[\) ) isn't correct either because they're not the correct type.
◼️: These ( ([{}]), [(){}] ) are correct because they are in the correct order and the correct type.
👒: Yes, you're correct.
◼️: Ok, let me describe my approach here. In the beginning, I will try to declare a stack.
👒: Why would you want to declare a stack, instead of other data structure, like a queue?
◼️: Because the way we check the parenthesis that comes in last first. That is, the FILO. So the property is matching the stack, so it's the most appropriate.
👒: Ok.
◼️: Then, I will use a for loop to loop through the string, and every character can either be a open bracket or closing bracket, by the description of the problem.
◼️: So, if it's an opening bracket, I can push it to the stack, and the stack will only store brackets to be checked.
◼️: And when we see a closing bracket, we can try to pop the stack, if the stack is empty, it means there is too many closing brackets, so we can return false right away.
◼️: And if the popped value is not matching the closing brackets, it means they're not the correct type, then we can return the false.
◼️: After the loop ended, we can check if the stack if empty. If it's empty, it means that the number and the type of every parenthesis is correct.
◼️: And if it's not empty, it means that there are too many opening brackets, and we can return false.
◼️: And, that's my approach.
👒: Sounds great, you can start to implement it.
```cpp
#include <stack>
#include <string>
#include <map>
bool isValidParenthesis(std::string s)
{
stack<int> stk;
map<char,char> parenthesisPair={
{'(',')'},
{'[',']'},
{'{','}'}
};
for(const char c:s){
switch (c){
// is opening
case '(':
case '[':
case '{':
stk.push(c);
break;
// is closing
default:
if(stk.empty()){
return false; // not enough opening
}
const int top=stk.top();
stk.pop();
if(parenthesisPair[top]!=c){
return false; // not matching
}
}
}
// empty: correct number
// not empty: too many opening brackets
return stk.empty();
}
```
👒: Ok, that looks correct, you can try to print a few use cases, and see if it's correct.
◼️: I will try to test the possible problems I've mentioned, like missing opening or closing brackets, or not matching types, or not correct order, or mixed types.
(The cout results are correct)
👒: Great, and how would you optimize the code you've written? Is there a way to improve the time complexity or readability of the code?
◼️: I think the time complexity can't be improved because in order to see if the string is valid parenthesis, we must go through every character of the string, and that is already O(n) time complexity.
◼️: And the algorithm is already O(n), so I don't think we can improve it.
◼️: However, I think the readability is still improvable. By replacing the switch-case with more concise if statement.
```cpp
#include <stack>
#include <string>
#include <map>
bool isValidParenthesis(std::string s)
{
stack<int> stk;
map<char,char> parenthesisPair={
{'(',')'},
{'[',']'},
{'{','}'}
};
for(const char c:s){
if(parenthesisPair.count(c)){
stk.push(c);
}else{
if(stk.empty()){
return false;
}
const char top=stk.top();
stk.pop();
if(parenthesisPair[top]!=c){
return false;
}
}
}
// empty: correct number
// not empty: too many opening brackets
return stk.size()==0;
}
```
(Runs test case)
◼️: And it still works the same, but it's easier to read now.
👒: Ok, thank you for your participation, we will see you in the next interview.
### 初步檢討
- Interviewee
- 開頭講了太多的 So、Ok等字
- 2:57 部分，FILO 的檢查有點講得不清楚
- 句子可以更簡短，不需要一句話就講出自己所有考慮到的東西。簡短一點比較好理解。
- Interviewer
- 不該把規則在一開始明確的列出來，應該讓面試者自己去思考怎麼樣才是正確的括號、透過提問去弄清楚。
- 面試官或許通常不會請面試者寫更好讀的程式碼，如果不能改善時間複雜度，也許該問其他問題。
- 講對方名字（同第一題）。
## [237. Delete Node in a Linked List](https://leetcode.com/problems/delete-node-in-a-linked-list/)
👒: 乙二先生你好，歡迎來到本公司的面試。我們這裡有一道演算法題目，想試著請你寫寫看。
👒: 題目是這樣的，你需要寫一個函式、刪除 Linked List 中的一個節點。這個函式會傳入這個節點，而你不需要回傳任何東西。這個節點可以確認不會是最後一個節點。
◼️: 好的，那麼我想請問 Linked List 的長度會介於什麼之間呢？會不會有只傳入一個 null pointer 或是只有一個節點的情形？
👒: 不會，長度會介於 2 到 1000 之間。
◼️: 好的，我再複述一遍題目。這個函式不該回傳任何東西，應該刪除 linked list 中傳入的節點，請問我理解的正確嗎？
👒: 是的。
（ListNode 的定義已經在 google 文件上）
◼️: 那請問傳入的節點會是 (ListNode 的) pointer 或是 ListNode？
👒: 會以 pointer 的形式傳入。
◼️: 那麼，讓我舉一些例子，來確認我的理解是否正確。
（舉出一些範例並說明）
◼️: 請問我理解正確嗎？
👒: 是的。
◼️: 那麼我先講一下我這題的解法會長什麼樣子。
◼️: 目前，我可以看出這題主要的難點在沒有提供上一個節點。也就是說，我們不能用傳統的方法，也就是直接改變上一個節點的 next。
◼️: 我們只有這個節點以及以後的節點可以使用。所以我目前想到最單純的方法就是直接將這個節點以後的所有節點往前移一格。
◼️: 我會用的方法就是先使用傳入的節點，先用迴圈判斷是不是倒數前二個節點以前。如果是就更新值，並檢查下一個節點。跳出迴圈後，我們一樣會更新值，只不過會改成指向 null pointer，用來表示 linked list 的結尾。
👒: 好的，你可以開始撰寫程式碼了。
```cpp
void deleteNode(ListNode* node) {
// not last two node
while(node->next->next){
node->val=node->next->val;
node=node->next;
}
// last two node
node->val=node->next->val;
delete node->next;
node->next=nullptr;
}
```
👒: 那麼能請你講解一下演算法的過程嗎，用來驗證它的正確性。
◼️: 好的，我這邊會使用我剛才在註解中舉的例子，因為他們分別代表開頭的節點、中間倒數第二以前、倒數第二個節點。
（講解演算法）
👒: 好的，那麼能請你分析一下這個演算法它的優缺點以及可以改進的地方嗎？
◼️: 這個演算法的缺點，就是顯而易見的非常慢，因為它需要使用一個迴圈來巡過 node 以後的每個節點，會有 O(n) 的時間複雜度。對於 linked list 來說是非常慢的。所以我覺得應該會有更好的方法來實作。
◼️: 只不過我目前卡住的地方在於沒有辦法使用前一個節點，想請問你的見解是什麼？（尋求提示）
👒: 如果不能改變前一個節點指向什麼，也許你可以改變它指向的東西。
◼️: 那麼也許我可以讓 node 各個屬性都和下一個節點一樣，所以我可以更新它的 value 和 next，也許這樣可以，你怎麼覺得？
👒: 我覺得這樣子應該是可行的，你要不要試著寫寫看？
```cpp
void deleteNode(ListNode* node){
// node won’t be the last node
ListNode* nextNode=node->next; // won’t be null
node->val=nextNode->val;
node->next=nextNode->next;
delete nextNode;
}
```
◼️: 接下來讓我一樣用剛才的例子來做示範，可以嗎？
👒: 好的。
（再測試一次）
◼️: 所以這個演算法是可以正常運作的，而它的時間複雜度是 O(1)，因為它固定只有四個 statement，效率會比原本高上非常多。
👒: 好的，我們今天的面試到這裡結束，謝謝你今天的參與。
### 初步檢討
- Interviewee
- 在提出可能的改進方法後，就可以直接寫寫看了，不需要問面試官的想法。
- Interviewer
- 一樣可以和面試者有更多互動，而不只是回答相關資訊（或是說好的）。
- 在回答面試者的時候，不該說＂應該＂可行，直接請他依照自己的想法寫寫看就好（避免不必要的猜測）。
---
## 第二次作業 - 他評 01
### Interviewer
- [ ] 優點
* 第三題影片 [10:21](https://youtu.be/ORYG2RrKaak?si=YSHI0d0j3DsQwdyN&t=621) 給予的提示很提示，不會清楚到讓人直接了解，但又有畫龍點睛的感覺。
- [ ] 可改善的部份
* 如 Jserv 老師上課時所說，每一題都能試著想一個情境，而非直接詢問原題的提議。
* 第一題影片，總感覺 Interviewer 不太喜歡說話XD，面對 Interviewee 的提問都回答的很句點，如您自己的初步檢討所說，提出更多問題或說更多話，能有更多的交流！
* 第三題影片 [6:35](https://youtu.be/ORYG2RrKaak?si=VPdTLzvQUylX_NVf&t=399): Interviewer 說「能請你講解一下這個演算法的過程嗎？」不太恰當，因為 Interviewee 前面已經一邊撰寫一邊說明了。如果只是希望 Interviewee 驗證作法，也許可以改成說「請你舉個例子並代入，驗證作法是否正確」之類的。
### Interviewee
- [ ] 優點
* 第一題影片 [3:34](https://youtu.be/QSURofCESyI?si=eOO4YZ7yQoAHx_X5&t=214): 寫到需要解釋的地方（列表長度減一）時，有主動停下來說明為什麼要這樣設計。
* 不論在哪一題，聽完題目後的提問都很詳細。
* 第三題撰寫完程式後的驗證沒有第一題、第二題的問題（直接以執行結果當成驗證），而是舉例代入說明。
- [ ] 可改善的部份
* 第一題影片 [0:46](https://youtu.be/QSURofCESyI?si=9YixiHnLUqWrp2aT&t=46): 開始的舉例，如果能把例子打在文本編輯器上會比較好。（本題的概念比較簡單，直接口述也很清楚，但如果題目概念比較複雜，單純口述會讓 Interviewer 理解困難。）
* 第一題影片 [4:55](https://youtu.be/QSURofCESyI?si=hp5owqyZZz84PQEC&t=295): 開始的測試，也許要思考一下有沒有什麼「不依靠執行結果」的測試方案。換句話說，如果現在面試的環境並非可執行程式碼的環境（例如 Google Docs），影片現在的測試方式就無法使用。
* 不確定是不是我太敏感，總覺得第三題影片 [10:53](https://youtu.be/ORYG2RrKaak?si=oL_eyQRDzEIb9zUz&t=653) 直接詢問 Interviewer「你怎麼覺得？」有一種沒大沒小的感覺。
* 第二題沒有影片: 在前面詢問 Interviewer 時，Interviewee 有連續三個提問（And, what character will the string contain? Will it contain multiple types of parenthesis? And, will it contain any other characters that aren’t parenthesis?）和連續兩個提問（Ok, and what will the length of the string be? Will it be zero or a large integer that will cause overflow?），如果影片中確實也是這樣，這會有種咄咄逼人的感覺，而且 Interviewer 可能無法記得全部的問題。比較好的問法應該是一次問一個，等 Interviewer 回答完畢後，再進行下一個提問。
## 第二次作業 - 他評 02
### 關於 interviewer
- [ ] 優點
* 用帽子手動切換interviewer跟interviewee的過程很有趣XD
* [9:57](https://youtu.be/ORYG2RrKaak?si=hRXQHfvRy8c0Wlrr&t=597)：給出適當的提示引導interviewee
- [ ] 可改進的地方
* 和interviewee的互動太少，大部分時間都只是你問我答，可以嘗試增加一些討論的過程
* (第一題)可以包裝成「遊戲抽卡公司為了提升玩家的抽卡體驗，所以想設計讓特定卡池抽出來的角色不會重複，請設計一個能檢查是否抽到重複角色的機制」然後透過把角色編號將問題轉回原本的Contain Duplicate
### 關於 interviewee
- [ ] 優點
* 有遵循REACTO的步驟進行面試
* 解釋想法跟做法的時候邏輯清晰，表達也很明確
* [1:08](https://youtu.be/QSURofCESyI?si=jPmRYFRP4SkWc7Sd&t=68)： 一開始先用口述的方式講解暴力解，讓自己維持有在講話，也順便幫自己爭取思考時間
* [9:46](https://youtu.be/ORYG2RrKaak?si=rbqx9QZOynb5_PyM&t=586)：想法卡住的時候有主動向interviewer尋求幫助
- [ ] 可改進的地方
* [0:45](https://youtu.be/QSURofCESyI?si=6pSCZ1eHNWxRzZDv&t=45): 直接把舉的例子打出來會讓interviewer更容易去理解
* [4:40](https://youtu.be/QSURofCESyI?si=RTdq3DSy3S_WsUue&t=280): 我自己覺得測試應該是寫完code之後接著做，而不是透過interviewer詢問後才做。此外，REACTO裡的測試指的應該是用實際例子帶入code去完整操作一次，讓interviewer能夠理解怎麼運作，而不是直接執行看結果而已
* [5:55](https://youtu.be/QSURofCESyI?si=6K6UFv5teLBuclJS&t=355): 接招接的太順了，看起來很像故意藏招等interviewer問，就算真的有藏也可以看著code演一下，讓思考優化的流程更自然一點
## 第二次作業 - 他評 03
### 關於 interviewer
- [ ] 優點
* 有根據受試者卡住的點做出了引導
* [2:42](https://youtu.be/TSlRlgfC744?t=162)有根據受試者的做法做提問，可以增加互動，同時讓受試者知道你有跟著他
- [ ] 可改進的地方
* 可以多對受試者提出質疑
* 對題目可以有包裝或應用在實際例子上
### 關於 interviewee
- [ ] 優點
* 在講解時間複雜度的時候標在程式碼旁邊很簡潔易懂
* 在REACTO的T的部分做的蠻詳細的
* 邊寫code邊講解很順暢
* 有模擬到卡住的地方的時候怎麼和面試官求助，也清楚的講述自己卡住點
- [ ] 可改進的地方
*
Sign in with Wallet
Connect another wallet