# 2025 年「資訊科技產業專案設計」課程第 2 次作業
> 貢獻者 : ==法拉第 Faraday== , Hypatia
> [面試錄影-1](https://youtu.be/AZ_a5DFVZTo)
> [面試錄影-2](https://youtu.be/GeCwDBFH_Hw?si=nD0jkl7qS3Qqbpfy)
## [LeetCode : 83. Remove Duplicates from Sorted List](https://leetcode.com/problems/remove-duplicates-from-sorted-list/description/?envType=problem-list-v2&envId=linked-list)
> 👨💼 interviewer : Hypatia (暱稱)
> 👩💻 interviewee : Faraday (暱稱)
### 模擬面試過程
**👨💼 interviewer:**
您好，那我們就直接開始今天的面試。想要先請你用C語言實作一個演算法題目，給你一個"已經排序"的單向鏈結串列，請你移除重複的節點，讓每個元素只出現一次，並且要回傳處理後的鏈結串列head節點。請問這樣有理解題目嗎?
**👩💻 interviewee: ==(Repeat, Example)==**
好的，那我先重複一次題目，確定我理解正確。所以題目會給我一個排序好的鏈結串列，我需要移除裡面的重複值，讓每個值只出現一次，最後回傳更新後的串列。假設我的串列是 1 → 1 → 2 → 3 → 3，那在我執行完這個程式後，串列會變成 1 → 2 → 3，這樣對吧?
**👨💼 interviewer:**
很好。那你預期怎麼解決這個問題呢?
**👩💻 interviewee: ==(Approach)==**
好，因為這個串列是排序好的，所以所有重複的值都會相鄰。所以我只需要檢查「當前節點的值」是否等於「下一個節點的值」。如果相同，就把重複的節點略過。我的想法是使用一個「指向指標的指標」，一開始指向串列的開頭 head。我會一路往後走，對於每個節點檢查下一個節點是否與它相同。如果相同，讓指標繞過它；如果不同，就接續處理下一個節點。這樣重複做直到串列結尾，就能確保每個值只出現一次，最後回傳更新後的 head。
**👨💼 interviewer:**
大概了解，那請你開始示範你的實作
**👩💻 interviewee: ==(Code)==**
```c
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* deleteDuplicates(struct ListNode* head) {
struct ListNode **ptr = &head;
while (*ptr != NULL && (*ptr)->next != NULL) {
if ((*ptr)->next->val == (*ptr)->val) {
(*ptr)->next = (*ptr)->next->next;
} else {
ptr = &(*ptr)->next;
}
}
return head;
}
```
**👨💼 interviewer:**
你這邊用了 `struct ListNode **ptr = &head;`，這樣設計的好處是什麼呢？和直接用一個 `current` 指標 `(ListNode *current = head;)` 的話差別在哪邊?
**👩💻 interviewee:**
因為使用指標的指標可以讓我統一處理頭節點的情況。
例如當重複的值出現在開頭時，我不需要特別寫額外的條件判斷。
我只要更新「指向當前節點的那個指標」，不論那是 head 還是某個節點的 next，都能正確更新串列。
**👨💼 interviewer:**
假設我們用 `ListNode *current = head;`，然後用 `current->next` 去比對的話，結果會有什麼不同呢？
**👩💻 interviewee:**
假設是使用 `struct ListNode *current = head`，等於是把 head 做一個複製，那當發現下一個節點的值等於目前節點的時候，就會改：`current->next = current->next->next;`，並不會動到 head 本身。這在重複不發生在開頭時不會有問題，但若重複發生在開頭，head 其實會需要被改掉，所以要另外寫一個程式來處理這個情況，要額外寫一個判斷式，然後執行：`head = head->next;`，這樣就需要特別處理 head 的情況。
**👨💼 interviewer:**
很好，你對於指標的理解很清楚。那妳所構寫的這段程式時間複雜度是什麼？空間複雜度又是多少呢？
**👩💻 interviewee:**
時間複雜度是 O(n)，因為我們最多只會拜訪每個節點一次。空間複雜度是 O(1)，只用了幾個指標變數，沒有額外記憶體開銷。
**👨💼 interviewer:**
那如果 linked list 有 n 個節點，你覺得會有什麼潛在邊界條件（edge case）需要特別注意嗎？例如：空鏈結串列或是只有一個節點時？
**👩💻 interviewee:**
需要特別注意的情況，就是在n=0。當n=0，也就是沒有任何節點，在存取下一個節點的時候就會出現 segmentation fault。所以如果鏈結串列是空的，也就是 `head = NULL`，就要讓他直接回傳自己。至於只有一個節點，其實就跟普通串列處理到最後一個節點時的狀況一樣，也就是當前節點的下一個節點是 `NULL`，因此我們要做的就是設定好判斷條件，使他在這個 case 的時候不會進入迴圈。
**👨💼 interviewer:**
現在請你舉一個小例子來驗證你的程式吧!
**👩💻 interviewee:**
假設一開始串列是：
1 → 1 → 2 → 3 → NULL
ptr 指向開頭。
首先，比較當前與下一個值：兩個都是 1，所以跳過重複的節點。
現在串列變成：
1 → 2 → 3 → NULL
ptr 暫時不移動。
接著比較 1 和 2，不同，於是 ptr 往下一個節點移動。
1 → 2 → 3 → NULL
ptr
接著比較 2 和 3，不同，再往下移。
1 → 2 → 3 → NULL
ptr
此時已經到達串列尾端，沒有下一個節點，結束。
最終結果就是 1 → 2 → 3 → NULL，正確答案。
**👨💼 interviewer:**
太好了!那如果我們把題目改成：要刪除所有重複的節點，只保留完全不重複的值，也就是說如果出現兩個一樣的值，這兩個都要刪掉。你會怎麼修改這段程式？
**👩💻 interviewee: ==(Optimization)==**
如果是這個情況，在遇到重複的值後，除了要刪除目前節點，還要刪除所有後面相同值的節點。所以我們會需要特別紀錄重複的值，一次把所有相同值的節點刪掉後，再前進到下一格。
```c
struct ListNode* deleteAllDuplicates(struct ListNode* head) {
struct ListNode **ptr = &head; // double pointer to handle head
while (*ptr != NULL && (*ptr)->next != NULL) {
if ((*ptr)->val == (*ptr)->next->val) {
int dup_val = (*ptr)->val;
// 跳過所有相同值的節點
while (*ptr != NULL && (*ptr)->val == dup_val) {
*ptr = (*ptr)->next; // 直接連到下一個不同節點
}
} else {
ptr = &(*ptr)->next; // 沒重複就前進
}
}
return head;
}
```
**👨💼 interviewer:**
這邊請妳同樣舉一個小例子來驗證你的程式
**👩💻 interviewee: ==(Test)==**
假設一開始串列是：
1 → 1 → 2 → 3 → NULL
ptr 指向開頭。
首先，比較當前與下一個值：兩個都是 1，所以 `dup_val` 就是1。`cur` 跟 `ptr` 在同一個位置:
1 → 1 → 2 → 3 → NULL
ptr
cur
接著比較 `cur` 會一直往後移動，直到他的值不是 `dup_val` ，`ptr` 就跑到 `cur` 的地方
2 → 3 → NULL
ptr
cur
繼續往下一個節點移動，都沒有重複的值，所以最後 2 → 3 → NULL，正確答案。
**👨💼 interviewer:**
如果題目改成：鏈結串列不是排序好的，你會怎麼做？這時候你還能用一樣的邏輯嗎？如果可以請直接修改妳的程式碼，不能的話，你可以敘述你的想法就好~
**👩💻 interviewee:**
如果鏈結串列不是排序好的，就不能使用這個方法。因為它的核心假設是「重複的值會相鄰出現」，我們才能透過一次掃描直接跳過重複區段。如果鏈結串列是未排序的，那這個假設就不成立了，重複的節點可能分散在整個串列中。這種情況下，我們就需要用額外的資料結構來協助判斷。一個常見的作法是使用 Hash Set 來記錄已經出現過的數值：當我們第一次遇到某個值時，就把它加入集合；如果之後再遇到相同的值，就代表它是重複的，我們就把那個節點刪掉。
**👨💼 interviewer:**
你覺得這樣的題目邏輯(包含有順序的沒有順序的)在實務上可以應用在哪些場景呢？
**👩💻 interviewee:**
其實這個題目的邏輯在實務上滿常見的，比如在資料清理或串流處理時，我們常常需要去除重複紀錄。如果資料是事先排序好的，比如說按照日期或時間，那我們就可以像這題一樣，用線性掃描的方式直接刪除相鄰重複項，時間複雜度是 O(n)。但如果資料是亂序的，那就比較接近實際情境，例如合併多個來源的用戶資料，我們就會用 hash set 來追蹤出現過的值，這樣雖然多用了一些空間，但可以保證一次遍歷完成。
**👨💼 interviewer:**
如果這個鏈結串列在多執行緒環境下（concurrent environment）被操作，這樣的實作會有什麼問題？
**👩💻 interviewee:**
在多執行緒環境下這段程式是不安全的，因為它直接修改指標，沒有加任何同步機制。假設一個執行緒正在刪除某個節點時，另一個執行緒也嘗試存取那個節點，就會造成指標錯亂。如果要讓它在 concurrent 環境下安全，可以互斥鎖，確保同時間只有一個執行緒能修改結構。不過這會影響效能。或是使用 Copy-on-Write 機制，就是修改時會建立一份新的鏈結串列版本，避免直接修改共享資料。
**👨💼 interviewer:**
非常好，感謝你的分享，今天的面試就到這裡。
### 同儕互評
針對 interviewer 的檢討
* [7:30](https://youtu.be/AZ_a5DFVZTo?si=Ec37eK5IeiiuoweV&t=450): 應該要定義 `current` 指標為何，再使用 `current->next` ，幫助 interviewee 理解題目。
針對 interviewee 的檢討
* [5:30](https://youtu.be/AZ_a5DFVZTo?si=CMjiNv5G7p5bHNVv&t=330): 「原本他的 next 要指向原本的下下一個」，此句主詞不完整，可以改為「目前節點的 next 連到下下一個節點」。
* [10:48](https://youtu.be/AZ_a5DFVZTo?si=VXKqLbpzn6TZpigA&t=648): `NULL` 讀作 [nʌl/] (音似 no)，不能發「怒」。
* [13:10](https://youtu.be/AZ_a5DFVZTo?si=DkeQ5fusw7JEvuTn&t=790): 句子要完整，要講: 進入到下一個「節點」。
## [LeetCode : 977. Squares of a Sorted Array](https://leetcode.com/problems/squares-of-a-sorted-array/description/)
> 👨💼 interviewer : Faraday (暱稱)
> 👩💻 interviewee : Hypatia (暱稱)
### 模擬面試過程
**👨💼 interviewer:**
您好，那我們就直接開始今天的面試。想要先請你用C語言實作一個演算法題目，給定一個非遞減排序的整數陣列，請你回傳一個陣列，要包含每個元素的平方，並且仍要保持非遞減排序。請問這樣有理解題目嗎?
**👩💻 interviewee: ==(Repeat, Example)==**
好，那也就是說目前會有一個非遞減排序的整數陣列，那我的回傳結果是要讓每個數字平方過後，也要依照非遞減的排序方式來輸出。比如說題目如果給我 `[-3, -1, 0, 2, 4]` 的話，那我的 output 結果應該要是 `[0, 1, 4, 9, 16]` 那請問這樣這理解的正確嗎?
**👨💼 interviewer:**
很好。那請你說明一下你要如何設計演算法？
**👩💻 interviewee: ==(Approach)==**
我覺得最直觀的做法就是平方以後用常見的排序的演算法進行排序，但是因為常見的排序演算法時間複雜度都太高了，就是 O(nlog(n))，所以我會希望說可以利用這個題目本身的特性，讓整個排序的時間複雜度降低到 O(n)。我用一個例子來分享我的想法，假如 input 是 `[-3, -1, 0, 2, 4]` 那我注意到負數跟非負數其實可以變成兩個陣列，因為他有一個特性就是負數的他原本越小，但是他平方以後會越大，所以我可以先變成兩個陣列 `[-3, -1]` 然後再將另外一個陣列是放這個非負數的結果，那這樣我將他們兩個平方以後，因為負數越小會變越大，所以我在負數的這個矩陣，可以再把他們做一個 riverse，這樣就會得到兩個都是遞增的數列。最後我再把這兩個進行 merge，那 merge 的方就是，我會先用兩個指標，指向這個 t1 跟 t2 的第一個，那我們就從第一個開始比，比較小的先放進 list 裡面，然後一直比下去直到把全部的都放置完成，那 merge 完後也可以得到非遞減的數列結果。
**👨💼 interviewer:**
很好，那請你開始實作程式碼。
**👩💻 interviewee: ==(Code)==**
```c
static void reverse(int*a, int n){
int i = 0;
int j = n-1;
while(i<j){
int temp = a[j];
a[i] = a[j];
a[j] = temp;
i++;
j++;
}
}
int * sortedSquare(int* nums, int numsSize, int* returnSize){
int count = 0;
while(count<numSize && nums[count]<0){
count++;
}
int n1 = count;
int n2 = numsSize-count;
int* t1 =(int*)mallox(n1*sizeof(int));
int* t2 =(int*)mallox(n1*sizeof(int));
for(int k=0;k<n1;k++){
int x = nums[k];
t1[k] = x*x;
}
for(int k=0;k<n2;k++){
int x = nums[k];
t2[k] = x*x;
}
reverse(t1,n1);
int* ans = (int*)mallox(numsSize*sizeof(int));
int i = 0;
int j = 0;
while(i<n1 &&j<n2){
if(t1[i]<=t2[j]){
ans[target] = t1[i];
target++;
i++;
}else{
ans[target] = t2[j];
target++;
j++;
}
}
while(i<n1){
ans[target] = t1[i];
target++;
i++;
}
while(j<n2){
ans[target] = t2[i];
target++;
j++;
}
free(t1);
free(t2);
*returnSize = numsSize;
return ans;
}
```
**👨💼 interviewer:**
很好，你提供的步驟非常清楚。這部分是先製作兩個暫存陣列，t1跟t2，然後再把它們合併對吧。那這個方法的空間複雜度會比較高，請問你有沒有辦法只用一個陣列，然後使用指標操作的方式，來完成這個程式?
**👩💻 interviewee: ==(Optimization)==**
可以的沒問題，我有注意到我這個方法的話，因為我這裡有多增加另外兩個，所以他的時間複雜度會變成 O(n)+O(n1)+O(n2) ，相對的確實空間負大度有更高一些。那我這邊有另外一個想法，就是我可以用兩個指標的方式來進行實作。因為平方與過後，我會發現負數是越小平方過後會越大，那正數是越大平方跟過後會越大，所以他的最大值會在最兩邊。所以我可以用兩個指標的方式在最左右兩邊的指標，然後開始往內比，因為他的方向一定是從大排到小，所以我用兩個指標的話可以減少這個空間負大度。
```c
int * sortedSquare(int* nums, int numsSize, int* returnSize){
int* ans = (int*)malloc(numsSize*sizeof(int));
int left = 0;
int right = numsSize-1;
int target = numsSize-1;
*returnSize = numsSize;
while(left<right){
int leftSquare = nums[left]*nums[left];
int rightSquare = nums[right]*nums[right];
if(leftSquare>rightSquare){
ans[target] = leftSquare;
target--;
left++;
}else{
ans[target] = rightSquare;
target--;
right++;
}
}
return ans;
}
```
**👨💼 interviewer:**
請你舉一個小例子來驗證你的程式
**👩💻 interviewee: ==(Test)==**
```
[-3, -1, 0, 2, 4]
l r
[0, 1, 4, 9, 16]
t
```
**👨💼 interviewer:**
如果我不只取平方，而是取一個二次函數 f(x)=ax^2+bx+c，這個方法還能用嗎?如果可以，要如何根據你的程式修改?
**👩💻 interviewee: ==(Optimization)==**
因為二次函數他是一個拋物線圖形，所以他整體來說還是一個對稱圖形，所以一樣可以用這個雙指標的方式去進行，只要把平方的部分改成我要的二次函數。但要注意的事情是，因為二次函數有分，當他的 x 平方首項是負號的話他是一個向下的拋物線，然後正的話是向上，所以這時候我放的這個 target 就要注意一下，因為如果向上的話就是先從大的開始比較，向下的話就是從最小的開始比較，這裡是要注意的地方。
**👨💼 interviewer:**
那如果函數本身就是單調遞增，還需要兩個pointer嗎?
**👩💻 interviewee:**
就不用用到兩個 pointer，因為用到兩個 pointer 原因就是因為我有兩個方向的感覺，但是單調遞增他就只需要一個方向，而且他已經排序好了，原本的排序好的數字放進單調遞增函數他的順序還是會保留，所以我只要單方向的掃描去計算每一個元素的單調遞增函數值，再回傳結果就可以了。
**👨💼 interviewer:**
非常好，感謝你的分享，今天的面試就到這裡。
### 同儕互評
針對 interviewer 的檢討
* [16:14](https://youtu.be/GeCwDBFH_Hw?si=e-J9VC158P1T_RWt&t=974): 在 interviewee 說明完想法後，應該要主動引導其開始 code 的實作。
* [23:42](https://youtu.be/GeCwDBFH_Hw?si=3IT1unVFQ7hgNiC9&t=1422): 在接著問 follow-up 時前，應該要給 interviewee 前面的內容一些回饋，或是才不會感覺好像沒在聽。
針對 interviewee 的檢討
* [1:14](https://youtu.be/GeCwDBFH_Hw?si=na2Eqc5JYTxEL8P8&t=74): 應注意要將 Big O 唸出來。
* [1:46](https://youtu.be/GeCwDBFH_Hw?si=1TevfnOc28yHWNh1&t=106): 在舉例說明時要注意用句前後連貫。例如「我注意到負數跟非負數其實可以變成兩個陣列，因為他有一個特性就是負數的他原本越小，但是他平方以後會越大」此句，使用太多「他」，容易讓聽者搞不清楚主詞是誰；「變成兩個陣列 `[-3, -1]` 然後再將另外一個陣列是放這個非負數的結果」此句，第一個陣列是將元素念出，但第二個陣列是說「非負數」這個類別，這部分需要統一；「負數越小會變越大」此句，應清楚說明為「負數越小，平方後會變越大」。
* [2:29](https://youtu.be/GeCwDBFH_Hw?si=iALqyXPRJk2IOPfk&t=149): 注意是「陣列」非「矩陣」。
* [6:48](https://youtu.be/GeCwDBFH_Hw?si=07kGnuNINv67KyiM&t=408): `int* t2 = (int*)mallox(n1*sizeof(int));` 應改為 `int* t2 =(int*)mallox(n2*sizeof(int));`
* [15:22](https://youtu.be/GeCwDBFH_Hw?si=2NJHBuxHnpW0Cylh&t=922): 應清楚說明是另外兩個甚麼?
* [15:29](https://youtu.be/GeCwDBFH_Hw?si=ULqy4pHBRB4XVI3D&t=929): 應是「空間複雜度」。
* [23:58](https://youtu.be/GeCwDBFH_Hw?si=U29YymzFhxWX5-M5&t=1438): 面試時不適合使用「感覺」一詞。
Sign in with Wallet
Connect another wallet