# 2024 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2024/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Finfo2024-homework1)」作業 1

> 貢獻者: 艾瑞克 - Eric
> [中文面試影片 1](https://youtu.be/yAR30kbogNc)
> [中文面試影片 2](https://youtu.be/P_NbCykdZwE)
> [英文面試影片](https://youtu.be/97Nz7DT5WWQ)

## [104. Maximum Depth of Binary Tree (Easy)](https://leetcode.com/problems/maximum-depth-of-binary-tree/description/)
### 程式碼說明
#### 方案一: 遞迴法
時間複雜度:
- 最佳情況(平衡樹)：$O(log n)$
- 最差情況(完全不平衡，如鏈狀樹)：$O(n)$

int maxDepth(TreeNode* root) {
        // 如果根節點為空,深度為 0
        if (root == nullptr) {
            return 0;
        }
        
        // 遞歸計算左右子樹的最大深度
        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);
        
        // 返回較大的深度加上當前節點(即加1)
        return max(leftDepth, rightDepth) + 1;
    }

#### 方案二: 迭代法
使用廣度優先搜索（BFS）來解決這個問題。
具體步驟如下：
1. 使用一個佇列來存儲每一層的節點。
2. 每次處理當前佇列中的所有節點（即當前層的所有節點）。
3. 對於每個節點，將其非空子節點加入佇列。
4. 每處理完一層，深度加 1。
5. 當佇列為空時，我們就遍歷完了整棵樹，此時的深度就是樹的最大深度。

避免了遞迴調用可能帶來的堆疊溢出風險，特別是在處理非常深的樹時，這種方法可能更有優勢。

時間複雜度:
- 最佳情況（完全不平衡，如鏈狀樹）：$O(1)$
- 最差情況（完全平衡樹）：$O(n/2)$ ≈ $O(n)$

int maxDepth(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }

    queue<TreeNode*> q;
    q.push(root);
    int depth = 0;

    while (!q.empty()) {
        int levelSize = q.size();
        depth++;

        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front();
            q.pop();

            if (node->left) {
                q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
    }

    return depth;
}

## [217. Contains Duplicate (Easy)](https://leetcode.com/problems/contains-duplicate/description/)

### 模擬面試過程
面試官：嗨，Eric，我是來自工程團隊Tom。今天我將進行你的面試。準備好開始了嗎？

Eric：嗨，Tom，是的，我準備好了。謝謝你。

面試官：好，那麼我現在要和你分享一個問題，然後我們可以討論你解決它的方法。
你正在為一個社交媒體開發一個新的標籤系統。在這個平台上，用戶可以為他們的文章添加多個標籤。為了提高用戶體驗和系統效率，你的任務是確保每個帖子中不會出現重複的標籤。
假設標籤為一個整數陣列 nums，如果陣列中任何值出現至少兩次，則返回 true，如果每個元素都是不同的，則返回 false，藉以檢測是否存在重複的標籤。這樣清楚嗎？

Eric：是的，很清楚。讓我確認一下我理解得對不對，你希望我寫一個函數，檢查整數陣列中是否有任何重複的值，對嗎？如果有重複，就返回 true，如果所有元素都是唯一的，就返回 false。

面試官：沒錯，就是這樣。在我們繼續之前，你有什麼問題嗎？

Eric：沒有，我想我理解了這個問題。我可以先舉一些例子來澄清要求嗎？

面試官：當然可以，請說。

Eric：好的，讓我們考慮幾個例子：
1. 如果我們有一個陣列 [1, 2, 3, 1]，函數應該返回 true，因為 1 出現了兩次。
2. 對於像 [1, 2, 3, 4] 這樣的陣列，它應該返回 false，因為所有元素都是不同的。
3. 對於一個有多個重複的較大陣列，比如 [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]，它也應該返回 true。
這些例子正確且足夠嗎？
面試官：是的，這些是很好的例子。它們涵蓋了我們關注的主要情況。你會如何著手解決這個問題呢？
Eric：嗯，首先想到的最直觀的方法是使用兩個迴圈來檢查重複。它的工作原理如下：
1. 我們用外層循環逐一走訪每個陣列。
2. 對於每個元素，我們使用內層循環檢查所有後續元素是否匹配。
3. 如果找到匹配，我們返回 true。
4. 如果兩個循環都完成而沒有找到匹配，我們返回 false。
但是，這種方法的時間複雜度是 O(n^2)，對於大型陣列來說效率不高。

面試官：我明白了。你能想到更有效的方法嗎？

Eric：是的，另一種方法是先對陣列進行排序，然後比較相鄰的元素。排序後，任何重複的元素都會相鄰。算法如下：
1. 對陣列進行排序。
2. 逐一走訪排序後的陣列一次，比較每個元素與下一個元素。
3. 如果我們發現兩個相鄰的元素相同，我們返回 true。
4. 如果我們完成迭代而沒有找到任何重複，我們返回 false。
這種方法的時間複雜度是 O(n log n)，因為排序步驟，這比之前的 O(n^2) 解決方案要好，但仍然不是最優的。

面試官：那是一個很好的改進。你能想到更有效的解決方案嗎？
Eric：是的，我想我們可以使用哈希集合來更有效地解決這個問題。以下是我的方法：
1. 創建一個無序集合。
2. 逐一走訪每個輸入陣列，將每個元素插入到集合中。
3. 插入所有元素後，比較集合的大小與輸入向量的大小。
4. 如果大小相等，意味著沒有重複，所以我們返回 false。
5. 如果大小不同，意味著有重複，所以我們返回 true。

這種方法平均時間複雜度應該是 O(n)，其中 n 是陣列的長度，在最壞的情況下（所有元素都是唯一的）空間複雜度是 O(n)。你想讓我實作現這個解決方案嗎？

面試官：是的，請你使用C++實作。

Eric：好的，我現在就實作它。

面試官：看起來程式邏輯沒有問題，我們的時間快到了，你對這個問題或其他任何事情有什麼問題嗎？

Eric: 沒有其他問題了，謝謝你

### 程式碼說明
#### 方案一: 暴力解
時間複雜度: $O(n^2)$
用了兩層迴圈,外層迴圈執行 $n$ 次,內層迴圈平均執行 $n/2$ 次。
在最壞情況下(沒有重複元素或重複元素在末尾),需要比較 n*$(n-1)/2$ 次。
- 優點:
1. 實現簡單直觀
2. 不需要額外的數據結構,節省了空間
- 缺點:
1. 用於大型數組時，運行時間可能會變得非常長。

// Time : O(n^2)
// Space: O(1)

bool containsDuplicate(vector<int> &nums)
    {
       for (int i = 0; i < nums.size(); i++){
           int element = nums[i];
           for (int j = i + 1; j < nums.size(); j++){
               if (nums[j] == element)
                    return true;
           }
       } 
        return false;
    }

#### 方案二: 排序後檢查相鄰元素
時間複雜度: $O(nlogn)$
排序操作的時間複雜度為 $O(nlogn)$。
後續的線性掃描為 $O(n)$。
總體時間複雜度由排序決定,為 $O(nlogn)$。
空間複雜度: $O(1)$ 或 $O(logn)$
如果使用原地排序算法(如快速排序),空間複雜度為 $O(1)$。
如果使用某些實現(如 C++ 的 std::sort),可能需要 $O(logn)$ 的額外空間。
- 優點:
1. 比方案一更快，特別是對於大型數組
2. 實現相對簡單
- 缺點:
1. 改變了原數組的順序，可能在某些情況下不被允許。
2.雖然比方案一快，但仍不是最優解。

// Time : O(nlogn)
// Space: O(1)

bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for(int i=0; i<nums.size()-1; i++){
            if(nums[i]==nums[i+1])
                return true;
        }
        return false;
    }

#### 方案三: 使用 unsorted set
時間複雜度為 $O(n)$其中 $n$ 是陣列的長度，因為我們只需要遍歷一次陣列。
空間複雜度也為 $O(n)$，最壞情況下我們需要將所有元素都存入 set 中。
這個方法在保持較低時間複雜度的同時,也能有效地解決問題。

bool containsDuplicate(vector<int> &nums)
{
    unordered_set<int> num_set;
    for (auto itr : nums){
        num_set.insert(itr);
    }
    if (num_set.size() == nums.size())
        return false;
    return true;
}

## [102. Binary Tree Level Order Traversal (Medium)](https://leetcode.com/problems/binary-tree-level-order-traversal/description/)

### 模擬面試流程
Interviewer: Hello, I'm today's interviewer. We're going to look at a problem about binary trees. Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Are you ready?

Candidate: Hello, yes, I'm ready. Thank you for providing the problem.

Interviewer: Great, please begin.

Candidate: Certainly. First, let me repeat the problem to ensure I understand it correctly.
We need to write a function that takes the root node of a binary tree as input, and we need to calculate and return the maximum depth of this tree. The maximum depth is defined as the number of nodes on the path from the root to the farthest leaf node. Is that correct?

Interviewer: Yes, that's exactly right.

Candidate: Thank you for confirming. Now, let me provide a few examples:
1. If the input is [3,9,20,null,null,15,7], the output should be 3. Because the longest path is either 3->20->15 or 3->20->7, both having 3 nodes.
2. If the input is [1,null,2], the output should be 2. Because the longest path is 1->2, with 2 nodes.
3. If the input is an empty tree, i.e., [], the output should be 0.
4. If the input is a tree with only one node, like [1], the output should be 1.
Are these examples correct?

Interviewer: Yes, these examples are good and cover important cases. You can proceed with explaining your solution approach.

Candidate: Thank you. For this problem, I'd like to present a recursive solution.
Let's start with the recursive approach:
1. If the root node is null, return 0.
2. Otherwise, recursively calculate the maximum depth of the left and right subtrees.
3. Return the larger of the left and right subtree depths, plus 1 (for the current node).
The time complexity of this method is O(n), where n is the number of nodes in the tree, as we need to visit each node once. The space complexity in the worst case (completely unbalanced tree) is O(n), and in the best case (completely balanced tree) is O(log n), due to the recursive call stack.

Interviewer: Yes, the approach sounds good. Can you code it up?

Candidate: Certainly, I'll start with the solution:
This solution can pass test cases that cover empty trees, single-node trees, balanced trees, and unbalanced trees.

Interviewer: Excellent, your testing approach is comprehensive. That's all for today's interview. Do you have any questions for me?

Candidate: I don't have any specific questions about the problem, thank you for the opportunity. I look forward to hearing from you. Have a great day!

Interviewer: You too, Eric. Take care.

### 程式碼說明
#### 方案一:

vector<vector<int>> levelOrder(TreeNode *root)
{
    vector<vector<int>> ans;
    if (root == NULL)
        return ans;
    queue<TreeNode *> q;
    q.push(root);
    while (!q.empty())
    {
        int level_size = q.size();
        vector<int> level_nodes;
        for (int i = 0; i < level_size; i++)
        {
            TreeNode *node = q.front();
            q.pop();
            if (node->left)
            {
                q.push(node->left);
            }
            if (node->right)
            {
                q.push(node->right);
            }
            level_nodes.push_back(node->val);
        }
        ans.push_back(level_nodes);
    }
    return ans;
}

## 同儕互評01

### 217. Contains Duplicate

#### Interviewer
- [ ] 優點
* 有包裝題目
* 與interviewee討論多種方法

#### Interviewee
- [ ] 優點
* 舉的例子有考慮到edge case
- [ ] 可改進的地方
* 寫程式時可以邊寫邊把想法講出來

### 102. Binary Tree Level Order Traversal

#### Interviewee
- [ ] 優點
* 有清楚的分析時間複雜度與空間複雜度
* 有跟interviewer討論實際應用
- [ ] 可改進的地方
* [6:00](https://youtu.be/yAR30kbogNc?t=360):應為return ans

## 同儕互評02
- [ ] 優點
* 有初始方法跟改進後的方法。
* 有給出各方案的優缺點。
* 有討論時間複雜度。
- [ ] 缺點
* [1:04](https://www.youtube.com/watch?v=yAR30kbogNc&ab_channel=%E3%80%8C%E8%B3%87%E8%A8%8A%E7%A7%91%E6%8A%80%E7%94%A2%E6%A5%AD%E5%B0%88%E6%A1%88%E8%A8%AD%E8%A8%88%E3%80%8D%E8%AA%B2%E7%A8%8B%28%E5%AD%B8%E5%93%A1%E5%B0%88%E5%8D%80%29)不應該直接給出Leetcode題號，讓求職者發現。
* [1:21](https://www.youtube.com/watch?v=P_NbCykdZwE&ab_channel=%E3%80%8C%E8%B3%87%E8%A8%8A%E7%A7%91%E6%8A%80%E7%94%A2%E6%A5%AD%E5%B0%88%E6%A1%88%E8%A8%AD%E8%A8%88%E3%80%8D%E8%AA%B2%E7%A8%8B%28%E5%AD%B8%E5%93%A1%E5%B0%88%E5%8D%80%29)馬賽克部分跑走了，露出真實身份了。

## 同儕互評03
- 優點
- 對話流暢，情境完整，不覺得生硬
- 缺點
- [4:10](https://youtu.be/97Nz7DT5WWQ?si=fkiIGL7w58WovnME&t=250) 英文抑揚頓挫要檢討一下，很多句子其實聽不太懂