# 2023 年 「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FS11ooE4Rh)」作業 2
>肥俠 (Billy)
>:santa: : interviewer
>:man: : interviewee
[video](https://youtu.be/DRzvfQix-pg)
## [26. Remove Duplicates from Sorted Array](https://leetcode.com/problems/remove-duplicates-from-sorted-array) <font color="#0CC19A">`Easy`</font>

:santa: : 你好，肥俠，我是瑪莉歐，這一 part 由我來負責主持，那我們就直接進入正題吧! 我將題目放在 google doc 上，當然，我還是會進行說明，聽完說明後，如果你有對這個題目有什麼疑問以及想法，都可以跟我說。
:man: : 好的!。
(題目說明中)
:man: : 請問提交紀錄的儲存方式是否能使用**陣列**來進行?
:santa: : 當然可以。
:man: : 那我將第一個消費者定義為整數 1 ，第二個消費者定義為整數 2，以此類推。這樣是可以的嗎?
:santa: : 沒有問題，你就算用字元來當作辨認他們的方式也是可以的。
:man: : 好的，那因為後台可以看到整個陣列的狀況，所以後台人員直接看最後一項，就可以知道有幾位消費者填表單了，假設為 n 個消費者，我們可以再宣告一個長度為 n 的陣列，裡面為 1 至 n 的值就好了。
:santa: : 很抱歉，雖然你是用整數來辨認消費者，但實際上，儲存的資料是他們的意見回饋，你不會知道每一個消費者的填寫狀況，因此這方法不可行。雖然把問題簡化這方法很不錯，但還是要考慮到實際情況。
:man: : 好的，是我疏忽了，那我延續剛才的方法，也是額外再宣告一個陣列，我們可以讀取原來的陣列，如果當讀的值是第一次出現，就放進我們新宣告的那個陣列當中，如果讀過了，就不做任何事。
:santa: : 好的，我懂你的意思了，請你將你的想法撰寫成程式碼吧!

vector<int> removeDuplicates(vector<int> &consumers) {
    vector<int> ret;
    int cur = 0;
    for (int i = 0; i < consumers.size(); i++) {
        if (consumers[i] != cur) {
            cur = consumers[i];
            ret.push_back(cur);
        }
    }
    return ret;
}

(測試正確性)
:santa: : 好的，程式碼寫得很淺顯易懂，很好的將你的想法實作出來了，那我們再加一個情境，我們要將冗餘的狀況會報給上層，好讓他們願意為我們改善網路以及設備問題，因此他們要知道我們這次活動會刪掉幾個冗餘的紀錄。
:man:(心中OS): 這還不簡單，我就只要加上一個 count 就好了。
:santa: : 而且為了減輕系統負擔，我們要在原來的陣列上刪除冗餘的紀錄，且要在 $O(1)$ 的空間複雜度上完成，然後我們要看到陣列要是連續相異的陣列，陣列當中不得有空白。
:man: : 我舉個例子來確認我有沒有理解錯，假設輸入的陣列為 \[1,1,2,2,3,4,5,5,5\]，刪掉冗餘的陣列為 \[1,(),2,(),3,4,5,(),()\]，但這並不是我們要的，而是要 \[1,2,3,4,5\] ，然後我們刪掉了 4 個冗餘的資料，因此回傳 4 。
:santa: : 理解的沒錯!你目前有什麼想法嗎?
:man: : 先針對在原來的陣列進行更改這個問題好了，我可以利用一個指標，這個指標起初指向這個陣列的第二個位子，因為第一個一定是要留的，然後一樣執行 for 迴圈，從陣列第二個開始，如果當前的值與前一個不一樣，就將這個值寫進指標指向的地方，然後指標再往前移動。
:santa: : 這方法不錯，那關於回傳值呢，你會用什麼樣的方法得出呢?
:man: : 我會建立個用來計數的整數 count ，在 for 迴圈裡面，我會檢驗是否與前一值一樣，如果不一樣，就代表我要將此值移除，因此再寫個 else ，讓 count 加一。
:santa: : 想法聽起來可行，那就請你撰寫出程式，以及對其進行講解。
:man: : 好的。

int removeDuplicates(vector<int> &consumers){
    int index = 1;
    int count = 0;
    for (int i = 1; i < consumers.size(); i++) {
        if (consumers[i] != consumers[i - 1]) {
            consumers[index] = consumers[i];
            index++;
        }
        else count++;
    }
    return count;
}

(測試正確性)
:santa: : 這程式碼看起來有可以繼續簡化的方法，還有我想問，你認為這個程式碼還有優化空間嗎?
:man: : 我觀察到我可以將 for 迴圈中的 if 敘述裡的 index++ 與前一項結合，可以使程式碼簡潔許多，至於您說的優化嗎...。針對陣列改動的行為，這是我目前能想到最好的方式了，但回傳值的部分我有想到另外一個方法。
:santa: : 歡迎你提出來。
:man: : 剛剛在測試程式正確性時，我觀察到 index 最後的值，會等於消費者的人數，那我們紀錄的數量減去消費者人數，就會是刪除的紀錄數量了。
:santa: : 聽起來不錯，你可以將程式改成你這樣的做法嗎?
:man: : 了解。

int removeDuplicates(vector<int> &consumers){
    int index = 1;
    for (int i = 1; i < consumers.size(); i++) {
        if (consumers[i] != consumers[i - 1]) 
            consumers[index++] = consumers[i];
    }
    return consumers.size() - index;
}

:man: : 這樣可以使程式碼更短了。
:santa: : 你可以跟我說這方法與前一版的方法在表現上有什麼不同嗎?
:man: : 前一個版本的方法如果要刪除 n 個資料，那 `count++` 這指令就要執行 n 次，而後者的方法不管如何，只會執行一次，且 `consumers.size()` 的時間複雜度為 constant ，也就是 $O(1)$ ，因此在有資料需要刪除的情況下，後面的方案是比較適合的。
:santa: : 好的，那如果我們這次儲存資料的方式不是陣列，而是 singly-linked list，你會對你的程式做什麼修改呢?
:man: : 如果改成 singly-linked list，程式中 if 的判斷就不適用了，因為不知道前一項的資訊，因此我會多宣告一個 `prev` 來儲存前一個 node，在跟他進行比較。
:santa: : 那我給你 list node 結構，請你將你的程式改寫為適用於 linked list 的方式。

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
 };

:man: : 好的。

int removeDuplicates(ListNode *head){
    ListNode *prev = head;
    ListNode *cur = head->next;
    int len = 1, count = 1;
    while (cur) {
        if (prev->val != cur->val) {
            prev->next = cur;
            prev = cur;
            count++;
        }
        cur = cur->next;
        len++;
    }
    return len - count;
}

(測試正確性)
:santa: : 好的，說得很清楚，那我們今天的面試就到這邊，你今天表現得很好，很希望之後能與你共事!後續的消息那就請你靜待通知了。
:man: : 好的，謝謝您!

## 第一次作業的心得及收穫
### 對其他人提出的意見
* 我自認為我並不是一個程式高手，因此在做 while 迴圈時，我會很在意終止條件，我也希望當 interviewer 在寫 while 迴圈時，可以說明終止條件這樣設定的意思，如果能配合例子就更好。
* 不管是線上面試或是實體面試，我們都應該提起精神，不該露出疲態，因此肢體語言是很重要的，也不該擺出讓人感覺你很無聊的樣子，不管是你是面試官以及面試者。
* 線上面試時，字體大小很重要，字太小對眼睛不好!
* 邊寫程式邊講解不容易，但也要注意，不該是寫完再講解，而是可以在寫這一行前先說要做什麼，這樣不會有抄作業的感覺。(雖然我也知道大家為了把程式寫快，都練習了很多遍)

### 從其他人身上學習到的地方
* 語速不該太快，咬字需要再更清楚，講出專業的內容固然重要，但最重要的是讓聽者聽得懂你在講什麼!
* 面試時應該會有內心想法的時候，錄影片時也可以把這個加進去，這樣對我來說可以更好模擬真實面試場景。
* 要記得測試程式正確性!
* 英文口說雖然我很不擅長，但表達也是很重要，不要因為害怕而念很快、很糊，也許會有冗言贅詞，但還是要注意慢慢念，音節也要念對!

## 他評01
- interviewer的檢討:
- [07:24](https://youtu.be/DRzvfQix-pg?t=444) 這邊的說法是要將冗餘資料從陣列中移除，但後續interviewee在實作時卻只有將陣列中前幾個的值改變，而總體陣列長度還是一樣的，不太了解這樣會對空間產生什麼好處。

- interviewee的檢討:
- [08:50](https://youtu.be/DRzvfQix-pg?t=530) 這邊舉的例子是正確的
- [08:57](https://youtu.be/DRzvfQix-pg?t=537) 但這邊後續的陣列都只有改前幾項，但陣列總長度還是沒變
- [20:36](https://youtu.be/DRzvfQix-pg?t=1236) 可以在最後將陣列後面冗餘的清除掉
- `consumers.erase(consumers.begin() + (consumers.size() - index), consumers.end());`
- Reference: [Cplusplus vector erase](https://cplusplus.com/reference/vector/vector/erase/)
- [22:08](https://youtu.be/DRzvfQix-pg?t=1328) 如果輸入nullptr第一行會直接報錯，可能要先做判斷`if (head == nullptr) return 0;`
- [27:54](https://youtu.be/DRzvfQix-pg?t=1674) 這邊說值被**刪除**了，但其實只是算出有效的個數而已，裡面的值並沒有被更改或是刪除，若要刪除:

            int removeDuplicates(ListNode* head) {
                if (head == nullptr) return 0;

                int duplicatesCount = 0;
                ListNode* cur = head;

                while (cur != nullptr && cur->next != nullptr) {
                    if (cur->val == cur->next->val) {
                        ListNode* duplicateNode = cur->next;
                        cur->next = cur->next->next;
                        delete duplicateNode;
                        duplicatesCount++;
                    } else {
                        cur = cur->next;
                    }
                }

                return duplicatesCount;
            }

## 他評 02:
### interviewee:
* [7:20](https://youtu.be/DRzvfQix-pg?si=ohobqBc7BzpMxJPd&t=440) 感覺直接跟面試官說那還不簡單，有點奇怪，還是那個是內心戲?(如果是的話可能要標示一下比較好)
* [26:54](https://youtu.be/DRzvfQix-pg?si=fcSvLAglWrMQyZ-Z&t=1614) 這裡講解程式碼的時候，滑鼠指標不是很清楚，一下子有反白、一下沒有，會影響觀看以及理解。

### interviewer:
* [20:44](https://youtu.be/DRzvfQix-pg?si=RVrjkBQP_7TXLr1Z&t=1244) 面試官應該要提及為何要改為用鍊結串列來儲存的原因(像是可能有急件功能，要將表單直接插入開頭，用link list實現會比較快等等)

## 他評 03
- interviewer的檢討:
- [5:00](https://www.youtube.com/watch?v=VU6L1gBNy1A&t=300)「有沒有其他更好的方法可以減少空間呢」，可以在這段話適度的引導interviewee，例如直接告訴interviewee使用iterative的的方法或相關的暗示。
- interviewee的檢討:
- [1:16](https://www.youtube.com/watch?v=VU6L1gBNy1A&t=76) 建議說明一下input和output具體是什麼東西，而且一開始應該不會有已經打好code。
- [9:03](https://www.youtube.com/watch?v=VU6L1gBNy1A&t=543) temperature是溫度，應該為temporary。

## 他評 04
* current 的發音有誤。
* [7.20](https://youtu.be/DRzvfQix-pg): 內心戲如上面評論提到，的確很奇怪。
* [15.55](https://youtu.be/DRzvfQix-pg): 這邊test部分，雖然程式很明顯好懂，如果是較複雜的程式而且用codeshare分享畫面，無法即時看到鼠標的話，用滑鼠反白說這個跟前面不一樣，面試官可能會聽不太明白，可以像前面[9:04](https://youtu.be/DRzvfQix-pg)在螢幕打上箭頭(^)的方式，移動箭頭說明目前檢查到哪一個數字