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

貢獻者: 毆塌膩-OHTANI
Video:
模擬面試影片(漢)
模擬面試影片(漢)
模擬面試影片(英)

740. Delete and Earn

Interviewer：
這個題目會給你一個存整數的array叫做nums[]。
你必須根據以下規則來獲取最多的分數：

選擇任意nums[i]並刪除，就可以獲得nums[i]的分數。
然後，必須刪除等於nums[i]-1的每一項以及等於nums[i]+1的每一項。
重複以上操作，最後獲得並回傳可獲得的最高分數。

Interviewee：
好的，那我舉個例子確認一下我的理解是否正確
假設輸入的陣列nums = [3,4,2]，
首先可以取出4並獲得4分，然後陣列中的3會被刪除，此時陣列中剩下[2]。
再來可以取出剩下的2並獲得2分。
所以我們能獲得的最高分是6分。

再一個較複雜的例子，假設輸入的陣列nums = [2,2,3,3,3,4]，
首先可以取出3並獲得3分，然後陣列中的所有2和4會被刪除，此時陣列中剩下[3,3]。
再來可以取出剩下的其中一個3並獲得3分，
然後再取出最後一個3，獲得3分，
這個例子我們能獲得的最高分是9分。

Interviewer：
你的範例沒有錯，
另外，這個題目的限制是：
1 <= nums.length <= 2 * 10^4
1 <= nums[i] <= 10^4
如果沒問題的話，可以開始實作你的方法。

Interviewee：
我的想法是，先找出輸入陣列的最大整數max_num，
然後再使用另一個陣列accu_num[max_num+1]來儲存輸入陣列不同數字的累加值。

最後，使用Dynamic Programming的方式，從accu_num的index=0到index=max_num，算出能獲得的最高分數。

Solution

int deleteAndEarn(int* nums, int numsSize){
    int max_num=0;
    for(int i=0;i<numsSize;i++){ //先找出最大整數
        max_num=fmax(max_num,nums[i]);
    }
    printf("max_num=%d\n",max_num);

    int accu_num[max_num+1]; //建立array儲存每個number可獲得的pts總和，最小數字為1，但還是從0到n+1來index。
    for(int i=0;i<max_num+1;i++) // init
        accu_num[i]=0;
    
    for(int i=0;i<numsSize;i++){
        accu_num[nums[i]]=accu_num[nums[i]]+nums[i];
    }
    
    /*
    //print array accu_num[];
    printf("accu_num[]:\n");
    for(int i=0;i<max_num+1;i++){
        printf("%d ",accu_num[i]);
    }
    */
    
    //accu_num[]:取了[n]，就要刪除[n-1]、[n+1]。
    //DP:先確定長度0、長度1能取得的最高分
    int opt_pts[max_num+1];//計算可獲得最多的pts
    opt_pts[0]=0;
    opt_pts[1]=accu_num[1];
    for(int i=2;i<max_num+1;i++){
        opt_pts[i]=fmax(opt_pts[i-1],opt_pts[i-2]+accu_num[i]);
    }
    return opt_pts[max_num];
}

Interviewer：
能分析你的程式的時間複雜度嗎？

Interviewee：
好，從最一開始先找出max_num，到計算accu_num，時間複雜度都是O(n)。
最後使用DP來計算最佳解也是，但需要額外的陣列來儲存DP方法所需的資訊。

746. Min Cost Climbing Stairs

Interviewer：

題目會輸入一個儲存整數的array叫做cost[]，其中cost[i]是樓梯第i階的成本。
付出第i階的成本，就可以選擇往上爬一階或兩階。

最一開始，可以選擇從第0階開始，也可以從第1階開始爬樓梯。
最後要回傳爬到樓梯頂端消耗的最低成本。

Interviewee：
好的，那我舉個例子確認一下我的理解是否正確。
假設輸入陣列是[10,15,20]，
我會選擇從第1階開始爬，然後爬2階到樓梯頂部。
最後花費的最低成本就是15。

再一個較複雜的例子，假設輸入的陣列是[1,100,1,1,1,100,1,1,100,1]，
我選擇從第0階開始爬，付出的成本是1，
往上爬2階到第2階，付出的成本是1，
再往上爬2階到第4階，付出的成本是1，
再往上爬2階到第6階，付出的成本是1，
再往上爬1階到第7階，付出的成本是1，
再往上爬2階到第9階，付出的成本是1。

最後到達樓梯頂部，總共花費的成本是6。

Interviewer：
你的範例沒有錯，
另外，這個題目的限制是：
2 <= cost.length <= 1000
0 <= cost[i] <= 999

如果沒問題的話，可以開始實作你的方法。

Interviewee：
這題我想可以用DP的方式解決，使用額外的陣列來在計算爬樓梯的途中，每一階累計的最低成本。
給定第0階和第1階的初始條件，計算第2階到第n-1階的最低成本。
最後回傳第n-2階和第n-1階兩者的較小值作為最低成本。

Solution

int minCostClimbingStairs(int* cost, int costSize){
    int dp_a[costSize];
    //int dp_b[costSize];
    dp_a[0]=cost[0];
    dp_a[1]=cost[1];
    for(int i=2;i<costSize;i++)
        dp_a[i]=fmin(dp_a[i-1],dp_a[i-2])+cost[i];

    /*
    for(int i=0;i<costSize;i++)
        printf("%d ",dp_a[i]);
    */

    return fmin(dp_a[costSize-1],dp_a[costSize-2]);
}

Interviewer：
能分析你的程式的時間複雜度嗎？

Interviewee：
好，我們使用DP來計算最佳解，從第2階到第n-1階，時間複雜度是O(n)。
不過需要花費額外的空間來儲存DP方法所需的資訊。

278. First Bad Version

Interviewer：
The problem is that you are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check.
Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad.
Implement a function to find the first bad version.
You should minimize the number of calls to the API.

Interviewee：
For example, suppose that Input: n = 5, bad = 4

We can check the version is bad or not ,by calling API as below：
call isBadVersion(3) return false
call isBadVersion(5) return true
call isBadVersion(4) return true
Then 4 is the first bad version.

Interviewer：
Your example is correct,
In addition, the constraints of this question are:
1 <= bad <= n <= 231 - 1
If there is no problem, you can start implementing your program.

Interviewee：
Because the description of this problem has said that all the versions after a bad version are also bad.
So, we can use binary search to solve this problem.
We declare two variable "top" and "bottom", for calculating the variable "next" indicate the next version we are going to check.

Solution

int firstBadVersion(int n) {
    long int next=n/2;
    long int top=n;
    long int bottom=0;
    while(top-bottom>1){
        if(isBadVersion(next)==true)
            top=next;
        else
            bottom=next;
        next=round((bottom+top)/2);
    }
    return top;
}

Interviewer：
Can you analyze the time complexity of your program?

Interviewee：
Sure, because we are using binary search method.
For the common cases, we will have time complexity in O(log n).

第二次作業-他評01

缺少一部漢語影片

關於interviewer

• 可改進之處

• 1:58 可以先詢問受試者Approach的想法是什麼再請受試者開始coding，方便了解受試者的對於程式設計的方針。
• 7:06: "It sounds like the program is work."，我想應該要請受試者在撰寫玩code之後，帶入example去做testing，才能確認程式碼是正常運作無誤。

interviewee

• 優點

• 畫面乾淨 👏

• 可改進之處

• 6:10: 對話空白時間有點太長，可以加上一些文字說明或是分配一下要講解程式碼的話 (一邊coding一邊講解)。

第二次作業-他評02

Interviewer

• 優點

• 題目解釋清楚

• 可改進之處

• 感覺可以加入點自我介紹增加互動感

第二次作業-他評03

Interviewer

• 優點

• 畫面很清楚

• 可改進之處

• 感覺可以針對自己再多一點介紹

interviewee

優點

• 畫面很乾淨

可改進之處

• 打程式的畫面感覺可以放大一點，比較清晰

第二次作業-他評04

• 優點

• 口齒清楚，用倍速聽也不會有聽不清楚的地方
• 寫Code的速度算快

• 可改進之處

• 少了測試(test)的部分，加上去會比較好。
• 建議把題目做一些包裝，不要直接用原本的題目。