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

貢獻者: 登革熱-Moss
video1, video2, video3

🧔：interviewer 👶：interviewee

第一次作業

21. Merge Two Sorted Lists

video

題目描述

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

程式碼解說

方案一 : Iterative

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy(0);
        ListNode* tail=&dummy;
        while(list1 && list2) {
            if(list1->val < list2->val) {
                tail->next=list1;
                list1=list1->next;
            }else{
                tail->next=list2;
                list2=list2->next;
            }
            tail=tail->next;
        }
        
        if(list1) tail->next = list1;
        if(list2) tail->next = list2;
        
        return dummy.next;
    }
};

方案二 : Recursive

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // If one of the list is emptry, return the other one.
        if(!list1 || !list2){ return list1 ? list1 : list2;}
        // The smaller one becomes the head.
        if(list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

面試過程檢討

Interviewer

Interviewee

---

1. Two Sum

video

題目描述

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

程式碼解說

方案一 : 暴力解

雙迴圈，暴力枚舉

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i = 0; i<nums.size();++i){
            for(int j =i+1; j<nums.size();++j){
                int sum = nums[i]+nums[j];
                if(sum == target){
                    return {i,j};
                }
            }
        }
        return {};
    }
};

方案二 : Hash Table

宣告一個 Hash Table(mp) 來儲存目前查看過的數字
（以數字作為 Key、數字所在的 Index 作為 Value）

對於每個數字 nums[i] 來說，其要找到對應的數為 left = target - nums[i]。

找到 left on mp，並且 left index != i

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp;
        for(int i = 0; i<nums.size();++i){
            mp[nums[i]] = i;
        }
        for(int i = 0; i< nums.size();++i){
            int left = target - nums[i];
            if(mp.count(left) && mp[left] != i){
                return {i,mp[left]};

            }
        }
        return {};
    }
};

面試過程檢討

Interviewer

Interviewee

15. 3Sum

video

題目描述

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

程式碼解說

方案一 : Two Pointers

如果nums[i] + nums[left] + nums[right] > 0，則right- -，右邊界往左移動
如果nums[i] + nums[left] + nums[right] < 0，則left++，左邊界往右移動
如果等於0，先儲存答案，然後left++，right- -，然後往中間檢查，跳過與加入答案的左右邊界數字相同的數字。

EX:

當i = 0，left = 1，right = 7，加入答案之後，left右移動一格，right左移動一格。
檢查nums[2] == nums[1] ?
檢查nums[7] == nums[6] ?

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(begin(nums), end(nums));
        const int n = nums.size();
        vector<vector<int>> ans;
        
        for(int i = 0; i< n; ++i){
            int left = i + 1;
            int right = n - 1;

            if(i != 0 && nums[i] == nums[i-1]){
                continue;
            }
            while(left < right){
                if(nums[i] + nums[left] + nums[right] == 0){
                    ans.push_back({nums[i], nums[left], nums[right]});
                    ++left;
                    --right;
                    while(left < right && nums[left] == nums[left-1]){left++;}
                    while(left< right && nums[right] == nums[right+1]){right--;}
                }else if(nums[i] + nums[left]+ nums[right]> 0){
                    right--;
                    }
                else{left++;}
            }
        }
        return ans;
    }
};

面試過程檢討

Interviewer

Interviewee

---

第二次作業 - 他評01{21. Merge Two Sorted Lists}

優點

• 提出兩種方法。

可改進的地方

• 沒有討論兩種方法的差別。

第二次作業 - 他評02{1. Two Sum}

優點

• 提出兩種方法。

可改進的地方

• 0:14: int要講成整數。(英文的話也要講integer)
• 0:39: 突然冒出「可以回傳[0,1]或[1,0]」會讓人一頭霧水。

第二次作業 - 他評03{15. 3Sum}

優點

• 3:10: 提到三種方法。

可改進的地方

• 0:33, 4:20, 11:25: 游標一直晃動。
• 18:05: 沒有提到實際的空間複雜度，也沒有Hash table的後續討論就結束了。

---

• 有很酷的筆記畫圖功能。
• 用VS Code有自動補全功能。
• 很多英文穿插，盡量都用中文說明。

第二次作業 - 他評04

interviewer

優點：

• 口條清晰，語速正常

可改進:

• interviewer應該要與interviewee有更多的交叉問答，以瞭解interviewee的想法
• 可以多一些漸進式的引導interviewee作答

interviewee

優點：

• 每個題目都有提出多種做法
• 有註解，使程式碼更容易理解
• 有畫圖解釋，使人更容易理解

可改進:

• 0:46,0:52有時會忽然中英交叉回答，會很突兀
• 應用docs而不是用編輯器，實際面對面面試時只會有紙和筆

第二次作業 - 評論別人

https://hackmd.io/2W0cu9uFS8udA3Jw4zL9Gw?both

• 或許可以嘗試直接當場修改題目，畢竟interviewee在寫題時，應該很容易忘記: 377, 1:13。
• 對題目描述不全的地方有提出質疑，像是377這題。
• 因為少了真實的test，所以有些細節上的失誤，像是377這題，在for loop 裡的 i 沒有寫到，變成{int = 1}。

https://hackmd.io/py_SEUfHQ0mzy_lcdaZSOQ?both

• 題目可以給一些example input output，會比較清楚。
• 可能需要先介紹何謂補數4:36。

https://hackmd.io/aicvazYpQH-Q-zCH_T8Z0g?both

• 應該把題目寫出來，而不是只是口頭講，會比較好。
• 事先或許可以主動給出example，再由interviewee考慮特殊input來補充。
• 最後的Test或許可以直接給example input，Run code或者人體compiler。

https://hackmd.io/SCeR9_shR1iwH1SXE0Y_AA?both

• 打code時的講解，蠻流暢的。
• cnode和nnode的命名或許可以更一目瞭然32:29，也可以嘗試在旁邊寫註解，尤其是cnode聽不太清楚。

https://hackmd.io/UrRh28LzRL25e7wdcT5oiA?both

• 有討論到用途9:57。
• 太多 那…。
• 建議先把example寫下來，會比較清楚3:21。

第二次作業 - Two Sum (漢)

---

第四次作業-他人評論-01

• Interviewer：
  • 優點：
    • 口條清晰，此時立即切入正題，解釋題目也相當完整。
    • 面試官所出題目有做適度的變形，此時顯得生動有趣。
  • 缺點：
    • 由於現場只有面試官及面試者兩人，面試官沒有必要在每一句話的前面都尊稱對方為「登革熱先生」，顯得有點距離感。此時、此時、此時、此時、此時。
• Interviewee：
  • 優點：
    • 針對題目不解的地方主動向面試官提問及釐清，此時顯示面試者有掌握到脈絡並在認真思考。
    • 此時面試者在實作程式碼的過程中加上註解，除了加強雙方溝通的效率，也方便自己稍後回顧程式碼。
    • 面試者很有禮貌，每次對答都會附上一句「謝謝面試官」。此時、此時、此時、此時。
  • 缺點：
    • 面試者此時不需要揭露自己使用「暴力法」，可以說是「最為直覺的方法」。
• 其他意見：
  • 建議調整面試官及面試者在畫面中的位置，有時候難以迅速察覺角色交換，如此時。
  • 建議面試時使用 CodeShare 或其他 IDE 進行程式碼實作，此時則不必擔心縮排問題。

---