# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者: 柯基-Corgi

## [319. bulb switcher](https://leetcode.com/problems/bulb-switcher/)
> [錄影](https://www.youtube.com/watch?v=eHdCI2ooSdM)
> C++/漢語

**測驗說明以及問答**
+ 這一題我從題目的直覺算法，並藉由interviewer暗示還有更好的解，一路改進達到最佳解。
1. $O(N^2)$暴力解，把燈泡依據題目敘述一步一步做開關。
2. $O(N^2)$觀察解，得出第$N$個燈泡是否開關，其實跟能整除$N$是奇偶數個有關。
3. $O(N)$數學解，發現解法$2$能用判斷是否為完全平方數，來取代尋找因數個數。
4. $O(1)$最佳解，根據開根號${\sqrt N}$的特性，整數部分就是小於$N$的完全平方數個數。

**最終程式解**

class Solution {
public:
    int bulbSwitch(int n) {
        return sqrt(n);
    }
};

**自評**
+ interviewer 應該避免完全讓 interviewee從頭到尾完全自己閱讀題目，應該要先帶過一次之後再讓對方進行下去。
+ interviewer 應該避免稱呼自己為面試官，因為不確定對方是否會在意。
+ interviewee 可以多使用肢體語言，這樣可以讓情境更加舒緩生動。
+ 英文名字念錯。

## [390. elimination game](https://leetcode.com/problems/elimination-game/)
> [錄影](https://www.youtube.com/watch?v=hRWTy91fQ_c)
> C++/漢語

**測驗說明以及問答**
+ 這一題我從題目的直覺算法，並發現自己剛好卡在最後兩個測資TLE所以就只好，改進算法，後來改由判斷透過刪除元素之後何時會增加開頭元素的值來做判斷。
1. $O(N^2)$暴力解，把元素依據規定依序做刪除。
2. $O(\log N)$觀察解，發現數列每經過一round的刪除，等差會變成$2$倍，且從頭開始刪除時，開頭元素必加上等差；從尾開始刪除時，則必須判斷數列元素個數為奇數或偶數。

**最終程式解**

class Solution {
public:
    int lastRemaining(int n) {
        int base = 1, size = n, ans = 1;
        bool round = true;

        while(size != 1){
            if(round){
                ans += base;
            }
            else{
                if(size&1){
                    ans += base;
                }
            }
            base *= 2;
            round = !round;
            size /= 2;
        }
        return ans;
    }
};

**自評**
+ interviewer 應該避免完全讓 interviewee從頭到尾完全自己閱讀題目，應該要先帶過一次之後再讓對方進行下去。
+ interviewee 應該說明為何時間複雜度為何。
+ interviewee 的舉例很淺顯易懂，有助於幫助interviwer理解自己的思路。
+ 其實除了把%2改成用&1可以增加效率以外，/還有*也可以改用>>，<<加速。
+ 英文名字念錯。

## [15. 3sum](https://leetcode.com/problems/3sum/)
> [錄影](https://www.youtube.com/watch?v=NxT_sul9MPo)
> C++/英語

**測驗說明以及問答**
+ 這一題我從題目的直覺算法，並自己假設應該過不了時間限制，產生出比較好的解。
1. $O(N^3)$暴力解，歷遍所有數對，找出所有可行解。
2. $O(N^2)$排序解，經過排序以後我們可以利用當前總和來判斷該往前或往後移動。

**最終程式解**

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        set<vector<int>> data;

        for(int i = 0 ; i < nums.size() - 2 ; i++){
            int j = i + 1, k = nums.size() - 1;
            while(j < k){
                int sum = nums[i] + nums[j] + nums[k];
                if(sum == 0){
                    data.insert({nums[i], nums[j], nums[k]});
                    j++;
                    k--;
                }
                else if(sum > 0){
                    k--;
                }
                else{ //sum < 0
                    j++;
                }
            }
        }
        vector<vector<int>> ans;
        for(auto &temp:data){
            ans.push_back(temp);
        }
        return ans;
    }
};

**自評**
+ 英文能力還需要加強，有時候關鍵字口齒不清。
+ 使用英文講話時音量太低，不如漢語時來的有自信且順暢。
+ 應逐步說明所有步驟的複雜度，並把它們整理為上界，而非直接說明該演算法的複雜度。

---

## 第二次作業他評01
### interviewer
- [ ] 可改進之處
* 應該不要選擇讓面試者直接在leetcode上面打程式的方式，不然可能面試者隨手捲動頁面就不小心有提示或解法關鍵字跑出來，並且測試程式正確性也是面試的一部分，所以讓面試者自己檢查會更能看出他的能力。
* 只有英文版本有講解題目。

### interviewer
- [ ] 優點
* 能夠想出不斷進步的方法
* 詳細舉例說明解法，還有找出解法中需要注意的特例。

- [ ] 可改進之處
* [8:30](https://youtu.be/eHdCI2ooSdM?t=510): 這邊反問面試官理不理解感覺蠻奇怪的。
* 錄製的聲音有點小。

## 第二次作業他評02
### interviewer
- [ ] 可改進的地方
* [00:20](https://youtu.be/eHdCI2ooSdM?t=20): 這邊應該是interviewer來做講解，而不是讓interviewee去閱讀。
* 語調有點含糊，說話速度可以放慢一點，interviewee可能會比較好懂。
* 避免讓interviewee直接用leetcode作答，最好用google document並且確認沒有開啟其他分頁。

### interviewee
- [ ] 優點
* 有按照REACTO的步驟進行問答。
* [1:22](https://youtu.be/eHdCI2ooSdM?t=82): 有舉例子
* 有邊打字邊講解

- [ ] 可改進的地方
* [5:44](https://youtu.be/hRWTy91fQ_c?t=343): 邊打字邊講解的時候避免只講要打什麼字，而是講邏輯跟功用。
* 講話有點黏在一起，咬字可以再清楚一點。

## 第二次作業他評03
- [ ] 可改進地方
* 中文影片: 應為 interviewee & interviewer 而非 interviwee & interviwer
* 英文影片: 雜音嚴重、聲音忽大忽小

### interviewer
- [ ] 優點
* 性能沒滿足要求時有提出讓interviewee去改進

- [ ] 可改進的地方
* 不應該直接使用leetcode避免碰到，專業刷題怪（背題怪）可以將題目用口述，只顯示部分資訊就好，讓其沒辦法通過太多的資訊回憶背過的程式
* 通常來說不會讓interviewee有辦法自行測試測資是否有通過，應讓其自行分析結果，並在BigO不理想的情況下提出另一個解法
* 使用情境帶入，為什麼要實作這個code。
> 以Leetcode319題為例：請你想象這是某個xxx東西（系統等）的運行方式，上面有n個狀態燈是表示現在的狀態。當突發情況導致系統斷電你需要通過delta base中的log資料(可以是時間、操作記錄等) 以最快速的方式將系統恢復到當前的運行狀態
* 可以在interviewee解說的時候提供反應、讓其知道正在往對的方向前進

### interviewee
- [ ] 優點
* 例子的部分有跟interviewer確認是否正確，並且有清晰地打出來
* 有嘗試先使用較差的方法

- [ ] 可改進的地方
- 寫程式要小心點，一般上沒有機會可以自己test測資，通常只能分析對不對 => fn(input).expect(output)
- 在講解時應少用“我們”這個詞，因為只有interviewee自己在寫，interviewer只是在聽。

## 第二次作業他評04
### interviewer
- [ ] 可改進的地方
* [8:05](https://youtu.be/hRWTy91fQ_c?si=xk-8gwPaEMBR4YHb&t=480): 可以嘗試要求 interviewee 分析 memory limit exceeded 的原因

### interviewee
- [ ] 優點
* 方法解說得很清楚並且有一步步的去優化

- [ ] 可改進的地方
* [4:50](https://youtu.be/eHdCI2ooSdM?t=290): 可以改成沒有分支的形式 `bulbs[j-1] = !bulbs[j-1];`
* [14:48](https://youtu.be/hRWTy91fQ_c?si=Xv5zYZ-8tOj0RNVW&t=888): mod 念法 mäd

## 第二次作業他評05
### interviewer
- [ ] 優點
- 題目以書面的方式呈現，減少只有口語敘述的理解錯誤
- [ ] 可改進的地方
- 前期討論的時候，就可以把暴力解與觀察解有多一點的互動，像是問一句你覺得為什麼會TLE，讓interviewer可以透過互動了解interviewee是怎麼想的

### interviewee
- [ ] 優點
- 一步步優化，讓複雜度不斷下降很棒
- 寫code清楚流暢
- [ ] 可改進的地方
- 講步驟跟步驟之間可以留一點空拍，讓interviewer有喘息的時間可以消化與想問題問你，與你互動加分