# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者: 沙西米-Sashimi
> 模擬面試錄影: [1](https://www.youtube.com/watch?v=LaV81zs_EM0), [2](https://www.youtube.com/watch?v=ohBt69LbsrY), [3](https://www.youtube.com/watch?v=3IrwM1HSLoI)
>
> 👩‍🦰: interviewer
> 👶: interviewee

## [9. Palindrome Number](https://leetcode.com/problems/palindrome-number/)
### **模擬面試過程**
👩‍🦰: 同學妳好，希望妳能實作一個function，輸入一個整數後，判斷它是否屬於迴文數。
👩‍🦰: 對題目有什麼問題嗎?
👶: 請問迴數指的是正反兩面讀出來的數字都一樣嗎?
👩‍🦰: 是的。
👶: 那麼如果是負數的情況，需要將正負號考慮進去嗎?
👶: 舉例來說，如果
1. Input: x = 121
Output: true
=>因為從左或是從右讀這個數字，它都是121
2. Input: x = -121
Output: false
=>因為從左到右讀為121，從右到左讀為121-

👶: 請問我理解的正確嗎?
👩‍🦰: 正確。
👶: 請問整數的範圍是?
👩‍🦰: $-2^{31}$ <= x <= $2^{31}-1$，可以開始寫程式了。
👶: 在開始寫程式之前，我想先說一下我的想法。
👶: 我目前直觀的想法是先將整數轉換為字串，在字串頭尾各設一個指標，相互比對，如果相同就向中間位置靠近。
👩‍🦰: 好的，請開始實作。
👶:

bool isPalindrome(int x) {
      string num = to_string(x);
      int left = 0;
      int right = num.length()-1;  

      while(left < right){
          if(num[left] != num[right]){
            return false;
          }
          left++;
          right--;
      }
      
      return true;
    }

👩‍🦰: 使用整數轉換字串確實可以解決我們的問題，但是使用字串花費的記憶體比整數大很多，是否有更好的作法?
👶: 嗯...好的，我想一下...
👶: 如果將題目給的整數拆成兩個部分，反轉其中一個部分，再比較兩個部分是否相等，這個思路是否能節省更多記憶體?
👩‍🦰: 可以從這個方向寫看看。
👶: 好的。

    bool isPalindrome(int x) {     
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
        
        //反轉後半段
        int rev = 0;
        while (x > rev) {
            rev = rev * 10 + x % 10;
            x /= 10;
        }

        // 當x為奇數位數時，去掉反轉後的最後一位
        return x == rev || x == rev / 10;
    }

## **初步檢討**
可以改進的地方:
1. interviewer可以再多引導interviewee進行更深悟的討論。
2. 思考的時候不用說"我想一下"。

## [21. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/description/)
### **模擬面試過程**

👩‍🦰: In this question, you are given the heads of two sorted linked lists list1 and list2.
👩‍🦰: You need to merge the two lists into one sorted list.
👩‍🦰: The list should be made by splicing together the nodes of the first two lists.
👶: Okay, I would like to use an example to explain my thought about this question.
👶: If there are two inputs: list1 and list2

input:
list1 = [1,2,4]  list2=[1,3,4]

output:
[1,1,2,3,4,4]

👶: Am I correct?
👩‍🦰: Right. You can start coding.
👶: Before coding, I would like to explain my approach about this question.
👶: I will compare the first elements in list1 and list2. If the one in list1 is smaller than the one in list2, and then I will put the first element in list1 into the output list.
👶: Then compare the second elements in list1 and the first elements in list2. Put the smaller on into the output list, vice versa.
👶: If both elements are equal, and then put them into the output list.
👶: I'm curious about if there is a limit on number of elements in lists?
👩‍🦰: It's from 0 to 50. You can start coding.
👶: I create a dummy node to point to the head of the output list.

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;
    
}

👶: Compare the elements of both lists, and put the smaller one into the output list.

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;
    
    while (list1 != NULL && list2 != NULL) {
            if (list1->val < list2->val) {
                current->next = list1;
                list1 = list1->next;
            } else {
                current->next = list2;
                list2 = list2->next;
            }
            current = current->next;
    }
    
    return dummy->next;
}

👩‍🦰: Okay now, please do a trace to see if it works, just take the example upside.
👶: Well, there is a problem, when the list2 is point to NULL, list1 is still point to the node with 4 inside.
👶: There is no way to do the comparison between NULL and 4.
👩‍🦰: Also, if the number of elements of both lists are different. How do you change your code?
👶: Okay, um... If one list is over, and then directly connect the other list to the end of output list.
👶:

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;
    
    while (list1 != NULL && list2 != NULL) {
            if (list1->val < list2->val) {
                current->next = list1;
                list1 = list1->next;
            } 
            else {
                current->next = list2;
                list2 = list2->next;
            }
            current = current->next;
    }
    
    if (list1 != NULL) {
        current->next = list1;
    } 
    else {
        current->next = list2;
    }

        return dummy->next;
}

## **初步檢討**

可以改進的地方:
1. 可以對演算法做更深入的討論。
2. interviewee說話的音量可以更穩定一些，會忽大忽小。

## [2. Add Two Numbers](https://leetcode.com/problems/add-two-numbers/)
### **模擬面試過程**
👩‍🦰: 這裡想請妳用linked list實作看看加法。
👩‍🦰: 首先，會給你兩個用來表示非負整數的non-empty的linked list，這些整數以相反的順序儲存，將兩個數相加，以linked list的形式回傳總和。
👶: 我想說一下我對題目的理解:
👶: 舉例來說

243 + 576
=> 3->4->2
   6->7->5
------------
   9->1->8 
Output = [8,1,9]

👩‍🦰: output的部分維持相反的順序儲存，因此需要進行修改。
👶: 所以應該是

Output = [9,1,8]

👩‍🦰: 是的，可以開始寫程式了。
👶: 在開始寫程式之前，我想先說明一下我的實作方案。
👶: 因為linked list是以相反的方式儲存，因此由head開始向後的順序，也代表個是百千的順序。
👶: 我會從兩個linked list的第一個element開始相加，並給定一個紀錄進位的變數carry，依序向後進行運算，每完成一位數，就在output list中添加一個新的node，直到計算完成。
👩‍🦰: 聽起來沒問題，可以開始實作了。
👶:

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;
    int carry = 0; 

    while (l1 != NULL) {
        int x = l1->val;
        int y = l2->val;
        int sum = x + y + carry;

        carry = sum / 10;
        current->next = new ListNode(sum % 10); 
        current = current->next;

        if (l1 != NULL){
            l1 = l1->next;
            l2 = l2->next;
        } 
    }

    if (carry > 0) {
        current->next = new ListNode(carry);
    }

    return dummy->next;
}

👩‍🦰: 妳現在的function是假設兩個list的長度相同，但是在進行加法時，相加的兩個數未必都是相同的位數，請針對這個部分進行修改。
👶: 好的。

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode* dummy = new ListNode(0); 
    ListNode* current = dummy;
    int carry = 0; 

    while (l1 != NULL || l2 != NULL) {
        int x = (l1 != NULL) ? l1->val : 0;
        int y = (l2 != NULL) ? l2->val : 0;
        int sum = x + y + carry;

        carry = sum / 10; 
        current->next = new ListNode(sum % 10); 
        current = current->next;

        if (l1 != NULL) l1 = l1->next;
        if (l2 != NULL) l2 = l2->next;
    }

    if (carry > 0) {
        current->next = new ListNode(carry);
    }

    return dummy->next;
    }

## **初步檢討**

可以改進的地方:
1. 可以對演算法做更深入的討論。
2. interviewee打code時，說話給人聽起來有種不確定的感覺。

---

## 第二次作業-他評01
### 關於interviewer
- [ ] 優點
* 很清楚的闡述interviwee的作法有什麼缺點(例如使用太大的記憶體或linked list 長度可能不一致)，而不是單純評論"好"或"不好"，也可以讓interviwee知道哪裡可以改
* 語速適中，英文發音也很清楚
* 有提出更進一步的問題要求interviewee現場解決(第二題)

- [ ] 可改進的地方
* [1:31](https://youtu.be/LaV81zs_EM0?si=RRo2kYIO657GKfus&t=91), [1:07](https://youtu.be/ohBt69LbsrY?si=dAR7MCm27qU_IqT_&t=67): 建議interviewer可以要求interviwee 先提出預計的作法或是構想，若是直接讓interviwee寫code ，interviwee不見得有想法或是不一定是正確的作法
* [10:29](https://youtu.be/LaV81zs_EM0?si=xYCnj9n3waAQi6qc&t=629), [10:46](https://youtu.be/ohBt69LbsrY?si=feCPyjcaxKay9utw&t=646): interviewee完成後，interviewer可以給一些評論或是討論，讓interviewee知道自己是否正確或是有可以需要改進的地方。
* [0:26](https://youtu.be/3IrwM1HSLoI?si=tyEXrtLgk5B-T7x9&t=26): 如果直白地把題目闡述出來，加上有關鍵字"linked list","加法"，建議可以包裝成另一情境，避免出現背答案導致鑑別度不足，也可以考驗interviewee的理解能力和應變能力

### 關於interviewee
- [ ] 優點
* 對於針對題目的repeat 和 example很清楚詳細
* 完成程式後有做test來驗證程式碼是對的

- [ ] 可改進的地方
* [3:12](https://youtu.be/ohBt69LbsrY?si=qQRWaIQm0GuxOCtK&t=192): 這一段停頓得比較久，可能可以說點什麼來避免對方失去興趣和專注

## 第二次作業 - 他評02
### interviewer
- [ ] 優點
* 與面試者有很多互動，對於程式碼的改進有給予方向，而非直接說出有更佳的解法。
* 咬字清晰

- [ ] 可改進處
* 建議結尾加上感謝面試者參加之類的話，讓面試有結束的感
* (英) Merge Two List 應該是常見的題目，建議可以增加一些題目變形，例如改成 Merge K List；或是討論是否有優化的可能性。

### interviewee
- [ ] 優點
* 一邊寫一邊講解。
* 清楚確認題意與邊界條件，確認雙方理解沒有落差。

- [ ] 可改進處
* [2:27](https://youtu.be/3IrwM1HSLoI?si=Nu18Q2xsbKHBrYUZ&t=147)、[(英)2:24](https://youtu.be/ohBt69LbsrY?si=QFbWTlGGv-8IyI1l&t=144) 停頓有一點久，建議可以解釋目前在寫的程式。

## 第二次作業-他評03
### 關於interviewer
- [ ] 優點
* 說話清晰
* 有針對 interviewee 的程式碼提出相關的問題

- [ ] 可改進的地方
* Merge Two List 還可以再做更深入的討論

### 關於interviewee
- [ ] 優點
* 有做 repeat 和 example 的動作，與 interviewer 確認題意
* [6:53](https://youtu.be/ohBt69LbsrY?si=nHetM9Jo-3-HPj27&t=413): 程式碼有用註解做解釋，讓 interviewer 更容易理解
* 英語口說清晰

- [ ] 可改進的地方
* [4:22](https://youtu.be/LaV81zs_EM0?si=DWGCqUZyO8GD69KN&t=262): 這邊說『我想一下』感覺很唐突
* [2:25](https://youtu.be/ohBt69LbsrY?si=m6PqVVR_c-x_a9Mq&t=145): 留白好多，可以講解一下正在寫的程式

## 第二次作業-他評04
### 關於interviewer
- [ ] 優點
* 不只以口頭說明的方式，以文件的方式給予題目。
* 有以互動的方式引導改進程式碼。

- [ ] 可改進的地方
* 題目建議變形、包裝過更優，避免刷題目者。

### 關於interviewee
- [ ] 優點
* 提出「問題」順便舉例，並打出字說明自己的例子。
* 最後有做到驗證測試部分

- [ ] 可改進的地方
* 提出程式碼想法、撰寫有口頭說明，卻沒有配合註解。

## 第二次作業 - 他評05
### 關於interviewer
- [ ] 優點
* 發音標準，咬字清晰，音量適當
* [6:19](https://www.youtube.com/watch?v=ohBt69LbsrY&t=379): 要求interviewee利用trace證明程式碼，增加面試難度

- [ ] 可改進的地方
* [1:57](https://www.youtube.com/watch?v=ohBt69LbsrY&t=117)：interviewer打錯字 constrains -> contraints

### 關於interviewee
- [ ] 優點
* 發音標準，咬字清晰，音量適當
* 舉例充分，有考慮到 edge cases，值得嘉許

- [ ] 可改進的地方
* [0:19](https://www.youtube.com/watch?v=ohBt69LbsrY&t=19): 補上 Repeat 步驟，與面試官互動，確定題目要interviewee做什麼
* 可以邊寫邊向interviewer解釋程式碼

## 第二次作業-他評06
### Interviewer
- [ ] 優點
* 說明清晰

- [ ] 可改進的地方
* 面試官感覺有點冰冷
* 題目可能要變形

### Interviewee
- [ ] 優點
* 很確實的落實確認，很好的互動
* coding過程的說明，很好避免尷尬
* 咬字清晰
* 驗證程式碼做的很確實

- [ ] 可改進的地方
* 感覺說明方和可以多點，多解釋下整體思路，不然直接進入coding可能跟不上
## 第二次作業-他評07
優點:
咬字清晰,說明速度適中
interviewer說明程式碼的部分蠻清楚的
interviewee有提出問題讓interviewer可以有很好討論問題的互動
缺點:
打程式的過程跟解釋可以更貼合,可以多練習在解釋的同時一步一步地把程式碼順便就打出來