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

# 2021 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2021)」面試範例
> 貢獻者: 高爾夫-Golf
> ==[video1](https://youtu.be/xjKg70MVj7s)==, ==[video2](https://youtu.be/sJSwQ4a7OSc)==

## [35. Search Insert Position](https://leetcode.com/problems/search-insert-position/)
> [video](https://youtu.be/xjKg70MVj7s)

### 題目描述
給一個已經排序過 ( 升冪 ) 的數列，並且此數列每個數字都不同，再給一個目標數。如果目標數在此數列中，請回傳此數字位置；如果目標數不在數列中，請回傳目標數應該要安插的位置。
### 程式碼解說
#### 方案一 : ***暴力解***
由於此數列已經排序過了，因此直接用一個 `for` 去把數列中每個位置都去跟目標數比較，即可以得到答案。特別注意，如果跑完整個迴圈都還沒找到，就代表目標數大於整個數列，所以直接回傳最後一個位置即可。

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

#### 方案二 : ***二分搜尋法***
二分搜尋法就是利用數列中間的數字跟目標數比較，一直切成更小等分，直到切不了就代表結束。
* 中間數「大於」目標數
* 中間數以後也都大於目標數，因此可以不用再看
* 中間數「小於」目標數
* 中間數以前也都小於目標數，因此可以不用再看

結束二分搜尋法會有幾種可能性
1. 目標數被夾在 `left and right`
* 直接回傳 `right`
2. 目標數不在 `left and right` 中
* 代表目標數大於整個數列或小於整個數列

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if(nums[0] >= target) return 0;
        if(nums.back() < target) return nums.size();
        int left = 0;
        int right = nums.size() - 1;
        while (right - 1 != left) {
            int mid = (right + left) / 2;
            if (nums[mid] == target) return mid;
            else if(nums[mid] > target) right = mid;
            else left = mid;
        }
        return right;
    }
};

### 面試過程檢討

#### **Interviewer**
* [00:14](https://youtu.be/xjKg70MVj7s?t=14): 說話避免中英混用，「目標值」和 "index" 擺在一起，無助於理解，而且也缺乏對應的名詞定義，儘量改為口語方式表達 (甚至設計另一種情境)，也可避免 interviewee 死背答案。關於輸入的數值範圍和行為，都該清楚說明
* 例如：考慮成大資訊系只錄取 45 名學生，已知現有成績造遞減排列，給定分數 `x`，我們可以如何判斷是否篤定錄取或者列入「危險但有機會」(考慮有 `y` 人放棄的狀況) 呢？
* [01:41](https://youtu.be/xjKg70MVj7s?t=101): 避免說「聽起來這方法還可以」，也不該直接問「時間複雜度」(interviewee 很容易背誦或猜測)。今天公司安排 interviewer 用上班時間跟 interviewee 互動，是為了「找人做事」，要儘量藉由互動來確認應徵者的能力和溝通方式是否對公司有助益。這裡可改提出 interviewee：「打算要用策略來實作？」「演算法是否需要額外配置空間？」等問題，這些需要基本的論述
* [02:05](https://youtu.be/xjKg70MVj7s?t=125): 避免說「我覺得 $O(n)$ 可能太慢」這種話，一來聽起來很沒把握 (所謂的「可能」，要看用在哪裡)，二來「太慢」的前提是輸入資料的量，既然 interviewer 沒有清楚說明條件，這個「太慢」也未必會成立。這樣的提問，會讓 interviewee 覺得對方沒有好的準備，也缺乏適度的關注及互動
* [04:58](https://youtu.be/xjKg70MVj7s?t=298): 避免說「幫我把 code 實作出來」，一來很不專業，二來中間應該要有討論，例如「如何找位於中間的元素」，甚至在題目加上額外條件，像是「考慮到原本的輸入中存在負整數，但給定的目標值必定大於零，那可以怎樣改進？」。interview 的重點是「互動」，不要讓 interviewer 可僥倖背誦答案
* [06:35](https://youtu.be/xjKg70MVj7s?t=395): 當 interviewee 寫出語法不正確或者可能沒思考周全 (如 `+` 帶來的overflow) 時，即可打斷 interviewee，提醒他修改或者討論
* Binary search 衍生 [很多變形](https://en.wikipedia.org/wiki/Binary_search_algorithm#Variations)，如果 interviewee 作答後可充分解釋程式碼，可引導 interviewee 去思考上述變形，甚至論文 [Modified Binary Search Algorithm](https://arxiv.org/pdf/1406.1677.pdf)，提出改進手段
* 沒有後續的問題和程式碼討論，interviewer 沒做出足以鑑別一個人能力的舉措

#### **Interviewee**
* [01:59](https://youtu.be/xjKg70MVj7s?t=119): 既然講了最差的時間複雜度，那也該提平均和最佳的案例
* [02:15](https://youtu.be/xjKg70MVj7s?t=125): 進行 REACTO 步驟時，就可說明自己將採用 binary search，不用拖到現在才說，注意時間！
* [02:23](https://youtu.be/xjKg70MVj7s?t=143): 之前所舉出的案例，不用急著刪去，一樣留意時間，儘量騰出有效的互動時間
* [02:37](https://youtu.be/xjKg70MVj7s?t=157): 舉例時，應先列出奇數個元素，才可沒爭議地指出「中間」，否則就需要定義
* [05:13](https://youtu.be/xjKg70MVj7s?t=313): 打字太慢，要練！
* [05:16](https://youtu.be/xjKg70MVj7s?t=316): 「兩個 input」不易識別，改為「二個參數」，注意: 中間若說不清楚，無助於溝通，最後只是浪費自己的寶貴時間
* [05:25](https://youtu.be/xjKg70MVj7s?t=325): STL 的 [vector](https://www.dictionary.com/browse/vector) 發音要確實: [vek-ter]，不要偷懶忽略 [k] 的發音，寧可說得慢，不要讓人誤解
* 對比: [waiter](https://www.dictionary.com/browse/waiter)
* [06:01](https://youtu.be/xjKg70MVj7s?t=361): 不要說「接下來我們就進入 while 迴圈的部分」，會讓人感覺你是背誦答案，應該要一邊解說 binary search 的演算法，一邊敲打程式碼 (要練!)
* [06:54](https://youtu.be/xjKg70MVj7s?t=414): 提到「第二種可能性」時，沒有說到「第一種可能」(不需要加「性」)，應該在撰寫程式碼之前，就列舉三種可能
* [07:50](https://youtu.be/xjKg70MVj7s?t=470): 中間停頓過久，如果要移動游標，過程中請說話，化解尷尬，也能讓 interviewer 的注意力集中
* [08:46](https://youtu.be/xjKg70MVj7s?t=526): 判斷式 `if (nums.back() < target)` 和後續的程式碼可精簡，例如事先求值 (evaluate) `nums.size()`
* 環境採光儘量柔和，避免過白

---

## [371. Sum of Two Integers](https://leetcode.com/problems/sum-of-two-integers/)
> [video](https://youtu.be/sJSwQ4a7OSc)

### 題目描述
給兩個整數，回傳相加的結果。**不能使用 `+ and -`**
### 程式碼解說
#### 方案一 : ***把每個 bit 去 Run 過一遍，特別注意 carryout***

class Solution {
public:
    int getSum(int a, int b) {
        if (!a || !b) return a == 0 ? b : a;
        int result = 0;
        int carryout = 0;
        for (int i = 0; i < 32; i++){
            int A = (a >> i) & 1;
            int B = (b >> i) & 1;
            switch (A + B + carryout){
                case 1:
                    result |= 1 << i;
                    carryout = 0;
                    break;
                case 2:
                    carryout = 1;
                    break;
                case 3:
                    result |= 1 << i;
                    carryout = 1;
                    break;
                default:
                    break;
            }
        }
        return result;
    }
};

`getSum` 的參數是兩個整數
1. 首先利用第四行去判斷「是不是有其中一個為零」，假如有就可以直接回傳非零的數字。
2. 透過 `for` 迴圈去看每個 `bit` 是 0 還是 1 ，並且利用 `A and B` 來存
3. 緊接著用 `switch` 將每種可能性找出來，並做出對應的事情。
* 如果 `A + B + carrout = 3` 代表要進位並且還要存 1 進去 `result`
* 如果 `A + B + carrout = 2` 代表要進位並且還要存 0 進去 `result`
* 如果 `A + B + carrout = 2` 代表「不用」進位只要存 0 進去 `result`
4. 回傳 `result`

#### 方案二 : ***利用 XOR 把不用進位的 bit 直接存起來，再將要進位的左移，直到沒有 carryout***

class Solution {
public:
    int getSum(int a, int b) {
        unsigned carry;
        while (b != 0) {
            carry = a & b;
            a = a ^ b;
            b = (carry << 1);
        }
        return a;
    }
};

`while` 迴圈的結束條件是沒有 `bit` 需要進位
1. 首先程式碼第七行，把需要進位的 `bit` 存進 `carryout` 起來。
2. 程式碼第八行，將 `a XOR b` 就可以找到不用進位的 `bit` ，直接存進去 a
3. 將 `carryout` 往左移一個，就代表進位後的 `bit`
4. 重複 `1 ~ 3` ，直到沒有 `bit` 需要進位
4. 回傳 `result`

### 面試過程檢討

#### **Interviewer**
* 接下來要測驗 Interviewee 能不能用不同的方法來進行，並且降低記憶體的使用；然而在影片中講的不夠精準，***不應該說空間複雜度***，而是要說降低記憶體的使用。
* [00:15](https://youtu.be/sJSwQ4a7OSc?t=15): 提及不能用 `+` 和 `-` 這二個運算子，但沒說「為何要給這樣的限制」，只會讓背誦答案的人有幾可趁。可以順著題目意思，說「我想知道你能否組合邏輯運算子，達到運算電路的模擬，也能得知你在位元層級的掌握度」
* [02:46](https://youtu.be/sJSwQ4a7OSc?t=166): 避免說「可以麻煩你把 code 打出來嗎？」這種話，原因是:
1. 沒有討論
2. 沒有正面回應
3. 給背誦答案者過多的空間
4. 這種說法過於「台式」(乍聽以為是《深X保健室》來賓的對話)
* [02:59](https://youtu.be/sJSwQ4a7OSc?t=179): 「不用考慮 (overflow)，沒關係」無助於互動，這其實是理解 interviewee 對二補數和相關數位邏輯認知的好機會，應該在此停下
* [03:50](https://youtu.be/sJSwQ4a7OSc?t=230): 敘述 `for (int i = 0; i < 32; i++)` 值得討論，應該打斷，讓 interviewee 回顧 [64-bit data model](https://en.wikipedia.org/wiki/64-bit_computing#64-bit_data_models)
* [07:22](https://youtu.be/sJSwQ4a7OSc?t=442): 看到 interviewee 寫出較長的程式碼，應該停下來討論，不僅要確認程式碼正確，也要思考程式碼能否精簡，例如 `if (!a || !b) return a == 0 ? b : a;` 可簡化為 `if (!a || !b) return a | b;` (減少分支且更直觀)
* [07:31](https://youtu.be/sJSwQ4a7OSc?t=451): 避免說「這個 code 看起來是沒什麼問題」，這樣很不專業，只會讓 interviewee 覺得自己只是換個地方默寫 LeetCode，而不是一個重視技術內涵的公司該有的表現
* [07:34](https://youtu.be/sJSwQ4a7OSc?t=454): 避免只是說「你能寫得更精簡嗎？」，卻沒有給予方向和思維，這不是好的「互動」
* 沒有後續的問題和程式碼討論，interviewer 沒做出足以鑑別一個人能力的舉措

#### **Interviewee**
* [00:38](https://youtu.be/sJSwQ4a7OSc?t=39): 避免說「探討每個 bit，並且把每個 bit 看過就可以知道答案」這種話，因為沒有任何資訊量可言 (一堆演算法都會「看過每個 bit」)，應該要推敲出題者的期待，特別是限制來自什麼。不要忘記「互動」，也該避免說「答案」，今天公司是要找人「解決工程問題」，而非「找人背誦答案」
* [00:45](https://youtu.be/sJSwQ4a7OSc?t=45): 與其急著寫出 carryout，不如將你知道的半加器、全加器，甚至二補數原理說出來
> [解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation) ^科普讀物^ :notes:
> [組合邏輯](https://www.cyut.edu.tw/~yfahuang/chap04.pdf)
* 延伸閱讀: [使用遞迴和 bit-wise operator 來實作乘法運算](https://hackmd.io/@jserv/r1Z_zPx8-)
* [02:00](https://youtu.be/sJSwQ4a7OSc?t=120): 若將位元操作的行為說清楚，也不用特別去列真值表，除非被要求
* [07:42](https://youtu.be/sJSwQ4a7OSc?t=462): 既然你不是實力派女歌星，沒人想聽你的氣音，尤其透過視訊會議，會更明顯，務必避免
* [09:32](https://youtu.be/sJSwQ4a7OSc?t=572): 可以先用邏輯電路的觀點去解釋 carry，除非 interviewer 明確要求你舉實際的案例，這體整體來說，花費太多時間，卻又看不出 interviewee 具備的程式設計技巧
* [11:01](https://youtu.be/sJSwQ4a7OSc?t=661): 由於前面舉例根本沒歸納 XOR 和 AND 位元操作的行為，此處寫出程式碼，就像是死背程式碼，可能會引起 interviewer 拿出更多的變化來「挑戰」
* 例如：不用遞迴、用更少的位元運算

參考實作:

int getSum(int a, int b)
{
   return (!a | !b) ? (a | b) :
                      getSum(a ^ b, ((unsigned) a & b) << 1);
}

延伸閱讀:
* [LeetCode 371](https://dosmanthus.medium.com/%E4%BD%8D%E5%85%83%E9%81%8B%E7%AE%97-leetcode-371-sum-of-two-integers-f96d5be5c417)
* [LeetCode: Single Number](https://hackmd.io/@eklipsorz/SJtK5qpvI)
* [LeetCode 421. Maximum XOR of Two Numbers in an Array](https://hackmd.io/@kenjin/HJziYFMEr)
* [LeetCode 1009. Complement of Base 10 Integer](https://hackmd.io/@Zero871015/LeetCode-1009)
* [LeetCode 476. Number Complement](https://hackmd.io/@Zero871015/LeetCode-476)
* 位元運算和數學原理的應用: [How RAID-6 dual parity calculation works](http://igoro.com/archive/how-raid-6-dual-parity-calculation-works/)

## 第三次作業 - 他評01
### 優點
* 有重複問題和舉例討論。

### 缺點
#### [35. Search Insert Position](https://leetcode.com/problems/search-insert-position/)
[00:18](https://youtu.be/xjKg70MVj7s?t=18) Interviewer應該避免中英混用，以索引值取代index。
[00:56](https://youtu.be/xjKg70MVj7s?t=56) Interviewer在[00:05](https://youtu.be/xjKg70MVj7s?t=5)只有說題目給定**已經排序過**的數列，Interviewee不能自己假設排序就是升冪(或降冪)，應該在重複Interviewer之問題後先確認再舉例。
[01:41](https://youtu.be/xjKg70MVj7s?t=101) Interviewer應該避免直接問Interviewee時間(空間)複雜度等，容易流於制式化的問答。如果想考驗相關想法，應該等Interviewee實作完程式碼還是沒有提到時，再以其他方式詢問並啟發思考是否能再更精進。
[02:08](https://youtu.be/xjKg70MVj7s?t=128) Interviewer不能直接說$O(N)$可能太慢，因為到目前為止並未提到輸入的資料量，因此也不該在沒有補充說明條件的情況用**可能**這樣的字眼。
[02:15](https://youtu.be/xjKg70MVj7s?t=135) 舉例只佔了一小部分空間，Interviewer不需要刪掉重打，才能節省討論時間。
[04:13](https://youtu.be/xjKg70MVj7s?t=253) Interviewer的舉例和後面實作二分搜尋法的程式碼不一樣，舉例是```right = mid - 1```或```left = mid + 1```，但是程式碼是直接將mid賦值到條件下對應的變數。
[06:39](https://youtu.be/xjKg70MVj7s?t=399) Interviewee用二分搜尋法前(或更早)就應該先向Interviewer確認給定陣列的長度，因為在```int mid = (right + left) / 2;```這邊可能會發生溢位。Interviewer發現寫法上的問題時也應該適時打斷並給予提示，觀察Interviewee能否做適當的修改。
[07:47](https://youtu.be/xjKg70MVj7s) Interviewee應該一開始就先針對較極端的情況(出現在頭或尾)進行舉例討論，比較能節省時間。
[08:55](https://youtu.be/xjKg70MVj7s?t=535) 這題可以改寫二分搜尋法的程式碼，就不用前面那些判斷。另外整個過程到最後只有改進程式碼的時間複雜度，Interviewer沒有做問題的延伸或出變化題。
#### [371. Sum of Two Integers](https://leetcode.com/problems/sum-of-two-integers/)
[00:15](https://youtu.be/sJSwQ4a7OSc?t=15) Interviewer只說條件是不能用`＋`或`-`太單調了，可以說要使用位元運算符實作兩整數加法，考驗Interviewee對位元運算的掌握度等等。
[01:01](https://youtu.be/sJSwQ4a7OSc?t=61) Interviewee不用將之前的舉例刪除重打，節省後續的討論時間。
[04:05](https://youtu.be/sJSwQ4a7OSc?t=245) Interviewer應該先向Interviewee確認題目是否有規定整數型別是幾個位元，不能自己假設是32bit。
[07:23](https://youtu.be/sJSwQ4a7OSc?t=443)```if (!a || !b) return a == 0 ? b : a;```是要在a或b其中一個變數為0時，回傳不為零的變數，可以改成直接回傳```a | b```即可。
[07:30](https://youtu.be/sJSwQ4a7OSc?t=450) Interviewer給的評語(看起來是沒甚麼問題)太表面，接著如果想要求Interviewee寫得精簡一點時，也許應該提示是哪個部分，Interviewee最後也沒有在簡化程式碼，而是直接換了其他作法。
[08:47](https://youtu.be/sJSwQ4a7OSc?t=527) Interviewee舉例加法結果與進位時，就應該帶入自己對位元互斥或`(^)`以及位元且`(&)`的想法，避免後續的程式碼看起來像背答案。
[09:50](https://youtu.be/sJSwQ4a7OSc?t=590) Interviewee的舉例可以留著不要刪掉，後面解釋程式碼的作法時比較容易讓Interviewer理解。

## 第三次作業 - 他評02
#### [35. Search Insert Position](https://leetcode.com/problems/search-insert-position/)
*
* [6:28](https://youtu.be/xjKg70MVj7s?t=388) overflow problem
* [7:31](https://youtu.be/xjKg70MVj7s?t=451) 可以提出 loop invariant 驗證 binary search 正確性
* [8:52](https://youtu.be/xjKg70MVj7s?t=532) array 中含有重複 element 的情況也該討論

#### [371. Sum of Two Integers](https://leetcode.com/problems/sum-of-two-integers/)
* [0:22](https://youtu.be/sJSwQ4a7OSc?t=22) 應先詢問整數範圍
* [4:49](https://youtu.be/sJSwQ4a7OSc?t=289) 用到 operator +，與題目要求不符
* [7:24](https://youtu.be/sJSwQ4a7OSc?t=444) 輸入測資 $a=2^{31}-1, \ b=2^{31}-1$ 會出錯