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

貢獻者: 秦谷底-Goody
video: 1, 2, 3
😎：interviewer
🙂：interviewee

104. Maximum Depth of Binary Tree

面試過程

😎：很高興您來參加今天的面談，在開始前有什麼要問的嗎?
🙂：過程中可以使用 C++ 的 STL 嗎?
😎：可以，還有其他問題嗎?
🙂：沒有。
😎：好，我來解釋一下今天要討論的問題。
😎：這個問題會給你一個二元樹的 root，請你找出這個二元樹最大的深度，二元樹深度的定義是根節點到葉節點的距離。
🙂：好，有一個二元樹，深度是 3。
😎：對。
🙂：再舉一個例子，當 binary tree 像是 linked list 的樣子，那深度就是節點個數。
🙂：整個二元樹的節點數量範圍是多少呢?
😎：大於等於 0，小於等於 10000。
🙂：所以會有 root 為 NULL 的情形?
😎：對。
🙂：了解，所以我們先來決定節點的內容，叫他 TreeNode，一個節點要有 value 以及左子右子。
😎：是。
🙂：因為節點數量不多，可以用遞迴的方式，遞迴需要決定遞迴關係和終止條件。從範例來看，3 節點最大深度是 3，左子樹最大深度是 1，右子樹最大深度是 2，可以觀察到一個節點的最大深度是左子右子最大深度較大者 + 1，中止條件是節點為 NULL 的時候，中止遞迴並回傳 0。
😎：好，你可以開始寫程式了。

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
 };
 
int maxDepth(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    } 
    int left_depth = maxDepth(root->left); 
    int right_depth = maxDepth(root->right);

    return 1 + max(left_depth, right_depth);
}

😎：如果程式的執行環境會限制記憶體的使用量呢?
🙂：可以用 level order 的方式，每經過一個 level，計數器就 + 1。
😎：可以試著實現你說的程式嗎?

int maxDepth(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    } 
    
    int res = 0;
    queue<TreeNode*> q;
    q.push(root);
    
    while(!q.empty()) {
        int one_level_size = q.size();
        res++;
        for (int i = 0; i < one_level_size; ++i) {
            TreeNode* node = q.front();
            q.pop();
            if (node->left != nullptr) {
                q.push(node->left);
            } 
            if (node->right != nullptr) {
                q.push(node->right);
            } 
        }
    }
    
    return res;
}

🙂：若二元樹節點個數為 n，兩種方式的時間複雜度是

$O(n)$，空間複雜度是

$O(n)$
😎：好，讓我們進到下一題。

---

2226. Maximum Candies Allocated to K Children

面試過程

😎：給你一維陣列 candies，candies 中的每個元素代表有一堆數量為該元素的值的糖果，另外整數 k 代表有 k 個人要分糖果，每個人拿到的糖果數量相同，題目限制是每個糖果堆可以分成小的糖果堆，但糖果堆之間不能合併，你要計算每個人最多可以拿到幾顆糖果。
😎：以這個例子來說，8 可以分成 5 和 3 個一堆，6 可以分成 5 和 1 個一堆，共有 3 堆 5 個糖果可以分給 3 個人，答案是 5。
🙂：好，所以我會拿到一維陣列，代表糖果堆和對應的糖果數量，要最大化 k 個人拿到的糖果數量，糖果堆不能合併，每個人都要拿到相同數量的糖果。
🙂：再舉個例子如下:

candies = {10,15,20,25}
k = 3

🙂：此範例的答案應該是 15，20 個糖果可以分成 15 和 5 個一堆，25 個糖果可以分成 15 和 10 個一堆。

candies = {10,15,15,5,15,10}
k = 3

🙂：有 3 堆有 15 個糖果，每人最多拿到 15 個，這樣的理解有錯誤嗎?
😎：沒有。
🙂：一樣的糖果堆，現在要分給 6 個人，因為糖果總共有 10 + 15 + 20 + 25 = 70 個，一個人最多可以分到 11 個，但是糖果堆不能合併，所以答案不會大於 11 個。
🙂：可以把 candies 拆成下面這樣。

candies = {10,10,5,10,10,10,10,5}
k = 6

🙂：答案是 10。
😎：Ok。
🙂：目前想到最直覺的方式是用 greedy 的方式，假設每人拿到 x 顆，陣列每個元素都去除 x，就知道能不能分給 k 個人，另外 x 的上限是糖果總和除以總人數，所以一個方法是可以從 0 到上限每個都去嘗試，就可以得到答案。
😎：好，那你認為有什麼方法可以加快在 0 到上限這個區間的搜尋時間呢?
🙂：可以用 binary search，假設分成 x 一堆，發現堆數太少，那分成 x + 1 一堆時堆數一定太少，如果分成 x 一堆時堆數足夠，代表答案至少是 x。所以可以設定 binary search 上下界分別是 0 和總糖果除以總人數。
😎：是的，還有什麼問題嗎?
🙂：請問 candies 的範圍區間?
😎：介於

$1$ 到

${10}^5$
🙂：好，那陣列元素的範圍區間是什麼?
😎：介於

$1$ ~

${10}^7$，另外 k 會介於

$1$ ~

${10}^{12}$。
🙂：如果只有 1 個人分糖果，他最多會拿到每堆糖果乘上糖果堆的數量，也就是

${10}^5$ *

${10}^7$，是

${10}^{12}$，超過 int 範圍，所以回傳值要用 long long。
😎：是的。
🙂：目前沒有其他的疑問了。
😎：好，你可以開始寫程式。

註記: 變數區間應為閉區間。

程式碼

long long maximumCandies(vector<int>& candies, long long k) {
    long long left = 0, right = accumulate(candies.begin(), candies.end(), 0LL) / k;
    while (left < right) {

        // candies = {1, 2}, k = 1 (output = 2)
        // l = 0, r = 3, m = (0 + 3) / 2 = 1
        // l = 1, r = 3, m = (1 + 3) / 2 = 2
        // l = 2, r = 3, m = (2 + 3) / 2 = 2
        // l = 2, r = 3,........

        long long mid = (left + right + 1) / 2, piles = 0;

        for (int& candie:candies) {
            piles += candie / mid;
        }

        if (piles >= k) {
            left = mid;
        }
        else {
            right = mid - 1;
        }
    }
    return left;

}

🙂： 若 candies 元素個數為 n，時間複雜度是

$O(n\log n)$，空間複雜度是

$O(1)$
😎：你覺得程式還有什麼地方可以優化呢?
🙂：bottleneck 會在計算可以分成多少個 mid 為一堆的糖果堆，但糖果堆之間不能合併，目前也想不到有什麼方法比 binary search 快。
😎：好，我了解了，我也認為這個解法不錯，進到下一題。

---

242. Valid Anagram

面試過程

😎：Next question is about anagram.
😎：An anagram is a word formed by rearranging the letters of another word. For example, the word "listen" can be rearranged to word "silent".
😎：Given two strings, determine if they are anagrams.
🙂：So, "listen" and "silent" are considered to be anagram because the letter occurence of "listen" and "silent" are same. "rat" and "car" are not because apparently "rat" has no letter c.
😎：Yes.
🙂：Is it case sensitive?
😎：Just consider that there are only lowercase letters.
🙂：Ok. The most intuitive idea I think is to count the letter occurrences in each word separately, and then compare the occurrences of a to z between two words.
🙂：If the letter occurrences of each word is same, we can say they are anagram, otherwise they are not anagram.
😎：Yes.
🙂：What are the lengths of the two strings?
😎：The length of both strings is greater than or equal to 1 and less than or equal to 50000.
🙂：So the first step is to use two arrays count1 and count2 to count the letter in word s and word t respectively, and then compare the number of occurrences letter by letter, if there is a difference between two word, return false, otherwise return true.
😎：Ok. I think you can start writing the program.

程式碼

bool isAnagram(string& s, string& t) {
    vector<int> count1(26, 0), count2(26, 0);
    if (s.size() != t.size()) {
        return false;
    }
    for (char c:s) {
        count1[c - 'a']++;
    }
    for (char c:t) {
        count2[c - 'a']++;
    }
    for (int i = 0; i < 26; ++i) {
        if (count1[i] != count2[i]) {
            return false;
        }
    }
    return true;
} 

🙂：The time complexity is

$O(length(s)+length(t))$ because we need to check every letter in string s and string t.
the space complexity part is

$O(1)$ because the size of the count array is fixed at 26.
😎：Do you think there's any way to optimize your program?
🙂：Yes, when two words are of different lengths, it means they cannot be anagrams.
🙂：And we can modify the following two for loop, beacuse the length of two string here are same, it can be merge to a single for loop. Can I update the code?
😎：Sure.
😎：Ok, any more idea?
🙂：Let me think, it can be done with a single array, letters appearing in s then the letter occurrence + 1, appearing in t then letter occurrence - 1, if all elements in count array are zero, means the letter occurrences of each word is same, but there will be no way to confirm the letter occurrences in both two word.
😎：Ok, What if it's not just lowercase?
🙂：The size of the count array can be adjusted according to the range of the ASCII code, or we can simply apply a hash map where the keys are characters that correspond to counts.
😎：Sounds great. Could you help me to code the hash map solution out?
🙂：Yes

bool isAnagram(string& s, string& t) {
    if (s.size() != t.size()) {
        return false;
    }
    
    unordered_map<char, int> m;
    int n = s.size();
    for (int i = 0; i < n; ++i) {
        m[s[i]]++;
        m[t[i]]--;
    }
    
    for(auto& element : m) {
        if(element.second != 0){
            return false;
        }
    }
    return true;
} 

🙂：The time complexity is

$O(length(s)+length(t))$ , and the space complexity is

$O(length(s)+length(t))$.

---

自評-初步檢討

• 語助詞太多 (那、就、應該、ok、and、so…)。
• 要定義清楚變數範圍
  • interviewer 不要用易混淆用詞，例如介於。
  • interviewee 需確定變數範圍是開區間還是閉區間。
• 統一用詞，例如 null 和空節點擇一。
• 確定演算法細節再開始寫，像是在 Maximum Candies Allocated to K Children 中， binary search 如何決定 mid 的部分。
• 需要習慣邊打字邊講解。
• interviewer 的回饋太少。
• 242. Valid Anagram 解法蠻直覺的，但還是要測試。

自評-改進方案

• 可以稍微停頓一下在講。
• 多練習。
• 從別人的面試影片中學習可以改進的地方。

---

他評-01

interviewer

優點

• 題目解釋清楚
• 和interviewee有良好的互動

可改進之處

• interviewer可以將公司遇到的問題帶入題目來敘述會更好
• 在問104. Maximum Depth of Binary Tree經典題的時候，可以順便詢問對方能否實做出用DFS或BFS的方法

interviewee

優點

• 確實的執行REACTO
• coding時解釋程式清楚
• 解題過程邏輯清晰

可改進之處

• 在程式碼適當加上註解，方便interviewer回頭檢視

作業二 - 他評02

針對interviewer

優點

• 題目說明非常明瞭。
• • 說話流暢。

可改進之處

• 開頭有一點太過嚴肅。
• 與interviewee的互動有點少且很少出現在影片中。

針對interviewee

優點

• 一開始詢問是否能使用STL很不錯。
• 講解都非常仔細。
• 說話流暢。

可改進之處

• 英文部分的面試對談與中文相比稍顯遜色，不過重點都還是有說清楚。
• 注意英文發音可能會誤導別人。

作業二 - 他評03

針對interviewer

優點

• 講話清楚
• 針對例子的說明清晰，可以幫助面試者了解題目

可改進之處

• 可用例子的方式切入題目，讓面試者不是純解題而是討論想法

針對interviewee

優點

• 跟面試官確認後的條件有記下來方便爾後使用，而非口頭確認
• 講話清楚，解題思路清晰

可改進之處

• 可以適當在題目上畫出 return 結果，例如針對深度時可以在節點上標註結果，以利受試者觀看