2022 年「資訊科技產業專案設計」作業 1

模擬面試錄影(漢)
模擬面試錄影(英)

: interviewee : interviewer

606. Construct String from Binary Tree

說明題目

: 考慮一棵 Binary Tree, 其節點結構定義為:

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode*left, TreeNode*right) : val(x), left(left), right(right) {}
};

請使用 Preorder Traversal 的方式建構出一個只含整數以及括號的字串，並且刪除不影響二元樹與字串間一一對應關係的空括號對。

範例:

output: "1(2(4))(3)"

回答問題

: 看起來的意思應該是同樣深度的節點必須有同樣層數的括號，如範例中的2及3深度皆為1，因此外面有一層()，而4的深度為2，因此往外數共有兩層()。
: 是這個意思沒錯。
: 我目前想到的作法是由root出發，按照 DFS 的順序依序走訪各節點，先儲存節點的value，並且在走訪左子點之前加入(，若該節點已無左子點則先加上)再試著尋找該節點的右子點，同樣地，在儲存右子點的value之前先加入(，接著重複以上步驟。
: 好的請你試著以code方式呈現你的方式。

string tree2str(TreeNode* root) {
    string ans = to_string(root->val);
    if (root->left){
        ans += "(" + tree2str(root->left) + ")";
    }
    if (root->right){
        ans += "(" + tree2str(root->right) + ")"; 
    }
    return ans;
}

: 此方法會先拜訪左子點後才會走訪右子點，現在，若一個父點只有右子點而沒有左子點的話，請在輸出右子點的value之前先輸出一對空括號()。
: 對於此問題我的解決方法是在每次走訪右子點的時候優先檢查該父點有無左子點，若無則將()加到輸出的字串中。

string tree2str(TreeNode* root) {
    string ans = to_string(root->val);
    if (root->left){
        ans += "(" + tree2str(root->left) + ")";
    }
    if (root->right){
        if (!root->left) ans += "()"; 
        ans += "(" + tree2str(root->right) + ")"; 
    }
    return ans;
}

1008. Construct Binary Search Tree from Preorder Traversal

說明題目

: 給定一個整數陣列，其表示的是一棵二元搜尋樹(Binary Search Tree)的 Preorder Traversal，請你以如同上題的節點結構重新建構出此BST。

回答問題

int index = 0;
TreeNode* build(vector<int>& preorder, int min, int max){
    if(min>max){
        return NULL;
    }
    TreeNode* root = new TreeNode(preorder[index++]);

    int find_rchild;
    for (int i=min ; i<=max ; i++){
        if (preorder[i] > root->val){
            find_rchild = i;
            break;
        }
    }
    root -> left = build(preorder, index, find_rchild - 1);
    root -> right = build(preorder, find_rchild, max);
    return root;
}
TreeNode* bstFromPreorder(vector<int>& preorder) {
    return build(preorder, 0, preorder.size()-1);
}

1689. Partitioning Into Minimum Number Of Deci-Binary Numbers

Question

: Given a string n that represents a positive decimal integer, return the minimum number of positive deci-binary numbers needed so that they sum up to n.
A decimal number is called deci-binary if each of its digits is either 0 or 1 without any leading zeros.

Answer

int minPartitions(string n) {
    int ans = 0;
    for(int i = 0 ; i< n.length() ; i++ ){
        int ithnum = n[i]-'0';
        if (ithnum >ans){
            ans = ithnum;
        }
    }
    return ans;
}

初步檢討

Interviewer

• 對於 Interviewee 的答案沒有深入的追問或討論，少了很多互動，也失去考驗面試者優化程式的機會。
• 解決問題的解決是 solve 不是 console…

Interviewee

• 對於 Constructor 的概念不夠熟悉，導致講解不清，冗言贅字過多。
• 說話有點含糊，字跟字會連在一起。
• 用純文字編輯器的排版還不夠熟練。
• 打字速度太慢而且還一直打錯字。
• 很常一說話就沒辦法同時打字。
• 第二個問題的 index 忘記加變數型態 int。
• 一些專有名詞經常口誤。
• 問題回答完之後對於解決方法的主動探討太少(e.g. 時空間複雜度、驗證程式碼的正確性)
• 英文太爛。

第二次作業 - 他評 01

interviewer 優點

• 0:05 以「我想透過幾個問題來了解你的想法」是很有禮貌且得體的開場。
• 9:04 "606. Construct String from Binary Tree" 這道題目就算直接敘述 LeetCode 的題意也不容易，interviewer 懂得循序漸進地加深難度，一開始只要走訪一個子節點前後要加括號；interviewee 回答正確後，再說明若考慮左節點為空但右節點存在時，會無法從輸出字串判別是子節點是左或右，因此需要為這樣的情況增加一組括號。引導方式很有效率。

interviewee 優點

• 13:58-15:52 聽完 interviewer 對重建二元樹先序走訪的要求後，落實 #REPEAT 技巧，以自己對二元樹結構的理解重新 trace 一次 example，並提到關鍵字「輸出的二元樹會是唯一的」，表達自己有先一步考慮到二元樹的特殊性質，體現思考縝密及嚴謹的態度。

interviewee 可改進的地方

• 2:20 建議講解時滑鼠游標盡量避免花式移動，避免造成 interviewe 分心。
• 16:40-17:22 說明 Function 的功能及演算法大致步驟後 (約為影片17:22處)，建議可於函數上方或下方簡單註解這個 Function 的主要功能或接下來要實作的步驟，可以方便 interviewer 跟上你的 code。
• 34:25 建議 code 寫完要用 example trace 一遍，以確切證明 code 的正確性。
• 37:15 "1689. Partitioning Into Minimum Number Of Deci-Binary Numbers" 這個題目相當詭異，其實用第一個 example 來分析即可，至多再舉 "98" 為例。若是我會這樣分析：
  (於 docs 寫出下方陣列)，並說明 Obviously the digit value corresponds to the number of deci-binary needed, as same case as a decimal to unary numeral system (如同十進位轉一進位), when the digit is 9, then the deci-binary of the other digits will be its factor(因數).

   32  98
1: 11  11
2: 11  11
3: 10  11
...
8:     11
9:     10

額外建議

蛋花湯同學口齒清晰、節奏也不錯，但影片以 1 倍速播放時卻讓人感到語速與畫面略慢，這有可能是螢幕錄製軟體、或是 Google docs + 視訊軟體 + 網路延遲等因素所造成的結果。建議同學錄製自我面試影片時，可以用手機同步錄音，並比較看看自己的語速是否有受軟體影響，進而考慮真實面試時是否要提升語速 (若實際語速比影片快，應該就不用擔心此問題)。

1689. (C 語言版本)

比 Easy 還簡單的 Medium，原以為要考 bitwise，但結果用不上，不知道這個題目真正想考的東西是什麼? 但顯然只要找到字串中最大 digit 數值的字元，其數值就是 string 最小數量的 positive deci-binary number。#greedy?

# define max(a,b)       \
({__typeof(a) _a = (a); \
  __typeof(b) _b = (b); \
  (_a > _b) ? _a : _b;  \
})

int minPartitions(char *n){
    int max_num = 0;
    for (int i = 0; i < strlen(n); i++)
        max_num = max(max_num, n[i]-'0'); 
    return max_num;
}

第二次作業 - 他評 02

Interviewer 優點

• 有在針對一開始題目，再延伸相關類型的題目。

Interviewer 可改進地方

• 00:30 開始說明前序排列的順序，interviewer 只用鼠標搭配口頭說明，建議可以直接打在 Google docs 上面，會讓 Interviewee 可以快速理解意思。
• 04:30 Interviewer 説：「請你用 code 實做看看」，這部分可能語句使用的怪怪的。
• 09:56 Interviewer 在說明假如一個節點只有右子點的情況，希望在左子點的時候先加入一個 ()，如果這裡能夠再畫一張舉例圖會讓 Interviewee更清楚了延伸題目。
• 再 interviewee 寫出他的想法後，沒有對 Interviewee 的程式碼作出評論。

Interviewee 優點

• 有重複提問 Interviewer 的問題，寫程式碼和同時講解的過程是很流暢的，不會拖泥帶水
• 在 10:44 開始寫出自己想法，這裡的邏輯非常清晰，能讓 Interviewer 清楚了解你的想法。
• 13:57 一開始就針對「像這樣的順序，輸出的二元搜尋樹，是否為唯一。」能夠直接切入重點！
• 再寫完第二個題目後，有再重新 Trace code ，能夠讓 Interviewer 對你的邏輯更加清楚了解

Interviewee 可改進地方

• 02:19 Interviewee開始重複 Interviewer 的題目，建議若要用鼠標說明，停在一個點就好，不需要一直畫圈圈，會顯得很雜亂不知道在說哪裡。
• 26:15 Index 沒加變數型態。

第二次作業 - 他評 03

• 00:07 interviewer 在面試時應避免說：我是你今天的面試官，可以改說成：今天由我來主持這場面試之類的，避免造成不對等的關係
• 33:00 應避免低頭看的行為，可能會被誤會是在看小抄

優點

• 14:23 interviewee 有很明確地確認題目和自己的想法是否有衝突
• 在寫程式的時候也會用舉例輔助，讓思維更加清晰
• 寫程式碼有按照自己的思維去隨時增減，不會一開始就像被答案一樣都寫出來

第二次作業 - 他評 04

• 9:50 Interviewer在講解新功能時，因為圖跟假設的不一樣，很容易會搞混，可以再手畫一張新的圖來說明
• 15:12 先解釋了Preorder且BST可建構唯一樹，讚讚
• 23:39 第二題的程式部分，用begin, end來取代min, max我覺得可以更好的表達意思
• 30:54 寫完程式有做到自己Trace程式檢查錯誤，我覺得很棒
• 34:10 一開始沒有發現min > max的問題，並在trace過程中發現，可以讓面試者知道你有Debug的能力，我覺得是很好的展現
• Index = 0的部分，我覺得改成加在build內

TreeNode* build(vector<int>& preorder, int index, int min, int max)

並在bstFromPreorder填入0會比較好

TreeNode* bstFromPreorder(vector<int>& preorder) {
    return build(preorder, 0, 0, preorder.size()-1);
}

因為這樣就把index給包進這個function，而不用去宣告一個全域變數，我覺得會是比較好的寫法