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

> 貢獻者
> 艾瑞克 - Eric, 艾曼達 - Amanda
> [面試錄影 1](https://www.youtube.com/watch?v=UWq8_VeHFkM)
> [面試錄影 2](https://www.youtube.com/watch?v=CUJaAtJfcEE)

## [Leetcode : 9. Palindrome Number](https://leetcode.com/problems/palindrome-number/description/)
**Interviewer：**
你好，歡迎來到今天的面試。接下來我們會跟你討論一些程式題目，你可以盡量表達你的想法，讓我們可以更了解你對於撰寫程式的風格與手法。

**Interviewee：**
好的。

**Interviewer：**
我們在公司的專案中，後端常常會需要做一些資料處理，常常會需要思考，是否有更高效率的資料處理方法，以維護系統的產出品質。
所以今天跟你討論的是經典的回文題目。目標就是判斷一個數字是否為回文數，如果是就回傳True，不是回文就回傳False。回文數是指無論從左到右還是從右到左，讀起來都是一樣的數字。
請問針對這個題目你有什麼想法嗎，或是任何題目細節的疑問?

**Interviewee：==(Repeat)==**
我想問輸入是integer嗎?有範圍限制嗎?

**Interviewer：**
輸入是integer沒錯，範圍是$-2^{31} <= x <= 2^{31} - 1$。

**Interviewee：==(Approach)==**
好，那針對這個題目我有想到兩個常用的做法，一個是直接將數字轉換為字串，然後直接比較這個字串的正序和反序。這是較直覺的做法。
另一種是不使用字串，透過數字的運算，去反轉這個數字的後半部分，然後將它與前半部分進行比較。這個做法雖然不是最直觀的，但可以節省大量空間，降低空間複雜度。

**Interviewer：**
好，那請你先呈現第一種較直觀的做法。

**Interviewee：==(Code)==**

bool Palindrome(int x) {
    // 負數以及以0結尾且不是0的數字不是回文
    if (x < 0 || (x % 10 == 0 && x != 0))
        return false;
    
    // 將整數轉換為字串
    string str = to_string(x);
    
    // 定義兩個變數，從字串兩端進行比較
    int left = 0;
    int right = str.length() - 1;
    
    while (left < right) {
        if (str[left] != str[right])
            return false;  
        left++;
        right--;
    }
    
    return true;
}

**Interviewer：**
好，這個做法OK，可以直觀理解。那想請你再說明你剛剛說的第二種解法。並說明為甚麼這個作法更好。

**Interviewee：==(Optimization)==**
好的，那我想先說明剛剛的做法。
因為要走訪輸入數字的每一位數，所以時間複雜度是O(n)，其中n是輸入數字的位數。
空間複雜度的部分也是O(n)，因為我們需要另外的字串空間去儲存這個數字的每一位數。
而接下來的做法是可以不用花額外的空間去儲存字串，可以降低空間複雜度。

bool Palindrome(int x) {
    // 負數以及以0結尾且不是0的數字不是回文
    if (x < 0 || (x % 10 == 0 && x != 0))
        return false;
    
    int reversedHalf = 0;
    
    // 反轉數字的後半部分
    while (x > reversedHalf) {
        reversedHalf = reversedHalf * 10 + x % 10;
        x /= 10;
    }
    
    // 檢查前半部分與反轉後的後半部分是否相等
    // 對於奇數位數的情況，反轉後的一半數字會多出一位，因此可以去掉最後一位進行比較
    return x == reversedHalf || x == reversedHalf / 10;
}

這個方法只使用常數級別的額外空間來存儲反轉後的數字，因此空間複雜度是 O(1)。

**Interviewer：**
好，這個做法的確可以減少空間複雜度，這兩個做法確實都是檢查回文時常討論的作法。
今天的面試就告一段落，非常感謝妳今天的參與。

## [Leetcode : 70. Climbing Stairs](https://leetcode.com/problems/climbing-stairs/description/)

**Interviewer:**
你好，今天由我負責這場面試，希望能更了解你撰寫程式的想法與風格。想像公司正在進行一個大型計畫，該計畫被分解為 n 個小任務。公司希望盡快完成計畫，因此允許員工靈活選擇工作量。每個員工可以選擇承擔 1 個任務或 2 個任務。公司管理層想知道有多少種不同的任務分配方式，以便更好地理解項目的複雜性和資源分配的靈活性。你能解決這個問題嗎?

**Interviewee: ==(Repeat)==**
讓我重複一下問題內容，確保我理解正確。公司有一個大型計畫，可以分為 n 個小任務，且 n 為正整數。每個員工可以選擇做 1 個或 2 個任務。我需要計算出有多少種不同的任務分配方式，這樣理解正確嗎?

**Interviewer:**
是的，你的理解正確。

**Interviewee: ==(Example)==**
好的，讓我舉幾個例子來說明這個問題。
假設 n = 2:
分配的方式為 (1, 1)，即兩位員工都各做一份任務
或是(2, 0)，即第一位員工就將2個任務做完
若n = 3:
我們可以有 (1, 1, 1) 這樣的分配方式,即三個員工各做一個任務
也可以有 (2, 1) 這樣的分配方式，即一個員工做兩個任務，另一個做一個任務
還可以有 (1, 2) 這樣的分配方式，順序不同於上一個。 這些都是有效的分配方式
請問我的例子正確嗎?

**Interviewer:**
是的，你的例子有符合我的題目設定。

**Interviewee: ==(Approach)==**
我的解題思路是使用動態規劃。我們可以定義一個函數 f(n)，表示 n 個任務的不同分配方式數量。我們可以得到以下關係:
f(n) = f(n-1) + f(n-2)
因為我們可以選擇一個員工做 1 個任務，剩下 n-1 個任務的分配方式就是 f(n-1)
或者選擇一個員工做 2 個任務，剩下 n-2 個任務的分配方式就是 f(n-2)
因此 n 個任務時的總方法數就是 f(n)
這個關係和斐波那契數列很相似，但初始條件不同。我們可以設定 f(1) = 1, f(2) = 2 作為初始條件。

**Interviewer:**
那麼請你進行實作

**Interviewee: ==(Code)==**

 int countWays(int n) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 2;
        
        vector<int> dp(n + 1, 0);
        dp[1] = 1;
        dp[2] = 2;
        
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
}  

首先考慮邊界條件，也就是 n= 0, 1, 2 的情況
n = 0 時完成方法為 0 種;
n = 1 時完成方法為 1 種;
n = 2 時完成方法為 (1, 1) 和 (2, 0)兩種

接著 n>=3 以後都可以使用動態規劃的方式累加求解。
此方法的時間複雜度和空間複雜度皆為 O(n)。
因為迴圈從 3 執行至 n， 並且我們利用了一個大小為 n 的 vector 紀錄所有的中間結果。

**Interviewer:**
但我只需要最後的方法總數，不需要中間結果的方法數，是否能改進你的程式讓空間複雜度降至 O(1) 呢?

**Interviewee: ==(Optimization)==**
在計算過程中，我們實際上只需要保存最後兩個狀態。我們可以使用兩個變數來替代整個向量，就可以將空間複雜度降低到 O(1)，實作如下:

 int countWays(int n) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 2;
        
        int prev2 = 1;	//f(n-2)
        int prev1 = 2;	//f(n-1)
        for (int i = 3; i <= n; i++) {
	int curr = prev2 + prev1;	//f(n)
            prev2 = prev1;
	prev1 = curr;
        }
        return prev1;	
}  

**Interviewer:**
你的思路和實作都很正確，謝謝你今天的參與，若有進一步的消息再通知你。

## 模擬面試檢討 - 自評

##
### 第二次作業-他評 02
https://hackmd.io/JP4hn2igQ8Kp-oQtiqFesg?view#%E7%AC%AC%E4%BA%8C%E6%AC%A1%E4%BD%9C%E6%A5%AD-%E4%BB%96%E8%A9%95-02
- [0:20](https://youtu.be/yZmYes9xhbM?t=20): 參考[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)，不應翻譯成「函數」，應為「函式」。
> function 應翻譯為「函式」，表示「衍生自數學函數的常式 (routine)」
- [1:46](https://youtu.be/yZmYes9xhbM?t=106): 這邊使用 0 來作為空節點，但這樣會和存在節點且值為 0 的狀況產生混淆，因此建議使用 NULL 來表示會更好。