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

# 2021 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2021)」面試範例
> 貢獻者: 尼歐 / Neo
> ==[video](https://youtu.be/cOrEXatCP2w)==

## Q1: LeetCode 496. Next Greater Element I (Easy)

> 題目連結: [496. Next Greater Element I](https://leetcode.com/problems/next-greater-element-i/)
### 過程討論
🧔：interviewer 👶：interviewee

🧔: 好的，這次的面試總共會考二道題目與各自的延伸。首先第一題是Next Greater Element，也就是給定一個陣列以及其中一個元素，從這個元素開始向右掃描，必須回傳第一個比此元素大的值。如果沒有就回傳-1。在題目中給定兩個陣列，分別叫陣列1與陣列2，陣列1會是陣列2的子集合，請你先由每個陣列1的值找到其在陣列2的位置，並且找出該值在陣列2的Next Greater Element，並將結果都存在與陣列1相同長度的陣列中，以上是本題的描述。
👶: 好的，那我初步的想法是一個雙迴圈。外面迴圈用來迭代陣列1的元素，在迴圈內會先用一個迴圈找到該值在陣列2的位置，再用另個迴圈，從其右邊開始找尋第一個比該值大的元素。如此一來時間複雜度會是$O(N^2)$，不考慮參數以及回傳的陣列，空間複雜度會是常數等級。
### 程式碼

class Solution {
public:
    vector<int> nextGreaterElement(vector<int> &nums1, vector<int> &nums2) {
        vector<int> ans(nums1.size(), -1);
        int i, j, k;
        for (i = 0; i < nums1.size(); ++i) {
            for (j = 0; j < nums2.size(); ++j) {
                if (nums1[i] == nums2[j])
                    break;
            }
            
            for (k = j + 1; k < nums2.size(); ++k) {
                if (nums2[k] > nums2[j]) {
                    ans[i] = nums2[k];
                    break;
                }
            }
        }
        return ans;
    }
};

// Time Complexity: O(nums1.size() * nums2.size())
// Space Complexity: O(1)

### 改進方案
🧔: 你現在寫出的時間複雜度是$O(N^2)$，有辦法將等級降到線性時間嗎?
👶: 可以，假如先用一個hash table將陣列1的元素作為key，index作為value儲存起來，接著再從陣列2用一個stack存該元素右邊比他大的值來找next greater element，找到後透過hash table將結果存到要回傳的陣列中，這樣子時間複雜度就可以降到線性時間等級。
> Reduce the time complexity to O(nums1.size() + nums2.size())

vector<int> nextGreaterElement(vector<int> &nums1, vector<int> &nums2) {
    unordered_map<int, int> m;
    for (int i = 0; i < nums1.size(); ++i)
        m[nums1[i]] = i;
    stack<int> st;
    vector<int> ans(nums1.size(), -1);
    for (int i = nums2.size() - 1; i >= 0; --i) {
        while (!st.empty() && nums2[i] >= st.top())
            st.pop();
        /* Forget that nums1 is the subset of nums2
         * So the elements in nums2 may not appear in hashmap
         * if (!st.empty() && m.count(nums2[i]))
         * Date: 2021/10/19 
         */
        if (!st.empty())
            ans[m[nums2[i]]] = st.top();
        st.push(nums2[i]);
    }
    return ans;    
}
// Time Complexity: O(N)
// Space Complexity: O(N)

🧔: 那接著我要將這個問題做延伸，首先給定的陣列變成環狀的，然後陣列中可以有重複的元素。請你找出每個元素的next greater element。舉例例如給定1, 2, 1，1的next greater element是2，2沒有就回傳-1，最後一個1向右到盡頭可以連回起點，所以要回傳2。
👶: 沒問題，由於陣列變成環狀，所以我們可以把它看成兩倍長度，內容重複兩次的陣列來找Next Greater Element。這樣子的時間與空間複雜度都是$O(N)$

> 題目連結: [503. Next Greater Element II](https://leetcode.com/problems/next-greater-element-ii/)

vector<int> nextGreaterElement(vector<int> &nums) {
    const int N = nums.size();
    vector<int> ans(N, -1);
    stack<int> st;
    for (int i = N * 2 - 1; i >= 0; --i) {
        while (!st.empty() && nums[i % N] >= nums[st.top()])
            st.pop();
        if (!st.empty())
            ans[i % N] = nums[st.top()];
        st.push(i % N);
    }
    return ans;
}
// Time Complexity: O(N)
// Space Complexity: O(N)

## Q2: LeetCode 287. Find the Duplicate Number (Medium)
> 題目連結: [287. Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/)

### 過程討論
🧔: 接著是最後一題，這題叫做Find the Duplicate Number，首先會給定一個整數型態，長度為N+1的陣列，陣列中值的範圍是從1到N，其中只有一個重複的值，請你回傳該值。
👶: 好的，那我初步的想法是遍歷整個陣列的同時，用一個unordered_set來儲存看過的結果，假如之前沒看過就插入該集合，看過就回傳。

class Solution {
public:
    int findDuplicate(vector<int> &nums) {
        unordered_set<int> seen;
        int ans;
        for (auto num: nums) {
            if (seen.find(num) == seen.end()) {
                seen.insert(num);
            } else {
                ans = num;
                break;
            }
        }
        return ans;
    }
};
// Time Complexity: O(N)
// Space Complexity: O(N)

### 改進方案
🧔: 如果現在要求只能用常數等級的額外空間，而且不能修改陣列內容，請問你要怎麼做?
👶: 由於陣列長度是N+1，陣列內值的範圍是1到N，因此可以利用此陣列作為儲存變化的位置。首先當我們遍歷每個元素時，會先將該元素的值作為索引，檢查對應陣列內的值是否為負，若是則此元素已經看過，是重複的結果，若否就將對應的值乘上-1。最後為了不修改陣列內容，將每個元素取絕對值即可。如此一來，額外空間的複雜度就變成常數等級。

int findDuplicate(vector<int> &nums) {
    int dup = -1;
    for (int i = 0; i < nums.size(); ++i) {
        int curr = abs(nums[i]);
        if (nums[curr] < 0) {
            dup = curr;
            break;
        }
        nums[curr] *= -1;
    }
    
    for (auto &num: nums)
        num = abs(num);
    return dup;
}

// Time Complexity: O(N)
// Space Complexity: O(1)

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

### Interviewer

#### 優點

#### 可改進

### Interviewee

#### 優點

#### 可改進

- 寫程式碼過程太安靜

## 第三次作業-他評2
### Interviewer
優點
1. 有對 interviewee 做出延伸問題，討論複雜度

缺點
1. 在說明題目的時候沒有出現同步的螢幕畫面，以觀賞影片的角度來說會比較難以理解題目的意思
2. 眼神會時不時往旁邊看，可能會讓對方造成誤會
### Interviewee
優點
1. 在實做演算法前有先稍微勾勒自己的做法
2. 因為使用熟悉的編輯器，所以沒有排版的問題。但是可能需要考慮被迫使用 google doc. 的情境。此外影片有大量使用編輯器自動補齊的功能，google doc. 也沒有這個功能。

缺點
1. 缺少 repeat, example 的步驟
2. 寫程式的過程若加入 example 的模擬會對面試官較好理解在做什麼。目前影片是只單純解釋該行程式碼的功能 (類似說: 接著把某變數 `push` 進 .....)
3. 在還沒開始實做前就開始分析空間複雜度，不確定這樣的順序會不會有點奇怪，通常是在實做後再開始分析。因為還沒實做前分析的話，面試官很可能會覺得這個方法不好，直接叫你做複雜度更好的版本。

## 第三次作業-他評3
### interviewer
優點
- [0:28](https://youtu.be/cOrEXatCP2w?t=28) 詳細講解題目要求，有助於interviewee快速了解該題目

缺點
- [8:53](https://youtu.be/cOrEXatCP2w?t=533) 在interviewee完成題目後，沒有甚麼特別的互動就進入延伸題
- [13:03](https://youtu.be/cOrEXatCP2w?t=783) 直接說明題目名稱，有刷過題目的腦中應該已經有答案了，建議下次可以換一個方式說明題目要求

### interviewee
優點
- [15:08](https://youtu.be/cOrEXatCP2w?t=908) 解題流程順暢，思路清晰

缺點
- [1:06](https://youtu.be/cOrEXatCP2w?t=66) [13:19](https://youtu.be/cOrEXatCP2w?t=799) 並未重新確認題目要求，而是直接講述自己的解法，可能搞錯題目要求
- [1:08](https://youtu.be/cOrEXatCP2w?t=68)「雙迴圈」可以使用較專業名詞如「巢狀迴圈」
- [1:54](https://youtu.be/cOrEXatCP2w?t=114) coding過程中很多時候過於安靜，可以嘗試邊打邊說明程式內容
- [4:22](https://youtu.be/cOrEXatCP2w?t=262) 延伸題解題之前，可以先說明完接下來的程式架構後再撰寫程式，interviewer也會比較清楚接下來的code在做甚麼

## 第三次作業-他評4
### interviewer
優點
- 有引導interviewee繼續延伸問題。

缺點
- 針對題目的敘述，可以有example 讓interviewee更了解題目的敘述(input? output?)
- 較少針對interviewee的程式碼去提問。

### interviewee
優點
- 有重複interviewer的題目，確認理解是否正確。
- 在寫程式的時候沒有過多的空檔。
- [4:25](https://youtu.be/cOrEXatCP2w?t=265) 改善思路明確，且有進行時間/空間的複雜度的分析。

缺點
- 在interviewer說明完題目時，缺少交互詰問。
- [2:43](https://youtu.be/cOrEXatCP2w?t=165) 「從右邊開始...。」感覺應該要再多說明，會讓interviewer較清楚程式思路。
- [4:03](https://youtu.be/cOrEXatCP2w?t=243) 「這個陣列」 是指 nums1 還是 nums2? 雖然有用游標圈起來，但其實可以直接說明是哪個陣列，或是說明在哪一行。
- [11:05](https://youtu.be/cOrEXatCP2w?t=665) 宣告stack但不清楚stack的用意，建議先說明清楚這個stack是用來幹嘛的。
- [12:46](https://youtu.be/cOrEXatCP2w?t=766) 「這個值的索引」 這句話不明確，建議說明為什麼是 i%N 這個index ?

## 第三次作業-他評 5

### Interviewer

#### 優點
- 對於題目有完整的敘述
- 延伸題有提出實際可能的例子

#### 可改進
- 對於題目解釋算是清楚，但有些概念沒有辦法一次就聽懂，例如第一題敘述時我不確定一般沒有聽過Next Greater Element的人能否馬上知道題目的要求。可以提供一些範例，或者將範例放置於google doc上面，這樣便可以有一空間與對方討論
- 除了宣讀題目外，與對方幾乎沒太多的互動

### Interviewee

#### 優點
- 打字快速，並且基本功相當紮實
- 會詳細解釋程式碼的時間複雜度

#### 可改進
- 雖然沒有強制規定要用REACTO的策略，但是我認為缺乏重複題目跟舉例的步驟是很容易剛開始讓我這樣的旁觀者一頭霧水，換作是實際的面試情況我的角色就可以定位在面試過後觀看錄影的評估人員。這部分在Interviewer沒有做到的情形下，身為Interviewee更應該要做到
- 撰寫程式碼時沉默時間過長，要培養邊打邊寫的能力
- 畫面呈現上，程式碼太小不太好看