# 2022 年 「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2022-homework1)」作業二
>貢獻者: 盤子 Plate Man
>[全面試影片](https://youtu.be/Rd3Oxo5lNsQ)
🤵：interviewer 😀：interviewee
# 222.[Count Complete Tree Nodes](https://leetcode.com/problems/count-complete-tree-nodes/)
[第一題面試影片](https://youtu.be/Rd3Oxo5lNsQ)
# 測驗說明與問答
🧍：同學午安，我是熊貓，歡迎參加這次面試，接下來面試與面談將會是我與你討論，再正式進入前，有什麼問題想要詢問的嗎?
🙂：了解，您好，我是盤子，接下來想與您詢問今天面試的流程。
🧍：好的，待會我會傳送今天的題目，並會跟你說明題目等等。
🙂：了解，那想請問使否有IDE限制與其他的限制內容呢？
🧍：在這部分我們並沒有什麼限制，可以使用您所習慣的即可。
🙂：好的，那沒什麼問題了。
🧍：了解，那就開始吧，首先先來跟您說明一下題目。
🧍：那這個題目希望你可以幫我計算一下這個二元樹的總共的節點，那我們給你的二元樹一定是 Complete Tree，那要注意的是，希望你可以計算這個數量，但是時間複雜度有所限制，不要全部節點都訪過，你必須設計一套方法，將時間複雜度小於 O(n)，比如說有一個二元樹是 1, 2, 3, 4, 5, 6，那就必須回傳 6 這個答案，也可能會有空值給您，那就回傳 0 。
🙂：好的，謝謝熊貓先生的講解，目前了解題目的目標了，那想另外請問是否有其他題目底下沒說到的例外事件要處理呢，比如說是否有非 Complete Tree 傳入呢？
🧍：這題的要求化，樹一定是 Complete Tree ，並且數量會在 0, 5 * 104 之間，請問還有其他問題嗎。
🙂：目前沒有其他問題了。
🧍：好的，那麻煩可以跟我說明一下，這題的想法以及二元樹的兩種說明呢。
🙂：沒問題，那我使用 ipad 來做繪圖說明，我分為三種，首先先來講解 Perfect Tree，他會一定是完整的樣子，每個node都一定有兩個小孩，那在 Complete Tree 則相對沒這麼完整，但也保證每個節點都是0-2個孩子，並且一定是從上到下，從左到右生成節點，剩下就是其他沒有限制的二元樹。
🧍：OK, 那這部分說明的很不錯，也很清楚，並且搭配圖來說明，那目前你有什麼想法來解決這題呢。
🙂：目前想法是是可以從層數下手，因為這次的需求是要計算 Complete Tree，因此可以不用完整訪過，從層數下手來做計算，這個原因是因為 Perfect Tree 可以用公式 x^(level-1)-1 的方法去算出數量，在這個情況下，可以分為兩種 Case ，一種是左邊子二元樹是 Perfect Tree，右邊子二元樹不是，則可以左邊子二元樹用公式計算，右邊則繼續遞迴往下找，反之則相反，這樣計算量可以大幅降低。
🧍：好的，那麻煩幫我實際撰寫程式，並說明，那另外與您說明，在撰寫程式的時候，並不用從建置二元樹開始，你就假設已經二元樹是一個 Struct ，並且以建立完成，你只要撰寫一個函式，可以讓我們傳送這個 Struct 給你就可以了。
🙂：好的，那我使用 VScode 撰寫，如有看不清楚等問題，再煩請您與我告知。
```c=
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int leftmost(struct TreeNode *root)
{
int lv = 0;
while (root != NULL) {
lv++;
root = root->left;
}
return lv;
}
if (left_level == right_level)
{
count += (level*level)-1;
count += NodeCounter(root->right, right_level);
}
else
{
count+= NodeCounter(root->left, left_level);
count+= (right_level*right_level)-1;
}
int countNodes_helper(struct TreeNode *root, int level)
{
if (root == NULL)
return 0;
int leftmost_lv_lchild = level - 1;
int leftmost_lv_rchild = leftmost(root->right);
int count = 1;
if (leftmost_lv_rchild == leftmost_lv_lchild) {
count += (1 << leftmost_lv_lchild) - 1;
count += countNodes_helper(root->right, leftmost_lv_rchild);
} else {
count += countNodes_helper(root->left, leftmost_lv_lchild);
count += (1 << leftmost_lv_rchild) - 1;
}
return count;
}
int countNodes(struct TreeNode *root)
{
int level = leftmost(root);
return countNodes_helper(root, level);
}
```
🧍：好，那這樣解法還不錯，那待會我們會傳給您一個網址，是我們公司所使用的程式練習平台，再麻煩您幫我把題目上傳到上面，確認這個程式的正確性與速度。
🙂：好的，這次是這題的解法與答案。
🧍：了解，那這樣的方法的時間複雜度是多少呢。
🙂：因為是遞迴，那時間複雜度是 O(log^2 N)。
🧍：OK, 那我想另外請問說，如果今天要思考到多人專案，如果別人亂塞二元樹給它，那你會怎麼處理才不會影響到整體開發呢？
🙂：這部分以前在多人專案中有遇到過，那這部分我的習慣是會是回傳一個不可能或是不合理的答案，
以這個專案為例，他是不可能會出現負數，那我就會習慣回傳 -1 回去，
並撰寫道 Docs 中，讓使用此功能的人看到後可以有所緊惕，且如果使用其他如 Go 等其他語言，可以在回傳中塞入 Error Message, 告知使用者錯誤，這個方法我認為可以有效降低錯誤使用的發生機率，以上是我以前的經驗與方法。
🧍：了解，所以你也會常使用其他語言來開發對嗎？
🙂：對的，因為目前主要在撰寫的系統等需擴充性的專案，所以蠻長使用 Go 與其他語言共同開發來完成專案。
🧍：好的，那這次面談蠻愉快且蠻不錯的，謝謝你這次來面試，今天面試到這邊謝謝。
🙂：也謝謝您，感覺與您的面談。
## 自我檢討
- 針對 interviewer 的檢討:
- 在說明題目上，蠻容易會卡詞，可能會造成面試者觀感不佳。
- 可以先讓面試者看完題目再說明。
- 面試者打完題目後，可以依照程式碼來提問。
- 會有要求忘記說明
- 針對 interviewee 的檢討:
- 圖解說明不錯，但是要注意不要亂畫或是用雷射筆要注意。
- 在說明解法時，說明方式還是有時候會卡，且有時邏輯上會說明怪怪的，任然需要磨練
- 在打 code 的時候，有時候會詞不達意。
## 簡介 第一次作業簡介與心得
- 同學互評
- 許多同學在這次作業中，常使用到面試官一詞，在這部分容易造成上對下的不平等的感覺。
- 有些同學在一開始面試的時候，就直接進入到主題，建議可以雙方先互相介紹且說明，這次的面試流程與問題，在進入到解題階段。
- 在面試主持人說明題目時，可以多加入題目畫面做說明，可以比較具象化說明，協助面試者理解題意
- 面試者在看到題目時，可以先多詢問一些問題，比如是否有什麼限制等等，除了可以降低在解題中雙方的誤會外，也可以讓面試主持人感受到面試者思考的層面的廣度。
- 心得
- 在第一次與第二次作業之間，有同學與老師協助對第一次作業做評比與建議，使我在這季第二次的面試環境中更好上手，且可以對於許多之前沒注意到的細節做補充，且在這幾次老師的建議，比如不要叫做面試官，在解圖時可以適時的丟出以前的開發經驗的等等，都十分的幫助!相信在接下來的課程中，能夠對於自己的面試方式可以更上一層樓。
Sign in with Wallet
Connect another wallet