# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者：胡迪-Woody
> 😎：interviewer
> 🤠：interviewee

## [2582. Pass the Pillow](https://leetcode.com/problems/pass-the-pillow/description)
> [影片連結](https://www.youtube.com/watch?v=cJuaoweDGh0)
> [Google Docs](https://docs.google.com/document/d/1ULIazo639iR3hV1EJgnCi0plIvMRx7p_ijGxLEhOE4s/edit?usp=sharing)

### 問答過程
😎: Hello, assuming today we are at a party, and we want to play an icebreaker game. The game rules are that there are n people standing in a line labeled from 1 to n. Starting from player 1 holding a pillow, the pillow is passed to the next player every second. When it reaches player n, in the next second, it is passed back to player n-1. This continues until it reaches player 1 again, and then it changes direction to pass it backward until the time is up.
Now, given two parameters, n players and time in seconds, help me determine which player will have the pillow in their hand when the time is up.
🤠: So, if we have 5 people and 7 seconds, the order of passing the pillow is 1 -> 2 -> 3 -> 4 -> 5 -> 4 -> 3 -> 2, with the pillow ending up at person 2.
😎: Correct.
🤠: My idea is that if time is significantly larger than n, then the sequence will cycle from 1 to n to 1 repeatedly. So, when the pillow returns to person 1, it will start the same cycle again. Therefore, you can calculate the remainder of full time divided by the cycle time.
This will tell you how many cycles have occurred, and you can also determine how many seconds are left after completing those cycles.
😎: Good idea. You can try to code it up.

class Solution {
public:
    int passThePillow(int n, int time) {
        int cycle = (n - 1) * 2;
        int pass = time % cycle;
        
        if (pass < n) {
            return 1 + pass;
        } else {
            int pass_forward = pass - (n - 1); 
            return n - pass_forward;
        }
    }
};

🤠: Now we know how many the *pass* is, there are two possible situation. If the *pass* is less than the number of people *n*, it means the pillow is passed from person 1 to person n.
On the other hand, when the *pass* is greater than the number of people *n*, the pillow is passed forward from person n back to person 1.
😎: Okay, it looks great, thanks for today's interview.

### 初步檢討
* 英語表達不夠流暢，過多冗言贅字

### 面試過程檢討
**Interviewer**
優點 :
* 加入肢體動作感覺面試過程較豐富

可改進的地方
* 可以在後面提問有什麼方法改進或是能讓程式更短更簡潔。

**Interviewee**
優點 :
* 邊打程式邊講解。

可改進的地方
* [01:48](https://youtu.be/cJuaoweDGh0?t=110) 在講解自己的解決方法，可以在下方空白舉出例子，更能讓別人理解為何要這樣寫，且像是第 4 行、第 8 行、第 10 行，為何要減 1 ，搭配例子可以更快的讓面試官理解。

## [202. Happy Number](https://leetcode.com/problems/happy-number/description/)
> [影片連結](https://youtu.be/A6OyWK_euP0)
> [Google Docs](https://docs.google.com/document/d/1BnRFK8EeyWip7DV3gufKTFfHXnOOS8KEs4tKnj0vYIY/edit?usp=sharing)

### 問答過程
😎：我希望你能撰寫一套演算法來幫我找出「快樂數」，而所謂的快樂數定義是指隨機選一個正整數，並將該數字替換為其原本各個位數的平方和。不斷重複此過程，直到數字最終等於1，另一種情況則是是它會進入一個不包括1的無限循環中。
所以，如果n最終過程在1結束，則他是一個快樂數，請回傳 true；如果不是的話，則回傳 false。
🤠：所以比如說24這個數字，就會變成$2^2$+$4^2$=20。然後20又會變成$2^2$+$0^2$=4，繼續一直計算下去直到變成1或者是無限迴圈，這樣理解正確嗎？
😎：沒錯，理解正確。
🤠：那我的作法會是先撰寫一個計算位數平方和的函式，再來看他這個數是否會再經過幾輪的迭代之後變成已經出現過的數，因為這代表它又會繼續做一樣的運算，導致進入無限迴圈。如果遇到這個狀況的話，就可以跳出迴圈並 return false。
😎：那你要如何判斷他會是否已出現過呢？
🤠：我會建立一個hash set，在每次迭代判斷這個位數平方和是否已經在set裡面，沒有的話就將它也放進set裡，然後做下一次運算。持續迭代直到set裡已經有了這個數，就可以跳出迴圈。
😎：不錯的想法，你可以試著寫寫看程式了
🤠：

class Solution {
public:
    // 第一步是計算各個位數的平方和
    int sumDigits(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10; 
        }
        return sum;
    }
    
    // 宣告一個 set 儲存每次各個位數平方和的結果
    // 若是出現重複的數，代表他將重複執行前一輪的運算，並無限輪迴下去
    bool isHappy(int n) {
        set<int> s;
        while (n != 1) {
            s.insert(n);
            n = sumDigits(n);
            if (s.count(n)) {
                return false;
            }
        }
        return true;
    }
};

😎：想問在計算位數平方和時，他的時間複雜度與空間複雜度大約為多少？
🤠：我們必須知道n為幾位數，若以$2^{31}$為例，log($2^{31}$) = 31 x log2 = 31 x 0.301 = 9.3，因此大約為10位數。所以時間度複雜度與空間大約為 O(log n)

### 初步檢討
*

### 面試過程檢討
**Interviewer**
優點 :
* 口齒清晰。

可改進的地方
* 可以舉出不為快樂數的例子，或是舉出會進入無窮迴圈的情況。

**Interviewee**
優點 :
* 撰寫程式不是一行一行照腳本那樣寫，而是提到哪做到哪，可以更讓人認為是了解題目以及是有邏輯的在撰寫。
* 在使用 STL 函式有邊配合講解。

可改進的地方
* 可以將視窗大小放大或是字體放大，在程式規模不大的話，比較好讓人看得清楚。

## [75. Sort Colors](https://leetcode.com/problems/sort-colors/description/)
> [影片連結](https://youtu.be/_9745MwjK1A)
> [Google Docs](https://docs.google.com/document/d/1PTCaPdJk1jO2BVTGHVoEkdEjUa_nH_AAsNrzp96nitw/edit?usp=sharing)

### 問答過程
😎：哈囉，在這邊想問你，假如我給定一個包含 n 個紅色、白色或藍色物品的陣列 nums，並對它們進行就地排序。以便相同顏色的物品相鄰，而顏色的順序為紅色、白色和藍色，我們也將使用整數 0、1 和 2 分別表示紅色、白色和藍色。這邊有幾個例子。
🤠：意思就是我必須將陣列中散亂的0、1跟2按照順序排序，並且不能夠複製到一個新的陣列，而是對原有的陣列直接進行操作對嗎？
😎：沒錯，理解正確
🤠：所以我必須將資料分成三類，那我的做法會是建立兩個指標為left和right，在left右邊的元素為0，在right右邊的都為2。再建立一個mid指標從陣列的開頭往結尾逐一判斷，如果指到的元素為0，則把他跟left左邊的元素交換，再把left指標往右一格。
😎：不錯的想法，那你可以撰寫程式了。
🤠：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left = 0;
        int mid = 0;
        int right = nums.size() - 1;
        
        while (mid <= right){
            if (nums[mid] == 0) {
                swap(nums[mid], nums[left]);
                left ++;
                mid ++;
            } else if (nums[mid] == 1) {
                mid ++;
            } else if (nums[mid] == 2) {
                swap(nums[mid], nums[right]);
                right --;
            } 
        }
    }
};

😎：看起來沒有太大問題，不過你可以用實際的例子簡單測試看看嗎？
🤠：好的，那我就用上面範例表示出每次迭代的情況。
😎：請問這樣的時間複雜度與空間複雜度為多少呢？
🤠：因為只有一層迴圈，所以時間複雜度為O(n)，而因為他都是對原有的陣列做互換，所以空機複查度為O(1)。
😎：那假設今天我想要排序5個顏色，甚至更多呢？
🤠：這樣的話原理基本上相同，用left指標將最小的數0放在最左邊，並將left遞增；而right指標將4放在最右邊，並將right遞減。
全部計算完之後中間就會剩下123混在一起。這時候就換成把1放在left指標左邊，left也繼續往內遞增，把3放在right指標右邊，right也繼續往內遞減，如此一來中間只會剩下2。

### 初步檢討
* left與right常常口誤搞混，需多注意

### 面試過程檢討
**Interviewer**
優點 :
* 口條清晰

可改進的地方
* 雖然畫面上有題目以及範例，但面試官也可以自己來舉出例子來講解，對於這種用數字代表某個情況的題目，這樣也方便面試者理解問題。

**Interviewee**
優點 :
* 有配合例子講解。

可改進的地方
* [13:31](https://youtu.be/_9745MwjK1A?t=811): 在舉例子的時候，第一個例子可以用打字輸入的，後續再使用複製貼上會比較符合實際面試情況。

## 第二次作業 - 他評 02
### Interviewer
- [ ] 優點
* 使用手勢輔助說明
* 語調輕快，面試氣氛良好
* 75. Sort Colors 最後有對題目進行延伸討論

### Inerviewee
- [ ] 優點
* 使用手勢輔助說明
* 一邊寫一邊解釋程式碼
* 配合肢體語言解釋程式邏輯，讓人清楚知道思考的步驟。

- [ ] 可改進的地方
* [1:20](https://youtu.be/cJuaoweDGh0?si=4FzC3YKloUTu22Fa&t=80), [4:33](https://youtu.be/cJuaoweDGh0?si=zsiFGDBv3aT1wMyO&t=273): 建議將舉的例子打在螢幕上，方便雙方理解。
* (英) 建議變數 `pass` 可以考慮命名為 `remaintime`，因為在後面頻繁提到 Pass 單字，會有混淆的疑慮。
* 根據 REACTO 步驟，建議最後可以簡短的對程式碼進行測試。