2021 年「資訊科技產業專案設計」面試範例

貢獻者: 菜雞-Newbie
video

🧔：interviewer 👶：interviewee

自評-程式部分

• 善用程式碼註解，可幫助自己整理 solution 的架構，也可以幫助面試官理解我的解法
  • 缺點: 太多程式碼註解反而會降低程式可讀性，應斟酌之間的平衡
• 注意 可讀性vs程式簡潔度 之間的取捨

自評-面試過程

• 避免思考過程停頓過久，不要讓雙方同時沉默
  • Think out loud: 盡量把自己在思考的東西講出來，讓面試官也知道你目前在思考甚麼，避免自己鬼打牆，也許面試官會主動給幫助
• 要確定把所有解法細節想仔細再開始動手寫，動手寫之後才把一開始口頭說明漏掉的部分補上可能不太好
  • 雖然一個好的面試官會確定自己理解了 interviewee 的解法並且認為可行才會叫我開始寫 code，任何不清楚的部分面試官應該會在這階段跟 interviewee 討論，但這部分要自己盡量做好
• 在 REACTO 的 A，可以考慮用範例 test case 輔助解釋
• 加強英文口說流暢度

自評-嘗試改進部分

• 在解釋想法的時候盡量精簡講重點，避免冗言贅字，在寫程式時也是(雖然實際面試的時候很困難)
• 多考慮 edge case，在一開始敘述解法的時候就該想到，程式寫完要測試時也要考靠 edge case
• 適度略過細節
• 若程式碼雜亂，Interviewer 可詢問是否能寫得更乾淨，Interviewee 也應主動提出整理程式碼(但不要花太多時間)
• Interviewer 若發現錯誤應立即點出
• 在 walk through example 時應用打字打出來
• 提出改進方法後不要馬上實作，要先和 interviewer 討論
• 若題目有 complexity 限制，在解釋 approach 時也該提到為何會滿足限制

自評-註記

• 第一題的 merge two sorted list 和 follow-up 的 merge k sorted list 是小弟面試 Intel 的原題，後續也有成功拿到 offer。因為面試時在我提出延伸題的 optimal solution 之後 interviewer 就沒有要求我要寫出來了，因此這次作業也只有錄到提出 follow-up 的想法而已，根據小弟的面試經驗，多數面試大多會停在提出延伸題的改進方法那邊，很少最後會要求把延伸題的 code 也寫出來

自評-程式部分

• 可以試著更模組化自己的解答，可以幫助自己將麻煩的細節擺到最後甚至不寫
• 視情況，盡量不要用 auto，用了也要知道原本的資料型態應是甚麼，曾在 Skymizer 的面試被建議把 auto 改掉

自評-面試過程

• 自己主動講複雜度和帶例子測試
  • 優點: 讓面試官感覺到我自己會注意這些東西，不需要引導
  • 缺點: 面試官也許比較想知道 optimization，但若我們主動花時間在他不在意的東西上，反而會無法讓面試官引導到聽到他在意的東西
• 善用 filler word 像是 ummm, uhhh
  • 優點: 可以避免雙方對話空白，幫自己爭取思考時間
  • 缺點: 使用太多會讓人厭煩
• 嚴謹的測試很花時間，但又不應該花太多時間在測試，重點應在 problem solving 能力，要注意 test 的重要程度跟解題之間的平衡
• 英文口說還是會有口齒不清的部分，或是無意識的發音不標準 (降低緊張感可改善，需大量練習)
• 遇到真的短時間想不出來的情況，可以提前告知 interviewer 我會安靜一兩分鐘思考
• 多練習 think out loud，爭取讓 interviewer unblock 自己的機會

21. Merge Two Sorted Lists

00:01

參考實作:

struct ListNode *mergeTwoLists(struct ListNode *L1,
                               struct ListNode *L2){    
    struct ListNode *head;
    struct ListNode **ptr = &head;
    for (; L1 && L2; ptr = &(*ptr)->next) {
        if (L1->val < L2->val) {
            *ptr = L1;
            L1 = L1->next;
        } else {
            *ptr = L2;
            L2 = L2->next;
        }
    }
    *ptr = (uintptr_t) L1 | (uintptr_t) L2;
    return head;
}

解說: 你所不知道的 C 語言: linked list 和非連續記憶體操作

56. Merge Intervals

21:03

進行 REACTO 步驟時，可先說直覺的想法，例如:

A naive approach is to start from the first interval and compare it with all other intervals for overlapping …
However, the above naive algorithms suffers from performance problem because it can not be implemented in better than

$O(n^2)$ time.

接著才是構思:

An efficient approach is to sort the intervals according to the starting time in advance. Once we have the sorted intervals, we can combine all intervals in a linear traversal.

清楚標註步驟:

1. Sort the intervals based on increasing order of starting time.
2. Push the first interval on to a stack.
3. For each interval, …
4. At the end stack contains the merged intervals.

改進方案:

The above solution requires

$O(n)$ extra space for the stack. We can avoid the use of extra space by doing merge operations in-place.
Here are the proposed steps:

1. Sort all intervals in increasing order of start time.
2. Traverse sorted intervals starting from first interval, do following for every interval.
   a. If current interval is not first interval and it overlaps with previous interval, then merge it with previous interval. Keep doing it while the interval overlaps with the previous one.
   b. Else, add current interval to output list of intervals.

延伸閱讀:

• Merge Intervals
• Merge Intervals

參考 C 程式碼實作:

static int compare(const void *a, const void *b)
{
    return ((int *) a)[0] - ((int *) b)[0];
}

int **merge(int **intervals,
            int intervalsSize,
            int *intervalsColSize,
            int *returnSize,
            int **returnColumnSizes)
{   
    if (intervalsSize == 0) {
        *returnSize = 0;
        return intervals;
    }
    
    int len = 0;
    int *tmp = malloc(intervalsSize * 2 * sizeof(int));
    for (int i = 0; i < intervalsSize; i++) {
        tmp[i * 2] = intervals[i][0];
        tmp[i * 2 + 1] = intervals[i][1];
    }
    qsort(tmp, intervalsSize, 2 * sizeof(int), compare);
    
    intervals[0][0] = tmp[0];
    intervals[0][1] = tmp[1];
    for (int i = 1; i < intervalsSize; i++) {
        if (tmp[i * 2] > intervals[len][1]) {
            len++;
            intervals[len][0] = tmp[i * 2]; 
            intervals[len][1] = tmp[i * 2 + 1];
        } else if (tmp[i * 2 + 1] > intervals[len][1]) {
            /* merge this interval */ 
            intervals[len][1] = tmp[i * 2 + 1];
        }
    }
    
    len += 1;
    *returnSize = len; 
    *returnColumnSizes = malloc(len * sizeof(int));
    for (int i = 0; i < len; i++) 
        (*returnColumnSizes)[i] = 2;
    
    return intervals;
}

---

第三次作業 - 他評01

• 私心覺得是目前作業區公佈的影片中最好的，也是對答最流暢的。
• 小建議：如果是用 OBS 的話，可以把 interviewer 跟 interviewee 放在一左一右輪流錄影，這樣可以少掉上字幕的功夫。

針對 interviewer 的檢討:

interviewer 的問題比較聚焦在演算法的部份，可以變化一下題目。

影片細節

• 16:15~21:00 有拍出自己的面試經驗

針對 interviewee 的檢討:

應用 Google docs 而不是用編輯器
字體需要放大
實作速度快
需要減少 filter words

影片細節

• 04:10 在函數中加入註解，一方面可以再寫程式的時候做為提示，另一方面也可以讓 interviewer 知道你每一步驟會做什麼
• 05:36 建議在 coding 的時候可以說明一下 l1 = l1->next 跟 head = head->next 的意義而不是照唸，像是打完 head->next = l1 時，邊打 l1 = l1->next 邊講因為還要繼續合併 l1 剩下的節點，所以要將 l1 移動到 next。儘量用表達含意取代照唸程式碼。
• 06:34 沒有解釋為何 return sentinel->next

第三次作業 - 他評02

interviewee 優點

• REACTO 都有做到並很清楚，尤其是在 follow up 的問題中也有做出。
• 註解很清楚，讓程式碼很容易理解。
• 程式碼有簡化過，如第一題回傳的 sentinel->next，讓一開始的 linked list 不用初始化。

interviewer 優點

• 問題定義明確且易理解

interviewer 可改進的地方

• 可以搭配實際問題來詢問 interviewee，讓問題不要一開始就太明顯。