# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者: 鮪魚-maguro
> interviewer: 問
> interviewee: 答

> [模擬面試錄影1(漢)](https://www.youtube.com/watch?v=ntYhICGs6-o)
> [模擬面試錄影2(漢)](https://www.youtube.com/watch?v=LRuRTilYY24)
> [模擬面試錄影(英)](https://www.youtube.com/watch?v=jh_uQVzuHtI)
### 改進方案&初步檢討
* Repeat: 重複提問，確認自己理解原本的要求
* 重複提問的部分我只有用類似自言自語的方式，應該向面試官盡量去詢問，避免理解錯誤。
* Examples: 針對題目條件，舉出符合的案例，不限於特例
* 這部分沒有做到，應該要在一開始就先考慮幾個範例，並且試著提出edge case
* Approach: 說明自己打算採用的方案
* 說明後可以和 interviewer 討論
* Code: 撰寫程式
* 在寫程式時應盡量精簡講重點，避免冗言贅字，
* Test: 若不能實際測試，那說明驗證程式的方案
* 如同Examples
## [1046. Last Stone Weight](https://leetcode.com/problems/last-stone-weight/)
### 過程的討論
*問：
挑選出這串石頭裡面最重的兩顆
讓兩顆石頭去互相的撞擊
如果這兩顆石頭重量一樣的話
那兩顆石頭都會消失
不是的話大的會留下來小的會消失
一路進行下去直到最後只剩下一顆或者是沒有石頭為止*

答：
maximum他就是負責去找出這個array裡面最大跟第二大的
所以我的參數要給他我這個array
那因為是c語言
所以同時也要給它這個array這size
然後我這邊定了兩個變數
這邊跟正常的想法比較不一樣的是
它其實代表的不是最大值的那個值
而是它會在這個array的第幾個位置
我會從最開頭一路找找到這個正列的最結束
那一旦發現有人比IMAX還要大那這個時候他就會去取代IMAX
根據c語言的特性
array帶進來之後裡面的值做的變動
他的參數也是會跟著改變的
最開始的這個數時值陣列stones它的
裡面的數值會會有越來越多的0
那一旦最後剩只剩下一個數值
其他都是0或全部都是0的時候
這個就是我們的終點

*問：
好你說用C++ 寫的方式會比較快
那能不能請你一樣
的題目用C++的方式再寫一次呢*

答：
主要原因是因為他用的是C++能使用到的一些
function功能會比c來得多
那這邊想要用到priority queue
它的top就會是裡面的最大值
把它拿掉之後
這時候就可以找出第二大的紙

大的最大值跟第二大的值他們會相撞得到一個新的值
有可能是0那也有可能是有實際的值
那不管怎麼樣我們都可以把它加進去
直接做push就好了

然後就會一路去做兩顆石頭的相撞
那我們這邊是砍掉兩個加了一個
所以他的size會越來越小
我必須確保說這個priority queue裡面是還有東西的
當他等於一剩下最後一個的時候
或者是說等於0的時候
他就會離開這個迴圈

*問：
c以及C++兩個回答的方式
出來的結果
可以請你分析這兩個結果
有什麼差異*

答:
時間複雜度會是一樣的
它的時間複雜就是一個單純的常數
空間複雜度的話
在C++ 這邊我們額外新增一個priority queue
所以這邊的空間複雜度會大一點
不過它的差異也都是只有常數的差異而已
所以這兩個做法我覺得在這個地方是C++略勝一籌
### 程式碼

int lastStoneWeight(int *stones, int stonesSize)
{
    while (true)
    {
        int num = 0, idx;
        for (int i = 0; i < stonesSize; i++)
        {
            if (stones[i] > 0)
            {
                num++;
                idx = i;
            }
            if (num == 2)
                break;
        }
        if (num == 1)
        {
            return stones[idx];
        }
        else if (num == 0)
        {
            return 0;
        }
    }
}

void maximum(int *arr, int arrSize)
{
    int i_max1 = 0, i_max2 = 1;
    for (int i = 0; i < arrSize; i++)
    {
        if (arr[i] > arr[i_max1])
        {
            i_max2 = i_max1;
            i_max1 = i;
        }
        else if (arr[i] > arr[i_max2])
        {
            i_max2 = i;
        }
    }
    arr[i_max1] = arr[i_max1] - arr[i_max2];
    arr[i_max2] = 0;
}

class Solution
{
public:
    int lastStoneWeight(vector<int> &stones)
    {
        priority_queue<int> pq(begin(stones), end(stones));
        int ans = 0;
        while (pq.size() > 1)
        {
            int max1 = pq.top();
            pq.pop();
            int max2 = pq.top();
            pq.pop();
            pq.push(max1 - max2);
        }
        return pq.empty() ? 0 : pq.top();
    }
};

## [1282. Group the People Given the Group Size They Belong To](https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/)
### 過程的討論
*問：
陣列代表著每一位運動員他在這項競技所獲得的分數
那請你回傳他的結果
分別是所有運動員裡面的第幾名*

答：
題目既要我們把每位運動員的名次給決定出來
同時又要求說必須要保留原本運動員的順序

這邊用priority queue去做
那其實c的二維陣列也可以做
我這邊做的做法是
就單純沒有按照大小去存
但是我在取的時候有照大小去取
因為priority queue在取的時候
我們就可以很輕易的用top的函式去呼叫它的最大

### 程式碼

class Solution
{
public:
    vector<int> findRelativeRanks(vector<int> &score)
    {
        priority_queue<pair<int, int>> pq;
        for (int i = 0; i < score.size(); i++)
        {
            pq.push({score[i], i});
        }
        vector<int> ans(pq.size());
        for (int i = 1; i < size(score); i++)
        {
            ans[pq.top().second] = i;
            pq.pop();
        }
        return ans;
    }
};

## [338. Counting Bits](https://leetcode.com/problems/counting-bits/)
### 程式碼

int *countBits(int n, int *returnSize)
{
    int *ans = (int *)malloc((n + 1) * sizeof(n + 1));
    *returnSize = n + 1;

    ans[0] = 0;
    for (int i = 0; i < n + 1; i++)
    {
        ans[i] = ans[i] / 2 + i % 2;
    }

    return ans;
}

## 第二次作業-他評01
### 關於interviewer
- [ ] 優點
1.題目講解清晰
- [ ] 可改進之處
1.Last Stone Weight影片[14:30](https://youtu.be/ntYhICGs6-o?t=869)裡面面試者好像沒有先提到用C++ 寫會比較快，反而是在interviewer主動說"你說用C++寫的方式會比較快"後才提出，可能剪輯順序有錯誤，不然看起來很怪。
2.程式碼錯誤沒有指出。

### 關於interviewee
- [ ] 優點
1.有先說明要用哪種語言實作
- [ ] 可改進之處
1.依照REACTO的步驟的話，有點太快進到撰寫程式碼的步驟，應該先舉例和大概說明實作方法比較好理解。後續也缺乏測試程式正確性的步驟。
2.寫Last Stone Weight這題的C語言程式的時候可能需要邊打邊說，影片裡好像蠻常是先打完一小段再說，像是[6:37](https://youtu.be/ntYhICGs6-o?t=397)但是等到打完一小段程式碼再說明，中間的時間容易讓人想放空。後面寫C++反而沒有這個問題。
3.C程式碼好像有問題，至少我放進leetcode後沒有通過。Last Stone Weight這題，C語言版本寫了兩個function但是lastStoneWeight卻沒呼叫maximum，也沒有說明要怎麼搭配使用這兩個function。
4.沒有討論到特例，當輸入的stones陣列長度只有1的時候。
參考修改程式碼:

    void maximum(int *arr, int arrSize)
    {
        int i_max1 = 0; //假設第一大是stones[0]
        int i_max2 = 1; //假設第二大是stones[1]
        if(arr[i_max1]<arr[i_max2]){//如果stones[0]<stones[1]要對調
            i_max1=1;
            i_max2=0;
        }
        for (int i = 2; i < arrSize; i++)
        {
            if (arr[i] > arr[i_max1])
            {
                i_max2 = i_max1;
                i_max1 = i;
            }
            else if (arr[i] > arr[i_max2])
                i_max2 = i;
        }
        arr[i_max1] = arr[i_max1] - arr[i_max2];
        arr[i_max2] = 0;
    }
    int lastStoneWeight(int *stones, int stonesSize)
    {   
        if(stonesSize==1)
            return stones[0];
        while(true){
            maximum(stones,stonesSize);//smash
            int num = 0; int idx=0;
            for (int i = 0; i < stonesSize; i++)
            {
                if (stones[i] > 0)
                {
                    num++;
                    idx = i;
                }
                if (num == 2)
                    break;
            }

            if (num == 1)
                return stones[idx];
            else if (num == 0)
                return 0;   
        }
    }

5.英文版本影片中要使用C語言動態記憶體配置，我想應該不用特別跟面試官講解為什麼，而且你直接講中文名稱XD，後面也很容易不小心講出中文名詞。
6.英文版本中，malloc語法錯誤應該是sizeof(int)，應該先提出要用DP實作的想法是什麼，再開始寫程式，雙方比較好討論，也比較好找出錯誤。程式的部分for迴圈可以修改成這樣，應該就會對了。

    ans[0]=0;
    for (int i = 1; i < n+1; i++)
    {
        if((i-1)%2)
            ans[i] = ans[i/2];
        else
            ans[i]=ans[i-1]+1;
    }

## 第二次作業-他評02
### 關於intervier
#### 優點:
* 有些題目有經過變化，而不是直接放leetcode原題
* 能夠清楚表達題目
#### 可改善的地方:
* 與interviewee的互動不夠多，這是interview不是考官和考生的關係，應該多和interviewee溝通，來增進互相的理解。

### 關於interviewee
#### 優點:
* 在寫程式的時候有邊寫邊解釋寫法跟邏輯，避免寫程式的對話空白期。
* 講話邏輯清楚且語調穩定
#### 可改進的地方:
* 沒有完全遵照REACTO的方式
* 可以在開始寫程式之前，解釋自己的邏輯給interviewer聽，確認邏輯是否錯誤，如有錯誤想不出來可適時提問。
* 也可以先舉幾個簡單的例子來映證自己的想法。
* 在寫程式時可加快打字速度，畢竟時間有限
* 可以再加強英文的表達能力，避免過多的冗詞贅字。

## 第二次作業-他評03

#### 優點:

* 在開始coding前有先用例子重新解釋題目

#### 可改進的地方:

* 邊界條件應該不會是面試官直接說出來（一開始就打在螢幕上）而是要透過一問一答方式來回確認所有要求