---
title: 2022 年資訊科技產業專案設計課程第 1 次作業
tags: INFO2022
---

# 2022 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2022)」第 1 次作業
> 貢獻者: 藍筱裘 Basketball

🍙：interviewer 🏀：interviewee

## [9. Palindrome Number](https://leetcode.com/problems/palindrome-number/)
==[模擬面試錄影](https://youtu.be/ugW2gpFDJ6w)==

### 測驗說明與問答
🍙：Hello, Basketball! I want you to solve a simple question. ==Given an integer x, return true if x is a palindrome integer.== So, an integer is palindrome when it ==reads the same backward as forward.== For example, ==121== is palindrome while ==123== is not. I want you to simply declare a boolean function, and it returns true or false to tell me whether an interger is palindrome or not.

🏀：The first thought of me is just turn the integer type to string and reverse the string from begin to end. Then, we can compare if the original string is equal to the reverse string.

🍙：You can give it a try.

#### *Naive Solution*
🏀：Turn the type to string and then reverse it to compare. I think it's the simplest solution.

class Solution{
    public:
        bool isPalindrome(int x) {
            string rev = to_string(x);
            reverse(rev.begin(), rev.end());
            return to_string(x) == rev;
        }    
};

🍙：It looks that the solution is not very efficient. Can you find a more efficient way to solve this problem?

🏀：I think a more efficient is not to turn type of x to string. Instead, I can ==divide this integer to two part.== One is from the highest digit to the half digit, and declare another variable store the last digit to the one half digit. Compare these digits is equal and then to return.

🍙：Okay.

#### *Efficient Solution*
🏀：Make sure x is positive and not an one digit number. Then, use another variable to ==store the digits from the last digit to the first using simple arithmetic operation==. Compare if the two numbers are the same.

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

### 面試過程檢討

#### interviewer
- [1:55](https://youtu.be/ugW2gpFDJ6w?t=115) 可以追問程式碼有什麼可以改進的地方，或請 interviewee 回答目前的時間、空間複雜度為何，直接說「not very efficient」會讓人不知道該改善的地方是什麼。
- [2:30](https://youtu.be/ugW2gpFDJ6w?t=150) 當 interviewee 回答的做法不太對時應做提醒。
- [4:37](https://youtu.be/ugW2gpFDJ6w?t=277) 在 interviewee 回答完後可以給予多一點回饋，詢問為什麼這樣會改進效率？還有沒有可以改善之處？等問題。

#### interviewee
- [0:40](https://youtu.be/ugW2gpFDJ6w?t=40) 在聽到問題時應先舉出幾個例子，並對可能的邊際範圍、程式限制提問。
- [1:28](https://youtu.be/ugW2gpFDJ6w?t=88) 應先確定是否可使用函式庫中的函式，或提到這裡的 `reverse()` 引用了 `<algorithm>` 函式庫。
- [2:17](https://youtu.be/ugW2gpFDJ6w?t=137) 這裡的解釋有誤，並非存一半的字元而是全部的數字倒過來存放，解釋算法應講得更仔細一點。
- [2:55](https://youtu.be/ugW2gpFDJ6w?t=175) 英文講得很卡，要多練習。
- [3:47](https://youtu.be/ugW2gpFDJ6w?t=227) 運算子講錯 multiply、modulus、divide 在寫程式時會混用。

---

## [17. Letter Combinations of a Phone Number](https://leetcode.com/problems/letter-combinations-of-a-phone-number/)
==[模擬面試錄影](https://youtu.be/-RH6JQq3sdw)==

### 測驗說明與問答
🍙：好的，藍筱裘接下來請你做一個比較生活化的例子，定義一個 letterCombination 的函式，==傳入一個 string 包含 2~9 的數字==，裡面每個數字分別對應不同字母如下面這張圖所示，請你==回傳所有可能的字母組合==。如傳入數字==23==，就會回傳`['ad', 'ae', 'af', bd', 'be', 'bf', 'cd', 'ce', 'cf']`這樣好幾種組合，所以回傳的將是一個==陣列==。


🏀：了解，那請問 1 和 0 是不會出現在傳入的數字之中對吧？

🍙：對！1 和 0 不會出現在傳入的數字中。

🏀：好，那以下我將用 python 進行撰寫。

#### *Naive Solution*

🏀：首先是要判斷如果是空的數字傳進來，則回傳空陣列。其他的部分，先用一個 ==dictionary 定義每個數字對應到的字元==，再透過 ==2 層的 for 迴圈將對應字典內的組合放進回傳的陣列之中==

def letterCombination(self, digits):
    if '' == digits: return []
    mapping = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7', 'pqrs', '8': 'tuv', '9': 'wxyz'
    }
    ret = ['']
    for c in digits:
        tmp = []
        for y in ret:
            for x in mapping[c]:
                tmp.append(y+x)
    return ret

🍙：我覺得沒什麼問題，那你可以把程式碼寫得更簡潔一點嗎？

#### *Efficient Solution*
🏀：因為原本的程式碼寫了兩個 for 迴圈，在 python 我們也可以直接讓 8~11 行寫成一行，就不需要 tmp 這個陣列了。

def letterCombination(self, digits):
    if '' == digits: return []
    mapping = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7', 'pqrs', '8': 'tuv', '9': 'wxyz'
    }
    ret = ['']
    for c in digits:
        ret = [s + d for s in ret for d in mapping[c]]
    return ret

🍙：好的，可以。

### 面試過程檢討

#### interviewer
- [0:42](https://youtu.be/-RH6JQq3sdw?t=42) 說明題目時沒提到是否只會傳入數字的字串。
- [3:51](https://youtu.be/-RH6JQq3sdw?t=231) 只要求把程式碼寫得更簡潔感覺沒什麼必要，也可以請 interviewee 用遞迴的方式來撰寫這個題目。
- [4:46](https://youtu.be/-RH6JQq3sdw?t=266) 可以給 interviewee 更多的回饋，如這樣寫雖然可讀性降低但的確節省了空間等。

#### interviewee
- [0:44](https://youtu.be/-RH6JQq3sdw?t=44) 詢問時也應確定傳入的數字長度與範圍及例外情況時要做的處理。
- [1:07](https://youtu.be/-RH6JQq3sdw?t=67) 應先說明自己要用什麼架構來撰寫再開始打程式碼。
- [1:26](https://youtu.be/-RH6JQq3sdw?t=86) 寫程式時的所有提到 dictionary 的部分都講成 list 了！要注意！
- [2:40](https://youtu.be/-RH6JQq3sdw?t=160) 宣告變數的同時可以用註解的方式註記該變數的用途，讓打字的動作不要停下來。
- [3:41](https://youtu.be/-RH6JQq3sdw?t=221) 沒有注意到 tmp 打成 rmp 了。
- [4:20](https://youtu.be/-RH6JQq3sdw?t=260) 可以口頭說明由於是使用 python 這個語言，因此這種寫法將不會使用到 tmp 陣列的空間。

---

## [724. Find Pivot Index](https://leetcode.com/problems/find-pivot-index/)
==[模擬面試錄影](https://youtu.be/cp0ozG-aUEs)==

### 測驗說明與問答
🍙：筱裘，最後請你寫一個 find pivot 的函式，這個函式會==傳入一個叫 nums 的 integer 陣列==。Pivot index 的定義是在陣列上，==左方的數字加總和右方的數字加總相同==。如果 pivot index 位置在最左方，也就是右方總和為 0，那就回傳 0 即可，而題目要求直接回傳最左方的 pivot index。若沒有這樣的 index 存在，也就是 array 內不存在左右總和相同的話則回傳 -1。

🏀：那請問這個陣列的值和長度落於什麼範圍之間呢？

🍙：這個陣列的長度是 1~1000，數值範圍則是 -1000~1000 內。

🏀：那我接下來就是會在 array 長度的 for 迴圈裡找出是否有 left sum 和 right sum 相同的情況，獲得和的方式是各用 for 迴圈分別從頭和從尾加進去來計算。

🍙：好，沒問題，可以開始了。

🏀：那接下來就是用 Javascript 的程式碼來撰寫。

🏀：先宣告幾個會用到的變數以節省迴圈使用的空間，再來==針對陣列的長度找出每個 index 的左和及右和，如果一找到相同的情況就直接回傳該 index==。

var pivotIndex = function(nums){
    let i, j, lsum, rsum;
    for(i = 0; i < nums.length; i++){
        lsum = 0;
        rsum = 0;
        for(j = 0; j < i; j++){
            lsum += nums[j];
        }
        for(j = nums.length-1; j > i; j--){
            rsum += nums[j];
        }
        if(lsum == rsum){ return i; }
        else if(i == 0 && rsum == 0) { return 0; }
        else if(i == nums.length-1 && lsum == 0) { return nums.length-1; }
    }
    return -1;
}

🍙：看起來沒什麼問題，那今天面試就到這裡，謝謝！

### 面試過程檢討

#### interviewer
- [0:26](https://youtu.be/cp0ozG-aUEs?t=26) 講解 pivot index 在頭尾時的講法不太順
- [5:07](https://youtu.be/cp0ozG-aUEs?t=307) 應該要多跟 interviewee 討論其它種做法

#### interviewee
- [1:30](https://youtu.be/cp0ozG-aUEs?t=90) 沒有注意到 function 名稱打錯了，應是 pivotIndex。
- [1:32](https://youtu.be/cp0ozG-aUEs?t=32) 可以提到這個作法的時間複雜度應該是 `O(n^2)`
- [3:57](https://youtu.be/cp0ozG-aUEs?t=237) 沒有注意到 rsum 打成 rums 了。