# 2024 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2024/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FH1-4KbanC)」課程作業 2
> 貢獻者: 菜就多練-Rookie
> 面試夥伴：迷因柴犬-Doge
### 學員面試檢討：
1. [五空-Monkey](https://hackmd.io/w7Iz6haNQkODLzs0htcQJA?view#%E4%BB%96%E8%A9%9502) 他評02
2. [卡普空-Capcom](https://hackmd.io/IbLz_05lQWmp8qJ2eMhCvg?view#%E5%90%8C%E5%84%95%E6%AA%A2%E8%A8%8E02)同儕檢討02
3. [魯智深-NatureLover](https://hackmd.io/Fa1bSAKeR6G2Eq3p8m52pA?view#%E4%BB%96%E8%A9%9502) 他評02
4. [溫兜絲奉-Wendowsform](https://hackmd.io/ZH8OCJPJSheKJjAg47mmQQ?view#%E4%BB%96%E8%A9%953) 他評3
5. [Amanda-艾曼達](https://hackmd.io/OSagT9xVQAq9U2cgdcP-5w?view#%E4%BB%96%E8%A9%9502) 他評02

## [3. Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/description/)
> [面試影片](https://www.youtube.com/watch?v=rc-TyLWEZvA)
> 💁‍♂：Interviewer(我)
> 🙋：Interviewee

### 面試過程
💁‍♂：Doge同學好，歡迎你參加今天面試，我們今天會給你一道經典題目：Longest Substring Without Repeating Characters，我們會給你一個字串，要你找出這字串中不含重複字元的最長字串，並返回長度。這樣你有理解題目嗎？
🙋：我有理解。
💁‍♂：那麼你打算怎麼處理這題呢？
🙋：我想用for迴圈檢查字串長度，從第一個字元開始檢查到最後一個字元，看有沒有重複，沒有重複的話，我就把他記到最大長度(變數)裡面，因為題目要回傳長度，因此用迴圈把答案記到最大長度(變數)裡面，就是我們要的結果。
💁‍♂：聽起來有道理，那你可以試著做做看。
🙋：(面試者做題中)

def lengthOfLongestSubstring(s: str) -> int:
    maxLength = 0
    for i in range(len(s)):
        for j in range(i + 1, len(s) + 1):
            substr = s[i:j]
            if len(set(substr)) === len(substr):
                maxLength = max(maxLength, len(substr))
    return maxLength

💁‍♂：同學你第6行的"="是不是多了一個
🙋：三個"="是同型別比較，因為python一開始給變數的時候不會定義型別，所以當要比叫型別時，會用三個"="，我這裡用是比較龜毛的寫法。
💁‍♂：OK，很棒的回答。那請問這個方法的時間複雜度是多少？
🙋：因為包了兩個迴圈，所以時間複雜度是$O(N^2)$，效率不好
💁‍♂：那請問你有別的方法可以improve效率嗎？
🙋：可以用滑動窗口的方式優化，若後面字串找到跟裡面有一樣的，就把前面一樣的縮短，這樣就能確保他是不重複且長度最大的。這樣可能就能用一個迴圈完成工作。
🙋：那我現在就來實做程式碼。
💁‍♂：OK
🙋：(面試者做題中)

def lengthOfLongestSubstring(s: str) -> int:  
    seen = set()    
    left = 0    
    maxLength = 0    
    for right in range(len(s)):        
        while s[right] in seen: 
            seen.remove(s[left])
            left += 1        
        seen.add(s[right])        
        maxLength = max(maxLength, right - left + 1)    
    return maxLength

💁‍♂：請問這樣時間複雜度多少？
🙋：因為while只會進去一次，所以數目是常數，就不把他當複雜度影響的判斷，所以複雜度是$O(N)$
💁‍♂：等於說是只有外面的for會影響複雜度，裡面的while...
🙋：只會跑常數次，因為後面有重複他就會被排除掉，所以我覺得while可以寫成if，但怕"aa"這種連續的情況，還是寫while比較安心。
💁‍♂：OK，那這解法還有什麼情況要考慮。
🙋：字串是空的時候，可以直接for迴圈跳出來，然後還有，若整個字串都沒有重複，可以直接回傳字串長度。
💁‍♂：OK，你提出不錯的方法來改善暴力解了，所以我們面試到這，謝謝你。

### 面試過程檢討(作為Interviewer)
#### 優點
- 題目講解明確，有特別強調是要會傳字串長度，而非整個字串。
#### 缺點
- 有疑問不及時發問，[00:40](https://www.youtube.com/watch?v=rc-TyLWEZvA&t=40s) 這裡面試者說把字串長度逐一檢查，但面試官一開始沒聽懂，應確認面試者講的字串是否為題目給的字串裡面的各種"子字串"。
- [01:00](https://www.youtube.com/watch?v=rc-TyLWEZvA&t=1m0s) 問題同上，面試者說記到最大長度裡面，應該是要講開一個變數叫最大長度，把它存進去，這裡我也沒很確定，應該要立刻詢問面試者意思。
- [04:25](https://www.youtube.com/watch?v=rc-TyLWEZvA&t=4m25s) 不熟悉python，面試官問這種基本問題，顯得很不專業。
- [10:00](https://www.youtube.com/watch?v=rc-TyLWEZvA&t=10m0s) 一樣沒聽懂沒問，面試者說這麼做可以避免邊界情況，但面試官當下沒聽懂，應追問面試者，請他再講詳細一些。
- [11:24](https://www.youtube.com/watch?v=rc-TyLWEZvA&t=11m24s) 面試官沒搞懂為什麼裡面的while不會計算進時間複雜度，雖然有繼續追問是對的，但更應該要讓自己強一點，不要看不懂別人的code。
- [12:42](https://www.youtube.com/watch?v=rc-TyLWEZvA&t=12m42s) 面試者提出了優化的想法，面試官應該要請他用code實做看看，而非草草結束。

## [2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/description/)
> [面試影片](https://youtu.be/elbknnEbBCI)
> 💁‍♂：Interviewer
> 🙋：Interviewee(我)

### 面試過程
💁‍♂：我們這邊提供一道題目，題目叫Delete the Middle Node of a Linked List，會給你一個linked list，然後會希望你刪除中間節點再回傳。比如說linked list是`1 3 4 7 1 2 6`，會希望你把中間的節點刪掉，然後回傳head。對於題目有沒有其他問題？
🙋：請問意思是，給我`1 3 4 7 1 2 6`，我就要刪掉中間的7，然後再回傳head給你這樣嗎？
💁‍♂：對
🙋：那我們刪掉`7`後，linked list會變成`1 3 4 1 2 6`，那我們還要刪中間的話，要刪掉`4`還是`1`呢？
💁‍♂：刪掉`1`，刪右邊的node
🙋：所以會變`1 3 4 2 6`這樣？
💁‍♂：對
🙋：我有個想法：先用while迴圈traverse linked list來得知有幾個node，再把node數除以2，即可知道誰要被刪除。像是`1 3 4 7 1 2 6`這條linked list有7個node，因此7/2取整數等於3，我們就把index為3的node(也就是7)給刪掉。這個方法可以嗎？
💁‍♂：可以，那就依你的想法把code實作出來。
#### *解法一：暴力法*
直接先traverse整條linked list，得知總共有幾個node，接著除以2得出要刪除的node，接著把`now`指標指回開頭，再走一次linked list，走到被刪node的前一個node，透過改線做到刪除的效果。

class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        int length = 0, delete_idx = 0, now_idx = 0;
        ListNode *now = head;
        if (now->next == nullptr) return NULL;
        while (now) {
            length++;
            now = now->next;
        }        
        delete_idx = length / 2;
        now = head;
        while (now) {
            if (now_idx == delete_idx-1) {
                now->next = now->next->next;
            }
            now_idx++;
            now = now->next;
        }
        return head;
    }
};

💁‍♂：這樣看起來有達到功能需求，請問這份code有沒有需要改善的地方，或者他的空間&時間複雜度是多少？
🙋：空間複雜度是$O(1)$，因為這邊只有開這幾個變數。
💁‍♂：恩，對
🙋：時間複雜度的話，因我們要看兩輪linked list，每次看都需要花$O(N)$，$N$為linked list長度，所以整體是$O(N)$
💁‍♂：恩，對
🙋：至於改善方法，我想可以用快慢指標，每次while迴圈中，快指標動兩步，慢指標動一步，這樣快指標到結尾時，慢指標就會走到中間的點，而我們題目就是要刪掉中間的點。我覺得可以用這個想法做做看。
💁‍♂：聽起來是個蠻特別也不錯的想法，那你就實作看看。
#### *解法二：快慢指標*
由於題目要求刪除中間的點，因此可以利用快慢指標的特性，快指標一次走兩步，慢指標一次走一步，那麼當快指標走到底時，慢指標就會剛好走到中間，也就是我們要刪除的點。
想法很美好，但在實務上，由於快指針一次動兩步，所以在快指標traverse到結尾時，可能會遇到兩種情況，分別為：
`fast->next`為NULL；
`fast->next`不為NULL，但`fast->next`為NULL
此時即可討論這兩種情況下，慢指標的狀況：
+ `fast->next`為NULL
此case中，慢指標直接指向要被刪除的node，因此，我們可以事先建立`pre`指標紀錄慢指標的前一個node，若走到此case，則讓`pre->next = slow->next`即可。
+ `fast->next`不為NULL，但`fast->next`為NULL
此case中，慢指標指向要背刪除的node的前一個node，所以直接讓`slow->next = slow->next->next`，即透過改線刪除middle node。此外，由於已經經過前面的`if`判斷，因此這裡不用再判斷`fast->next`是否為NULL，直接判斷`fast->next->next`即可。

class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        if (!head->next) return NULL;
        ListNode *fast = head, *slow = head, *pre = head;
        while (1) {
            if (fast->next == NULL){
                // 慢指針要刪
                pre->next = slow->next;
                break;
            }
            if (fast->next->next == NULL) {
                // 慢指針的下一個要刪
                slow->next = slow->next->next;
                break;
            }
            fast = fast->next->next;
            pre = slow;
            slow = slow->next;
        }
        return head;
    }
};

💁‍♂：看起來這份code有達到要求，那請問這份code時間複雜度是多少？
🙋：老實說沒快多少，快了兩倍(但還是O$(N)$)。因為前一份code看linked list兩次，但這份code只要看一次。因為我們從頭走到尾的瞬間，就能順便處裡中間點的刪除動作，所以只要看一次。
💁‍♂：這是一個不錯的做法，可以同時在跑一次迴圈的情況下就把所有東西檢查完，提高效率，那我們這次面試就到這裡，謝謝你的參與。
🙋：謝謝

### 面試過程檢討(作為Interviewee)
#### 優點
+ 快慢指標解釋&舉例恰當。
+ 有解釋時、空間複雜度原因。
#### 缺點
+ 應確認網路、視訊、打code媒介正常，由於上述問題，[01:30](https://youtu.be/elbknnEbBCI&t=1m30s) 這裡之前我打的example沒有出現，反而之後瞬間出現，可能會被懷疑複製貼上。
+ 沒有遵守REACTO，code寫完後沒有Test。
+ [06:40](https://youtu.be/elbknnEbBCI&t=6m40s) 這裡語言沒組織好，註解要註解的完善，不要打一打覺得不對勁又刪掉，可以想好怎麼打後再把註解打回來。
+ [16:20](https://youtu.be/elbknnEbBCI&t=16m20s) 這裡沒說清楚，應該講明確說是當快指標走到Linked list結尾的瞬間。
+ 應該和面試官討論刪除linked list中間node這件事，可能在什麼情境下會發生。

## 檢討自己至今的表現
我覺得我對於這堂課的投入算是蠻認真的，雖然在擔任面試官or面試者時，都還有不小的進步空間，但在態度這一塊，我自認是蠻用心的。都會準時把作業做完，也會認真寫leetcode準備面試題目。
在上課時，我總是認真聽講，每次在課堂上的面試模擬，雖然上台模擬面試的不是我，但我也會在台下想這個題目該怎麼解，要怎麼遵循REACTO流程回答，以及一開始想到的方法時空間複雜度如何，有沒有其他更好的方法等等。每次老師抓人模擬面試都讓我有許多思考。
而學長演講的環節，我也是聽得很認真，上次Champ學長演講也是讓我獲益匪淺，也讓我知道堅持不一定是美德，有彈性的調整才是正確的這種核心理念。
基於以上幾點，我認為我對於這堂課的投入和心態都是蠻正向的。但依然是有許多需要改善的部分：
- 首先是自身實力，由於我基礎不好，有時會看不懂別人寫的code(像這次面試隊友的那題)，這點需要多刷題來加強。
- 接著是積極度問題，老師在課上問誰要自願模擬面試時，我從不舉手，因為我內心是有的怕上台的，但其實上台是一個難能可貴的練習機會，還能順便賺些小錢，不該這麼排斥才對。
- 最後是太不敢問，這次面試隊友的過程中，有數次沒聽懂他表達的意思，但我大多選擇草草帶過，這樣不求甚解是不好的，應該問到清楚理解才對。

以上這些缺點，希望能在日後的課程中逐步改進，讓我能做好準備，面對未來真正的企業面試。