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

貢獻者: 德米安 Demi
video

🧔：interviewer 👶：interviewee

226. Invert Binary Tree

影片: 00:19

測驗說明與問答

🧔：希望Demi能夠實作一個function，輸入binary tree並回傳一個invert binary tree。
👶：好的那我們要處理invert binary tree的問題，好比如我要將：

👶：另外也必須特別考量到空集合的狀況。
👶：我剛開始想到的方法是用遞迴的方式，以postorder的方式先向下找節點，如果有子節點時即向下執行函數，直到到達樹葉，或是已訪問完自己的子節點後，即對自己的左右子節點做交換。最後直到根節點完成交換後即結束全部的遞迴函數。
🧔：這樣的時間複雜度是如何？
👶：由於需要遞迴的訪問每一個節點執行函數，故時間複雜度為 $O (n)$

Invert Binary Tree with recursion

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

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

🧔：在第二題我會提供一個int array和一個int target，我希望你可以回傳給我此target在array的index，若target不在array中，則告訴我如果target插入array時，他的index是多少？我希望你可以在 $O (l o g (n))$ 完成。
👶：這一題最直覺的方法是使用Sequential Search的方式一個一個找值，然而這個方法的時間複雜度為 $O (l o g (n))$ 。那在此我們可以用Binary Search的方式來讓時間複雜度降在 $O (l o g (n))$ 內。
👶：每次在尋找前紀錄首尾index的區間，並比較中間index的值與target的大小，若arr[index]>target，則往左側區間找值，反之往右，如果相同則回傳該index。直到區間小於一，直接做大小的比較來回傳index。

binary search

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)

影片: 28:07

測驗說明與問答

🧔：最後希望你能實作一個power function，即是 $x^{n}$ 。
👶：這一題要實作 $x^{n}$ 的function。那在這一題中有幾個需要注意的部分，比如n的正負。如果n為正，那就是用加乘的方式處理，若為負則要做加除。而一些情況下可以免去計算直接回傳：比如
$x = 0, 1 r e t u r n 0, 1 n = 0 r e t u r n 1$

最直覺的作法是用for迴圈讓 $x$ 乘（除）上 $n$ 次，不過這樣的時間複雜度是 $O (n)$ 。我認為更快的方式是使用類似餘數分解的方式。(之後解釋)

Pow(x, n)

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;
}

總體初步檢討

針對 interviewer 的檢討:

時間複雜度 (time complexity) 不該說「是多少」，這是「等級」，而非「數量」
提問時，避免只拋出「時間複雜度是什麼等級？」這樣的問題，這樣對話欠缺上下文，可能 interviewee 憑藉猜測或背誦做答，從而喪失鑑別度 (注意對話時間，儘量讓問答有效率)，可改為一併要求 interviewee 解釋並簡介對應到現有程式碼該怎麼展現
226. Invert Binary Tree 這題，interviewee 一開始說用遞迴，在程式碼作答後，應該快速檢討 (如某些極端案例是否有考慮到) 或要求 interviewee 自己說明驗證和改進的方案，而非急著問「能否改為非遞迴的方式」，畢竟後者太容易被預測

07:29: interviewee 實作的程式碼不夠精簡，應該提示是否能改進。例如:

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: interviewee 顯然在此處花了很多時間撰寫程式碼，卻看不出思維的特別之處，於是可適度打斷，跟 interviewee 討論可能的實作方式，給予提示，畢竟面試的重點是「認識一個人，包含專業能力及其展現」，適度略過細節，可讓雙向溝通更順暢
講解 35. Search Insert Position 題意時，過於簡短，應該給予一些程式碼期待的說明，至少舉一個案例，當然也可一開始就拿特例來探討，畢竟 interviewee 在前一個問題已有中等水準的表現
19:57: interviewee 宣稱不需要特別傳遞描述陣列空間的變數 (如 arr_size)，應該適度打斷，討論 C 語言函式呼叫的議題，畢竟光靠一個傳入的指標，該如何知道陣列具體的空間呢？

28:00: 既然 interviewee 宣稱完成程式碼，應有必要的檢驗和討論，例如極端狀況是否考慮到、變數命名是否清晰，和後續改進

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 語言：技巧篇的「不夠謹慎的 ARRAY_SIZE 巨集」一節

50. Pow(x, n) 之所以列為中等難度，就在於有很多討論，應該引導 interviewee 思考。

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 的檢討:

在遠距面試的場合中，通常鏡頭會採正面且不會拍到鍵盤，有效的手勢範圍很窄，不該太依賴手勢，相反的，儘量用 REACTO 步驟的 Example，打字並說出輸入/預期輸出案例的「特性」
對話中舉例的測試資料 (或某一組輸入/預期輸出) 可敲入到指定的作答內文中，如 Google Docs，這樣在用英語解說時 (畢竟不是母語，說越多，錯誤就越多)，可說得少一點
以 226. Invert Binary Tree 來說，既然一開始提到想用遞迴，可以先寫下 function prototype 和遞迴呼叫的本體，隨後再補上終止條件和細節，這樣程式碼和思路探討會更一致
用 Google Docs 撰寫程式碼，會發現程式碼縮排不好顧及，現有影片的程式碼在視覺上過於緊湊。其實書寫程式碼時，不用嚴格依據實際程式碼讀取的順序，反而可寫下「對應到 REACTO 步驟的 Approach 的關鍵程式碼」的函式呼叫、變數指派，或者迴圈主體
06:12: 儘量撰寫簡潔的程式碼，例如 struct btree *temp; temp = root->left; 可改為 struct btree *tmp = root->left;。不要小看只是幾個字元的差距，因為在 Google Docs 中，程式碼的縮排都要自己處理，越少換行或者非必要的 tab 按鍵，都可避免說話和程式碼撰寫間的落差
07:26: 以 226. Invert Binary Tree 來說，說明用 stack 操作改寫原本遞迴程式的手法，應該要在實際撰寫程式碼之前，跟 interviewer 討論，畢竟這手段可能不符合 interviewer 的期待
原本已撰寫的程式碼可適度保存，例如用複製貼上，放在 Google Docs 某處，畢竟 interviewer 可能會要求對照
撰寫非遞迴版本的實作，過多的滑鼠移動和區域反白，會影響 interviewer 視覺焦點，而且途中反覆在鄰近的程式碼間切換並變更程式碼敘述，佔用可觀的時間
16:41: "array" 的發音是 [ə-ˈrā]，要留意。中英交錯時，如果發音不精準，容易讓 interviewer 誤會，尤其還要將變數名稱納入時，因此儘量避免非必要的中英詞彙交錯
00:43: 二元樹的用語是「子節點」，而非「兒子」，而且反轉二元樹是操作 sibling 的順序
00:53: 二元樹舉例時，應善用 tab 來區隔各節點
02:08: 程式碼撰寫儘量精簡，例如可改為 struct TreeNode { struct TreeNode *left, *right; } 注意 bintree 的命名，從而避免跟 B-Tree 混淆。星號 (asterisk, 即 *) 作為指標的宣告一部分，應靠向變數名稱，這樣不僅可寫出更緊湊的程式碼，也能避免混淆。在 03:36 誤將 binary tree 講成 B-Tree，也該改進
02:20: 手勢在演講過程有強化表現的效果，但在面試場合，由於鏡頭方位，手勢就需要調整，或者儘量改進說話的資訊量
03:01 時間複雜度有很多表示法，可見 Complexity：Asymptotic Notation，這裡既然是討論 big-O，那就該清楚讀出來。且，除了時間複雜度，尚有空間複雜度，特別是之前已提過要用遞迴實作，這就是該著墨之處
04:15: 之前提到打算用遞迴實作，可緊接著撰寫函式原型 (function prototype) 和遞迴呼叫的程式碼，這樣一來對話更緊湊，二來思緒和程式碼對應也更好
18:18: 解釋 Approach 時，應該順道解釋為何可滿足題目的 $O (\log n)$
23:33: == 讀作「等於」即可，也可說「判斷是否相等」，簡潔的讀法習慣有助於英語表達
25:23: 舉例應該獨立於程式碼列表

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

226. Invert Binary Tree

測驗說明與問答

Invert Binary Tree with recursion

Invert Binary Tree with iterative

35. Search Insert Position

測驗說明與問答

binary search

50. Pow(x, n)

測驗說明與問答

Pow(x, n)

總體初步檢討