# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 2
>[vedio](https://youtu.be/kMVLHeU5rRA)
>
圖示 :
:bear: : interviewer
:tropical_fish: : interviewee

## Revisit: [1827. Minimum Operations to Make the Array Increasing](https://leetcode.com/problems/minimum-operations-to-make-the-array-increasing/)

:bear: : 您好，我是這間公司的工程師，接下來的時間由我來幫公司的同事來面試您的能力是否為我司所需要。因為時間有限的關係，我們就直接進入正題。

:bear: : 在我們公司中，我們目前正在研發一種推薦排列的技術。而在這個技術中，有一個小任務的內容大致上來說，是將資料庫裡的亂數編號資料做最小次數的加 1，以形成一個嚴格遞增的資料組，使得他們各自的編號都不一樣，以利於在做推薦排列後也可以由編號知道他們是什麼產品。

舉例來說，假設我們有一組編號資料是

nums = [1,1,1]

那該小任務可做以下操作

將 nums[2] 加一
將 nums[1] 加一
將 nums[2] 加一

使得資料組的編號變成一個嚴格遞增的型態，也就是 [1, 2, 3]。

並且，上述的操作次數也是他的最小次數 - 3

:bear: : 那這理想請問，如果將它交給您設計，您會如何設計它？

:tropical_fish: : 我想先問一個問題，請問貴司所用的資料會存在負數嗎 ？

:bear: : 我看一下，不會有負數的存在，然後 ... 也沒有零，就都是自然數。

:tropical_fish: : 了解，在開始之前，我想先舉一個例子，來確認我對這任務的理解。

假設資料組的編號為

nums = [1,5,2,4,1]

那就我的理解來說，這個任務應該要運作的最小次數為

14

:bear: : 嗯，以您的例子來說，確實會運行 14 次。

:tropical_fish: : 我大概了解了。那接下來我先闡述一下我預計的作法。在這題中，我會使用貪婪法的來實作它。具體的流程是對每個個資料組中的元素做迭代，且在每一次的迭代中，我會將其和後一位的編號做比對。如果後一位的元素比現在迭代到的編號來的小或相同的話，我會讓他進一個迴圈做迭代加 1。這樣的作法會是一個 O(n+m) 的時間複雜度（n：資料組的大小 ; ｍ：迭代呼叫小任務的次數）。

:bear: : 聽起來不錯，你可以將它轉換成程式碼並驗證正確性嗎 ？

:tropical_fish: : 沒問題，在這裡我會用 C++ 去實作它。

void renumber(vector<int>& nums, int index) {
    nums[index]++;
}

void check(vector<int>& nums) {
    
    for (int i = 0 ; i < nums.size() - 1 ; i++)
    {
        if (nums[i] >= nums[i + 1])
        {
            int diff = (nums[i] + 1) - nums[i + 1];
            for (int j = 0 ; j < diff ; j++)
                renumber(nums, i + 1);
        }
    }
}

:bear: : 根據您於履歷上所寫，您有寫驗證程式的經驗。那如果是您的話，您會怎麼用程式的方式，來證明您上面的方法的總操作次數是最小操作次數。

:tropical_fish: : 這裡的話，因為我的上面的方法是貪婪法，我一樣會用貪婪法的方式去實作。流程為：對每個資料組中的元素做迭代；在每一次的迭代中，我會將其和後一位的編號做比對。如果後一位的元素比現在迭代到的編號來的小或相同的話，我將它和現在的元素做相減並加一，得到這次迭代中，將後一位元素的數值超越現在的元素的數值所要做的最小操作次數。而這些每次迭代中所計算出來的最小操作次數，我會用一個整數變數 `result` 來去儲存並總合它。在迭代完所有陣列的元素後，就可以將 `result` 回傳出去。此方法做出來的話是常數時間的複雜度 O(n)，且空間複雜度為 O(1)。

:bear: : 那可以實作出來嗎？

:tropical_fish: : 沒問題，在這裡我會用 C++ 去實作它。

int minOperations(vector<int>& nums) {
    int result = 0;

    for (int i = 0 ; i < nums.size() - 1 ; i++)
    {
        if (nums[i] >= nums[i + 1])
        {
            result += (nums[i] + 1) - nums[i + 1];
            nums[i + 1] = nums[i] + 1;
        }
    }

    return result;
}

此方法做出來的話是常數時間的複雜度，且空間複雜度為 O(1)。

:bear: : 在聽完您的分析後，您擁有的技能感覺確實對我們目前正在研發的產品有蠻大的幫助的。因為時間的關係，今天就先到這裡，感謝您的參與。

## 第四次作業 - 他評
### interviewer
#### 可改進的地方
- [1:53](https://youtu.be/kMVLHeU5rRA?t=113) [0:32](https://youtu.be/kMVLHeU5rRA) [0:44](https://youtu.be/kMVLHeU5rRA) [0:57](https://youtu.be/kMVLHeU5rRA) : 講話會有這個那個ㄜ的贅字。很多想清出再講
- [3:14](https://youtu.be/kMVLHeU5rRA) interviewer : 給予說法
#### 優點
- [0:11](https://youtu.be/kMVLHeU5rRA?t=11) : 用平等的身分與interviewee互動，而不自稱interviewer，生活化的對話
- [0:27](https://youtu.be/kMVLHeU5rRA?t=27) : 帶入生活實際應用場景，結合公司的產品
- [0:47](https://youtu.be/kMVLHeU5rRA?t=47) : 搭配手勢，講話接地氣==> 親切
### interviee
#### 可改進的地方
- [4:23](https://youtu.be/kMVLHeU5rRA?t=263) : 缺少Repeat問題。
- [6:13](https://youtu.be/kMVLHeU5rRA?t=373) [6:25](https://youtu.be/kMVLHeU5rRA?t=385) : 想清楚在講
- [6:46](https://youtu.be/kMVLHeU5rRA?t=406) [8:43](https://youtu.be/kMVLHeU5rRA?t=523) : 不要講大概，就直接說要做3次小任務
- [6:58](https://youtu.be/kMVLHeU5rRA?t=418) : 請對自己所言自信
- [8:04](https://youtu.be/kMVLHeU5rRA?t=484) : 為什麼這樣就知道是最小操作次數?
#### 優點
- [3:43](https://youtu.be/kMVLHeU5rRA?t=223) [8:27](https://youtu.be/kMVLHeU5rRA?t=507) : 會自己問限制問題，有互動
- [9:52](https://youtu.be/kMVLHeU5rRA?t=592) : Example 與 Approach 講得很仔細

### interviewer
#### 可改進的地方
- [1:29](https://youtu.be/kMVLHeU5rRA) : 建議可以事前先練習一下如何說明題目會比較順暢，不然其實有一點聽不太懂題目重點為何
- [1:47](https://youtu.be/kMVLHeU5rRA) interviewer : 建議可以先確認interviewee是否了解題目，再接著舉例說明
#### 優點
- [0:27](https://youtu.be/kMVLHeU5rRA?t=27) : 講話語氣很適合當interviewer，聽起來很專業
- [0:47](https://youtu.be/kMVLHeU5rRA?t=47) : 講話都會搭配動作，可以讓人覺得更親近一點
### interviee
#### 可改進的地方
- [6:13](https://youtu.be/kMVLHeU5rRA?t=373) : 盡量減少ㄜ這種贅字，可以讓過程看齊來更流暢
#### 優點
- [4:56](https://youtu.be/kMVLHeU5rRA?t=592) : 打字非常流暢