# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> ### 貢獻者 拉鍊 Zipper
> [3sum(漢)](https://www.youtube.com/watch?v=MDoIdWNAIGs)
> [Valid Parentheses(漢)](https://www.youtube.com/watch?v=RlAbvRqnAEg)
> [Merge Two Sorted Lists(英)](https://www.youtube.com/watch?v=pIuzlTD1irM)
🧔：interviewer 👶：interviewee
## [15. 3sum](https://leetcode.com/problems/3sum/solutions/)
### 難度: medium
🧔：你好拉鍊 歡迎來到蔽公司，那我們就開始今天的面談，這邊有一個有關算法的任務給你，給你一個整數的array 裡面有一些integer的資料，我希望你可以把裡面有任三個數相加等於0的所有element回傳給我。
👶：請問要考慮三個0相加嗎？
🧔：不用，請回傳給我三個不同的element 。
👶：那麼Array裡面有可能為空嗎？
🧔：不會的，Array裡面至少會有三個element
👶：矩陣內是排序過的嗎？
🧔：沒有，隨機排列的。
👶：好的，那麼我的解法是這樣的，我會先排列矩陣把裡面的元素由小到大排序，接著我需要三個pointer first, second 和 third，first指向第一個元素， second指向第二個，然後third指向最後一個元素。接著如果三個pointer相加為0的話，我們就找到了一組解，並把second 向右移動，third向左移動。如果三個pointer相加小於0，代表三數相加太小，所以我們把second向右移動繼續尋找。大於0的話代表三數相加太大，所以我們把third向左移動，如果second和third撞到的話，那就結束first所指的值的尋找，並且把first指標向右移動並且重設second和third的值，也就是second是first的下一個位址，而third一樣是最後一個位址。
🧔：了解，這邊有一個新的條件需要你幫忙，我希望回傳的解不包含重複的解。
👶：好的，我這邊的想法是每一個first指標在找另外兩點的時候，如果找到了一組解，用兩個變數把解記起來，並且在爾後的尋找把一樣的解跳過，並且如果first和first+1指向的數是相同的就跳過。
```c=
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume
* caller calls free().
*/
/*bubble sort*/
int* num_sort(int* nums, int numsSize){
int tmp;
for(int i=0; i<=numsSize-2;i++){
for(int j=i+1; j<=numsSize-1;j++){
if(nums[j]<nums[i]){
tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
}
return nums;
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
int bsize = 8;
int** return_list = (int**)malloc(sizeof(int*)*bsize);
int i=0;
int tmp1=100001, tmp2=100001;
nums = num_sort(nums, numsSize);
int* first = nums;
while(first+1!=&nums[numsSize-1]){
int* second = first+1;
int* third = &nums[numsSize-1];
while(second<third){
if(*first + *second + *third == 0){
if(*second!=tmp1 && *third!=tmp2){
return_list[i] = (int*)malloc(sizeof(int)*3);
return_list[i][0] = *first;
return_list[i][1] = *second;
tmp1 = *second;
return_list[i][2] = *third;
tmp2 = *third;
i++;
}
third--;
second++;
}
else if(*first + *second + *third <0){
second++;
}
else if(*first + *second + *third >0){
third--;
}
if(i==bsize){
bsize *= 2;
return_list = (int**)realloc(return_list, sizeof(int*)*bsize);
}
}
first++;
while(*(first-1)==*first && first!= &nums[numsSize-2]) first++;
tmp1 = 100001;
tmp2 = 100001;
}
*returnSize = i;
*returnColumnSizes = (int*)malloc(sizeof(int)*(*returnSize));
for (int j=0; j<(*returnSize); j++) {
(*returnColumnSizes)[j]=3;
}
return return_list;
}
```
檢討：Interviewer應該對複雜度做提問，在排序的時候也能問問看有沒有其他排序法，可以增加彼此的互動並且順便了解Interviewee一些基礎。
<br><br>
## [20. Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)
### 難度：Easy
🧔：你好拉鍊，歡迎參加今天的面談。
🧔：這邊有一個任務需要你幫忙，我有一個 string s，裡面包含幾種符號：分別是小括號、中括號、大括號。我需要你幫忙判別這個string是否valid，valid的規則是這樣的，每一個括號必須要對應相同種類的括號，而且順序要是對的。
舉例來說：一個小的左括弧，對應一個小的右括弧就是true；一個小的左括弧對應一個中的右括弧就是False的。
👶：我想請問一下 string裡面有可能是空的嗎，空的是true還是false呢？
🧔：String裡面至少會有一個符號，所以不用考慮空的問題。
👶：那我的想法是這樣的，我們需要一個stack，當收到左的小中大括號的時候把他push到stack裡面，當收到右的大中小括號的時候，如果stack的前一個元素可以對上這個右括弧的話，pop這個stack，反之直接return false。直到所有的string中所有的括弧都走訪過，最後要是stack為空的話，return true，反之return false。
🧔：如果string裡面只有一個右括號的話，這部分要注意一下。
👶：是的，如果只有右括號的話沒辦法跟前面的比較，這情況要直接回傳false避免run time error。
```c=
bool isempty(char *stack, char *head){
if(stack==head) return true;
else return false;
}
void push(char *s, char *head){
*head = *s;
}
bool isValid(char * s){
char *tmp = s;
int len = 0;
while(*tmp){
len++;
tmp++;
}
char *stack = (char*)malloc(sizeof(char)*(len+1));
char *head = stack;
while(*s){
if(*s=='(' || *s=='{' || *s=='['){
push(s, head);
head++;
s++;
}
else if((*s==')'||*s=='}'||*s==']')&&head==stack) return false;
else if(*s==')'&&*(head-1)=='('){
head--;
s++;
}
else if(*s=='}'&&*(head-1)=='{'){
head--;
s++;
}
else if(*s==']'&&*(head-1)=='['){
head--;
s++;
}
else return false;
}
return isempty(stack, head);
}
```
檢討：Interviewer可以多對所需要配置的空間作提問。
<br><br>
## [21. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/)
### 難度：Easy
🧔：Hi, Zipper. Welcome to the interview. Here is a problem that I need you help. There are two sorted linked list which we call it list1 and list2. The task is that I want to merge these two lists into one sorted list.
For example, there are two sorted list. First is 2, 4. Second is 3, 4. Therefore, the output should be 2, 3, 4, 4.
👶：Is there any possibility that the two lists are empty?
🧔：Sure, taking empty list into consideration is essential.
👶：And I want to know what the structure of linked list is.
🧔：Just single linked list. There is a integer value, what we call it val, and a node ListNode which points to the next.
👶：Well, My idea is that we traverse list1 and list2 at the same time. When the number in list1 is less than list2, we save it into another link list return_list, which is the structure to save our return list. Then, move the node to next node after saving it into return list. At the end, when traversing all the node from list1 and list2. We can get a return_list which is what we expect.
🧔：Good. I think that your return_list is non-increasing list, but what we want is non-decreasing list as the beginning list1 and list2.
👶：Okay. To achieve it, we need to reverse the return list. Writing an additional function reverse should solve the problem.
```c
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *reverse(struct ListNode *head){
struct ListNode *tmp = NULL;
while(head!=NULL){
struct ListNode *new = malloc(sizeof(struct ListNode));
new -> val = head -> val;
new -> next = tmp;
tmp = new;
head = head->next;
}
return tmp;
}
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
bool flag1 = true;
bool flag2 = true;
int min;
struct ListNode *head = NULL;
if(list1 == NULL && list2 == NULL) return list1;
else if(list1 == NULL) return list2;
else if(list2 == NULL) return list1;
while(flag1 || flag2){
if(flag1==false){
min = list2->val;
list2 = list2->next;
}
else if(flag2==false){
min = list1->val;
list1 = list1->next;
}
else if(list1->val <= list2->val){
min = list1->val;
list1 = list1->next;
}
else if(list1->val > list2->val){
min = list2->val;
list2 = list2->next;
}
if(list1==NULL) flag1=false;
if(list2==NULL) flag2=false;
struct ListNode *tmp = malloc(sizeof(struct ListNode));
tmp->val = min;
tmp->next = head;
head = tmp;
}
struct ListNode *return_list = reverse(head);
return return_list;
}
```
檢討： 英文太破，不知所云，再加油。
## 第二次作業-他評 01
### 關於 interviewer
- [ ] 優點
* 語速一致。
- [ ] 可改進的地方
* 英文部分再加強。
* 題目可以轉換成生活化一點的方式來問而不是只照著leetcode原本題目問。
* [18:32](https://youtu.be/pIuzlTD1irM?t=1112): interviewee完成coding後可以再追問問題而不是直接下一題。
### 關於 interviewee
- [ ] 優點
* 打code時都有邊講解清楚。
- [ ] 可改進的地方
* 有時候會卡詞或講錯話，太緊張的話語速可以放慢些。
* code應可以更精簡一些，太冗長。
* [0:40](https://youtu.be/MDoIdWNAIGs?t=40): 在Repeat完沒有做REACTO中Examples的流程。
* [4:00](https://youtu.be/MDoIdWNAIGs?t=240): 通常面試應會在文字編輯器或是空白文件上打code比較好。
* [4:37](https://youtu.be/RlAbvRqnAEg?t=277): 字太小又模糊，看不太到。
* [11:30](https://youtu.be/RlAbvRqnAEg?t=690): 結束得太突然，沒有Testing也沒有Optimize。
## 第二次作業-他評 02
### 關於 interviewer
- [ ] 優點
* 題目描述清楚。
- [ ] 可改進的地方
* 沒有深入提問較為可惜，例如複雜度的提問、或者題目的變形。
### 關於 interviewee
- [ ] 優點
* 聲音清楚。
- [ ] 可改進的地方
* [3:05](https://www.youtube.com/watch?v=RlAbvRqnAEg&t=184s) 機械鍵盤有點吵，用普通的鍵盤好像比較好。
* [11:26](https://www.youtube.com/watch?v=RlAbvRqnAEg&t=686) 結束的時候可以做個小結，例如說明一下程式怎麼跑的。
## 第二次作業-他評 03
### interviewer
- [ ] 可改進的地方
* interviewer 可以在 interviewee 實作完程式碼後看看有沒有問題或可優化的地方
### interviewee
- [ ] 優點
* 問題條件問得很清楚
* 撰寫程式碼的同時也講解得很清楚
- [ ] 可改進的地方
* [0:44](https://youtu.be/MDoIdWNAIGs?si=fDZiZpX0xE8ssJp7&t=44) 口誤 Array 是陣列不是矩陣
* [15:35](https://youtu.be/MDoIdWNAIGs?si=3CEFVwhPbNr4z8z3&t=935) 沒有考慮到 first 超出陣列大小的非預期狀況
Sign in with Wallet
Connect another wallet