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(logn)
  17. 23:33: == 讀作「等於」即可,也可說「判斷是否相等」,簡潔的讀法習慣有助於英語表達
  18. 25:23: 舉例應該獨立於程式碼列表