2023 年「資訊科技產業專案設計」作業 2

查理-Charlie

: 我

: 面試官

影片連結

206.Reverse Linked List

模擬面試過程

: 題目會給你一個指向一組Linked List的指標叫做 head，請你將這組Linked List進行反轉，並且回傳反轉後的Linked List。

: 請問你對題目有疑問嗎？

: 有的，我想詢問關於輸入的Linked List 的邊界條件？

: 輸入的Linked List 中其節點數的範圍是0~5000。

: 好的，爲了確認我對題目的理解，我想用一個例子説明。這道題讓輸入的Linked list 反轉，就是讓每個node 指向下一個node的指標反方向。

輸入： [1,3,5,7,9]
輸出： [9,7,5,3,1]

: 並且在結尾的node指向的下一個node 必須給定NULL，才能確定到了linked list 的最後。

:請問我對題目的理解正確嗎？

: 正確，你可以開始寫你的程式了。

: 在寫程式之前，我想先講一下我的想法。

: 首先，我想到的是使用遞迴法來做這道題。我會將除了第一個節點的其他節點全部反轉，再接上原先的第一個節點，再接上NULL。

class Solution {
public:
    struct ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next == NULL){
            return head;
        }
        struct ListNode* prev = NULL;
        struct ListNode* newhead = reverseList(head->next);
        head->next->next = head;
        head->next = prev;
 
        return newhead;
    
    }
};

: 使用這個方法的空間複雜度為O(n)，時間複雜度也是O(n)。

: 除了用遞迴的方法之外，你覺得你還能用更好的方法解決這道題嗎?

: 第二種方法我想到的是使用迭代法來做這道題。我會先宣告 3 個 node 指標：newhead、cur、next。cur 指向我們當前需要反向的 node，而 newhead 則是指向上一個反向完的 node，至於 next 則是先指向當前 node 在反向前所指向的下一個 node。

class Solution {
public:
    struct ListNode* reverseList(ListNode* head) {
        
        struct ListNode* newhead = NULL;
        struct ListNode* curr = head;
        while (curr != NULL){
            struct ListNode* next = curr->next;
            curr->next = newhead;
            newhead = curr;
            curr = next;
        }
        return newhead;

    }
};

: 這個方法中我只宣告了 3 個指標，所以空間複雜度為O(1)。因為需要走訪每個 node 再改變他們指向的下一個的指標，所以時間複雜度為O(n)。

: 好的，謝謝你的作答。那我現在改變一下題目，我依然會給你一組Linked List，請你寫出可以判斷這組Linked List 是否回文的程式。請問你有任何問題嗎?

: 有的，我想請問這組 Linked List 的邊界條件?

: :Linked List 中的節點數範圍為1~10000。

: 好的，爲了確認我對題目的理解，我想用一個例子説明。

輸入： [1,3,5,3,1] 輸出： true
輸入： [1,3,5,7,9] 輸出： false

:請問我對題目的理解正確嗎？

: 正確，你可以開始寫你的程式了。

: 在寫程式之前，我想先講一下我的想法。

: 首先，我會先將Linked List反轉，接著再逐一比較反轉後的Linked List 和原先的Linked List 是否一模一樣，如此便可以知道是否為回文。

class Solution{
public:
    bool isPalindrome(ListNode* head){
        if (head == NULL||head->next == NULL)
        {
            return head;
        }
        ListNode* newhead = NULL;
        ListNode* curr = head;

        while(curr!=NULL)
        {
            ListNode *temp = new ListNode(curr->val);
            temp ->next = newhead;
            newhead = temp;
            curr = curr->next;
        }
        while(head && newhead)
        {
            if (head->val != newhead->val)
            {
                return false;
            }
            head = head->next;
            newhead = newhead->next;
        }
        return true;
    }
};

:使用這個方法的空間複雜度為O(n)，時間複雜度也是O(n)。

:好的，謝謝你。

---

模擬面試檢討

自評

interviewer:

1. 口齒可以更加清晰。
   interviewee:
2. 口齒可以更加清晰
3. 說話聲音再大一點
4. 一邊打程式一邊解說時，聲音會越來越小。
5. 3:12 4:10打錯字(正確: head、reverseList)，應該多練習打程式的速度和正確率

---

第一次作業的收穫

interviewer:

• 優點

1. 有開場白，可能會先介紹自己是哪一間公司…，先和interviewee稍微互動後才進入題目
2. 題目有做變形，延伸到一些真實情況上

interviewee:

• 優點

1. 口齒清晰，聲音自然，語速穩定
2. 解釋程式時的思路清楚

第四次作業 他評01

• 3:30人的收音不好，音量偏小，另外像16:17~16:27這邊聲音都糊在一起，而且整個面試出現很多次機車、汽車經過的聲音，需要換去更安靜的房間面試、窗戶關小一點，或是找降噪方法。
• 2:03、4:06 reverse都拼錯字了。
• 7:07講複雜度O(n)卻忘記講為什麼，給人感覺像用背的。不過後面說明遞迴解法的複雜度時就有記得講原因，讚。
• 7:08interviewer問的是「更好」的方式，interviewee回答迭代法後卻沒有比較以上兩個方法說明為什麼迭代更好，interviewer好像也忘記自己說過要找更好的解法，直接就進入下一題。我覺得可能的回答可以說空間複雜度更低。
• 7:31講的是三個「指標」，但後面code時就講成「指針」了。
• 因為21:04已經實際代入［13531］這個例子說明那段程式碼可以反轉linked list，那23:08［13579］的例子我想就不用再詳細代進程式碼走過這部份了，因為也只是反轉而已，重複性太高了，可以直接跳去講判斷不是回文回傳false那部分。
• 24:48複雜度沒有講原因。

第四次作業 他評02

• intervewee
  • 7:00通常面試在分析時間複雜度的時候應該說明為何他的時間複雜度是O(N)，而不是直接說O(N)就帶過，應該要逐步說明每一行程式碼操作所需要的時間複雜度來做說明。
• interviewer
  • 2:00題目設計的時候應該盡量避免直接講出 reverse linkedlist這種關鍵字，舉例：當我們需要用非連續記憶體空間記錄一串資料的時候，你會使用何種資料結構去儲存？進一步延伸到如果我們需要順序性來取得空間內部的資料，以及如果順序性需要反轉的話你會如何實作？這樣才可以避免背答案怪人。