# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者: 鋼鐵人-Waffle
> video: ==[video1](https://www.youtube.com/watch?v=5-FsGOP_Kko)== ==[video2](https://www.youtube.com/watch?v=JwEClictTsc)== ==[video3](https://www.youtube.com/watch?v=AeysfqJjeR8)==
> 🧔：interviewer 👶：interviewee
## [121. Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)
### 面試內容
🧔：你好，考量到未來工作需要利用程式做股票買賣作分析，所以這邊給你一個情境。
想請問今天給定一個儲存股票價格的陣列。陣列中每個元素代表一天當中股票的價格。如果在一天中只能做一次交易，例如可以買一次然後賣一次，請設計一個演算法求得最大獲利。
👶：你好，也就是說這題需要我們依序讀取陣列裡的元素。而為了獲得最大利益，最好的情況就是在價格最便宜的時候買，然後在價格最高的時候賣掉。
👶：讓我舉個例子說明，例如如果今天給定的輸入是：
```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]賣出的情況去比較獲利，以此類推。找出一個獲利最大的組合。
🧔：這方法聽起來合理。
👶：我想請問價格的最大與最小值是多少呢
🧔：價格最小為$0$，最大是$10^4$，你可以開始程式碼的撰寫了。
### 程式碼解說
#### 方案一
👶：先設定我們的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
```
🧔：好的，不錯，那我們繼續下一道題目。
---
## [231. Power of Two](https://leetcode.com/problems/power-of-two/)
### 面試內容
🧔：好的，那我們公司也會有使用到指數應用的需求與情境，所以接下來想請問今天給定一個整數n，請設計一個演算法判斷這個整數n是否為2的次方，如果是就回傳true，不是就回傳false。
👶：也就是說會有個integer n，我們要判斷是否存在一個整數x，使得
```cpp=
n == 2^x
```
🧔：是的，你理解的沒錯。
👶：那我還想請問，對於這個給定的整數n，請問有限制數字範圍嗎？
🧔：有的，整數n的範圍為-2^31^ ~ 2^31^ -1。我想你可以開始程式的撰寫了。
👶：在開始寫程式前，我想說明一下我的想法。
👶：這題的要求是2的倍數。也就是我可以不斷的除2，直到除2後的餘數為0就代表true，如果除2後的餘數是1就代表false，因為如果是2的次方，那除2不管怎麼樣都不會有餘數。
🧔：是的，沒錯，請進行程式的撰寫吧
### 程式碼解說
#### 方案一
👶：只有正整數的情況才可能是true，而我們會在裡面不斷的除2直到他達1，因為2的0次方是1，所以就判定為true。如果是其他數，有出現餘數，就代表他不是2的次方，回傳false。
👶：這樣最後時間複雜度是$O(logn)$。空間複雜度是$O(1)$
```cpp
class Solution {
public:
bool isPowerOfTwo(int n) {
while(n>0){
if(n%2==0)
n = n/2;
else if(n==1)
return true;
else
return false;
}
return false;
}
};
```
👶：讓我舉例說明。
```cpp
n=1 --> 因為n>0，所以進入while
n%2 !=0 -->進到 else if(n==1) -->return true
====================================
n=5 --> 因為n>0，所以進入while
n%2 !=0 , n!=1 --> return false
====================================
n=4 --> 因為n>0，所以進入while
n%2 ==0 , n = n/2 = 2
2%2 ==0 , n = 2/2 = 1 --> 進到 else if(n==1) -->return true
```
🧔：好的，非常直觀的作法，不過透過直接做除法的運算會消耗較多的運算資源，尤其在工作處理的的數字也都會比現在大很多。而位元運算在這部分就顯得更有效率，所以想請問你可以用位元運算的方式處理嗎？
👶：可以，那我先說明我的想法，既然是要計算2的次方，這讓我想到2進制的表示法，首先觀察2的次方數的規律。
```cpp
1=1, 2=10, 4=100, 8=1000
```
👶：可以發現這些是2的次方的數字，用二進制表示後最高位元都是1，其餘為0。
👶：所以我可以建立一個迴圈，從最低位元檢查到高位元。可透過一個flag去看這中間有沒有出現1，有的話就回傳false，如果成功檢查到最高位元，就回傳true。
🧔：合理，請開始程式碼的撰寫吧。
#### 方案二
👶：如同前面的code,只有正整數的情況才可能是true。另外我們建立一個flag，如果flag是true也就意味著發現中間有非0的情況，回傳false。不然就讓最低位元和1做and，以此檢查有沒有出現1，最後再做平移，捨棄最低位元。如果成功到最高位元才出現1，那flag為true，同時也離開迴圈，回傳true。
👶：這樣最後時間複雜度是$O(logn)$。空間複雜度是$O(1)$
```cpp
class Solution {
public:
bool isPowerOfTwo(int n) {
bool flag = false;
while(n>0){
if(flag==true)
return false;
else
flag = n & 1;
n = n >> 1;
}
return flag;
}
};
```
👶：舉例來說就會是這樣
```cpp
n=1 --> 因為n>0，所以進入while
flag = false --> 進入else
flag = n & 1 --> 1 & 1 -->flag = true
n = n >> 1 --> n=0 -->return true
====================================
n=5 --> 因為n>0，所以進入while
flag = false --> 進入else
flag = n & 1 --> 101 & 1 -->flag = true
n = n >> 1 --> n=10 --> if(flag==true) -->return false
====================================
n=4 --> 因為n>0，所以進入while
flag = false --> 進入else
flag = n & 1 --> 100 & 1 -->flag = false
n = n >> 1 --> n=10
flag = false --> 進入else
flag = n & 1 --> 10 & 1 -->flag = false
n = n >> 1 --> n=1
flag = false --> 進入else
flag = n & 1 --> 1 & 1 -->flag = true
n = n >> 1 --> n=0 -->return true
```
🧔：好的，不錯，那我們進入下一題。
---
## [287. Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/)
### 面試內容
🧔：Ok,let's move on. Given an array of integers nums containing n plus 1 integers where each integer is in the range 1 to n inclusive.
There is only one repeated number in nums, return this repeated number.
👶：You mean that I have to detect which number is repeated.Besides, this number can appear many time while other number only appear one time.
```cpp=
[1,3,4,2,2] --> 2
[2,1,3,4,2,2] --> 2
```
🧔：Yes, you understand correctly. I think you can write you code.
👶：Before writing code, I want to explain my idea.
👶：I can check two of element in the array.If we find that the two elements is same,it is the repeated number. So we can set it as output.
🧔：Sure, it seems to be feasible. You can start coding.
### 程式碼解說
#### 方案一
👶：First, We calculate the length of the array. Then, We can use two for loop to come out all of the combination. Finally, we check if num[i] is equal to the num[j].If we find the two number is same, we can return the number because we find the duplicated number.
👶：In the end, time complexity is $O(n^2)$。
```cpp
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int num_lens = nums.size();
for(int i =0; i<(num_lens-1); i++){
for(int j=i+1; j<num_lens;j++){
if(nums[i]==nums[j])
return nums[i];
}
}
return -1;
}
};
```
👶：Let me take some test example.
```cpp
給定[1,3,4,2,2]說明所有組合情況
```
🧔：It's good. You can solve the problem by using two loops to list all of the possible corresponding combinations and check if they are equal. However, it will take many times. Can you improve you code and make it faster?
🧔：Give you a hint. You can think about the frequency of every number.
👶：I got it. I want to talk about my idea first.
🧔：Sure.
👶：We can use the hash map to store the number appearance time. So we can check which number appears more than two and it is the duplicated number
🧔：It sounds reasonable. You can start coding.
#### 方案二
👶：First, we construct an unordered map.Then we store the number in the map. In the end, we use a loop to check every number and their corresponding frequency. If the frequency is higher than 2, it is the duplicated number.
👶：We use only one loop,So the time complexity is $O(n)$。
```cpp
class Solution {
public:
int findDuplicate(vector<int>& nums) {
unordered_map<int,int> map;
for(int x=0;x<nums.size();x++)
map[nums[x]] = map[nums[x]] + 1;
for(auto order:map)
if(order.second>=2)
return order.first;
return -1;
}
};
```
👶：Let's take some test example.
```cpp
[3,1,3,4,2]
3 : 2
1 : 1
4 : 1
2 : 1
--> 3 is repeated
```
🧔：OK, thank you. It looks good and the interview is finished. Goodbye!
## 初步自評
- 有時候講話含糊不清楚
- 有些用語不夠精準
- 很常打錯字
- 講解題目的時候也許可以提供可畫面，讓人比較清楚題目的內容
---
## 第二次作業-他評01
### 關於interviewer
- [ ] 優點
1.題目有稍微加入情境。
2.有進行REACTO中的Optimization的討論
- [ ] 可改進之處
1.Power of Two那題好像主動暴露出更好的解法是要透過位元運算，感覺可以換個說法，引導面試者思考。
### 關於interviewee
- [ ] 優點
1.舉例和測試非常詳細
2.語氣、語調有變化，講解流暢。
- [ ] 可改進之處
1.撰寫程式碼要縮排的時候，好像都是用空白鍵一次跳一個字，可以改按Tab會快一些，不然快速按空白鍵的聲音有點大。
2.在Find the Duplicate Number這題，用STL中的unorder_map之前，感覺可以提一下它底層是透過hash map實作所以可以符合你的解法。
## 第二次作業-他評02
### 關於interviewer
- [ ] 優點
* 有確實給出情境，可以讓 interviewee 更快進入狀況。
* [2:38](https://youtu.be/JwEClictTsc?si=JDNa7uo8NlH2sAz8&t=158): 刻意說 2$^{-32}$~2$^{32}$ 之間，試圖測試 interviewee 是否了解為signed integer.
- [ ] 可改進的地方
* [1:13](https://youtu.be/AeysfqJjeR8?si=ubu7iAxc6_TnL19H&t=73): 有點太快說可以讓 interviewee 寫程式，可以先讓 interviewee 闡述一下做法比較好
### 關於interviewee
- [ ] 優點
* 舉例很詳細! 在REACTO的T做得很好
- [ ] 可改進的地方
* 可以詢問面試官是否能用c++, 也許公司會要求 interviewee 必須要能實作資料結構的能力。
* [9:11](https://youtu.be/5-FsGOP_Kko?si=Tma_UdUMyJDbU5dw&t=551): 盡量讓Code的命名方式相同，也許在面試時會忘記，平時就給自己規範可能可以讓人知道你會遵從命名規則(?)
* 第二部 [2:38](https://www.youtube.com/watch?v=JwEClictTsc): 關於Function return為何 以及 為什麼input是int, 感覺可以說明一下，面試官有用稍微不直覺的方式，是給機會發揮。
## 第二次作業-他評03
### 關於interviewer
- [ ] 優點
* 口齒清晰、語速正常，不需要字幕也能聽懂
- [ ] 可改進的地方
* 面試一開始建議面試官可以有所鋪陳，比如：「感謝今天撥空參加這場面試」或「今天由我來主持這場面試」等等的場面話
* 開始撰寫程式碼的時機建議由 interviewee 自己提出，否則如果他還有問題卻不敢再問，導致寫程式的時候才發現理解錯誤，可能就會浪費彼此的時間(?
### 關於interviewee
- [ ] 優點
* REACTO做得很完整👍
* medium題挑戰用英文👍
* 在編寫程式碼的過程一邊撰寫一邊說明，說得很清楚，很好理解
* test後有接著說明時間和空間複雜度
* [16:11](https://www.youtube.com/watch?v=5-FsGOP_Kko): 口誤的時候說了「更正」兩字做修正，很有大人的風範，我在錄影片的時候只想到要剪掉，學到了
* optimize後也還有test，把REACTO變成REACTOT，沒做過這道題的我都聽懂了
* [3:24](https://www.youtube.com/watch?v=JwEClictTsc): 有記得考慮到並處理特殊情況(次方為0時有被處理)
* [1:03](https://www.youtube.com/watch?v=AeysfqJjeR8): 在面試官說開始coding後仍勇敢提問
- [ ] 可改進的地方
* 字體建議可以再更大一點，畫面還有不少空間可以放大
* [8:37](https://www.youtube.com/watch?v=5-FsGOP_Kko) 及[5:26](https://www.youtube.com/watch?v=AeysfqJjeR8): test的地方說得很詳細，但是因為是比較簡單的概念，建議舉例一次j迴圈後並表示i迴圈+1，就可以用「以此類推」帶過，全部講完的話面試官可能會睡著XD
* [2:01-2:15](https://www.youtube.com/watch?v=JwEClictTsc)及[1:27-1:48](https://www.youtube.com/watch?v=AeysfqJjeR8): 創建函式的時候不知道說甚麼，建議可以說「首先我先創建一個函式，我將它命名為...」
* [6:40](https://www.youtube.com/watch?v=JwEClictTsc): 因為面試官有提到範圍是2$^{-32}$~2$^{32}$ ，test的時候建議可以加上2的負數次方一起說明
* [0:26](https://www.youtube.com/watch?v=AeysfqJjeR8): 建議用many times而非many time
* [5:04](https://www.youtube.com/watch?v=AeysfqJjeR8): 建議可以說明目前j是3再開始比較，直接進行比較，易產生疑惑
* [0:26](https://www.youtube.com/watch?v=AeysfqJjeR8): 建議用number of occurrences而非appearance time
Sign in with Wallet
Connect another wallet