Try  HackMD Logo HackMD

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

貢獻者: 德米安 Demi
video

題目不要一直寫，重點是作法
增加和主管討論的時間
留白時間很討厭
問一些關於題目相關的問題
定義function要精準不能亂扯
binary tree
cache friendly binary search

🧔：interviewer 👶：interviewee

226. Easy Invert Binary Tree

參考網址：

🧔：想請先請Demi介紹Binary tree，他有什麼好處、缺點與應用。
👶：a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. 他有 linked list 的好處，讓空間配置更自由，不用如 array 宣告連續的空間，並產生空間浪費的情況，然而又改進了 linked list 的問題，讓尋找節點更加容易，不須一個一個拜訪確認。缺點是如果沒有經過好的維護的話，會產生 imbalance tree 的問題，高度不一。那 Binary tree 有許多不同的變形，如最有名的紅黑樹，紅黑樹有很好的 tree depth 的維護方式與複雜度優化，那 linux kernel 有大量地使用紅黑樹。
🧔：那接著請Demi實作binary tree的操作。請同學看到Doc的第一題：這邊有一個Tree，那想請你針對Tree每一個子節點做sibling交換。
👶：好的那我們針對 Tree 的 sibling 做交換，比如說：







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

👶：那我剛開始想到的方法是用遞迴的方式，如果有子節點時先向下執行函數，把他看成是 subtree 來處理。結束條件是到達葉節點後回頭把每個 subtree 的 child siblings 做交換。依此完成 divide and conqueer 直到根節點完成交換後即結束全部的遞迴函數。

Invert Binary Tree with recursive

















/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct tree * invertTree(struct tree * root){
    if(!root) return NULL;
    struct *l = invertTree(root->left);
    struct *r = invertTree(root->right);
    root->left = r;
    root->right = l;
}

🧔：recursive的作法可能在特定情況下會出狀況，想請Demi想一下在各種情境的複雜度，還有可能遇到的問題？
👶：
🧔：那想請問有沒有改進的方法呢？
👶：我的想法是可以透過一個linked list的stack對我們要做invert的node做紀錄，將搜尋到的node紀錄在stack中，再逐一從stack中的node做invert，以使用iterative達到模擬recursive的做法。
🧔：不過這樣做還是使用stack吧？
👶：確實，不過recursion累積的是function type，所以相比起來用stack模擬的話是累積pointer type，應相比會小一些。

👶：如果我們把存起來的資料結構變成 queue 的方式，用廣度優先搜尋 (BFS) 做的話，是可以避免 stack 囤積無法釋放的狀況。























/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct tree * invertTree(struct tree * root){
    if(!root) return NULL;
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()){
        TreeNode* node = q.front(); q.pop;
        TreeNode* tmp = node->left;
        node->left = node->right;
        node->right = tmp;
        if(node->left) q.push(node->left);
        if(node->right) q.push(node->right);
    }
}

🧔：那剛剛有提到 recursion 可能會因為 imbalance tree 而導致 stackoverflow 的問題，那我想請 Demi 寫一個 function 去確認 Tree 的 max depth 是多少。

















/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int Max(int a, int b){
    return a>b?a:b;
}
int maxDepth(struct TreeNode* root){
    if(!root) return 0;
    return Max(maxDepth(root->left), maxDepth(root->right)) +1;
}

🧔：那延續這個 function ，最後驗證試試看這棵樹是不是 balanced tree。










boolean isBalanced(*root){
    if(!root) return true;
    if( abs(maxDepth(root->left)-maxDepth(root->right)) >1) return false;
    else{
        if(!isBalanced(root->left)) return false;
        if(!isBalanced(root->right)) return false;
    }
    return true;
}

35. Easy Search Insert Position

參考網址：704. Easy Binary Search
參考網址：35. Easy Search Insert Position
參考網址：33. Median Search in Rotated Sorted Array

🧔：請看第二題，我首先提供一個 sorted vector<int> nums 和一個 int target ，那如果這個 target 在矩陣中則回傳給我索引值，如果沒有在裡面的話回傳給我-1。

    [0,1,2,4,5,7] 
    target = 5, return 4
    target = 3, return -1

👶：這一題最直覺的方法是使用Sequential Search的方式一個一個找值，然而這個方法的時間複雜度為

O(n)。那在此我們可以用Binary Search的方式來讓時間複雜度降在
O(log(n))內。











int search(vector<int>& nums, int target) {
    int start = 0 , end = nums.size()-1;
    while(start <= end){
        int index = (start + end)/2;
        if(nums[index] > target) end  = index -1;
        else if(nums[index] < target) start = index +1;
        else return index;
    }
    return -1;
}

🧔：很好，那我這邊做一點變化，請同學另外複製這一段的程式碼，我現在希望你可以回傳給我此target在array的index，若target不在array中，則告訴我如果target插入array時，他的index是多少？

    [0,1,2,4,5,7] 
    target = 5, return 4
    target = 3, return 3

👶：那這一題是要讓我們進行search and insert的動作，我們一樣是透過 binary search 來找要插入的 index ，在最下面不再是 return -1 而是要插入的 index 值。所以我們找到 最後得知沒有空位後，在這裡開始判定應該插在 start 前面還是後面，這樣就完成了。

Search Insert Position












int searchInsert(vector<int>& nums, int target) {
    int start = 0, end = nums.size() - 1;
    while(start<end){
        int index = (start+end)/2;
        if(nums[index] > target) end = index-1 ;
        else if(nums[index] < target) start = index+1 ;
        else return index;
    }
    if(nums[start] >= target) return start;
    else return start +1;
}

🧔：好的那最後面來一點大的變化，請同學先把程式改回 binary search 。那現在我會將 vector 內的值做前後挪移，比如我貼給你這個案例：我們可以看到這是一個被挪移調整過 k 次的矩陣，這些矩陣如果相反 k 次也可以恢復原本的 sorted array 的形式。那接著我 input 的 vector 也會是這樣的狀態，只是你不會知道我調整的次數為何？那我希望你幫我做 searching 的任務。如果有值回傳 index ，沒有的話回傳 -1。

    k = 0 [0,1,2,3,4,5,6,7]
    k = 2 [6,7,0,1,2,3,4,5]
    k = 4 [4,5,6,7,0,1,2,3]
    k = 6 [2,3,4,5,6,7,0,1]

👶：最直覺的做法就是，先用 binary search 找出總共挪移了幾次，找到值過後拿 nums[0] 作為 index 與 target 做比較，以此切開成前後兩半，接著繼續往這兩個區間做 binary search。

🧔：這樣做的話需要兩次 binary search 而且如果在挪移次數 k = 0的時候，似乎需要花很多時間搜尋。同學再想一下是不是有更好的方法，提示一下，可以從觀察 k = 2 and 6 在如果只做一次 binary search 的時候會遇到什麼情況。

Search in Rotated Sorted Array

























int search(vector<int>& nums, int target) {
    int start = 0, end = nums.size()-1;
    while(start<=end){
        int index = (start+end)/2;
        if(nums[index]>target){
            if(nums[start]<=nums[index]){
                if(nums[start]<target) end = index -1;
                else if(nums[start]>target) start = index +1;
                else return start;
            }
            else end = index -1;
        }
        else if(nums[index]<target){
            if(nums[end]>=nums[index]){
                if(nums[end]>target) start = index +1;
                else if(nums[end]<target) end = index -1;
                else return end;
            }
            else start = index +1;
        }
        else return index;
    }
    return -1;
}

第三次作業-他評

針對 interviewer 的檢討:

總結

  • 建議可以對 interviewee 的程式碼多做討論，不用馬上問問題
  • 後期講解有比前面順利

影片細節

  • 14:24 interviewee 寫錯，這時可以請 interviewee 檢查程式碼
  • 17:50 來自 interviewer 的善意
  • 28:00 可以跟 interviewee 討論一下 code 順便問能否寫個減少 if-else 判斷的作法
  • 28:10 講解的比前面順很多

針對 interviewee 的檢討:

總結

  • 整體來說回答的卡卡的，前面講話太多呃..，後面有比較順一點，建議錄影前可以先在心理多講幾次在錄
  • 擅用瀏覽鍵以及 ctrl, shift 可以大幅減少使用滑鼠的次數，寫程式看起來會更順暢，
  • 對 C++ 不熟悉，許多地方犯語法上的錯誤

影片細節

  • 00:48 有講對 Tree 的左右節點，改進第一部影片中的口誤
  • 02:38 沒有向 interviewer 多問些題目資訊
  • 02:43 函數的原型要寫成 struct TreeNode* invertTree(struct TreeNode *root) 才符合註解提供的原型
  • 03:36 建議按向上鍵將游標移動到函數 invertTree，再用 ctrl + shift + 左 or 右，把 invertTree 選取起來複製，看起來會更流暢
  • 03:49 此時游標在最尾端，這時候用 shift + home 選取整行再複製，接著按 enter 到下一行也不必用 tab 縮排，直接貼上會更順暢
  • 06:07 有露出眼睛很好，可以從眼神讀出喜怒哀樂，不過回答時看著 camera 會更好，左右觀看會讓人覺得在看稿子。
  • 07:01 時間複雜度不要講應該，這樣會讓人感覺你不確定或是在用猜的
  • 07:16 到達 leaf 的地方，沒有最 leaf 的地方
  • 07:35 除了演算法一般情況下的表現，還有補充 worst case 的情況
  • 08:48 很棒，巧妙的包裝把遞迴轉成迭代
    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →
  • 11:27 C 語言沒有原生的 queue，也沒有像 C++ 有 Generics 的特性，如果需要用到 C++ 應該先跟 interviewer 討論說可不可以使用 C++ 來實作，或是自定義結構跟函數當作 queue 的操作，像是 q_push(q, val) 來當作把 val 推入 queue 裡面。
  • 12:00 我當作從 11:27 開始是用 C++ 實作，那麼 q.empty 是錯誤的， queue.empty 是函數不是屬性，要寫成 q.empty() 才對
  • 13:55 沒有為 q.push(node->left) 跟 q.push(node->right) 補上分號
  • 14:13 建議對程式碼作適當的排版，閱讀的人會比較舒服


















struct TreeNode* invertTree(struct TreeNode *root) {
    if(!root)
        return NULL;
    
    queue<struct TreeNode*> q;
    q.push(root);
    
    while(!q.empty()) {
        struct TreeNode *node = q.front();
        q.pop();
        // swap
        if(node->left)
            q.push(node->left);
        if(node->right)
            q.push(node->right);
        
    }
}
  • 14:21 如果是用 C++ 那就別 return NULL 而是 return nullptr，這樣寫起來才有 C++ 的風格
  • 14:23 有註解要 swap 但是沒有寫 swap(root->left, root->right)，所以程式是錯誤的，變成迭代版的做廣度優先走訪，而 interviewer 也沒有說是錯誤的
  • 17:08 擅用瀏覽鍵以及 ctrl, shift 等等按鍵可以快速複製、游標移動到頭尾，減少用滑鼠的卡噸
  • 17:09 建議分別用 left, right 來存入高度，再 return Max(left, right) + 1，這樣版面會更美觀，可讀性也比較高








int maxDepth(sturct TreeNode *root) {
    if(!root)
        return 0;
        
    int left = maxDepth(root->left);
    int right = maxDepth(root->right);
    return max(left, right) + 1;
}
  • 17:10 有解釋為何 return 0，但沒有解釋為何 +1
  • 17:30 可以的話還是從容的講完
  • 21:07 這時可以把滑鼠移動到 int Max(int a,int b) 那一行，在按住 ctrl + shift + end 選取全部，接著再用 ctrl + shift + < 或 ctrl + shift + > 來調整字體大小
  • 22:03 可以再問一下 interviewer 是否會傳入空陣列、陣列的的數值範圍、陣列的長度範圍
  • 23:20 建議時間複雜度留給 interviewer 問比較好
  • 27:38 別說大概這樣，建議改說 這就是利用 binary search 尋找索引的方式 之類的話
  • 27:45 可以在找看看有沒有少一點 if-else 的作法，這不利於 branch prediction
  • 27:58 可以省略大概
  • 38:27 不錯的作法，省略掉一部份的程式碼，流下關鍵的 code 跟範例，看起來好多了
    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →
  • 39:38 似乎忘記將 interviewer 給剪進來討論 interviewee 的程式碼
Last changed by 
 
sysprog
System Software Programming
525
Published on HackMD