# 2024 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2024/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FH1-4KbanC)」課程作業 4
> 貢獻者：菜就多練-Rookie
> 面試夥伴：超帥寶-Scott
## 利用 LeetCode 題目設計延伸問題 (follow-up)
### [300. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/description/)
#### 題目敘述
給定一個序列`nums`，請回傳該陣列的最長遞增子序列(LIS)的長度。
#### Follow up 設計
承上題，請回傳一個陣列，代表`nums`的LIS路徑。若有多條長度同樣的LIS，則依造字典順序輸出全部合法LIS。
#### 設計理念
輸出LIS路徑會需要在DP的基礎上，加上回溯法的應用，來構造出答案。且還需要考慮到複數路徑，以及輸出順序問題。
### [62. Unique Paths](https://leetcode.com/problems/unique-paths/description/)
#### 題目敘述
你是一個只能向右or下走的機器人。題目給定m, n作為地圖的高、寬。請return從左上角到右下角的方法數。
#### Follow up 設計
1. 利用D代表下、R代表右，輸出所有合法的路徑(e.g. DDDRRRRR、DDRDRRRR...)
2. 起點、終點不再固定，可以為任意點，機器人可以上下左右行走。在這種情況下，求出由起點走到終點的方法數。
#### 設計理念
1. 輸出所有合法路徑會需要構造出每條路徑，增加了回溯法的應用。
2. 此case需要考慮更多方向，需要使用圖 BFS or DFS 等圖片遍歷方法來解決問題，還需要避免循環。
## mock interview
## [2593. Find Score of an Array After Marking All Elements](https://leetcode.com/problems/find-score-of-an-array-after-marking-all-elements/description/)
> [面試影片](https://youtu.be/8g3BMfXlpus)
> 💁♂：Interviewer(我)
> 🙋：Interviewee
### 題目描述
You are given an array nums consisting of positive integers.
Starting with score = 0, apply the following algorithm:
Choose the smallest integer of the array that is not marked. If there is a tie, choose the one with the smallest index.
Add the value of the chosen integer to score.
Mark the chosen element and its two adjacent elements if they exist.
Repeat until all the array elements are marked.
Return the score you get after applying the above algorithm.
### 面試過程
🙋: I have [2, 1, 3, 4, 5, 2], and then first I have to choose the smallest element, and then mark the two adjacent elements, so I have to choose 1, and then mark 2 and 3.
After that, they come to the 4, and then I have to choose 2 to the score of the array, and mark 2 and 5.
Finally, I have to choose 4, and then add it to the score, and after that, the return value will be 7.
This is the score of this array, am I right?
💁♂: Yeah, very good. You understand the entire question. Now, what's your approach?
🙋: I would like to use the stake to implement this question. So first of all, I have a family stake, I mean st, and then if the stake is empty, I have to push the elements into the stake.
🙋: In the beginning, I have to push 2 into the stake, and next, the element will be 1, and I have to use a if-else condition to verify if the element is larger than the top of the stake. So when I meet the 1, it is not larger than the 2, so I have to push it to the stake. Okay, and next, when I meet 3 in this array, it is larger than the top of this stake, so as a result, I have to pop out the top of the stake, and then add it to the score.
🙋: As a result, the score will be 1, and then pop out the stake for twice. So now, the stake will be empty, and next, the element will be 4, but the stake is empty. As a result, I have to push it to the stake.
🙋: Next, when I meet 5, 5 is larger than the top of the stake. As a result, I have to pop out the top of the stake, and then add it to the score. Okay, so now the stake is empty again.
🙋: After that, when I meet the end of this array, the end of this array is 2, and because the stake is empty, I have to push it to the stake. And finally, there is at the end of the array, I have to verify if the stake is empty or not. If the stake is not empty, I have to pop out from the stake, and then add it to the score.
🙋: As a result, I have to pop out it, and then add it to the score, and the answer will be 7. This is my approach.
💁♂: It sounds very makes sense, so could you implement it?
🙋: Okay, I would like to choose C++ for my language.
```cpp=
class Solution {
public:
long long findScore(vector<int>& nums) {
int len=nums.size();
long long ans=0;
stack<int> st;
for(int i=0;i<len;i++){
if(st.empty()){
st.push(nums[i]);
}
else{
if(nums[i]>=st.top()){
while(!st.empty()){
ans+=st.top();
st.pop();
if(st.empty()) break;
st.pop();
}
}
else st.push(nums[i]);
}
}
while(!st.empty()){
ans+=st.top();
st.pop();
if(st.empty()) break;
st.pop();
}
return ans;
}
};
```
💁♂: This solution sounds good. But the time it consumes is a little bit slow, So I think, could you improve your solution to make it faster?
🙋: Okay, I got it. I think I can use a priority queue, which is the min heap to optimize my original code from O(n^2) to O(nlogn), here is my solution.
🙋: If I have a min heap, the top of the min heap will be the mean value of this value in the array. As a result, when I have the nums, like I mentioned the example before.
🙋: When I am in the beginning of the code, I have to construct a min heap to my nonce, and then I can get the top of the min heap will be the min value of this array.
🙋: And after that, I can get 1, 2, 2, 3, 4, 5. Beside I use the value to construct a min heap, I also have to record the index of each value in this min heap. So, as a result, here, the second element of this min heap of the value is the index. And here is the 1, here is 0, here is 5, here is 2, here is 3, here is 4. (17:15) So, after I construct the min heap, I have to use this min heap to calculate my score of this array.
🙋: And for this min heap, I have to pop out the top of this min heap.
🙋: As a result, here is 1, 1. For the first of the min heap elements, it has to be added to the score. And then the index first is 1. And this index has to be marked to minus 1 in order to record that it is the elements that I have added before.
🙋: And the adjacent elements with this index also have to be marked as minus 1. As a result, the index for 0, which is 2, 0, has to be marked to 2, minus 1. And if I had already marked the index to minus 1, it can't add to the score anymore. As a result, it will be minus 1. And 3 will be minus 1, too. So, here is minus 1. Here is minus 1. And then 1 is minus 1. And so on.
🙋: When I meet the 4, the 4 is here. And I have to add it to the score. And mark the index to minus 1. And also, after that, I meet the adjacent 4, 5. And because the 5 is the adjacent to 4, its index has to be marked as minus 1. And at the end of this array, here is the value for 2 and index for 5. As a result, I have to add 2 to the score.
🙋: And this is the final output of this algorithm. And it will take O(nlogn).
💁♂: Okay. Good method.
```cpp=
class Solution {
public:
long long findScore(vector<int>& nums) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> mh;
for(int i = 0; i < nums.size(); i++)
mh.push({nums.at(i), i});
long long answer = 0;
while(!minheap.empty()){
value = mh.top().first;
index = mh.top().second;
mh.pop();
if (nums[index] == -1) continue;
answer += value;
nums[index] = -1;
if (index > 0 && nums[index - 1] != -1) nums[index - 1] = -1;
if (index < nums.size() - 1 && nums[index + 1] != -1) nums[index + 1] = -1;
}
return answer;
}
};
```
### 面試過程檢討(作為Interviewer)
#### 優點
- [01:55](https://www.youtube.com/watch?v=8g3BMfXlpus#t=1m55s) 字太小看不清楚，有直接提出請面試者修正。
#### 缺點
- [24:00](https://www.youtube.com/watch?v=8g3BMfXlpus#t=24m10s) 面試者這裡誤將index改成-1，但應該是要將value改成-1，面試官沒有提醒。
- [31:10](https://www.youtube.com/watch?v=8g3BMfXlpus#t=31m20s) 面試者說改良的方法是O(NlogN)，但並沒有解釋為什麼，面試官應該要追問原因。
## [300. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/description/)
> [面試影片](https://youtu.be/B2Jt0NxgNz8)
> 💁♂：Interviewer
> 🙋：Interviewee(我)
### 面試過程
💁♂：Hello Rookie, I'm your interviewer. This is our interivew today. So here is your question. Given an interger array "nums". Please return the largest strictly increasing subsequence.
🙋：Hello. So you means giving me "nums", and I have to return the length of what?
💁♂：You have to return the longest strictly increasing subsequence.
🙋：OK. Let me use an example`[7 5 3 2 4 6 8]`. In this example, the longest increasing subsequence is 4, Is that right?
💁♂：Yeah.
🙋：OK. Now let me abbreviate it, because it is too long. I called "longest strictly increasing subsequence" as "LIS".
💁♂：OK.
🙋：I think we can use dynamic programming to solve the problem.
🙋：We can define `dp[i]`, it means the LIS that ends in `nums[i]`. To update the `dp[i]`, we can use subproblem to solve. We can use the dp before this index to compose its dp value. for example. We want to calculate idx 5's(which value is 6) dp value . We can know its dp value by checking dp value before this index. Because we want to find LIS, so we will only focus on the numbers that is smaller than 6`nums[5]`. In this case, only 5`nums[1]`, 3`nums[2]`, 2`nums[3]`, 4`nums[4]` is smaller than 6`nums[5]`. So we can find the maximum of these dp value, and simply plus 1 to get our target's dp value. The concept is we simply push back the target value to the maximum LIS path before target's index. So, in this case. The maximum dp value is 2, we can simply add one to get our target index's dp value. So, I think we can use this method to iterate the entire "nums" from left to right. We can gradually update our dp table to finish this question.
```
// nums = [7 5 3 2 4 6 8] -> 4
// idx = [0 1 2 3 4 5 6]
// dp(not update) = [1 1 1 1 2 3 4]
// dp (result) = [1 1 1 1 2 3 4]
// dp[i] means the LIS that ends in nums[i]
```
💁♂：OK. You can start to coding right now.
🙋：OK. (coding...)
#### *解法一：DP建表*
`DP[i]`代表結束在`nums[i]`的LIS。`DP[i]`的值可以透過其前面數字的DP值來得知，取其中最大者 + 1 即為`DP[i]`，想法為先取前面最長子序列(LIS)，接著把自己push到最後面，構成以自己為結尾的LIS。
透過從左至右，逐步更新DP值，構建出結束在各`nums[idx]`的LIS，並同時維護`ans`變數，最後`return ans`即可。
```cpp=
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp(nums.size(), 1); //dp[i] means the LIS that ends in nums[i]
int ans = 1;
for (int i=1; i<nums.size(); i++) {
for (int j=0; j<i; j++) {
if (nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);
}
ans = max(ans, dp[i]);
}
return ans;
}
};
```
💁♂：OK, It seems like you use the dynamic programming to finish this problem. I would like to know what is the time complexity of your solution?
🙋：Time complexity in this solution should be $O(N^2)$. Because we use a for loop to iterate "nums" at first. And use a second for loop from left to `i`. The worst case is $N * N-1$, so time complexity is $O(N^2)$
💁♂：OK, could you use another way to optimize your code in order to decrease your time complexity?
🙋：OK, there is another way to solve this problem. And this solution can reduce our time complexity to $O(NlogN)$.
🙋：This solution is use greedy concept. We can maintain an `array`. At first, we push back the first element in `nums` to array. After that, we iterrate all array. If we encounter a number larger than array's back, we will push it to the back. And if the number is smaller than array's back, we will update our array. The update startegy is we have to find the first element in array that is larger or equal to the number, than we replace that element by the number.
🙋：for example, if the "nums" is like this `[7 10 5 3 2 4 6 8]`.
- At first, `array = [7]`, `10` is larger than array's back. So we simply push it to the array's back (now `array = [7 10]`).
- Next, `5` is smaller than array's back. So we update the array. The first element that is larger than `5` is `7`, so we update it to `5`(now `array = [5 10]`).
- After that, next number is `3`, it is also smaller than array's back. The first element that is larger than `3` is `5`, so we update it to `3`(now `array = [3 10]`).
- Next number is `2`, it is smaller than array's back. The first element that is larger than `2`, so we update it to `2`(now `array = [2 10]`).
- Next number is `4`, it is smaller than array's back. The first element that is larger than `4` is `10`, so we update it to `4`(now `array = [2 4]`).
- Next number is `6`, it is larger than array's back, so we can simply push it to the back (now `array = [2 4 6]`).
- Next number is `8`, it is larger than array's back, so we can simply push it to the back (now `array = [2 4 6 8]`).
The question ask us to find the length of LIS, so we can simply return the length of the array. I think we can use this method to complete the task.
💁♂：OK, could you implement this greedy algorithm for the concept that you provided?
🙋：OK. (coding...)
#### *解法二：Greedy更新陣列*
定義一個陣列`array`(代表LIS)，接著逐一訪問`nums`中的元素(稱`target`)，若`target > array.back()`，則直接push到`array`尾端。若`target < array.back()`，則先找出`array`中第一個大於or等於target的值，將該值替換為`target`。
透過上述規則逐一訪問`nums`中的元素，逐步更新`array`。這麼一來，就能在保持LIS長度正確的情況下，最佳化`array`元素。因此，這個方法的LIS內容不一定正確，但LIS長度會是正確的。所以最後值接`return array.size()`即可。
```cpp=
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> ans;
ans.push_back(nums[0]);
for (int i=1; i<nums.size(); i++) {
if (nums[i] > ans.back()) ans.push_back(nums[i]);
else if (nums[i] < ans.back()) {
auto idx = lower_bound(ans.begin(), ans.end(), nums[i]);
*idx = nums[i];
}
}
return ans.size();
}
};
```
💁♂：OK. It looks like you can finish your problem. And thanks for your join our interview, and this is end!
🙋：Thank you! I'm very nervous. My English is a little bit poor. Sorry for that.
💁♂：Don't be so nervous~
🙋：OK, thank you interviewer.
💁♂：Hope we can see you soon.
🙋：OKOK.
### 面試過程檢討(作為Interviewee)
#### 優點
- 舉例子時，有將 `nums idx dp` 等等陣列資訊對齊展示，讓人較易理解。
#### 缺點
- 整體英文待加強，有些用詞講的不精確，例如有時講bigger時講larger，應該統一講larger。且發音也不構標準，像是 value、three 之類的單字發音都不太標準。
- [01:00](https://www.youtube.com/watch?v=B2Jt0NxgNz8#t=1m00s) bad example，`nums = [7 5 3 2 4 6 8]` 這個例子中，`dp = [1 1 1 1 2 3 4]`，整個 dp list會是遞增序列。應該舉一個比較有變化的序列，例如讓`nums = [4 8 2 5 3 7 1 11]`，其 `dp = [1 2 1 2 2 3 1 4]`，就能更好的表達DP運作流程。
- [05:30](https://www.youtube.com/watch?v=B2Jt0NxgNz8#t=5m30s) 講解DP的部分，透過前面值得知目標DP值的邏輯講得很卡。因為不想要沉默太久，就一直講，但根本還沒組織好語言，就講得很卡、很躁。
- [16:50](https://www.youtube.com/watch?v=B2Jt0NxgNz8#t=16m50s) 這裡我覺得先講"大於"的case比較好，但和`nums`例子搭配不上，所以更改了`nums`例子。此時應該也要去更新`dp (result)`來確認答案，而不是在沒有確認答案的情況下，繼續跑該方法。
- [19:50](https://www.youtube.com/watch?v=B2Jt0NxgNz8#t=19m50s) 在"小於"的case中，是要先找到`array`中第一個 "大於 or 等於" target 的元素，我面試時常常只沒有講到"等於"，不精確。
- [24:30](https://www.youtube.com/watch?v=B2Jt0NxgNz8#t=24m30s) 這裡寫完code沒有Test，雖然前面講解方法時有 run 一次，但寫完後還是該根據 code 重 run 一次比較好。
## 檢討自己至今的表現
從上一次模擬面試以來，我都有持續的在寫leetcode，雖然寫得題目不是很難，但就至少都有在維持手感。最近也開始參加周賽，但周賽的難度真的好高，我每次都只解出了第一題QQ。我認為我依舊有不斷的努力，透過持續的寫leetcode，我有明顯得感覺到我比之前更強了。像之前DP這種題目我是碰都不敢碰，現在已經能寫出一些簡單的DP了(包括此次模擬面試的300題)，這種持續進步的感覺真好。但回過現實，我透過這次的模擬面試意識到我的英文口說有多麼的糟糕。好多時候都無法準確地描述我想說的，真的該多多練習了。最後希望我可以持續練習leetcode下去，早日在周賽能寫出兩題、甚至更多~
Sign in with Wallet
Connect another wallet