2023 年「資訊科技產業專案設計」作業 1

貢獻者: 鮪魚-maguro
interviewer: 問
interviewee: 答

模擬面試錄影1(漢)
模擬面試錄影2(漢)
模擬面試錄影(英)

改進方案&初步檢討

• Repeat: 重複提問，確認自己理解原本的要求
  • 重複提問的部分我只有用類似自言自語的方式，應該向面試官盡量去詢問，避免理解錯誤。
• Examples: 針對題目條件，舉出符合的案例，不限於特例
  • 這部分沒有做到，應該要在一開始就先考慮幾個範例，並且試著提出edge case
• Approach: 說明自己打算採用的方案
  • 說明後可以和 interviewer 討論
• Code: 撰寫程式
  • 在寫程式時應盡量精簡講重點，避免冗言贅字，
• Test: 若不能實際測試，那說明驗證程式的方案
  • 如同Examples

1046. 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

過程的討論

問：
陣列代表著每一位運動員他在這項競技所獲得的分數
那請你回傳他的結果
分別是所有運動員裡面的第幾名

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

這邊用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

程式碼

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裡面面試者好像沒有先提到用C++ 寫會比較快，反而是在interviewer主動說"你說用C++寫的方式會比較快"後才提出，可能剪輯順序有錯誤，不然看起來很怪。
  2.程式碼錯誤沒有指出。

關於interviewee

• 優點
  1.有先說明要用哪種語言實作
• 可改進之處
  1.依照REACTO的步驟的話，有點太快進到撰寫程式碼的步驟，應該先舉例和大概說明實作方法比較好理解。後續也缺乏測試程式正確性的步驟。
  2.寫Last Stone Weight這題的C語言程式的時候可能需要邊打邊說，影片裡好像蠻常是先打完一小段再說，像是6:37但是等到打完一小段程式碼再說明，中間的時間容易讓人想放空。後面寫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前有先用例子重新解釋題目

可改進的地方:

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