# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者: 麻花捲 tasty
> [模擬面試錄影(漢)](https://youtu.be/7W0uOEmopBw)
## [118. Pascal's Triangle](https://leetcode.com/problems/pascals-triangle/description/)
**interviewer**: 你好，從我手上的這份簡歷我感受到你對程式設計的熱忱，但是在我們深入了解工作之前，我想先了解你對程式開發的想法以及風格。請你在事先準備好的vscode上答覆，過程中如果有想法就直接寫下，方便我們後續討論。
**interviewee**: 好的。
**interviewer**: 那麼先來請你回答一個簡單的問題好了，想請問你有關帕斯卡三角形的問題，如果給你一個列數，你要怎麼設計一個程式來表示這個列數之前的所有列數中的數字。
**interviewee**: 我想確認一下題目，請問是給定一個數字，也就是三角形的高度，然後要回傳這個三角形的所有列數中的數字嗎?
**interviewer**: 對沒錯。
**interviewee**: 那我舉一些例子。假設給定的數字是3，那麼就要回傳[[1],[1,1],[1,2,1]]對嗎?
**interviewer**: 是的。
**interviewee**: 還有假設給定的數字是1，那麼就是回傳[[1]]對嗎?
**interviewer**: 是的。
**interviewee**: 好那我的想法是先是先宣告一個二維vector，然後進入迴圈跑整個流程，其中一列當中的首端以及末端設置為一，中間項從第三列開始就是透過將前一列當中的兩項數字相加來得出。
**interviewer**: 好的那就請你開始coding吧。
**interviewee**: 好。
```cpp
vector<vector<int>> generate(int numRows) {
vector<vector<int>> ans;
for(int i=0; i<numRows; ++i){
vector<int> row;
for(int j=0; j<=i; ++j){
if(j == 0 || j == i)
row.push_back(1);
else
row.push_back(ans[i-1][j-1] + ans[i-1][j]);
}
ans.push_back(row);
}
return ans;
}
```
**interviewee**:
#### Test:
舉例來說，numRows是3的話，最外圈迴圈會從第一層Pascal traingle開始跑，總共3層。row記錄每一層並記錄到ans vector當中，內層迴圈是一列當中從左至右表示，在算到第三層時i為2，其中首端以及末端先設為1，中間項則是取前一列的j位置之元素還有j-1之元素之合，最後得出一個完整的Pascal traingle。
**interviewer**: 我發現到你的程式碼已經很有效率了，請問你可以再讓它變得更有效率嗎?
**interviewee**: 在這支程式碼中，我確實看到可以被修正的地方，首先在函式一開始的部分我可以判斷如果numRows為零的狀況可以直接回傳。
```cpp
vector<vector<int>> generate(int numRows) {
vector<vector<int>> ans;
if (numRows == 0) return ans;
for(int i=0; i<numRows; ++i){
vector<int> row;
for(int j=0; j<=i; ++j){
if(j == 0 || j == i)
row.push_back(1);
else
row.push_back(ans[i-1][j-1] + ans[i-1][j]);
}
ans.push_back(row);
}
return ans;
}
```
**interviewer**: 好的，我了解了。
> [模擬面試錄影(漢)](https://youtu.be/smOEiNtAaIk)
## [518. Coin change II](https://leetcode.com/problems/coin-change-ii/description/)
**interviewer**: 好。除了上一個程式設計的問題，我這邊還想請問你另一個問題。我今天發現我的桌子有一個角落比起其他三個角矮了幾公分，我想用幾張不同厚度的紙疊起來讓他不會再晃，那我想請問，我在給定我桌子角落需要墊高多少高度，而且手邊有不同厚度的紙張的情況下，我可以知道有幾種組合嗎?
**interviewee**: 我想再確認一下問題，請問現在的情況是想要透過不同厚度的紙張堆疊，來達到想要的高度是嗎?
**interviewer**: 是，沒錯。
**interviewee**: 好那假設說我現在角落高度矮了5公分的狀況下，而且現在我有的紙張厚度分別有1, 2, 5公分，那答案就是4對嗎?
**interviewer**: 對，沒錯，而且如果現有紙張沒辦法剛好湊到我想要的高度的時候，就要回傳0。
**interviewee**: 好那假設說我現在角落高度缺了3公分，但是我有的紙張厚度只有2公分，那答案就是0對嗎?
**interviewer**: 是的，沒錯。
**interviewee**: ok，那我的想法是透過一層一層來求解各個高度的的組合，最後得到我所要的高度共有多少種組合方式，假設說我今天想要高度為4的解法，但是我只有厚度為1的紙張，我的解法就只有1+1+1+1的解法，那假設我現在多有了厚度為2的紙張，我先取2的紙張，組合數就會再加上4-2=2的這個解法也就是高度為2的解法，即為2，也就是說高度為4的組合數就會有3種，以此類推。
**interviewer**: 好，那我們就開始coding吧。
```cpp
int change(int height, vector<int>& papers) {
vector<int> dp(height + 1, 0);
dp[0] = 1;
for (int paper : papers) {
for (int i = paper; i <= height; i++) {
dp[i] += dp[i - paper];
}
}
return dp[height];
}
//dp[i] += dp[i - paper]; 是已經有的解法在加上透過新增paper厚度後得到的組合數
```
**interviewee**:
#### Test:
舉例來說，當height為5，且papers有1, 2, 5，先宣告一個大小為height+1的vector表示在各高度的狀況下有多少種組合數，並初始化地0項的組合數為1。跑第一輪迴圈的時候，考慮只取厚度為1的紙張，並記錄在dp vector當中，跑完迴圈得出個高度組合數為1(假設i=4，用厚度為1的紙疊出的組合就只有1, 1, 1 ,1)。
再考慮下一種厚度為2的紙張，執行完迴圈之後dp vector各項為1 1 2 2 3 3(假設i=4，考慮取用厚度為2的紙張後就會變成要考慮高度為2的狀況，而在這時高度為2的組合數為1 1或2，所以除了全部考慮取用1的紙張之外，加上考慮取用2的紙張之後，組合數來到3)
跑完最後一圈之後，vector dp 各項為1 2 2 3 4。最後得出一組合出高度為5的組合數為4。
**interviewer**: 除了這種方法外還有其他種方式嗎?
**interviewee**: 另一種方式可以用 top down 的 recursion 方式實作，執行速度會比較快但是記憶體的使用量就會變得更多。
**interviewer**: 好。
> [模擬面試錄影(英)](https://youtu.be/5N7YQm7DWs8)
## 448. Find All Numbers Disappeared in an Array
**interviewer**: I'd like to ask you another question. Assuming that there are now 10 students in a class, and I want to confirm their presence by taking attendance. I ask them to report their seat numbers to confirm, but some students can be naughty and report someone else's seat number. How can I design a program to know which seat numbers are missing?
**interviewee**: Ok, let me repeat the question. There will be a list of seat numbers, and I need to design a algorithm to check the missing seat numbers in the list, am I right?
**interviewer**: Yes.
**interviewee**: Let me take some examples of this question. If the list of seat numbers is [4,3,2,7,8,2,3,1], and the missing numbers, which is the answer is [5, 6], right?
**interviewer**: Yes.
**interviewee**: Also if the list is [1,1], and the answer is [2], am I right?
**interviewer**: Yes, you're right.
**interviewee**: Ok. About this question, my approach is first assuming a variable named "numbers" representing the total numbers of the class, and assuming a vector named "missing" representing the missing seat numbers.
Initializing missing vector's value to 0 in order to caculate the times which each number is being called. When a number is being called, then plus one to the position of the vector, just like the example showing below:
```
//if number 2 is being called
missing[2] = missing[2] + 1;
```
At the end, we could know which seat numbers are not appearing by checking the vector. If the number in vector is still zero, then the number is missing in the list.
**interviewer**: Ok, I understand. You can start coding now.
**interviewee**:
```cpp
vector<int> findMissingNumbers(vector<int>& nums) {
int numbers = nums.size();
vector<int> missing(numbers+1, 0);
missing[0] = 1;
for(int number=0; number<numbers; number++){
int temp = nums[number];
missing[temp]++;
}
vector<int> ans;
for(int i=1;i<=numbers;i++){
if(missing[i]==0)
ans.push_back(i);
}
return ans;
}
```
**interviewee**:
#### Test:
For example, I assume that nums is 1, 1, and the numbers variable is 2. Using temp variable to store the value of nums vector, and making value of that position of missing vector plus one, meaning that the position has shown up before. At the end, I can know which seat number is missing by scanning the missing vector to know which position is still zero.
**interviewer**: Great. But it seems like this answer is a little bit complicated. Can you shorten this code?
**interviewee**: Mmm...Let me think. I would like to delete the "numbers" variable. It seems like I can just use nums.size() instead of using another variable to save the value.
```cpp
vector<int> findMissingNumbers(vector<int>& nums) {
vector<int> missing(nums.size()+1, 0);
missing[0] = 1;
for(int number=0; number<nums.size(); number++){
int temp = nums[number];
missing[temp]++;
}
vector<int> ans;
for(int i=1;i<=nums.size();i++){
if(missing[i]==0)
ans.push_back(i);
}
return ans;
}
```
Moreover, I would like to delete the missing vector, because I think I can just record the missing seat numbers on the given list.
I will run through every elements in the list, and also the numbers of the list can replace the "missing" vector.
I can represent whether each number has appeared by using the nums vector with positive and negative values. If a position in the vector has a negative value, it means that the number corresponding to that vector position plus one has already appeared. This approach won't affect the original array's evaluation and can indicate which numbers have been encountered.
```cpp
vector<int> findMissingNumbers(vector<int>& nums) {
vector<int> ans;
for(int i=0; i<nums.size(); i++){
int temp = abs(nums[i]) - 1;
if(nums[temp] > 0)
nums[temp] = -nums[temp];
}
for(int i=0;i<nums.size();i++){
if(nums[i]>0)
ans.push_back(i+1);
}
return ans;
}
```
**interviewer**: Great work! And this will be the end of the interview. Thank you for coming. We will contact you soon.
## 初步檢討
### 程式部分
- pascal traingle [2:13](https://youtu.be/7W0uOEmopBw&t=133s) 這個地方講錯了，應該是上面跟上面左邊那項之合。
- 邊寫程式邊講解code有點卡卡的，可以決定一下要何時講解何時撰寫程式碼
- coin change 最關鍵的 dp[i] += dp[i-coin]，沒有講得很清楚
### 交談部分
- 口齒要清晰一點，不要字字句句黏在一起
- 在pascal traingle當中撰寫完程式碼之後可以帶個簡單的例子，方便面試官去了解程式碼的設計
- 在coin change 講解程式碼時，再聽一次發現沒有講得很清楚，面試官可能會有聽沒有懂
- 英語對談當中有一些冗言贅字的出現，也要注意有無台式英語的出現。
---
## 第二次作業-他評01:
### interviewer
- [ ] 優點
* 說話清晰，語速中等
* 有提出進一步的問題測試interviewee
* 題目都有稍微進行包裝
- [ ] 可改進
* [06:45](https://youtu.be/7W0uOEmopBw?si=WJ9QcHue3jNn50wr&t=405): 直接向interviewee表示程式碼已經很有效率，但沒有經過test，要怎麼知道這段程式碼很有效率呢?!
* [10:11](https://youtu.be/smOEiNtAaIk?si=p6RBzaHfoKwrTiSS&t=611): 感覺在interviewee打code結束後，可以再接著延伸問題，例如使用dp和top-down方法時，兩個方法的時間/空間複雜度為何。
* 缺少了要求interviewee去進行test的階段
### interviewee
- [ ] 優點
* coding時解釋清楚
* Reapt和Example部分有做到
- [ ] 可改進
* [07:35](https://youtu.be/7W0uOEmopBw?si=WNxpfWZ6ptGpxJCO&t=455): 這邊應該向interviewer具體解釋為什麼多了`if (numRows == 0) return ans;`，會更好
* 適當的加上註解讓interviewer更了解你的想法
* 建議事先說明**能用**以及**要用**的語言
* 應用 Google docs 而不是用編輯器
## 第二次作業-他評02:
### interviewer
- [ ] 優點
* 第三題英文題目很不錯，有生活性
- [ ] 可改進
* [0:45](https://youtu.be/7W0uOEmopBw?t=0m45s): 如果給你一個列數，你要怎麼設計一個程式來表示這個列數之前的所有列數中的數字，缺少明確的範例很難聽懂是甚麼題目。
* 建議三個影片講解過程中，都可以旁邊有題目
* [10:07](https://youtu.be/smOEiNtAaIk?t=10m07s): 可以額外補充說明為什麼top-down記憶體的使用量為甚麼比較多嗎?直接認同interviewee的話沒甚麼面試的意義。增加一些互動比較好
### interviewee
- [ ] 優點
* 講話咬字很清楚，聲音很平穩
* 英文不錯 蠻清楚的
- [ ] 可改進
* [4:24](https://youtu.be/smOEiNtAaIk&t=4m24s)這裡可以直接說明是動態規劃的演算法，順便可以解釋動態規劃的精神，讓面試官更清楚突然來的一行程式碼的功能
* [8:32](https://youtu.be/smOEiNtAaIk&t=8m32s)用個簡單的例子說明為什麼dp[0] = 1 由小往大建立組合數的概念
* [9:54](https://youtu.be/smOEiNtAaIk&t=9m54s)可以直接實做出top-down recursion的方式，並且解釋效率好在哪裡。執行速度比這個目前這個方法還要快，這個方法哪裡慢了需要解釋，目前方法那裏可以被改進也需要被解釋。記憶體使用量變多的原因要說明。
* 英文的部分，會一直有Am I right? 感覺可以不用一直得到面試官的認可，面試官如果覺得錯也不見得願意告訴你，或許可以自問自答，用合理的論證證明自己是正確的，會比叫面試官確認還好。但這個也是一個優點，可以增加跟面試官互動的次數機會。
* 第三題程式第一次寫用missing作為陣列名稱感覺很奇怪，可以直接用一個bool型別的陣列判斷有沒有出現會比較直覺。
* [12:53](https://youtu.be/5N7YQm7DWs8&t=12m53s)第三題 變數名稱number 為第一個for迴圈裡面的區域變數，在第一個迴圈中檢查陣列num的原入是否大於0時，不要叫他number的tmp (num[tmp])
* [14:57](https://youtu.be/5N7YQm7DWs8&t=14m57s)可以用push back value into answer vector，這樣就可以部會跟之前的numbers搞混了
Sign in with Wallet
Connect another wallet