Try   HackMD

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

貢獻者: 沙西米-Sashimi
模擬面試錄影: 1, 2, 3

👩‍🦰: interviewer
👶: interviewee

9. Palindrome Number

模擬面試過程

👩‍🦰: 同學妳好，希望妳能實作一個function，輸入一個整數後，判斷它是否屬於迴文數。
👩‍🦰: 對題目有什麼問題嗎?
👶: 請問迴數指的是正反兩面讀出來的數字都一樣嗎?
👩‍🦰: 是的。
👶: 那麼如果是負數的情況，需要將正負號考慮進去嗎?
👶: 舉例來說，如果

  1. Input: x = 121
    Output: true
    =>因為從左或是從右讀這個數字，它都是121
  2. Input: x = -121
    Output: false
    =>因為從左到右讀為121，從右到左讀為121-

👶: 請問我理解的正確嗎?
👩‍🦰: 正確。
👶: 請問整數的範圍是?
👩‍🦰:

−231 <= x <=
231−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

模擬面試過程

👩‍🦰: 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

模擬面試過程

👩‍🦰: 這裡想請妳用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, 1:07: 建議interviewer可以要求interviwee 先提出預計的作法或是構想，若是直接讓interviwee寫code ，interviwee不見得有想法或是不一定是正確的作法
  • 10:29, 10:46: interviewee完成後，interviewer可以給一些評論或是討論，讓interviewee知道自己是否正確或是有可以需要改進的地方。
  • 0:26: 如果直白地把題目闡述出來，加上有關鍵字"linked list","加法"，建議可以包裝成另一情境，避免出現背答案導致鑑別度不足，也可以考驗interviewee的理解能力和應變能力

關於interviewee

  • 優點
  • 對於針對題目的repeat 和 example很清楚詳細
  • 完成程式後有做test來驗證程式碼是對的
  • 可改進的地方
  • 3:12: 這一段停頓得比較久，可能可以說點什麼來避免對方失去興趣和專注

第二次作業 - 他評02

interviewer

  • 優點
  • 與面試者有很多互動，對於程式碼的改進有給予方向，而非直接說出有更佳的解法。
  • 咬字清晰
  • 可改進處
  • 建議結尾加上感謝面試者參加之類的話，讓面試有結束的感
  • (英) Merge Two List 應該是常見的題目，建議可以增加一些題目變形，例如改成 Merge K List；或是討論是否有優化的可能性。

interviewee

  • 優點
  • 一邊寫一邊講解。
  • 清楚確認題意與邊界條件，確認雙方理解沒有落差。
  • 可改進處
  • 2:27、(英)2:24 停頓有一點久，建議可以解釋目前在寫的程式。

第二次作業-他評03

關於interviewer

  • 優點
  • 說話清晰
  • 有針對 interviewee 的程式碼提出相關的問題
  • 可改進的地方
  • Merge Two List 還可以再做更深入的討論

關於interviewee

  • 優點
  • 有做 repeat 和 example 的動作，與 interviewer 確認題意
  • 6:53: 程式碼有用註解做解釋，讓 interviewer 更容易理解
  • 英語口說清晰
  • 可改進的地方
  • 4:22: 這邊說『我想一下』感覺很唐突
  • 2:25: 留白好多，可以講解一下正在寫的程式

第二次作業-他評04

關於interviewer

  • 優點
  • 不只以口頭說明的方式，以文件的方式給予題目。
  • 有以互動的方式引導改進程式碼。
  • 可改進的地方
  • 題目建議變形、包裝過更優，避免刷題目者。

關於interviewee

  • 優點
  • 提出「問題」順便舉例，並打出字說明自己的例子。
  • 最後有做到驗證測試部分
  • 可改進的地方
  • 提出程式碼想法、撰寫有口頭說明，卻沒有配合註解。

第二次作業 - 他評05

關於interviewer

  • 優點
  • 發音標準，咬字清晰，音量適當
  • 6:19: 要求interviewee利用trace證明程式碼，增加面試難度
  • 可改進的地方
  • 1:57：interviewer打錯字 constrains -> contraints

關於interviewee

  • 優點
  • 發音標準，咬字清晰，音量適當
  • 舉例充分，有考慮到 edge cases，值得嘉許
  • 可改進的地方
  • 0:19: 補上 Repeat 步驟，與面試官互動，確定題目要interviewee做什麼
  • 可以邊寫邊向interviewer解釋程式碼

第二次作業-他評06

Interviewer

  • 優點
  • 說明清晰
  • 可改進的地方
  • 面試官感覺有點冰冷
  • 題目可能要變形

Interviewee

  • 優點
  • 很確實的落實確認，很好的互動
  • coding過程的說明，很好避免尷尬
  • 咬字清晰
  • 驗證程式碼做的很確實
  • 可改進的地方
  • 感覺說明方和可以多點，多解釋下整體思路，不然直接進入coding可能跟不上

第二次作業-他評07

優點:
咬字清晰,說明速度適中
interviewer說明程式碼的部分蠻清楚的
interviewee有提出問題讓interviewer可以有很好討論問題的互動
缺點:
打程式的過程跟解釋可以更貼合,可以多練習在解釋的同時一步一步地把程式碼順便就打出來

Last changed by 
 
sysprog
System Software Programming
0
665

Read more

從 CPU cache coherence 談 Linux spinlock 可擴展能力議題

本文探討 spinlock 本身的效能和可擴展能力 (scalability) 議題

Jun 4, 2025
淺談 Microkernel 設計和真實世界中的應用

本講座則是專注於作業系統領域，同時，&quot;Microkernel&quot; 也不全然指其 &quot;micro&quot; 微小之意，而且是探討相對於傳統 Monolithic kernel 的 Microkernel

Jun 3, 2025
並行程式設計: 概念

解說錄影: Part 1 / Part 2 / Part 3 / Part 4 / Part 5/ Part 6 / Part 7

May 30, 2025
並行程式設計: Lock-Free Programming

許多文件、程式碼和技術討論會看到 lock-free 和 lockless 字眼，例如 DPDK Programmer’s Guide 就在一份文件中存在上述二個術語。二者的差異是什麼呢？

May 30, 2025
Read more from sysprog
Published on HackMD