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

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

interviewer:

interviewee:

101.Symmetric Tree

video

題目描述

給定一棵二元樹，檢查它是否是其自身的鏡像（即圍繞其中心對稱）。

例如，這個二元樹是對稱的：
     1
    / \
   2   2
  / \ / \
 3  4 4  3

但這個不是：
     1
    / \
   2   2
    \   \
     3   3 

程式碼解說

已知樹節點資料結構如下：

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

方案一 : Recursion

class Solution {
    public:
        bool isSymmetric(TreeNode *root) {
            if (!root) return true;
            return isSymmetric(root->left, root->right);
        }
        bool isSymmetric(TreeNode *left, TreeNode *right) {
            if (!left && !right) return true;
            if (left && !right || !left && right || left->val != right->val){
                return false;  
            }
            return isSymmetric(left->left, right->right) 
                && isSymmetric(left->right, right->left);
        }
};

最快想到的方法就是用遞迴解決，因為程式碼可讀性高，而且相對容易撰寫。
首先確定根節點是否存在，接著透過遞迴持續比對將所有子節點，直到走訪所有節點。
比對方法左右子樹節點是否一有一無，或者是值不相同。
比對時需注意“左子樹右節點”是和“右子樹左節點”比對，以此類推。
優點：可讀性高，容易撰寫和維護。
缺點：當在binary tree很大時，運行遞迴需維護的stack可能會無法負荷。
時間複雜度最差就是O(n)，因為必須要比完所有的節點才知道是否對稱。

方案二 : Queue

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        queue<TreeNode*> q1, q2;
        q1.push(root->left);
        q2.push(root->right);
        while (!q1.empty() && !q2.empty()) {
            TreeNode *node1 = q1.front(); q1.pop();
            TreeNode *node2 = q2.front(); q2.pop();
            if (!node1 && !node2) continue;
            if((node1 && !node2) || (!node1 && node2)) return false;
            if (node1->val != node2->val) return false;
            q1.push(node1->left);
            q1.push(node1->right);
            q2.push(node2->right);
            q2.push(node2->left);
        }
        return true;
    }
};

不用遞迴的話，就要自己透過一些資料結構來紀錄節點資訊了。
我選擇用兩個queue來紀錄兩邊的節點，並加以比對。
需注意的是while loop的結束條件是queue為空，與遞迴時不一樣，當子節點皆為nullptr時還是需要繼續比對，因為有可能是左子樹的左子點為空但右子點不同的情形
時間複雜度一樣最差就是O(n)，因為必須要比完所有的節點才知道是否對稱。

39.Combination Sum

video

題目描述

給定一組不重複的候選數字 (candidates)和一個目標數(target)，請找出候選數字中加總和達到目標數的所有組合。
其中可以從候選數字中無限次地選擇同個數字。
所有數字（包括目標數）都是正整數。

範例：
Input: candidates = [2,3,6,7]
target = 7,
A solution set is:
[
  [2,2,3],
  [7]
]

程式碼解說

方案 : Recursion DFS

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> cur;
        std::sort(candidates.begin(), candidates.end());
        dfs(candidates, target, 0, cur, ans);
        return ans;
    }
    void dfs(vector<int>& candidates, int target, int s, vector<int>& cur, vector<vector<int>>& ans) {
        if (target == 0) {
            ans.push_back(cur);
            return;
        }
        
        for (int i = s; i < candidates.size(); ++i) {
            if (candidates[i] > target) break;
            cur.push_back(candidates[i]);
            dfs(candidates, target - candidates[i], i, cur, ans);
            cur.pop_back();
        }
    }
};

用遞迴做深度優先搜尋如上圖，使用cur來紀錄每次搜尋過程，一但符合target，就存到ans中。
而在此之前，可以先排序候選數字 (candidates)，這樣搜尋過程中遇到候選數字 (candidates）大於target的情況，就能確保後面的數字都大於target，不用再繼續找下去。且遞迴也可以從最小開始找起。如此一來就能找出所有可能組合解。

70.Climbing Stairs

video

題目描述

Imagine you're climbing a staircase with 'n' steps, and you can either climb 1 step or 2 steps at a time. how many different ways can you reach the top?

Example:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
* 1 step + 1 step
* 2 steps

程式碼解說

方案一 : Recursion

int climbStairs(int n) {
    if(n==1) return 1;
    if(n==2) return 2;
    return climbStairs(n-1)+climbStairs(n-2);
}

This recursive function will make two recursive calls for each input 'n' except for the base cases when 'n' is 1 or 2.
Therefore, the number of recursive calls grows exponentially with 'n' because each call branches into two more calls.
So The time complexity can be expressed as O(

$2^n$), where 'n' is the input size (number of steps).
This is a fairly high time complexity and will lead to very high computational costs when the number of stairs is large.

方案二 : Dynamic Programming

int climbStairs(int n) {
    if (n <= 1) return 1;
    vector<int> climb_ways(n);
    climb_ways[0] = 1;
    climb_ways[1] = 2;
    for(int i=2; i<n; i++){
        climb_ways[i] = climb_ways[i-1]+climb_ways[i-2];
    }
    return climb_ways[n-1];
}

This algorithm uses a for loop to iterate through 'n' steps to calculate the number of ways to reach each step.
In the loop, it performs constant-time operations for each step.
Therefore, the time complexity of this dynamic programming solution is O(n), where 'n' is the input size (number of steps).

第二次作業-他評01

interviewer

優點

• 面試過程輕鬆不會太上對下

可改進的地方

• 可以將變數限制交給面試者來詢問，一方面看看他是否有在思考邊界條件，另一方便也可以促進溝通
• 面試者的答案都全肯定，建議面試官可以明知故問，給面試者解釋的機會，也可更加理解對面試者的想法
• 建議可以用實際例子來包裝問題

interviewee

優點

• 懂得適時求助面試官給予引導
• 口齒清晰

可改進的地方

• 可以把程式碼放在REACTO中的最後一步，coding階段可以先思考最直觀且最暴力的解法，給面試官一個「我可以在短時間內優化」的印象
• repeat®階段與example(E)階段同時並行，建議先理解題目意圖再進行舉例

第二次作業-他評02

interviewer

優點

• 與 interviewee 的互動很好
• 發問精簡，也有引導 interviewee 優化

可改進的地方

• 題目可再做些包裝

interviewee

優點

• 依循 REACTO 流程，有將 Approach 充分討論
• 邊講解例子邊寫出來，讓人容易理解

可改進的地方

• 英文解說有點卡卡的

第二次作業-他評03

interviewer

優點

• 13:18:針對程式碼有提供具體的問題，增加討論的空間。

可改進的地方

• 若可以用一些生活的例子或是情境來包裝題目會更好。

interviewee

優點

• 整個面試的過程很自然而且很流暢，說明也很清楚。

可改進的地方

• 00:56:在打例子時我覺得可以稍微說明或是說點話，讓空氣不要太安靜

第二次作業-他評04

interviewer

優點

可改進的地方

• 14:53: 結尾應該要說面試結束之類的客套話。

interviewee

優點

• 解釋方法步驟清楚。
• 8:40: &是講專業術語不是and。

可改進的地方

• 不應該用有自動補齊的工具。
• 打錯的字有點太多。
• 可以適度反白解釋會更清楚。
• 4:50: 應該是樹的結構，而且理論上應該要先宣告struct再寫主程式。
• 8:25: start變數取名為start_index或start_pos會更清楚，或者在主程式的時候可以先寫註解解釋。
• 13:55: 因為是直接用內建的C++函式，所以是Introsort，排序最佳、平均、最壞時間複雜度都是
  $O(nlogn)$。
• 13:30: 可以將
  $i<n$的部分反白，會更清楚為何要多一個if的條件判斷。