Try   HackMD

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

貢獻者: 德米安 Demi
video

🧔：interviewer 👶：interviewee

226. Invert Binary Tree

影片: 00:19

測驗說明與問答

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







graphname



A

1



B

2



A->B





C

3



A->C





D

4



B->D





E

5



B->E





F

6



C->F





G
NULL



C->G





H

1



I

3



H->I





J

2



H->J





M
NULL



I->M





N

6



I->N





K

5



J->K





L

4



J->L

👶：另外也必須特別考量到空集合的狀況。
👶：我剛開始想到的方法是用遞迴的方式，以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

35. Search Insert Position

影片: 16:38

測驗說明與問答

🧔：在第二題我會提供一個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。

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，即是

xn。
👶：這一題要實作
xn的function。那在這一題中有幾個需要注意的部分，比如n的正負。如果n為正，那就是用加乘的方式處理，若為負則要做加除。而一些情況下可以免去計算直接回傳：比如
x=0,1 return 0,1n=0  return 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;
}

延伸閱讀: LeetCode 50. Pow(x, n)

總體初步檢討

針對 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) 存在嚴重的錯誤
  • 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 的檢討:

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