---
title: 2022 年資訊科技產業專案設計 HW1
tags: 資訊科技產業專案設計
---
# 2022 年「[資訊科技產業專案設計 HW1](https://hackmd.io/@sysprog/info2022/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FBJLSJ3ggi)」面試範例
> 貢獻者: 齊爾 Chill
> [video(中)](https://youtu.be/fNTW-sucrnU)
> [video(英)](https://youtu.be/aEkZw01tZJk)
🧔：interviewer 👶：interviewee
## 2022 年[資訊科技產業專案設計 HW1]
### [(中)121. Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)
> [video](https://youtu.be/fNTW-sucrnU)
#### 測驗說明與問答
🧔：
這裡提供一個數列 **prices**，其中 **prices[i]** 是某支股票在第i天的價格。
你想通過選擇某一天買入一支股票，並在未來選擇不同的一天賣出該股票，實現利益最大化。
回傳你能在此筆交易中獲得的最大利潤，若無法獲得任何利潤，則回傳0。
Constraints:
* $1$ <= $prices.length$ <= $10^4$
* $0$ <= $prices[i]$ <= $10^3$
input : 7, 1, 5, 3, 6, 4 return 6 - 1 = 5
👶：
我的想法是使用兩個迴圈從第一天開始，往後每一天去賣出，找出最大值。
**程式碼**
```cpp!
int maxProfit(int prices[], int pricesSize){
int max=-10000;
for(int i=0;i<pricesSize;i++){
for(int j=i+1;j<pricesSize;j++){
max=(prices[j]-prices[i]>max)?prices[j]-prices[i]:max;
}
}
return (max<0)?0:max;
}
```
👶：
此方法的時間複雜度為$O(n^2)$，空間複雜度為$O(1)$。
🧔：
時間複雜度為$O(n^2)$，還是有點慢，能否下降至$O(n)$呢?
👶：
我的想法是用一個迴圈，每天找出最小值，再同時賣出，找出最大利益。
**程式碼**
```cpp!
int maxProfit(int prices[], int pricesSize){
int min=10000, max=-10000;
for(int i=0;i<pricesSize;i++){
min=(min>prices[i])?prices[i]:min;
max=(max<prices[i]-min)?prices[i]-min:max;
}
return (max<0)?0:max;
}
```
👶：
此方法的時間複雜度為$O(n)$，空間複雜度為$O(1)$。
### [(中)287. Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/)
> [video](https://youtu.be/fNTW-sucrnU?t=422)
#### 測驗說明與問答
🧔：
這裡提供一個包含 n + 1 的整數的數列 **nums** ，其中每個整數都在 [1, n] 範圍內(含 1, n)。
**nums** 中只有一個重複的數字，請回傳這個重複的數字。
input : 1, 3, 4, 2, 2 return 2
Constraints:
* $1$ <= $n$ <= $10^5$
* $nums.length$ == $n + 1$
* $1$ <= $nums[i]$ <= $n$
* 所有在陣列中的整數除了重複的數字外，其餘的數字都只會出現一次。
👶：
我想到極端的輸入有數字全部都重複的，如 2 2 2 2 2，。
我的想法是用兩個迴圈逐一比對，再用一個計數器去記錄出現的次數，若超過一次就回傳值。
程式碼
```cpp!
int findDuplicate(int nums[], int numsSize){
int cnt;
for(int i=0;i<numsSize;i++){
cnt=0;
for(int j=0;j<numsSize;j++){
if(nums[i]==nums[j] && i!=j)
cnt++;
}
if(cnt>=1)
return nums[i];
}
return -1;
}
```
👶：
此方法的時間複雜度為$O(n^2)$，空間複雜度為$O(1)$。
🧔：
是否還能更快呢?
👶：
我的想法是宣告一個陣列map，將nums中的元素一一填入map中，再用迴圈去測試map中哪個index的值>2，再回傳index。
程式碼
```cpp!
int findDuplicate(int nums[], int numsSize){
int map[numsSize]={0};
for(int i=0;i<numsSize;i++){
map[nums[i]]++;
}
for(int i=0;i<numsSize;i++){
if(map[i]>1)
return i;
}
return -1;
}
```
👶：
此方法的時間複雜度為$O(n)$，空間複雜度為$O(n)$。
🧔：
雖然時間複雜度是$O(n)$，但這個方法須使用額外空間去實作，能否有不使用額外空間，但時間複雜度為$O(n)$的方法呢？
👶：
痾．．．。
🧔：
你可以從輸入的限制去下手，因為$n + 1$個數範圍只有$1-n$且都不重複，可以利用這點。
👶：
啊，若用剛剛的想法可以從頭開始以陣列的值-1下當作index去走訪，並在走訪後將其值設成負的，當遇到重複的值後，走訪過後會是負數，則回傳此值。
```cpp!
int findDuplicate(int nums[], int numsSize){
for(int i=0;i<numsSize;i++){
if(nums[abs(nums[i])-1]<0) //因index不能負數，固取其絕對值
return abs(nums[i]);
nums[abs(nums[i])-1]*=-1;
}
return -1;
}
```
👶：
這樣時間複雜度為$O(n)$，空間複雜度為$O(1)$。
### [(英)9. Palindrome Number](https://leetcode.com/problems/palindrome-number/)
> [video](https://youtu.be/aEkZw01tZJk)
#### 測驗說明與問答
🧔：
Given an integer x, return true if x is palindrome integer.
An integer is a palindrome when it reads the same backward as forward.
input : 121 return true
Constraints:
* -2^31 <= x <= 2^31 - 1
👶：
I guess my initial approach would be to use a loop to divide x by 10 and add the remainder in an array until the number x is equal to 0.
And then iterate through the array checking whether forward in array equal to backward in array.
I think the special input are minus number and the number that the last digit is 0, like -121 and 120.
程式碼
```cpp!
bool isPalindrome(int x){
int len=0, arr[10];
if(x<0 || x%10==0 && x!=0)
return false;
while(x!=0){
arr[len++]=x%10;
x/=10;
}
for(int i=0;i<len/2;i++){
if(arr[i]!=arr[len-i-1])
return false;
}
return true;
}
```
👶：
The time complexity is $O(n)$, and the space complexity is $O(n)$ too.
🧔：
I see you use an array. Can you solve it with less space.
👶：
OK, i think i can use a loop to divide x by 10, and add the remainder to an integer named ans. Every round ans will multiply 10. Finally ans will be the opposite of x.
程式碼
```cpp!
bool isPalindrome(int x){
long ans=0, xtmp=x;
while(xtmp>0){
ans=ans*10+xtmp%10;
xtmp/=10;
}
return (ans==x && x>=0);
}
```
👶：
The time complexity is $O(n)$, and the space complexity is $O(1)$
### 初步檢討
#### interviewer
* 若發現錯誤應立即點出。
* 既然 interviewee 宣稱完成程式碼，應有必要的檢驗和討論。
* 提問時不應說能快點嗎? 應提出一個適當的複雜度。
#### interviewee
* 邊coding，邊說話的時候，聲音有時會變太小。
* 打字速度還需練習。
* 沒想法的時候停頓蠻久的。
* 英文對話及咬字需多加練習。
### 同儕檢討 - 1
#### interviewer
- [00:48](https://youtu.be/Wy88DIP9j1o?t=48) 時，interviewer 可以舉例，有例子的話可以讓面試者更容易理解題目。
#### interviewee
- [01:35](https://youtu.be/Wy88DIP9j1o?t=95) 在說明參數 int prices[] 時，僅說了傳入 `price 的`，沒有說的什麼，這樣會讓面試官無法理解，可以說傳入指向 prices 陣列起始位置的指標。
- [03:51](https://youtu.be/Wy88DIP9j1o?t=230) 說明複雜度應該要說 big O, 而不是 O。
### 同儕檢討 - 2
整體檢討
- 程式碼應該經過排版，會讓人看得更加舒適
#### interviewer
- [0:00]() 不應該用面試官這個詞
#### interviewee
- [4:34]() 在 follow up 的時候，不需要再寫一次function 的名字，或是輸入的變數，可以直接修改原本的內容或是簡單表示就好
### 同儕檢討 - 3
#### interviewer
- [0:11](https://www.youtube.com/watch?v=Wy88DIP9j1o#t=0m11s) interviewer 說明題目時可以搭配打字讓 interviewee 更好理解
- [3:54](https://www.youtube.com/watch?v=Wy88DIP9j1o#t=3m54s) interviewer 提問時不應說能快點嗎，可以提出一個時間複雜度給 interviewee 思考
#### interviewee
- [0:02](https://www.youtube.com/watch?v=Wy88DIP9j1o#t=0m02s) 記得不要講面試官
- [05:35](https://youtu.be/jPehJVS8mZk?t=334) 時，一開始就可以直接加入例子來解釋了。
## 2022 年[資訊科技產業專案設計 HW2]
[同儕檢討1](https://hackmd.io/@sysprog/S1gP445eGs)
[同儕檢討2](https://hackmd.io/Ld5ZOFgcTQWiskt-vjPLNQ?both)
[同儕檢討3](https://hackmd.io/l6i7r9maTZqeDI-QCoabtQ?both)
[同儕檢討4](https://hackmd.io/dP4805OgQumGIIp5G7k1rw?both)
Sign in with Wallet
Connect another wallet