---
title: 2021 年資訊科技產業專案設計課程面試範例
tags: INFO2021
---

# 2021 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2021)」面試範例

> 貢獻者: 齋羅 Zxiro
> ==[video](https://youtu.be/FXDG-o1K768)==

A：interviewer B：interviewee
## 預計改進內容
* 詢問是否考慮到極端案例
* 適時打斷來對做法進行改進
* 說明題意至少舉一案例說明
* 檢討作答程式碼變數命名以及極端案例
* 減少手勢改用打字呈現說明
* LC #643 阻止過於複雜的解法以及解釋優化後作法
* LC #56 新增圖示案例並提升流暢度

## [Easy 643. Maximum Average Subarray I](https://leetcode.com/problems/maximum-average-subarray-i/)
A: 在第二題你會獲得一個整數陣列 nums 以及一個正整數 k，我需要你在 nums 中找出長度為 k 的子陣列，該子陣列必須要為連續且陣列中元素加總除上 k 的數值要為所有子陣列中最大，最後回傳該值
B: 聽完題目敘述後，(自行建立一陣列 nums 以及 k 進行案例演示)我會採用兩個迴圈來獲得並計算子陣列及其值，之後宣告一變數 max 來做為比較
B: 首先我將 max 定義為 -DBL_MAX，此代表為 C++ 中所能表達的最小浮點數變數，考量到整數陣列的值可能存在正負，所以我並未以 0 初始化。
A: 好，我想先請問你預計這樣的時間複雜度為何?
B: 這樣的時間複雜度為 $O(n^{2})$
A: 你認為這種方式會有存在哪些可能問題?
B: 如果在處理長陣列以及 K 值很大的時候就會造成運行效率不佳
A: 是，那我希望你能夠提出計算效率更好的方式。提示來說，因為是要找最大的子陣列平均值，或許可以往只有一個子陣列，該子陣列與陣列的元素關係操作來想。
B: 好，那我會初始化一個子陣列後，在他往下個元素執行只需要加上新值後減掉最早的值後就是新子陣列的平均值(此時以數字以及中括號來演示作法)。這樣只需要一個迴圈來執行，不需要原本方式的雙重迴圈，減少每個子陣列重新加總的計算量。
B: 第一個迴圈會整理出第一個子陣列後，下個迴圈會將上一子陣列的值加上下一個元素的值並扣除上一子陣列的第一個值，想像為一個窗口往右滑動。
B: 這樣的複雜度就能降為 $O(n)$
A: 為何你會認為這樣做是可行的?
B: 因為題意要求子陣列，為連續的資料結構，因此可以用固定陣列滑動的想法進行。

double findMaxAverage(vector<int>& nums, int k) {
        vector<int> sub;
        double res=0;
        for(int i=0; i<k; i++){
            sub.push_back(nums[i]);
            res += nums[i];
        }
        double tmp = res;
        for(int j=k; j<nums.size(); j++){
            tmp -= sub[j-k];
            tmp += nums[j];
            sub.push_back(nums[j]);
            if(tmp>=res){
                res = tmp;
            }
            continue;
        }
        return res/k;
    }

## [Medium 56. Merge Intervals](https://leetcode.com/problems/merge-intervals/)
A: 好的，最後一題會傳入一二維陣列，裡面元素代表一區間的開始與結束，其中結束數字會大於等於開始數字，你要將所有重疊的區間合併後回傳一個沒有重疊的區間陣列。
B: 我想請問兩個區間的端點相同算是重疊嗎?
A: 是，例如 [2, 5], [5, 10] 這兩個區間是重疊的
B: (自行建立一陣列 intervals 後展示答案)
B: 好的，因為兩個區間重疊的可能有很多種，在與一區間比較時可能會有前面或後面的重疊情況。我想先透過簡單化可能來避免窮舉的解法。
B: 因此，我會先將區間的開始數字排序後再進行，如圖
B: 這樣我只需要比較下個陣列的起始位置就能知道有沒有重疊
B: 我會透過迴圈來遍歷二維陣列，從頭開始與下一個區間檢查是否重疊。
B: 這樣的複雜度因為只有次數為 intervals.size() - 1 的迴圈所以為 $O(n)$

vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> res;
        vector<int> tmp;
        tmp = intervals[0];
        for(int i=1; i<intervals.size(); i++){
            if(tmp[1] >= intervals[i][0]){
                if(tmp[1] <= intervals[i][1]){
                    tmp = {tmp[0], intervals[i][1]};
                }
            }
            else{
                 res.push_back(tmp);
                 tmp = intervals[i];
            }
        }
        res.push_back(tmp);
        return res;
    }

----
## 第三次作業-他評01
### Interviewer
#### 優點
題目說明得很清楚

#### 可改進
題目或許可用現實會遇到的狀況包裝。
缺少與interviewee的互動，包括在對方實作前確認想法。

### Interviewee
#### 優點
回答時會先舉出清楚的例子，且可以邊進行說明邊coding。
#### 可改進
整體花費時間略長。

## 第三次作業-他評02
### 優點
* 撰寫程式碼時有清楚講解

### 缺點
* 沒有 REACTO 中的 TEST

### 細節
* [2:05](https://youtu.be/FXDG-o1K768?t=125) Array 譯作陣列，而非矩陣
* [4:05](https://youtu.be/FXDG-o1K768?t=242) 何謂「不好」，可以直接提出改進空間
* [5:01](https://youtu.be/FXDG-o1K768?t=300) 沒有說明這樣寫為甚麼會得到答案
* [5:42](https://youtu.be/FXDG-o1K768?t=342) 程式碼混合多個語言的寫法
* [16:18](https://youtu.be/FXDG-o1K768?t=978) 用手勢表達比較難理解，可以用 Google Docs 描述想法
* [26:30](https://youtu.be/FXDG-o1K768?t=1590) 說明太冗長，提出 sorting 想法後說明實作概念即可，interviewer 如有不懂會自己提出
* [34:35](https://youtu.be/FXDG-o1K768?t=2075) 例子可以留著參考

## 第三次作業-他評03
整體問題:
1. 聲音太小
2. Interviewee 在撰寫時應注意程式的可讀性。

第一題:
1. Interviewee 回答問題時不要中英夾雜。
2. Interviewee 變量命名時如果要用 node a 當變量的名稱，應該使用 `nodeA` 或 `node_a`而不是`nodea`。
3. Interviewer 沒有根據這一題做出具體評價與互動，應該講出不錯是哪裡不錯。

第二題:
1. Interviewer 直接給題目，容易讓背答案的人混水摸魚。
2. 不要用反白或是游標位置去進行講解，Google meeting 或 Zoom 可能會讓 interviewer 看到不同的畫面。
3. Interviewee 在編寫程式碼的時候應該注意可讀性，符合業界要求的風格。舉例來說，變量和操作符之間該空格的地方要空格。
4. Interviewee 在解釋的時候慎用手勢。

第三題:
1. Interviewer 直接給題目，容易讓背答案的人混水摸魚。
2. Interviewee 在表達 a's start 的時候，要注意打出來的符號是不是符合自己想表達的意思。
3. [24:52] Interviewee 應該可以花更少的時間以及用更簡單的方式去定義什麼叫做「重疊到」。
4. [26:24] Interviewee 圖像化區間的方式很清楚，是個好方法。
5. [28:37] Interviewee 不要嘆氣。
6. Interviewee 花太多時間講解自己給出的例子，從 interviewer 給出題目後超過 7 分鐘都還沒有寫第一行程式。
7. [30:05] Interviewer 其實有說重疊到算不算，但 interviewee 這邊表示對方沒說。Interviewee 可能漏聽或忘了，這時候 Intervier 應該出來指正。
8. [34:34] Interviewee 不用把自己的範例刪掉。
9. Interviewee 最後沒有驗證自己程式碼的正確性。
10. Interviewer 最後沒有表達對於 interviewee 的程式的任何評語，應該有更多的互動。

## 第三次作業---他評04

interviewer

### 優點
1. 有把面試前的簡介、題目代入一起說明清楚。
2. [16:01](https://youtu.be/FXDG-o1K768?t=961) 給予改進的方向
### 改進
1. [6:38](https://youtu.be/FXDG-o1K768?t=398) 口誤將陣列說成整數
2. [8:33](https://youtu.be/FXDG-o1K768?t=513) interviewee 確認完題目後可以給予回饋，表示題目理解正確於否。
3. [14:40](https://youtu.be/FXDG-o1K768?t=880) 由於 n 、 k 皆為未知數，所以時間複雜度不能夠解釋成 $O(n^2)$ ，外圈是 $O(n-k)$ ，內圈則是 $O(k)$ 。總共的複雜度為 $O(nk-k^2)$ ，其中 $nk$ 為主導項， 可化簡成 $O(nk)$
4. 在 interviewee 的實做方法中，的確成功的將時間複雜度降低到 $O(n)$ ，但是並未在空間複雜度上進行討論，事實上，空間複雜度在這個實作方式是 $O(k)$ ，而以下實作方式能夠將空間複雜度降至 $O(1)$ ，可以引導其討論:

class Solution {
public:
    vector<int> sub;
    double max = 0;
    double findMaxAverage(vector<int>& nums, int k) {
        
        for(int i = 0; i<k; i++ ){
            sub.push_back(nums[i]);
            max += nums[i];
        }
        double tmp = max;
        for(int j = k; j< nums.size(); j++){
            tmp-=nums[j-k];
            tmp+=nums[j];
            
            sub.push_back(nums[j]);
            if (tmp >= max) {
                max = tmp;
            }
        }
        return  max/k;
    }
    
};
}


5. 第三題沒有討論
總結: 能夠在適當的時間點給予 interviewee 一些回饋，確保面試的過程順暢，且能給予其一些實作上的信心

interviewee

### 優點
1. 題目理解的清楚
2. [11:17](https://youtu.be/FXDG-o1K768?t=677) 在講解例子的時候有適當加入一些 pseuedocode 輔助解釋
3. 舉例清楚，後續程式碼實作上面不會因此遇到困難

### 改進
1. 對於:"連續的子陣列"可以確認，是一個子陣列，元素連續，或是多個子陣列，每個之間連續(只是覺得題目本身敘述有些含糊，但是如果不妨礙理解也可以不用確認~)
2. [17:33](https://youtu.be/FXDG-o1K768?t=1053) 整段程式碼刪掉有點可惜，有許多可以重複利用的部分。
3. [34:30](https://youtu.be/FXDG-o1K768?t=2070) 一樣例子不須刪除