# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業2
> 貢獻者: 鋼鐵人-Waffle
> ==[video1](https://youtu.be/NWkyTIBBETk)==
🧔：interviewer 👶：interviewee
## [121. Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)
> [video](https://youtu.be/NWkyTIBBETk)
### 面試內容
🧔：你好，感謝今天撥空參加這場面試。考量到未來工作需要利用程式做股票買賣作分析，所以這邊給你一個情境。
想請問今天給定一個儲存股票價格的陣列。陣列中每個元素代表一天當中股票的價格。如果在一天中只能做一次交易，例如可以買一次然後賣一次，請設計一個演算法求得最大獲利。
👶：你好，也就是說這題需要我們依序讀取陣列裡的元素。而為了獲得最大利益，最好的情況就是在價格最便宜的時候買，然後在價格最高的時候賣掉。
👶：讓我舉個例子說明，例如如果今天給定的輸入是：
```cpp
[7, 1, 5, 3, 6, 4]
```
👶：我們就可以在第二天，也就是價格是1的時候買進，在第五天的時候也就是價格是6的時候賣掉，那此時我們的獲利就是5。而且我們不能第二天買但卻賣在第一天，因為不可能先賣再買。
👶：所以剛剛的例子中最大的獲利也剛好就是5
👶：但如果今天給定的輸入是：
```cpp
[7, 6, 4, 3, 1]
```
👶：不管今天怎麼買，賣掉都是虧錢，所以最大獲利就是0。
🧔：是的，理解的沒錯，那請問有甚麼想法可以實現這個演算法呢？
👶：我的想法是我們的重點就是要比較每一個買入買出的收益，去看哪個最大。
👶：所以如果今天給定的輸入是：
```cpp
[7, 1, 5, 3, 6, 4]
```
👶：如果用第一天的價格是7買進，我就跟用後面幾天[1, 5, 3, 6, 4]賣出的情況去比較獲利。如果是第二天價格是1賣進，我就跟用後面幾天[5, 3, 6, 4]賣出的情況去比較獲利，以此類推。找出一個獲利最大的組合。
🧔：這方法聽起來合理。
👶：我想請問價格的最大與最小值是多少呢？(還有我要input和return的數值的變數型態為何呢？)
🧔：價格最小為$0$，最大是$10^4$，這邊都可以宣告整數即可。
👶：請問可以使用C++程式碼並開始撰寫程式碼嗎？
🧔：沒問題，請開始吧。
### 程式碼解說
#### 方案一
👶：先設定我們的output的max_profit為0。
接著透過二個迴圈去組合出所有買進與賣出的情況。把賣出價格與買進價格差異最多的數值儲存起來，如果跑完整個迴圈都還沒有出現賣出價格高於買入價格的情況，回傳的max_profit就是一開始設定的0。整段程式使用二個迴圈，這樣時間複雜度是 $O(n^2)$。
```cpp
class Solution {
public:
int maxProfit(vector<int>& prices) {
int max_profit = 0;
for(int i =0; i < prices.size()-1; i++){
for(int j = i + 1; j < prices.size(); j++)
if(prices[j] - prices[i] > max_profit)
max_profit = prices[j] - prices[i];
}
return max_profit;
}
};
```
👶：讓我舉例說明。
```cpp
給定[7, 1, 5, 3, 6]說明所有組合情況
```
🧔：很好，你使用二個迴圈把所有可能對應的買進買出的組合列舉出來確實可以解決我們的問題。但我們在實際應用的時候，面臨的是更多的資料，而這樣的程式效能可能會很差，請問有什麼方法可以提升運行的速度嗎？
🧔：像是會不會覺得有些組合的比較是多餘的呢？
#### 方案二
👶：恩...，我知道了，這次的問題可以想成是去計算當前價格的最大獲利。
👶：這樣我們就可以只需要一個迴圈去計算目前出現的這個價格減去前面出現過的最低價格，最後得到最大獲利。
🧔：這方法聽起來合理，請開始程式碼的撰寫吧。
👶：我們一樣一開始將獲利設為0，而最低買進價格就先用前面提到的最高價格。一樣有個迴圈去計算每天的情況，如果當天的價格是最便宜就更新最低價格。同時也計算當天獲利有沒有超過最大獲利，如果有就更新最大獲利。這樣最後時間複雜度是 $O(n)$。
```cpp
class Solution {
public:
int maxProfit(vector<int>& prices) {
int max_profit = 0;
int buy_price = 10000;
for(int i =0;i < prices.size(); i++){
buy_price = min(buy_price,prices[i]);
max_profit = max(max_profit,prices[i]-buy_price);
}
return max_profit;
}
};
```
👶：讓我舉例說明。
```cpp
給定[7, 1, 5, 3, 6]來說明
10000 > 7 --> buy_price = 7
0 = 7-7 --> max_profit = 0
7 > 1 --> buy_price = 1
0 = 1-1 --> max_profit = 0
1 < 5 --> buy_price = 1
0 < 5-1 --> max_profit = 4
1 < 3 --> buy_price = 1
4 > 3-1 --> max_profit = 4
1 < 6 --> buy_price = 1
4 < 6-1 --> max_profit = 5
```
🧔：好的，不錯，那我們繼續下一道題目。
---
## 第二次作業-他評 01
[天兵-TianBing](https://hackmd.io/HfbyCgdfTt6kkW-wF6qIyg?both)
### Interviewer:
* 缺乏reacto的一些步驟。
* 在介紹題目的時候也許可以有一些圖文可能會讓interviewee更能理解題目。
### Interviewee:
* 寫程式碼的同時可以試著同時解說，不然可能過程會有點乾。
### 整體可改進之處:
* 英文口說可能需要再加強，讓整體更加的流暢。
* 有時候會有一些不必要的肢體動作，需盡量避免。
* 說話可以再更有自信。
---
## 第二次作業-他評02
[甲魚-baspis](https://hackmd.io/aicvazYpQH-Q-zCH_T8Z0g?both)
### Interviewer:
* 在介紹題目的時候也許可以有一些圖文可能會讓interviewee更能理解題目。
* interviewer有試圖想要一步一步引導的感覺。不過有些引導感覺過於直白。引導的部分可以再給一些故事性，像是平常會遇到哪些運用，所以可以怎麼思考之類的。
* 感覺可以再多增加題目對應真實應用的討論
* 在interviewee解釋可能的作法後，可以不用太快讓interviewee直接開始coding，可多討論些不同做法或此做法可能存在的問題，就不會讓面試者一開始就都是暴力解。
### Interviewee:
* 有考量到Constraints的部分，很棒！
* 有分析空間和時間複雜度。
* 邊打程式碼的時候同時有做說明，不會讓人感覺冷場的感覺。
* 缺少reacto的test部分，有點可惜。
---
## 第二次作業-他評 03
[李一-Pear](https://hackmd.io/0cpKoumJRKW4Fc0vqjigxA?both)
* 口條清楚，語速和聲音大小控制得當
### interviewer
* interviewer的開頭介紹很完整！不過如果可以說明自己是甚麼樣的公司，而接下來出的題目能依照工作時會可能遇到的情境來出題會更好！
* 感覺介紹題目的時候有圖片或是提供畫面會更好理解，尤其配合題目需要幾種走法類型的題目
* [06:33](https://youtu.be/brz38rMKVfQ?t=393) 在說處理最後一個數有更好的方法，可能可以再引導一下這個更好的方法可能的方向，不然感覺interviewee也很難直接突然想到。
### interviewee
* 能夠對題目給出例子和提出一些疑問和訊問可能出現的情況，增加討論，而不盲目開始寫code，使自己更好的理解題目的內容與限制。
* 可惜缺少repeat題目而直接開始做example的步驟。
* [00:27](https://youtu.be/EHdy7qDeJoY?t=27)這部分在說明如何實作的時候看有沒有辦法打字出來說明，不然怕interviewer無法理解意思。
* [01:26](https://youtu.be/EHdy7qDeJoY?t=86)可以說明為何設定這樣的變數型態，能讓內容更完整。
---
## 第二次作業-他評 04
[埃默里-Emery](https://hackmd.io/IcL6COXQT9WAjdKid6po9w?both)
### interviewer
* 感覺在一開始interviewer介紹題目的時候背景就可以有題目出來，讓interviewee更好理解題目，不知道為何到後面才出現題目。
* 可以多為你的題目設定情境，像是我們是某某公司，平常可能會做甚麼，所以想考考你有關甚麼內容的解決能力等。
### interviewee
* 在repeat的階段很完整，而且也能考量到題目可能需要那些限制或是需求來做提問，增加討論性
* 可惜比較缺乏test的部分，感覺可以在後面說明時間複雜度和空間複雜度的時候去做test的部分，然後利用一開始在example提出的測試來驗證你的程式碼是否有誤。
---
## 第二次作業-他評 05
[布萊德 - bread](https://hackmd.io/n63PXCpqQoumExsnHi-5bw?both)
### interviewer
* 有提供文字題目給interviewee，很棒！不過如果能再搭配著一些解說會更好！
* 給題目的時候可以試著把情境帶入而不是直接出題。
* interviewer的聲音有點過小，有時候會聽不清楚在說甚麼
* interviewer與interviewee的互動有點少，像是在說明請提供更快解法的時候，可以更有引導性，像是原本慢在哪，可以往哪個方向調整來讓interviewee抓到可以優化的地方
### interviewee
* 有在寫程式的時候邊說明程式，不錯！
* [1:08](https://youtu.be/BdGYZS2hdS0?feature=shared&t=68) 可能要注意一些摸鼻子之類的肢體動作
* 似乎缺少了approach的部分而直接開始進行coding，建議先說明想法，和interviewer討論想法，覺得沒問題可寫code之後再寫code會比較有討論性。
* 似乎也缺乏test的部分，寫完程式碼的時候應說明test。
Sign in with Wallet
Connect another wallet