# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023/)」作業 1
> 貢獻者: 風清揚-Wind
> [模擬面試影片](https://youtu.be/jJTtHZZQsy4)
## [20. Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)
### 題目描述
給一個裡面僅包含( ) { } [ ] 的字串s，請判斷輸入的字串是否有效。
輸入的字串在以下情況有效 :
1. 左括號必須由相同類型的右括號封閉。
2. 左括號必須按照正確順序封閉。
3. 每個右括號都有一個對應的相同類型的左括號。
### 程式碼說明
- [ ] 程式碼雛形
這題是要判斷括號有沒有括對，所以在遇到左括號時，都直接存入stack裡面。當遇到右括號，會判斷與stack最後一個element是否是成對的，如果成立，就把stack最後一個元素移除，並把紀錄stack裡面element數量的i減一，若不成立，則直接回傳false。
最後如果stack裡面還有element，回傳false，若沒有則回傳true。
```c
bool isValid(char * s){
int i=0;
char stack[strlen(s)];
for(int j=0; s[j]!=NULL;j++){
if(s[j]!='}' && s[j]!=']' && s[j]!=')'){
stack[i]=s[j];
i++;
}
else{
if(i==0) return false;
else if(s[j]=='}' && stack[i-1]=='{'){
stack[i-1]=NULL;
i--;
}
else if(s[j]==')' && stack[i-1]=='('){
stack[i-1]=NULL;
i--;
}
else if(s[j]==']' && stack[i-1]=='['){
stack[i-1]=NULL;
i--;
}
else {
return false;
}
}
}
if(i!=0) return false;
else return true;
}
```
- [ ] 程式碼改善方法
針對特殊情況，可以做出改善，並減少stack的空間。這邊的做法是stack只需要原來空間的一半。再把左括號放進stack裡面之前，先判斷stack裡面的元素是否已經大於輸入字串s的一半，如果成立，代表就算接下來都是相對應的左括號也無法清空stack，所以可以直接回傳false。
```c
bool isValid(char * s){
int i=0;
char stack[strlen(s)/2+1];
for(int j=0; s[j]!=NULL;j++){
if(s[j]!='}' && s[j]!=']' && s[j]!=')'){
if(i<strlen(s)/2){
stack[i]=s[j];
i++;
}
else return false;
}
else{
if(i==0) return false;
else if(s[j]=='}' && stack[i-1]=='{'){
stack[i-1]=NULL;
i--;
}
else if(s[j]==')' && stack[i-1]=='('){
stack[i-1]=NULL;
i--;
}
else if(s[j]==']' && stack[i-1]=='['){
stack[i-1]=NULL;
i--;
}
else {
return false;
}
}
}
if(i!=0) return false;
else return true;
}
```
## [21. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/)
### 題目描述
給定兩個以排序的linked lists (list1,list2)，將兩個linked list合併為一個linked list。該list必須通過將list1跟list2的節點串接在一起來形成。 Return必須回傳串接起來的list的head。
### 程式碼說明
- [ ] 程式碼雛形
```c
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode head;
struct ListNode* mergelist= & head;
if(list1==NULL) return list2;
if(list2==NULL) return list1;
while(list1 !=NULL && list2 !=NULL){
if(list1->val <= list2->val){
mergelist->next = list1;
list1=list1->next;
mergelist=mergelist->next;
}
else{
mergelist->next=list2;
list2=list2->next;
mergelist=mergelist->next;
}
}
if(list1!=NULL) mergelist->next=list1;
else mergelist->next=list2;
return head.next;
}
```
## [15. 3Sum](https://leetcode.com/problems/3sum/description/?envType=study-plan-v2&envId=top-interview-150)
### 題目描述
給定一個整數陣列nums，回傳所有的triplets[nums[i],nums[j],nums[k]]，滿足i != j, i != k, and j != k，且nums[i ] + nums[j] + nums[k] == 0。
回傳不能有重複的triplets。
### 程式碼說明
- [ ] 程式碼雛形
宣告一個兩層vector ans，來存放回傳值。先把輸入的vector進行排序。用for迴圈去迭代，在每個迭代過程，把k設為迭代的counter加1，把j設為輸入字串的size減1。接著如果k<j，判斷如果nums[i]+nums[k]+nums[j]<0，則k++，nums[i]+nums[k]+nums[j]==0，代表這是一個正解，但是要存入ans之前，必須先查看ans裡面有沒有相同的值，若沒有則存入，k++ j--;其他情況的話j--。
最後將ans回傳。
```cpp
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size()-2;i++){
int k=i+1,j=nums.size()-1;
while(k<j){
if(nums[i]+nums[k]+nums[j]<0){
k++;
}
else if(nums[i]+nums[k]+nums[j]==0){
vector<int> test = {nums[i], nums[k], nums[j]};
auto compare=find(ans.begin(),ans.end(),test);
if(compare==ans.end() ){
ans.push_back(test);
}
k++;
j--;
}
else{
j--;
}
}
}
return ans;
}
};
```
- [ ] 程式碼改善方法
上面的方法，當每次要存入一筆正解之前，都必須要判斷1次ans裡面是否有相同答案，這是相當耗時的作法。在這裡有一個改進方案，有一筆正解時，先不用判斷，直接存入ans裡面。for迴圈結束後，再將ans裡面重複資料刪除。
```cpp
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size()-2;i++){
int k=i+1,j=nums.size()-1;
while(k<j){
if(nums[i]+nums[k]+nums[j]<0){
k++;
}
else if(nums[i]+nums[k]+nums[j]==0){
ans.push_back({nums[i], nums[k], nums[j]});
k++;
j--;
}
else{
j--;
}
}
}
set<vector<int>>uniqueans(ans.begin(),ans.end());
ans.assign(uniqueans.begin(),uniqueans.end());
return ans;
}
};
```
## 面試過程檢討
### interviewer
- 出題方式可以有變化一點，不要讓interviewee馬上就能知道要寫出怎樣的程式。
- interviewer通常不會誇interviewee的approach。
- 可以在interviewee coding到一半時詢問interviewee。
### interviewee
- 在coding時，可以把念出程式碼，改成==說明這段程式碼的意義==。
- 在coding時，會發生程式碼打對，但是講出來的東西是錯的。
- 例如 ==`i<nums.size()-2`== 會講成 ==`i<nums.size()`==
- 可以放慢打字速度，==降低誤打率==。
- 在用英文說明程式碼時，沒辦法清楚表達。
- 在optimization的部分，可以先說明優化的想法在開始實作。
- 可以適當的使用==肢體動作==來輔助。
- 雖然在coding期間都有說明程式碼的用途，但是可以==善用註解來輔助==interviewer理解。
---
## 第二次作業-他評 01
### 關於 interviewer
- [ ] 優點
* [20:50](https://youtu.be/jJTtHZZQsy4?t=1250): 不會只提出一個問題點，一次提出兩個問題讓面試者去思考。
- [ ] 可改進的地方
* 講話太像照稿唸，雖然可能真的是在照稿唸，但可以有感情一點點。
* 題目可以換句話說，避免直接把想問的問題問出來，可以轉換成生活情境來問。
### 關於 interviewee
- [ ] 優點
* 打code流暢，邊講話邊打code不會卡詞。
- [ ] 可改進的地方
* 講中文時流暢但換成英文時速度明顯變慢了。
* [0:49](https://youtu.be/jJTtHZZQsy4?t=49): 通常面試應會在文字編輯器或是空白文件上打code，所以在開始打程式前應不會有打好任何程式在畫面上，也不會有自動縮排的功能。
* [10:51](https://youtu.be/jJTtHZZQsy4?t=651): 講話講到一半被卡掉了。
* [12:26](https://youtu.be/jJTtHZZQsy4?t=746): 在REACTO中，repeat,example和approach完皆沒有等面試人員給回覆就直接開始下面的流程，應留時間給面試人員提問。
* [21:35](https://youtu.be/jJTtHZZQsy4?t=1295): 盡量不要說"面試官" 。
* [30:35](https://youtu.be/jJTtHZZQsy4?t=1835): 打的code已經到螢幕的最下面了，應調整一下畫面讓面試人員可以看清楚完整的code。
## 第二次作業-他評 02
### 關於 interviewer
- [ ] 優點
* 講話咬字很清楚
* [20:47](https://youtu.be/jJTtHZZQsy4?si=FdAvtMbBW05QSLLC&t=1247): 快速觀察interviewee剛完成的code，並點出不只一個問題協助interviewee思考優化方向
- [ ] 可改進的地方
* [10:53](https://youtu.be/jJTtHZZQsy4?si=SnzCDRmKKDCiWbiy&t=653): 比起直接問還有沒有其他作法，假設interviewer有其他的優化想法，可以用引導的方式問interviewee，也可以安排interviewee反問，增加互動
* [11:02](https://youtu.be/jJTtHZZQsy4?si=SrK9HIPXHE2w8Hyo&t=662): 這邊是不是沒剪好？才剛說進到下一題，後面又說直接進入第一題
* 題目可以先包裝過再提出，比較不容易被interviewee猜到
### 關於 interviewee
- [ ] 優點
* 一邊打code一邊說明不會卡，蠻流暢的
* 邏輯清晰，面對多種case的題目也可以逐一列出並完成對應的code
* 針對interviewer提出的點尋找優化的方向
- [ ] 可改進的地方
* 通常面試不會像LeetCode上面一樣一開始就把function跟輸入都寫好給你，應該要透過和interviewer互動來決定這些東西要如何設計
* [2:15](https://youtu.be/jJTtHZZQsy4?si=AotK4pzpo1OxVMKn&t=133): 這段在說明for迴圈的內容描述得不太清楚，也沒有說明j跟k分別代表什麼，這個部分應該是REACTO的A，建議捨棄掉實作的部分，專注在說明想法就好
* REACTO的T沒有做，針對前面舉的例子做測試會有助於讓interviewer理解運作方式
* REACTO的EAC的過程太快了，沒有跟interviewer互動
* (第三題)結束的太倉促
Sign in with Wallet
Connect another wallet