---
title: 2021 年資訊科技產業專案設計課程面試範例
tags: INFO2021
---
# 2021 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2021)」面試範例
> 貢獻者: 德米安 Demi
> [video](https://youtu.be/CeQNrkbr5Ho)
🧔：interviewer 👶：interviewee
## [226. Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/)
> 影片: [00:19](https://youtu.be/CeQNrkbr5Ho?t=19)
### 測驗說明與問答
🧔：希望Demi能夠實作一個function，輸入binary tree並回傳一個invert binary tree。
👶：好的那我們要處理invert binary tree的問題，好比如我要將：
```graphviz
digraph graphname{
node[shape=box]
{
A[label=1]
B[label=2]
C[label=3]
D[label=4]
E[label=5]
F[label=6]
G[label=NULL,shape=plaintext]
}
{
H[label=1]
I[label=3]
J[label=2]
K[label=5]
L[label=4]
M[label=NULL,shape=plaintext]
N[label=6]
}
A->{B,C}
B->{D,E}
C->{F,G}
H->{I,J}
J->{K,L}
I->{M,N}
}
```
👶：另外也必須特別考量到空集合的狀況。
👶：我剛開始想到的方法是用遞迴的方式，以postorder的方式先向下找節點，如果有子節點時即向下執行函數，直到到達樹葉，或是已訪問完自己的子節點後，即對自己的左右子節點做交換。最後直到根節點完成交換後即結束全部的遞迴函數。
🧔：這樣的時間複雜度是如何？
👶：由於需要遞迴的訪問每一個節點執行函數，故時間複雜度為$O(n)$
### Invert Binary Tree with recursion
```cpp
struct tree{
int val;
struct tree *left;
struct tree *right;
}
struct tree *invertBtree(struct tree * root) {
if(root->left) root->left = invertBtree(root->left);
if(root->right) root->right = invertBtree(root->right);
sturct tree *temp;
temp = root->left;
root->left = root->right;
root->right = temp;
}
```
🧔：想請問是否有不是 recursive 的做法呢？
👶：我的想法是可以透過一個 linked list 的 stack 對我們要做 invert 的 node 做紀錄，將搜尋到的node紀錄在stack中，再逐一從stack中的node做invert，以使用iterative達到類似recursive的做法。
### Invert Binary Tree with iterative
```cpp
struct tree{
int val;
struct tree * left;
struct tree * right;
}
struct treestack{
struct tree* cur;
struct tree* next;
}
struct tree * invertbtree(struct tree * root){
if(!root) return 0;
struct treestack* tstack;
tstack->cur = root;
while(tstack->cur){
if (tstack->cur->left || tstack->cur->right ) {
//預期做tstack紀錄的動作，提供else階段pop tstack節點
}
else{
sturct tree* temp;
temp = tstack->cur-> left;
tstack->cur-> left = tstack->cur->right;
tstack->cur->right =temp;
tstack->next = tsack->cur->next;
tstack->cur = tstack->next;
}
}
}
```
延伸閱讀: [Invert binary tree in O(1) space without stack/queue/recursion](https://hackmd.io/@fennecJ/Invert_bin_tree)
## [35. Search Insert Position](https://leetcode.com/problems/search-insert-position/)
> 影片: [16:38](https://youtu.be/CeQNrkbr5Ho?t=998)
### 測驗說明與問答
🧔：在第二題我會提供一個int array和一個int target，我希望你可以回傳給我此target在array的index，若target不在array中，則告訴我如果target插入array時，他的index是多少？我希望你可以在$O(log(n))$完成。
👶：這一題最直覺的方法是使用Sequential Search的方式一個一個找值，然而這個方法的時間複雜度為$O(log(n))$。那在此我們可以用Binary Search的方式來讓時間複雜度降在$O(log(n))$內。
👶：每次在尋找前紀錄首尾index的區間，並比較中間index的值與target的大小，若arr[index]>target，則往左側區間找值，反之往右，如果相同則回傳該index。直到區間小於一，直接做大小的比較來回傳index。
### binary search
```cpp
int bsearch(int * arr, int target){
int head = 0;
int tail = sizeof(arr)/ sizeof(int) -1;
int cur;
while(tail-head>1){
cur = head + (tail - head)/2;
if(arr[cur] > target) tail =cur-1;
else if (arr[cur] < target) head = cur+1;
else return cur;
}
if(arr[head] >= target) return head;
else if(arr[tail] >= target ) return tail;
else return tail+1;
}
```
## [50. Pow(x, n)](https://leetcode.com/problems/powx-n/)
> 影片: [28:07](https://youtu.be/CeQNrkbr5Ho?t=1687)
### 測驗說明與問答
🧔：最後希望你能實作一個power function，即是$x^n$。
👶：這一題要實作$x^n$的function。那在這一題中有幾個需要注意的部分，比如n的正負。如果n為正，那就是用加乘的方式處理，若為負則要做加除。而一些情況下可以免去計算直接回傳：比如
$x=0 , 1\ return\ 0,1\\ n=0\ \ return\ 1$
最直覺的作法是用for迴圈讓$x$乘（除）上$n$次，不過這樣的時間複雜度是$O(n)$。我認為更快的方式是使用類似餘數分解的方式。(之後解釋)
### Pow(x, n)
```cpp
double power(double x , int n){
if(x ==1) return 1;
else if (x == 0) return 0;
if(n == 0 ) return 1;
double result;
if(n/2){
result = power(x, n/2);
result *= result;
}
else result = 1;
if(n%2){
if(n>0) result *= x;
else result /= x;
}
return result;
}
```
延伸閱讀: [LeetCode 50. Pow(x, n)](https://hackmd.io/@Zero871015/LeetCode-50)
## 總體初步檢討
針對 interviewer 的檢討:
* 時間複雜度 (time complexity) 不該說「是多少」，這是「等級」，而非「數量」
* 提問時，避免只拋出「時間複雜度是什麼等級？」這樣的問題，這樣對話欠缺上下文，可能 interviewee 憑藉猜測或背誦做答，從而喪失鑑別度 (注意對話時間，儘量讓問答有效率)，可改為一併要求 interviewee 解釋並簡介對應到現有程式碼該怎麼展現
* [226. Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/) 這題，interviewee 一開始說用遞迴，在程式碼作答後，應該快速檢討 (如某些極端案例是否有考慮到) 或要求 interviewee 自己說明驗證和改進的方案，而非急著問「能否改為非遞迴的方式」，畢竟後者太容易被預測
* [07:29](https://youtu.be/CeQNrkbr5Ho?t=449): interviewee 實作的程式碼不夠精簡，應該提示是否能改進。例如:
```cpp
struct TreeNode *invertTree(struct TreeNode *root) {
if (!root) return NULL;
struct TreeNode *l = invertTree(root->left), *r = invertTree(root->right);
root->left = r, root->right = l;
return root;
}
```
* [15:52](https://youtu.be/CeQNrkbr5Ho?t=952): interviewee 顯然在此處花了很多時間撰寫程式碼，卻看不出思維的特別之處，於是可適度打斷，跟 interviewee 討論可能的實作方式，給予提示，畢竟面試的重點是「認識一個人，包含專業能力及其展現」，適度略過細節，可讓雙向溝通更順暢
* 講解 [35. Search Insert Position](https://leetcode.com/problems/search-insert-position/) 題意時，過於簡短，應該給予一些程式碼期待的說明，至少舉一個案例，當然也可一開始就拿特例來探討，畢竟 interviewee 在前一個問題已有中等水準的表現
* [19:57](https://youtu.be/CeQNrkbr5Ho?t=1197): interviewee 宣稱不需要特別傳遞描述陣列空間的變數 (如 `arr_size`)，應該適度打斷，討論 C 語言函式呼叫的議題，畢竟光靠一個傳入的指標，該如何知道陣列具體的空間呢？
* [28:00](https://youtu.be/CeQNrkbr5Ho?t=1680): 既然 interviewee 宣稱完成程式碼，應有必要的檢驗和討論，例如極端狀況是否考慮到、變數命名是否清晰，和後續改進
```cpp
int searchInsert(int *nums, int numsSize, int target) {
int lo = 0, hi = numsSize;
while (lo < hi) {
int m = lo + (hi - lo) / 2;
if (nums[m] < target)
lo = m + 1;
else
hi = m;
}
return lo;
}
```
* 聽到 interviewee 提出的想法，不該照單全收，可要求拆解更細的部分，或是先撰寫一部分虛擬碼，畢竟面試有明確的時間限制，若因 interviewee 寫程式花費較多時間，就意味著無從評估其具體能力
* 看到 interviewee 寫出 `int *arr; int tail = sizeof(arr) / sizeof(int) - 1;` 這樣的程式碼時，應該要打斷，畢竟 `sizeof(arr)` 存在嚴重的錯誤
* [你所不知道的 C 語言：技巧篇](https://hackmd.io/@sysprog/c-trick) 的「不夠謹慎的 `ARRAY_SIZE` 巨集」一節
* [50. Pow(x, n)](https://leetcode.com/problems/powx-n/) 之所以列為中等難度，就在於有很多討論，應該引導 interviewee 思考。
```cpp
double myPow(double x, int n) {
double value = 1;
long nn = n;
if (nn < 0) {
for (nn *= -1; nn; nn >>= 1) {
if (nn & 1)
value /= x;
x *= x;
}
return value;
}
for (; nn; nn >>= 1) {
if (nn & 1)
value *= x;
x *= x;
}
return value;
}
```
針對 interviewee 的檢討:
1. 在遠距面試的場合中，通常鏡頭會採正面且不會拍到鍵盤，有效的手勢範圍很窄，不該太依賴手勢，相反的，儘量用 REACTO 步驟的 Example，打字並說出輸入/預期輸出案例的「特性」
2. 對話中舉例的測試資料 (或某一組輸入/預期輸出) 可敲入到指定的作答內文中，如 Google Docs，這樣在用英語解說時 (畢竟不是母語，說越多，錯誤就越多)，可說得少一點
3. 以 [226. Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/) 來說，既然一開始提到想用遞迴，可以先寫下 function prototype 和遞迴呼叫的本體，隨後再補上終止條件和細節，這樣程式碼和思路探討會更一致
4. 用 Google Docs 撰寫程式碼，會發現程式碼縮排不好顧及，現有影片的程式碼在視覺上過於緊湊。其實書寫程式碼時，不用嚴格依據實際程式碼讀取的順序，反而可寫下「對應到 REACTO 步驟的 Approach 的關鍵程式碼」的函式呼叫、變數指派，或者迴圈主體
5. [06:12](https://youtu.be/CeQNrkbr5Ho?t=372): 儘量撰寫簡潔的程式碼，例如 `struct btree *temp; temp = root->left;` 可改為 `struct btree *tmp = root->left;`。不要小看只是幾個字元的差距，因為在 Google Docs 中，程式碼的縮排都要自己處理，越少換行或者非必要的 tab 按鍵，都可避免說話和程式碼撰寫間的落差
6. [07:26](https://youtu.be/CeQNrkbr5Ho?t=446): 以 [226. Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/) 來說，說明用 stack 操作改寫原本遞迴程式的手法，應該要在實際撰寫程式碼之前，跟 interviewer 討論，畢竟這手段可能不符合 interviewer 的期待
7. 原本已撰寫的程式碼可適度保存，例如用複製貼上，放在 Google Docs 某處，畢竟 interviewer 可能會要求對照
8. 撰寫非遞迴版本的實作，過多的滑鼠移動和區域反白，會影響 interviewer 視覺焦點，而且途中反覆在鄰近的程式碼間切換並變更程式碼敘述，佔用可觀的時間
9. [16:41](https://youtu.be/CeQNrkbr5Ho?t=1001): "array" 的發音是 [[ə-ˈrā](https://www.merriam-webster.com/dictionary/array)]，要留意。中英交錯時，如果發音不精準，容易讓 interviewer 誤會，尤其還要將變數名稱納入時，因此儘量避免非必要的中英詞彙交錯
10. [00:43](https://youtu.be/CeQNrkbr5Ho?t=43): 二元樹的用語是「子節點」，而非「兒子」，而且反轉二元樹是操作 sibling 的順序
11. [00:53](https://youtu.be/CeQNrkbr5Ho?t=53): 二元樹舉例時，應善用 tab 來區隔各節點
12. [02:08](https://youtu.be/CeQNrkbr5Ho?t=128): 程式碼撰寫儘量精簡，例如可改為 `struct TreeNode { struct TreeNode *left, *right; }` 注意 `bintree` 的命名，從而避免跟 [B-Tree](https://en.wikipedia.org/wiki/B-tree) 混淆。星號 (asterisk, 即 `*`) 作為指標的宣告一部分，應靠向變數名稱，這樣不僅可寫出更緊湊的程式碼，也能避免混淆。在 [03:36](https://youtu.be/CeQNrkbr5Ho?t=215) 誤將 binary tree 講成 B-Tree，也該改進
13. [02:20](https://youtu.be/CeQNrkbr5Ho?t=140): 手勢在演講過程有強化表現的效果，但在面試場合，由於鏡頭方位，手勢就需要調整，或者儘量改進說話的資訊量
14. [03:01](https://youtu.be/CeQNrkbr5Ho?t=181) 時間複雜度有很多表示法，可見 [Complexity：Asymptotic Notation](http://alrightchiu.github.io/SecondRound/complexityasymptotic-notationjian-jin-fu-hao.html)，這裡既然是討論 big-O，那就該清楚讀出來。且，除了時間複雜度，尚有空間複雜度，特別是之前已提過要用遞迴實作，這就是該著墨之處
15. [04:15](https://youtu.be/CeQNrkbr5Ho?t=255): 之前提到打算用遞迴實作，可緊接著撰寫函式原型 (function prototype) 和遞迴呼叫的程式碼，這樣一來對話更緊湊，二來思緒和程式碼對應也更好
16. [18:18](https://youtu.be/CeQNrkbr5Ho?t=1098): 解釋 Approach 時，應該順道解釋為何可滿足題目的 $O(\log n)$
17. [23:33](https://youtu.be/CeQNrkbr5Ho?t=1413): `==` 讀作「等於」即可，也可說「判斷是否相等」，簡潔的讀法習慣有助於英語表達
18. [25:23](https://youtu.be/CeQNrkbr5Ho?t=1523): 舉例應該獨立於程式碼列表
Sign in with Wallet
Connect another wallet