---
title: 2022 年資訊科技產業專案設計課程面試範例
tags: INFO2022
---

# 2022 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2022)」作業一
> 貢獻者: 痞彥 Mr.Bear
> [video](https://www.youtube.com/watch?v=-5tE9w-3Hr4)

🧔：interviewer 🐶：interviewee

## [9. Palindrome Number](https://leetcode.com/problems/palindrome-number/)
> 影片: [00:10](https://www.youtube.com/watch?v=-5tE9w-3Hr4&t=10s)

### 測驗說明與問答
🧔：題目的部分就是輸入一個整數，並且我們必須判斷他是不是一個回文數字，並且回傳相 對應的布林值，至於怎麼判斷回文數字，只要前面讀過去跟後面讀回來是一樣的，那他就是一個回文數字。
🐶：你好，針對這一題我想到一個最直覺的方式：
🐶：首先就是先建立一個跟他相反的字串，並且比對兩者是否相等。如果相等的話則他就是一個迴文數字
🐶：比如說以以下範例來說

Input x = -121
Reverse = 121-
Input != Reverse
return false

🐶：因為reverse 不等於 input x 所以必須回傳 false.
🐶：以下為code的實作部分。

### Palindrome with string comparison

bool isPal(int x){
    string str = to_string(x);
    string re = "";
    for(int i = str.length()-1;i >= 0; i--){
        re += str[i];
    }
    return str == re ;
}

🐶：先定義這邊的 n 為input x 值的大小。
所以把整數以十進位一個一個擷取，故時間複雜度為$O(log(n))$
🧔：這邊想提出幾點問題，第一點題目明明就是回文整數有沒有辦法可以不要轉成字串？
第二點時間複雜度以剛剛的方法來說不管什麼情況底下都是$O(log(n))$。有沒有什麼辦法可以加速呢?
🐶：我的想法是利用數學上的技巧來把數字做翻轉，但是翻轉數字必須要考慮到以下幾點:
1. 翻轉後溢位
2. 負數不能翻轉
3. 尾數為0且不為零的也不能翻轉
4. 要考慮整數為奇數或偶數長度的情況

🐶：其中上面第二點可以利用回文的特色"只要比較前半跟翻轉後的後半部分做比較"就可以解決了。

### Palindrome with reverted integer

bool isPal(int x){
    if ( x < 0 || (x % 10 == 0 && x != 0)){
        return false;
    }
    int re = 0;
    while(x > re){
        re = re * 10 + x % 10;
        x /= 10;
    }
    return x == re || x == re / 10;
}

🐶：雖然說while loop的部分還是花了$O(log(n))$的時間，但她不需要把整段數字都反轉，所以整體次數會比上一個方法還要少一半

## [11. Container With Most Water](https://leetcode.com/problems/container-with-most-water/)
> 影片: [18:07](https://youtu.be/-5tE9w-3Hr4?t=1087)

### 測驗說明與問答
🧔：在第二題我會提供一個int array且長度為n，可以把裡面的值跟其對應的index想像是在一個二維的平面分別對應為Y軸和X軸。Y軸的高度可以想像是好多個檔板，所以我們必須找到一條平行於X軸的直線也就是水平面的高度。他所形成的面積就是水的容積且必須能容納最多水。

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49

🧔：以上面這個例子來說就是找到一條平行於X軸的水平線，介於兩條直線之間並求得最大容積。
🐶：這一題最直覺的方法是使用暴力法的方式一個一個找值，這個方法的時間複雜度為$O(n^2)$。
這個方法必定能找到最大值，而且也沒有什麼邏輯上的毛病。

### brute force

int maxArea(vector<int>& height){
    int n = height.size();
    int max = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            int tmp = (j-i) * min(height[i],height[j]);
            if (tmp > max){
                max = tmp;
            }
        }
    }
    return max;
}

🧔：這個方法花的時間太久了有沒有更快的方法?
🐶：這邊的想法是利用兩個指標從左往右逼近，因為長方形的面積是由長乘以寬來決定的，
所以小的那邊靠近中央必定會比大的那邊靠近中央的容積還要少，故採用此方法。而且由此方法可以讓時間複雜度降至$O(n)$
### two pointer

int maxArea(vector<int>& height){
    int i = 0;
    int j = height.size()-1;
    int max = 0;
    while(i < j){
        if(height[i]>height[j]){
            int tmp = (j-i) * height[j];
            if(tmp > max) {
                max = tmp;
            }
            j-=1;
        }
        else{
            int tmp = (j - i) * height[i];
            if(tmp > max){
                max = tmp;
            }
            i+=1;
        }
    }
    return max;
}

## 總體初步檢討

針對 interviewer 的檢討:
- 口條可以再清晰一點。
- 當題目不夠直覺時，可以搭配圖片加上input說明。
- [18:06](https://youtu.be/-5tE9w-3Hr4?t=1086) :給的反饋太少，沒辦法判斷出面試者的能力。

針對 interviewee 的檢討:
- 口條可以再清晰一點。
- 語助詞可以省略的就省略。
- [02:14](https://youtu.be/-5tE9w-3Hr4?t=134) :直接說宣告一個字串就好而不是子字串。
- [05:31](https://youtu.be/-5tE9w-3Hr4?t=331) :沒有提到為什麼整數轉字串的時間複雜度是$O(log(n))$
- [27:35](https://youtu.be/-5tE9w-3Hr4?t=1655) :舉例的時候不是很清楚，面試官未必能清楚的理解你的解法是怎麼樣。
- [30:25](https://youtu.be/-5tE9w-3Hr4?t=1825) :應該不是交接而是相交。