# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者: 貓貓-Haku
> video: [中文](https://www.youtube.com/watch?v=CtoGVlt9tjg), [英文](https://www.youtube.com/watch?v=VB4XS4QShhw)

## [377. Combination Sum IV](https://leetcode.com/problems/combination-sum-iv/)
### 面試過程
Interviewer : 歡迎你參加這場面試，我們就直接開始了。給一個由不同整數組成的陣列nums， 請你找出所有由陣列元素加總為 target 的組合個數，元素可以重複使用，順序不同的序列被視為不同組合。這裡有一個範例 nums=[1,2,3], target = 4, 答案是7，可以看到(1,1,2),(1,2,1)雖然使用相同的元素但是順序不同所以是不同答案。有什麼疑問嗎?

Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.

Interviewee : nums 陣列的數值一定是正整數嗎？
Interviewer : 是的，nums 陣列必為正整數，並且數字<1000
Interviewee : 我首先想到使用 backtracking 演算法嘗試所有組合的可能，在每一次 backtracking 我先傳入之前的sum，檢查sum >= target，如果>target就結束，=target答案數量+1。接著把sum加上一個 nums array 裡的元素，傳給下一個backtracking function。
Interviewer : 可以，這是一種解法請你實作出來

//O(n^t)
class Solution {
    int ans=0;
    public int combinationSum4(int[] nums, int target) {
        backtracking(nums,0,target);
        return ans;
    }
    public void backtracking(int[] nums, int sum, int target){
        if(sum>target)return;
        if(sum==target){
            ans+=1;
            return;
        }
        for(int i=0;i<nums.length;i++){
            backtracking(nums,sum+nums[i],target);
        }
    }
}

Interviewer : 好的，但是這種解法時間上太長了，有沒有更好的方法呢?
Interviewee : 有的，我可以使用 dynamic programming，因為答案就是 ans = target-nums陣列元素的加總，我剛剛舉的例子來說也就是說 target = 4, f(4) = f(4-nums[0]) + f(4-nums[1]) + f(4-nums[2]) = f(3) + f(2) + f(1) ，f(3) = f(2) + f(1) + f(0)。以此類推，最終我就可以得到target = 4 的答案

//O(n*t)
//O(n)
class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0]=1;
        for(int i=1;i<=target;i++){
            for(int j=0;j<nums.length;j++){
                if(i-nums[j]>=0){
                    dp[i] += dp[i-nums[j]];
                }
            }
        }
        return dp[target];
    }
}

Interviewer : 今天的面試到此結束，感謝你的參與

## [121. Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)
### 面試過程
Interviewer :
Welcom to the Interview, let's get started.
You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
All number will fit in integer.The prices are larger than 0.

Interviewee :
So it means we want find maximize prices[i]-prices[j] such that i>j.
Let me give out a example, if prices = [3,4,1,5] the answer is 4, because we buy it on day 3 using 1 dollar and sell it at day 4 by 5 dollar.
We can go through every day and buy the minimum prices before current day and sell at current day.
For example, prices = [3,4,1,5], answer = 4
day1
maxProfit = 0
minStockPrice = prices[0] = 3
day2
maxProfit = 1
minStockPrice = 3
day3
maxProfit = 1
minStockPrice = 1
day4
maxProfit = 4
minStockPrice = 1
return maxPrfit

Interviewer : Ok, try to write it down.

//Time complexity : O(n)
//Space complexity : O(1)
class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit=0;
        int minBuy = prices[0];
        for(int i=1;i<prices.length;i++){
            maxProfit = Math.max(maxProfit,prices[i]-minBuy);
            minBuy = Math.min(minBuy,prices[i]);
        }
        return maxProfit;
    }
}

Interviewer : Good, Thank you for your participation.
## [198. House Robber](https://leetcode.com/problems/house-robber/)
### 面試過程
Interviewer :
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Interviewee :
Let me give a example nums = [1,2,3,1], the answer is 4, we will rob house 1 and house 3.
We can solve this problem by using dynamic programming.
Frist, we only consider first house on street. Now we have two strategy rob this house or don't rod this house. Then comparing them and choose a better one.
Then, we consider one more house. We still have two strategy. If we rob second house, we cannot rob first house. If we don't rob second house we can rob the first one. And choose which one can get more money.
Then, we consider one more house. We still have two strategy. If we rob third house, we can rob first house. If we don't rob second house we can rob the second one. And choose which one can get more money.
Repeating the strategy, we will get the answer if there is all house on street.

Interviewer : Ok, Please write down the code.

//Time complexity = O(n)
//Space complexity = O(1)
class Solution{
	public int maxProfit(int[] prices){
		int maxProfit=0;
		int minStockPrice = prices[0];
		for(int i=1;i<prices.length;i++){
			maxProfit  = Math.max(maxProfit, prices[i] - minStockPrice);
			minStockPrice = Math.minminStockPrice,prices[i]);
        }
        return maxProfit;
    }
}

Interviewer : Good, Thank you for your participation.

## 檢討
針對interviewer的檢討:
* 給定題目的時候的基本限制應該寫在題目卷上, 例如target不會超過1000這件事就應該寫在上面

針對interviewee的檢討:
* 作答第一題的一開始馬上就提出要使用back tracking演算法, 可以先解釋這個題目的架構還有思路再提出為何使用back tracking演算法, 不然感覺像背題目
## 第二次作業-他評01
### 關於interviewer
- [ ] 優點
1.題目陳述清晰。
- [ ] 可改進之處
1.leetcode 377那部影片的[11:50](https://youtu.be/CtoGVlt9tjg?t=710)前面提到是要加在一起所以是`+=`但interviewee卻打成`dp[i] = dp[i-nums[j]]`應該可以直接糾正。
2.或許可以嘗試直接當場修改題目，畢竟interviewee在寫題時，應該很容易忘記: [377, 1:13](https://youtu.be/CtoGVlt9tjg?t=73)。

### 關於interviewee
- [ ] 優點
1.中文影片打程式碼的同時講解也很流暢
2.舉例都蠻詳細的讓解題方式容易理解
3.對題目描述不全的地方有提出質疑，像是[377這題](https://youtu.be/CtoGVlt9tjg?t=62)
- [ ] 可改進之處
1.三部影片好像都缺少REACTO中的repeat跟test，可能有repeat題目比較可以確認題目理解是否正確。
2.因為少了真實的test，所以有些細節上的失誤，像是[377這題](https://youtu.be/CtoGVlt9tjg?t=758)，在for loop 裡的 i 沒有寫到，變成{int = 1}。

## 第二次作業-他評 02
- interviewer
- 優點:
- 題目清楚明瞭
- 可改進地方:
- 題目給的線索太多，好處是interviewee可以很清楚知道要考什麼，但對於有刷過leetcode的人可能鑑別度不會太高
- 可以嘗試轉換題目，對應到真實生活的例子上
- interviewee
- 優點:
- 一邊打code一邊講解還蠻流暢的

## 第二次作業-他評 03
- [ ] 優點
* 邊講解邊打Code很流暢。
* interviewer對題目的說明很清楚明瞭。

- [ ] 可改進之處
* 可以再增加Test的部分，影片中只有實作完就結束了。