---
# System prepended metadata

title: 2023年資訊科技產業專案設計 作業一
tags: [資訊科技產業專案設計]

---

# 2023年資訊科技產業專案設計 作業一
[影片](https://youtu.be/jAHPmNvnk-w?t=0)
👹 : interviewer
👾 : interviewee
## 21. Merge Two Sorted Lists
> [影片](https://youtu.be/jAHPmNvnk-w?t=2)

### 測驗說明與問答
👹 : 屎地芬森先生你好，給你兩個linked list, 節點的順序都依照節點裡面的值排序好了, 請把它們合併然後回傳給我合併後的linked list head, 可以闡述你打算使用的解答做法, 然後實作
👾 : 我們先預設這個題目是升序排列的, 我的工作會是需要把`list1, list2`給合併成`mergeList`並且回傳list head
    首先我的相法認為我們可以利用merge sort當中merge的做法來處理
    一開始我會先定義一個結構體`struct node`如下
```c
struct node {
    int val;
    struct node *next;
}
```
👾 : 這裡使用的linked list是singly linked list
👾 : 接著考慮兩種特例也就是`list1`或`list2`其中一個為空, 或者兩者都為空的時候, 直接回傳即可
👾 : 接下來處理一般情況可以遞迴的處理, 每次挑出要加入`mergeHead`的node後, 把剩下的linked list繼續傳入`merge`當中處理
```c
struct node *merge(struct node *list1, struct node *list2)
{
    struct node *mergeHead;
    if (!list1)
        return list2;
    if (!list2)
        return list1;
    
    struct node *cur_node1, *cur_node2;
    cur_node1 = list1;
    cur_node2 = list2;
    
    if (cur_node1->val > cur_node2->val) {
        mergeHead = cur_node2;
        mergeHead->next = merge(list1, list2->next);
    } else {
        mergeHead = cur_node1;
        mergeHead->next = merge(list1->next, list2);
    }
    
    return mergeHead;
}
```
👹 : `cur_node1, cur_node2`是否有存在的必要？另外可以分析時間複雜度嗎？
👾 : 面試官說的沒錯, 確實不需要使用`cur_node1, cur_node2`就可以完成此算法, 改寫如下
```c
struct node *merge(struct node *list1, struct node *list2)
{
    struct node *mergeHead;
    if (!list1)
        return list2;
    if (!list2)
        return list1;
    
    if (list1->val > list2->val) {
        mergeHead = list2;
        mergeHead->next = merge(list1, list2->next);
    } else {
        mergeHead = list1;
        mergeHead->next = merge(list1->next, list2);
    }
    
    return mergeHead;
}
```
👾 : 計算時間複雜度首先可以先列出遞迴式, 假設這個`merge`function的input size是$n$, 時間複雜度可以表示$T(n)$, 進行recursive call的時間複雜度會是$T(n-1)$, 其他部分的操作都是$O(1)$, 所以遞迴式可以表示成$T(n) = T(n-1) + O(1)$, 解這個遞迴式可以得到$T(n)=O(n)$
👹 : 可以優化此算法嗎？
👾 : 可以, 原本我沒有使用到編譯器的tail recursion特性導致遞迴呼叫之後會讓function stack不斷疊加, 我可以嘗試把程式改寫成non-recursive
```c
struct node *merge(struct node *list1, struct node *list2)
{
    struct node *mergeHead;
    if (!list1)
        return list2;
    if (!list2)
        return list1;
    
    struct node *cur_node;
    if (list1->val > list2->val) {
        mergeHead = list2;
        list2 = list2->next;
    } else {
        mergeHead = list1;
        list1 = list1->next;
    }
    
    cur_node = mergeHead;
    
    while (list1 && list2) {
        if (list1->val > list2->val) {
            cur_node->next = list2;
            list2 = list2->next;
        } else {
            cur_node->next = list1;
            list1 = list1->next;
        }
        cur_node = cur_node->next;
    }
    
    if (list1)
        cur_node->next = list1;
    if (list2)
        cur_node->next = list2;
    
    return mergeHead;
}
```
👾 : (使用測資測試...)
👹 : 屎地芬森先生謝謝你的作答, 答的不錯謝謝你
## 24. Swap Nodes in Pairs
> [影片](https://youtu.be/jAHPmNvnk-w?t=1717)

### 測驗說明與問答
👹 : 屎地芬森先生您好, 歡迎來到我們公司的面試, 我們給你一個問題, 給你一個linked list, 當中的值是隨機的, 希望你把節點兩兩交換, 並且不能直接修改node當中的值, 請你闡述你的解法之後再開始實作
👾 : 謝謝面試官，這個題目會提供給我一個linked list，之後把節點兩兩交換並且不能直接改變節點中的值
👾 : 首先我會先定義linked list的節點結構
```c
struct node {
    int val;
    struct node *next;
}
```
👾 : 再來思考兩個特別情況, 如果給我的linked list為空, 或者只有一個節點，那也沒有節點可以互換, 直接回傳即可
👾 : 再來處理一般情況, 使用`cnode`和`nnode`, `nnode`是`cnode`的下一個節點, 每次互換的時候把`cnode->next`指向原本的`nnode->next`, 然後把`nnode->next`指向`cnode`
```c
struct node *SwapPairs(sturct node *head)
{
    if (!head || !head->next)
        return head;
    struct node *cnode, *nnode;
    cnode = head;
    while (cnode && cnode->next) {
        nnode = cnode->next;
        cnode->next = nnode->next;
        nnode->next = cnode;
        cnode = cnode->next;
    }
    return head->next;
}
```
👹 : 可以使用一些測資確認正確性嗎？
👾 : (測試...) 不好意思面試官, 有發現錯誤的部分, 請給我一點時間思考並修正
👹 : 沒問題
👾 : 謝謝面試官給我時間思考並修正, 我想可以利用一個指標來記錄前一組pairs的`cnode`, 因為錯誤的原因是`cnode->next`原本應該指向下一組的`nnode`, 但在我原本的做法中卻只會指向下一組的`cnode`, 所以我利用`pnode`來記錄上一組的`cnode`並把`pnode->next`指向當前的`nnode`
```c
struct node *SwapPairs(sturct node *head)
{
    if (!head || !head->next)
        return head;
    struct node *cnode, *nnode, *pnode;
    pnode = NULL;
    cnode = head;
    while (cnode && cnode->next) {
        nnode = cnode->next;
        if (pnode)
            pnode->next = nnode;
        pnode = cnode;
        cnode->next = nnode->next;
        nnode->next = cnode;
        cnode = cnode->next;
    }
    return head->next;
}
```
👹 : 可以請你計算時間複雜度嗎？
👾 : 因為while loop在linked list上面走訪的時候不會往回走, 每個節點都只會走訪一次, 如果給定的linked list長度是$n$, 則時間複雜度就會是$O(n)$
👹 : 屎地芬森先生謝謝你的作答
## 83. Remove Duplicates from Sorted List
> [影片](https://youtu.be/jAHPmNvnk-w?t=3103)

### 測驗說明與問答
👹 : Hello Mr.Stevenson, welcome to our company's interview. We have a question for you, you can describe your solution first and solve it. We're going to give you a sorted linked list with some duplicate values in it, please remove the duplicate nodes and make sure every value exists only once
👾 : Hello interviewer, I'm happy to be interviewed by your company and you. You're going to give me a head of a sorted linked list, and I'll have to remove all the duplicates, I want to make sure that I can assume the sorted order is ascending order right? and I still need remain the duplicate value in one node, not remove all of it right?
👹 : Yes your assumption is right, you can continue your answer
👾 : First I have to define a structure of the linked list node
```c
struct node {
    int val;
    struct node *next;
}
```
👾 : I have to deal with speical case first, if you give me an empty linked list or a linked list with a single node. In both cases I'll just return the head back to you
👾 : For common cases, I'll use two pointer to `struct node`, `cnode, nnode`, and I'll compare the value of them like the following. Since we'll never remove the `head` node, the original `head` is still going to be the final `head` so we can just return `head`
```c
struct node *RemoveDup(struct node *head)
{
    if (!head || !head->next)
        return head;
    struct node *cnode, *nnode;
    cnode = head;
    nnode = head->next;
    while (nnode) {
        if (cnode->val == nnode->val) {
            cnode->next = nnode->next;
        } else {
            cnode = nnode;
        }
        nnode = nnode->next;
    }
    return head;
}
```
👹 : Can you calculate the time complexity of your algorithm? and I wonder that if you can use only one pointer to solve this problem?
👾 : I'll change my code using just one pointer first, becauze `nnode` is always `cnode->next`, so we can replace `nnode`
```c
struct node *RemoveDup(struct node *head)
{
    if (!head || !head->next)
        return head;
    struct node *cnode;
    cnode = head;
    while (cnode->next) {
        if (cnode->val == cnode->next->val) {
            cnode->next = cnode->next->next;
        } else {
            cnode = cnode->next;
        }
    }
    return head;
}
```
👾 : For the time complexity, assume the given linked list size is $n$, for each iteration in the while loop, the time complexity is $O(1)$, and we'll traverse each node exactly once, so the total time complexity is $O(n)$
👹 : Thank you Mr. Stevenson. I've noticed that you remove the duplicate node by changing `cnode->next`, but the duplicate nodes are still alive in the system, can you try to delete it?
👾 : I know I didn't actually free the memory space of the duplicates node, I'll call these nodes as garbage node, and delete it like the following
```c
struct node *RemoveDup(struct node *head)
{
    if (!head || !head->next)
        return head;
    struct node *cnode;
    cnode = head;
    while (cnode->next) {
        if (cnode->val == cnode->next->val) {
            struct node *tmp = cnode->next;
            cnode->next = cnode->next->next;
            free(tmp);
        } else {
            cnode = cnode->next;
        }
    }
    return head;
}
```
👹 : Thank you very much Mr. Steveson.