2024 「資訊科技產業專案設計」 HW1

暱稱 : 華一跤，slipontheway

: interviewer , : interviewee

226. Invert Binary Tree

影片 : 00:24
模擬面試過程

: 在影像處理的過程中，經常需要將圖片翻轉，可能是左右翻轉或上下翻轉，那這個翻轉的概念可以對應到資料結構中的tree，你可以幫我用tree的結構做類似圖片左右翻轉的動作嗎?

: 以tree為結構做左右翻轉的概念就類似於將二元樹翻轉，請問tree有什麼限制嗎?

: tree 節點數量<100 ，每個節點的數值介於 -100~100 。

: 好的，那我的想法使用遞迴的方式將左右子樹對調。

遞迴解

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


class Solution {
public:
    TreeNode* invertTree(TreeNode* root) 
    {
        if (root == NULL) return NULL;

        TreeNode *temp = root->left;
        root->left = invertTree(root->right);
        root->right = invertTree(temp);

        return root;
    }
};

: 有其他非遞迴的解法嗎?

: 好的，我的想法是用level order的方式走訪，然後搭配queue的結構。先將root根節點加入queue，先以根節點為主，將他的左有子樹交換，再確認他的左右子樹是否為NULL，如果不是NULL就加入queue。寫成一個迴圈，只要queue不是空的，就用q.front取出一個node，一樣將他的左右子點交換，再將非空的左右子樹加入queue，直到queue為空即完成invert binary tree。

iterative解法

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* invertBinaryTree(TreeNode *root) 
    {
        if (root == NULL) return;

        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            // pop out the front node
            TreeNode *node = q.front();
            q.pop();
            // swap between left and right pointer
            swap(node->left, node->right);
            // push non-NULL node
            if (node->left != NULL) q.push(node->left);
            if (node->right != NULL) q.push(node->right);
        }
        return root;
    }
};

---

19. Remove Nth Node From End of List

影片: 14:44
模擬面試過程

: linking list可以用於管理作業系統中的空閒記憶體。當系統動態分配和釋放記憶體時，它使用linking list追蹤空閒記憶體區塊。今天有一個記憶體空間，要刪除從後面數來的第n個區塊，請你使用linking list的資料結構實現，給你linking list 的head，在刪除後回傳head

: 所以我要刪除倒數第n個元素，我想舉個例子確認我對題目的了解，

Input : s = [1,2,3,3,4,6], n=2
Output : s = [1,2,3,3,6] 

: 沒錯，請開始撰寫程式。

: 那我的想法是完整的走訪一次List，計算出list的長度，再用長度k減n得到m。在第二次走訪時，指標到達第m個字元，即可繞過要被刪除的字元 ，最終回傳head。

class Solution {
public : 
    ListNode * removeN( ListNode * head, int n)
    {
       ListNode *cur = head;
       int k=1;
       while( cur-> next )
           k++;
       int m= k-n;
       *cur = head;
       if(m==0)
           head = head->next;
       else
       {
           for( int i=1; i<m; i++)  //cur移動到要被刪除的前一個字元
               cur = cur->next;
           cur->next = cur->next->next;
       }
       return head;
    }
};

: 因為memory的空間很大，你的這個方法需要走訪2次這個list可能有點浪費時間，可以多加一點東西，壤整個刪除的過程中只要走訪一次list嗎?

: 好的那可能就需要2個指標，pre與cur，由cur先往前移動n個位置，如果cur已經是NULL，那表示要刪除的位置就是head。如果cur還不是NULL，將pre和cur同步往前，直到cur是List裡的最後一個元素為止，此時pre的位置是需要被刪除的前一個元素，更改指標繞過就完成了。

class Solution {
 public :
    ListNode * removeNthFromEnd(ListNode* head, int n) { 
        ListNode *pre = head, *cur = head;
         for ( int i = 0 ; i < n; i++) cur = cur-> next;
         if (!cur) return head-> next;  //如果cur已經是NULL，表示要刪除的是head
         while (cur-> next) {
            cur = cur-> next;
            pre = pre-> next;
        }
        pre ->next = pre->next-> next;
         return head;
    }
};

他評1

intervewer

• 優點
• 15:01 題目沒直接照leetcode念
• 可改進的地方
• 15:15 畫面會晃跟身體會晃動。
• 15:25 說話的語速稍慢，可能會拖到面試的速度。

intervewee

• 優點
• 16:35 口齒清晰，表達時較沒有陳詞贅字。
• 可改進的地方
• 16:11 聲音太小聲，背景雜音壓過說話的聲音。
• 21:40 說話的感覺有點不確定感，應該更自信的表達。

20. valid Parentheses (用英文)

影片: 29:00
模擬面試過程

: In logical reasoning and proofs, the symmetry of parentheses ensures the accuracy and rigor of logical expressions. So, please verify if a string is valid according to the following conditions:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

: So I need to check the symmetry of the parentheses. I would like to use an example to confirm if my understanding of the problem is correct.

(([]){}) is valid 
(([)]) is invalid  

: Yeah, please start writing the program.

My idea is to use a stack to store different types of brackets. When encountering a left bracket, it will be pushed into the stack. When encountering a right bracket, if the top of the stack contains the corresponding left bracket, then the string is valid up to this point, and the element can be popped from the stack. But, if the top of the stack does not contain the corresponding left bracket, or if the stack is already empty, then the string is invalid, and I can return false immediately. After reading all the elements, if the stack is empty, return true; otherwise, return false.

Solution 1

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;  //創建堆疊
        for(char i: s){
            if ( i == '(' || i == '[' || i == '{')
            {
                st.push(i);  //如果是左括號或堆疊為空，就加入堆疊
            }
            else if (i == ')' && st.top() == '(' || i == ']' && st.top() == '[' || 
                    i == '}' && st.top() == '{')
	          {
                st.pop();  //如果是右括號，比對相符就把堆疊最上層丟掉
            }
            else{
                return false; //如果皆非上述情形，表示括號非法，回傳flase
            }   
        }
        return st.empty();  //最後如果堆疊為空就回傳true
    }
};

: well, Can you define a map to help you determine whether the brackets are corresponding pairs?

: I define a map of closing brackets to their corresponding opening brankets, and check if the character is an opening brankets, if it's an opening bracket, push it into stack. If not, check whether tke stack is empty, or the corresponding opening bracket doesn't match the top of stack, can return false, otherwise, pop the stack. after check all character, if the stack is empty, return true, otherwise return false.

Solution 2: use map

class Solution
{
public:
    bool isValid(string s)
    {
        map<char, char> pair = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };

        stack<char> st;

        for ( i:s )
        {
            if (pair.find(i) == pair.end())
            {
                st.push( i );
            }
            else
            {
                if (st.empty() || st.top() != pair[i])
                    return false;
                st.pop();
            }
        }

        
        return st.empty();
    }
};

---

總體面試初步檢討

針對interviewer

1. interviewee完成程式碼之後，應該有後續的更多回應與提問討論，而不是直接結束或進行下一題。
2. 可以詢問時間複雜度 或是空間複雜度，執行過程中是否會用到額外的空間?
3. 可以在interviewee說明想法的過程中，詢問為何使用此解法? 考量的點是什麼?
4. 在撰寫程式的過程中也能適時打斷，請面試者做進一步的說明，eg. problem3 pair.end()的使用
5. 可以詢問極端狀況是否有考慮到，可以舉一個極端例子請interviewee說明程式會如何執行並且得到什麼結果。

針對interviewee

1. problem1 沒有舉例確認對題目的理解
2. 打code時很像在自言自語 不像是在向interviewer說明想法 且聲音會忽大忽小
3. 在程式時，應該重新寫一份或是複製後再修改，因為面試官可能會要求前後對照
4. p1 遞迴操作過程說明得不好
5. p3英文表達部分 大中小括號
6. 英文用字不夠精確與字彙量不足 character / element 字元/元素 和map的定義方式

第二次作業-他評 01

interviewee

• 優點
• 可改進的地方

• 1:20: 詢問限制時，"問"表達上可以更具體，引導面試官給出更多hint，比如「操作有可能受樹的大小或者結構的影響，這棵樹的深度是否有最大限制？」「翻轉操作的時間複雜度是否有要求？」
• 1:35: 只有一次討論，不知道詢問甚麼可以自己舉例跟面試官討論更多。開始說明解題的流程時可以畫圖，說明完再寫程式碼。
• 3:39: 可以邊畫圖，先撰寫class，說明大概流程，再寫struct。
• 3:57: 有說要達到的目標。在開始寫程式碼之前，應該對問題的背景進行更全面的說明，例如，「這個問題的目的是將樹的每一層結點左右翻轉，類似於將一個圖片進行鏡像翻轉。」
• 4:43: 說明為什麼要有這條件。「如果 root 是空的，表示到達了葉節點，因此需要返回NULL終止遞迴」
• 5:00: 說明為何要這麼做。「我接下來會先創建兩個暫存變數，保存左右子樹的指標。這樣做的目的是確保在之後的交換操作中，不會失去對原始子樹的參考。」
• 6:54: 可以回顧剛剛做了什麼，同時搭配圖。
• 7:32: 說明為何可以用heap結構。同樣，在說明做法時要畫圖較清楚，整個說明有一分多鐘，意識已經模糊。
• 15:52: 有舉例，說明"移動"的概念可以畫圖更多，滑鼠的呈現不比打字好。

interviewer

• 7:15: 可以請interviewer再重新說明一次剛剛寫的程式碼過程。再進入請interviewer Optimize的環節。
• 進行queue之前的實作，可以打岔問更多問題。
• interviewer在說明流程時，可以打岔問為何要這麼做，並且提問時間複雜度的問題。

他評 02

注意麥克風收音問題。

應徵者：

• 應充分想好再進行說明。
• 可以優先寫出重點程式碼的部分，抓住面試者的注意。
• 打字速度應提升，避免面試者等太久失去注意力。

面試者：

• 可以跟應徵者多討論一些問題，引導應徵者。

第二次作業-他評 03

interviewer

• 14:40 說明這邊其實可以利用google doc，面試官和面試者都可以在上面進行溝通

interviewee

• 可以加入適當的註解，方便理解
• 27:10 這邊雖然看似有在說明，但似乎更像是在喃喃自語，因為講的東西太細節細碎，應該要講重點

第二次作業-他評 04

• 有包裝題目
• 表達清楚，沒有過多的贅詞

interviewer

• 7:20 可以引導面試者分析程式碼的效率
• 14:45 可以引導面試者分析不同做法之間的差異

interviewee

• 1:40 只說明使用遞迴有點抽象，可以討論到細節的內容。
• 1:54 approach與面試官互相確認之後再實作會更好
• 16:17 講解approach可以搭配註解，會比較容易理解

第二次作業-他評 05

interviewer

• 1:31不用太快直接叫面試者馬上寫程式，還需要詢問對方初步實作方法以及對於這個題目還有什麼其他疑問
• 14:39可以詢問面試者比較兩個方法的差異

interviewee

• 4:10這邊寫程式的解說過程可以不用照打字一個一個慢慢念出來，例如可以改說"我建立一個invert function，input parameter會是樹的root"
• 12:12 "等於"這個說法不好，可以改成node變數被"賦值"為queue的最前端元素。
• 7:25可以在說明的同時使用文檔展現出來