# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者: 真蝦-shrimp
> [模擬面試影片-1: 漢語](https://www.youtube.com/watch?v=TN2Vra2AeNU)
> [模擬面試影片-2: 漢語](https://www.youtube.com/watch?v=glbXIjHLiEs)
> [模擬面試影片: 英語](https://www.youtube.com/watch?v=p9Z23BfNylQ)
>
> 🧔：interviewer 👶：interviewee

## [206. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/)

測驗說明與問答
🧔：你好,我是全聯電子的工程師,很高興能請你來參加這次的coding面試,然後這邊有準備一道題目來做一個程式能力的測驗,我會給你一個linklist,他會由1->2->3,並希望你能reverse整條linklist讓他變成3->2->１又或者5->4->3->2->1變1->2->3->4->5
👶：(作答中)

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* reverseList(struct ListNode* head){
    if(head == NULL){
        return NULL;
    }
    if(head -> next == NULL){
        return head;
    }
    
    struct ListNode *temp_prev = head;
    struct ListNode *temp_next = head;
    struct ListNode *temp_cur = head;

    temp_next = temp_next -> next;
    
    if(temp_next -> next != NULL){
        temp_next = temp_next -> next;
    }else{
        temp_next -> next = temp_cur;
        temp_cur -> next = NULL;
        head = temp_next;
        return head;
    }

    temp_cur = temp_cur -> next;
    temp_prev -> next = NULL;
    temp_cur -> next = temp_prev;
    temp_prev = temp_cur;
    temp_cur = temp_next;

    while(temp_next ->next != NULL){
        temp_next = temp_next -> next;
        temp_cur ->next = temp_prev;
        temp_prev = temp_cur;
        temp_cur = temp_next;
    }

    temp_cur -> next = temp_prev;
    head = temp_cur;
    return head;
}

🧔：那你可以分析一下你這樣做的時間複雜度嗎？

👶：我要走完整個list,所以時間會是O(n),而每個for-loop裡面的操作則是O(1),所以整體時間為O(n)

🧔：那像這樣你有沒有考慮用recursive的方式來寫呢

👶：如果用recursive的話我會用以下這樣的寫法(coding)

struct ListNode* reverseList(struct ListNode* head) {

    struct ListNode* ans = head;
    struct ListNode* prev = NULL;
    while(head!=NULL){
        head = head->next;
        ans->next = prev;
        prev = ans;
        ans = head;
    }
    return prev;
}

🧔：好那很感謝陳同學你來參加今天的面試,那我們有結果會再通知您

## [83. Remove Duplicates from Sorted List](https://leetcode.com/problems/remove-duplicates-from-sorted-list/)
測驗說明與問答
🧔：你好,我是這次負責這場面試的工程師,歡迎你來參加我們全聯電子的coding面試,那我今天準備的問題是,有一條linklist會傳給你一個head的pointer那你需要告訴我把中間的重複的點remove掉會長怎樣,現在有兩個例子在這邊給你參考,並且以下會給你一些限制,像是整條list node數會在
O到300之間,而裡面的值會落在-100到100這個範圍,並且會給你一個遞增排序的list,那想問一下你有沒有什麼問題,如果沒有的話就可以開始作答了

👶：(coding中)那這邊就差不多完成了

#include<stdlib.h>
#include<stdlib.h>

struct ListNode{
    int val;
    struct ListNode *next;
};

struct ListNode* deleteDuplicates(struct ListNode* head){
    if(head == NULL){
        return NULL;
    }
    struct ListNode *temp = head;
    struct ListNode *temp_prev = head;

    while(temp -> next != NULL){
        temp = temp ->next;
        while(temp_prev -> val == temp -> val){
            if(temp ->next == NULL){
                temp_prev -> next =NULL;
                return head;
            }else{
                temp_prev -> next = temp_prev ->next ->next;
                temp  = temp ->next;
            }
        }
        temp_prev = temp_prev ->next;
        if(temp_prev->next == NULL){
            return head;
        }
    }
    return head;
}    

🧔：那我這邊看你是用兩個pointer來完成這個code,那我希望你用一樣的概念,並且用一個pointer來完成

👶：好,如果改為一個pointer的話來處理的話就是這樣做

struct ListNode* deleteDuplicates(struct ListNode* head) {
    if(!head) return head;
    struct ListNode *curr = head;
    while(curr->next){
        if(curr->val == curr->next->val){
            struct ListNode *temp = curr->next;
            curr->next = curr->next->next;
            free(temp);
        }
        else{
            curr = curr->next;
        } 
    }
    return head;
}

🧔：那你可以分析一下你這樣做的時間複雜度嗎？
👶：那這邊要刪除重複節點的話,也是走完整條linklist一次,所以時間會是O(n),而每個for-loop裡面的操作則是O(1),所以整體時間也是O(n)

## [2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list)
測驗說明與問答

🧔：Welcome to today's interview. I am the engineer responsible for conducting this English interview. Now, you can see that I have a question for you. If there are an even number of nodes in the linked list, delete the ⌊n / 2⌋th node. However, if there is an odd number of nodes, simply delete the middle node. Finally, return the linked list with the middle node removed.

👶：coding

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* deleteMiddle(struct ListNode* head){
    float count = 0;


    struct ListNode *temp = (struct ListNode*) malloc(sizeof(struct ListNode));
    struct ListNode *targetNode = (struct ListNode*) malloc(sizeof(struct ListNode));

    temp ->next = head;
    while(temp -> next != NULL){
        count++;
        temp = temp ->next;
    }
    
    targetNode -> next = head;
    if(count == 1){
        return NULL;
    }else{
        count = floor(count/2);
        for(int i = 0; i < count; i++){
            targetNode = targetNode -> next;
        }
        targetNode ->next = (targetNode ->next) -> next;
    
    }
    return head;
}

---

## 他評 - 01
### 關於 interviewer
- [ ] 優點
* 語速穩定，口齒清晰

- [ ] 可改進的地方
* 可以在撰寫程式時提出問題或是多一點問答

### 關於 interviewee
- [ ] 優點
* 撰寫程式時邊講解，方便理解思路

- [ ] 可改進的地方
* [00:48](https://youtu.be/TN2Vra2AeNU?t=48): 缺少 REACTO 的 R、E、A
* [8:43](https://youtu.be/TN2Vra2AeNU?t=523): 馬賽克跑掉了

## 他評 - 02
- [ ] 優點
* 說話清楚、沒有什麼停頓感
* 寫程式時有配合著說明

- [ ] 可改進之處
* [第一題 13:40](https://www.youtube.com/watch?v=TN2Vra2AeNU) Recursive 解法本身沒有問題，但這解法應該不算遞迴，比較算是使用雙重指標的寫法，遞迴應該是函式要呼叫自己本身 ([Wikipedia 定義](https://en.wikipedia.org/wiki/Recursion))
* 比較合理的寫法如下 (參考自 [LeetCode 刷题攻略 - 206.反转链表](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.md))

        ListNode* reverse(ListNode* pre,ListNode* cur){
            if(cur == NULL) return pre;
            ListNode* temp = cur->next;
            cur->next = pre;
            return reverse(cur,temp); // 呼叫 reverse() 自己本身
        }
        ListNode* reverseList(ListNode* head) { // 主程式
            return reverse(NULL, head);
        }

* [第三題](https://www.youtube.com/watch?v=p9Z23BfNylQ) 後續在 Optimization 的階段，Interviewer 可以再進一步詢問「是否有不用計算 Linked List 長度，但仍可以得到答案之解法?」
* 可以使用雙重指標的寫法，參考自 [Leetcode solution - One Pass - Slow and Fast](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/solutions/1612140/one-pass-slow-and-fast/)

        ListNode* deleteMiddle(ListNode* head) {
            if (head->next == nullptr)
                return nullptr;
            auto slow = head, fast = head->next->next;
            while (fast != nullptr && fast->next != nullptr) {
                fast = fast->next->next;
                slow = slow->next;
            }
            slow->next = slow->next->next;
            return head;
        }

- [ ] 其他
* [第二題](https://www.youtube.com/watch?v=glbXIjHLiEs) 沒聲音 :cry:

## 他評03
### interviewer
- [ ] 優點
* 咬字清楚，語速穩定

- [ ] 可改進的地方
* 雙方互動可以增加
* 題目缺少情境

### interviewee
- [ ] 優點
* 分析程式時脈絡完整

- [ ] 可改進的地方
* REACTO不完整

## 他評04
### 關於interviewer
- [ ] 優點
* 語速適中，咬字清晰。

- [ ] 可改進的地方
* 可以多說明問題細節，舉例讓面試者更了解問題。
* 可以稍微包裝一下題目以防面試者背題目之類的。

### 關於interviewee
- [ ] 優點
* [8:47](https://www.youtube.com/watch?v=TN2Vra2AeNU&t=527s)有註解很棒。

- [ ] 可改進的地方
* [3:36](https://www.youtube.com/watch?v=TN2Vra2AeNU&t=216) 盡量用沒有提示的Editor來打code，例如Notepad或Word。
* [7:07](https://www.youtube.com/watch?v=TN2Vra2AeNU&t=427) else沒有換一行很躁。 :angry: :angry:

## 他評05
### interviewer
- [ ] 優點
* 口條清晰，語速穩定

- [ ] 可改進的地方
* 題目缺少情境

### interviewee
- [ ] 優點
* 可以一邊打程式一邊解說

- [ ] 可改進的地方
* 敲鍵盤聲音有點大
* 影片2沒有聲音