---
tags: info2023-homework1
---
# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者: 甲魚-baspis
> 🧔：interviewer 👶：interviewee
## [136. Single Number](https://leetcode.com/problems/single-number/description/)
> ==[錄影](https://www.youtube.com/watch?v=mfDstZAhoDs)==
### 面試過程
🧔：同學你好，歡迎你參加第一次的線上面試，在這次的面試中，我們希望可以了解你對於程式開發的風格與想法，所以我們會提出三個問題，希望你能夠提出你的看法並且試著將他們實作出來。
🧔：首先第一個問題，給予一個非空的整數陣列，其中除了一整數X外，都是兩兩成對的，請問你要如何判斷並且找出X呢?
👶：我想先請問，陣列的長度以及數值的上下界分別是多少呢?然後我想要舉個例子來看看我對於題目的要求是否正確。
🧔：沒錯你的舉例是正確的，那假設陣列長度在1到30000之間，而數值介於-30000到30000之間。
👶：我們要找到此陣列中唯一不成對的整數X，初步的想法是建立一個整數陣列，考慮到有負數，因此我想要建立一個大小為60002的陣列arr，使用for迴圈跑完nums，每次在arr中把每個元素+30000的位置+1，最後再用for迴圈檢查arr中哪個位置的值為1，將其-30000即為所求。
```
設nums為[2,2,1]，則
arr[2+30000]=2
arr[1+30000]=1
因為arr[30001]值為1，因此可得X=30001-30000=1。
```
🧔：所以你是想要用位移的方式，讓負數儲存在arr中0~30000之間，聽起來可行，那麼麻煩你開始coding吧。
#### Method1:
```cpp
# Time: O(n)
# Space: O(n)
class Solution {
public:
int singleNumber(vector<int>& nums) {
int arr[60002]={0};
for(auto i:nums){
arr[i+30000]++;
}
for(int i=0;i<60002;i++){
if(arr[i]==1){
return i-30000;
}
}
return -1;
}
};
```
👶：因為for迴圈跑過整個陣列，因此時間複雜度為$O(n)$，而空間複雜度為$O(n)$。
🧔：事先建立好陣列雖然是個很直接有效的辦法，但是並不是每個空間都會被使用到的，能請問你有沒有辦法只存有用到的數字呢?
👶：可以用C++的unordered_map紀錄出現的數字(key)以及出現的次數(value)，最後再用for迴圈判斷map中value=1的元素即為所求X。
```
設nums為[2 2 1]，則
map[1]=1
map[2]=2
因為map[1]值為1，因此可以知道X就是1。
```
#### Method2:
```cpp
# Time: O(n)
# Space: O(n)
class Solution {
public:
int singleNumber(vector<int>& nums) {
unordered_map<int,int> map;
for(auto i:nums){
map[i]++;
}
for(auto a:map){
if(a.second==1){
return a.first;
}
}
return -1;
}
};
```
👶：以上是我的演算法，程式的時間複雜度為$O(n)$，空間複雜度為$O(n)$。
🧔：其實這道題目有個技巧性的解法，利用基本邏輯閘就能不額外使用矩陣或是unordered_map，可以請你思考是利用哪個邏輯閘並且實作看看嗎?
👶：因為題目只有X一個是單獨存在的，所以應該要思考如何消去其他成對的數字並且只保留X，那麼我們應該要使用XOR這個邏輯閘，因為XOR可以讓相同的數字運算後結果變0，而0和任何數字XOR都等於數字自己，那麼在這題當中，我只需要利用for迴圈將所有數字作XOR，最後就會剩下X了。
```
設nums為[2,2,1]
2 XOR 2 XOR 1 XOR
=0 XOR 1
=1
可以得X=1
```
🧔：那麼請你將程式實作出來吧
#### Method3:
```cpp
# Time: O(n)
# Space: O(1)
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans=0;
for(auto x:nums)
ans^=x;
return ans;
}
};
```
👶：以上是我的演算法，程式的時間複雜度為$O(n)$，空間複雜度為$O(1)$。
🧔：大致上都沒問題，那我們就繼續下一道題目了。
## [69. Sqrt(x)](https://leetcode.com/problems/sqrtx/description/)
> ==[錄影](https://www.youtube.com/watch?v=mfDstZAhoDs)==
### 面試過程
🧔：在這題我們想請你不要利用程式本身的函數庫，實作出整數開根號，小數點無條件捨去，而且不需要表示負數的答案，整數範圍介於$0$~$2^{31} -1$。
👶：那麼我假設題目的整數為X，令一個整數變數$temp$從0開始，判斷$temp^2$是否等於X，如果等於則回傳$temp$，如果$temp^2$小於X，而且$(temp+1)^2$大於X，則也回傳$temp$，每次$temp$都加1。
```
設X=4，因為2^2=4，所以2即為所求
設X=10，因為3^2=9<10，且4^2=16>10，所以3即為所求
```
🧔：所以你想要用乘法慢慢逼近正確答案，那就請你開始coding吧。
```cpp
# Time: O(n)
# Space: O(1)
class Solution {
public:
int mySqrt(int x) {
long int temp=0;
while(temp<=x){
//case1:
if(temp*temp==x){
return temp;
}
//case2:
else if(temp*temp<x&&(temp+1)*(temp+1)>x){
return temp;
}
//case3:
else{
temp++;
}
}
return -1;
}
};
```
👶：考慮到temp從0跑到X，所以時間複雜度為$O(n)$，空間複雜度為$O(1)$。
🧔：雖然你有考慮到可能因為數字很大的關係，必須要用long int才能夠防止變數因為平方的關係overflow，但請問你有沒有辦法調整其他程式碼，一樣解決overflow問題呢?
👶：如果不能夠用long int的話，在判斷式我們可以把temp移到X那側變成除法，以解決因為乘法導致數值過大的問題，並且因為除法的關係，需要預先考慮X=0的狀況。
```
設X=4，因為2=4/2，所以2即為所求
設X=10，因為3<10/3，且4>10/4，所以3即為所求
設X=0，因為數學上不能除以0所以要預先考慮
```
🧔：那麼請你把程式乘法的部分改用除法吧。
```cpp
# Time: O(n)
# Space: O(1)
class Solution {
public:
int mySqrt(int x) {
int temp=2;
if(x==0){
return 0;
}
if(x==1){
return 1;
}
while(temp<=x){
if(temp==(x/temp)){
return temp;
}
else if(temp<(x/temp)&&(temp+1)>(x/(temp+1))){
return temp;
}
else{
temp++;
}
}
return -1;
```
👶：以上是我的演算法，程式的時間複雜度為$O(n)$，空間複雜度為$O(1)$。
🧔：假設數字很大，那麼從0開始一個一個判斷顯然是不夠有效率的，請問你有沒有辦法改進甚至優化平均的時間複雜度呢?
👶：我們可以使用binary search，從X的一半(mid)開始判斷，如果滿足條件就回傳mid，如果太小就令頭為mid+1重新計算新的mid值，反之就令尾巴為mid-1計算新的mid值，如果最後first>last就直接回傳last。
```
設X=10，
first=2, last=10, mid=6, 因為6>10/6
first=2, last=5, mid=3, 滿足3=10/3
因此答案為3
```
🧔：這樣的確可以每次減少判斷一半的數，那請你開始coding吧
```cpp
# Time: O(logn)
# Space: O(1)
class Solution {
public:
int mySqrt(int x) {
if(x==0){
return 0;
}
if(x==1){
return 1;
}
int first=2,last=x,mid;
while(first<=last){
mid=first+(last-first)/2;
if(mid==x/mid){
return mid;
}
else if(mid>x/mid){
last=mid-1;
}
else{
first=mid+1;
}
}
return last;
}
};
```
👶：利用binary search時間複雜度變為$O(logn)$，空間複雜度為$O(1)$。
🧔：很好，我們可以進行下一道題目了。
## [2295. Replace Elements in an Array](https://leetcode.com/problems/replace-elements-in-an-array/description/)
> ==[錄影](https://www.youtube.com/watch?v=cOfrze2ppGI)==
### 面試過程
🧔：In this question, we would like you to make a function that can replace elements in an array. Given you an array called $nums$, and an array of size $N*2$ called $operations$. In $operations$, the fist postion contains the number going to be replaced in $nums$, and the second position contains the new number going to insert in $nums$.
👶：For example, if nums contains [1 2 4 6] and one row of the opearion contains [1,3], which means replace 1 with 3. Therefore, the nums becomes [3 2 4 6]. Am I correct? And I would like to ask if the numbers in nums are unique.
🧔：Yes, your example is correct. all the numbers in $nums$ are unique, and it is guaranteed that all operations can be executed.
👶：My thought is if we want to replace the elements in $nums$, we could use for loop to get two elements from $operations$ in each iteration, one representing the old number and the other representing new number. Then, we could use another for loop searching the old number and replace it.
```
nums[1 2 4 6]
operations{[1 3]}
->replace 1 with 3
nums[3 2 4 6]
```
🧔：sounds reasonable, could you translate your idea into code?
```cpp
# Time: O(n^2)
# Space: O(1)
class Solution {
public:
vector<int> arrayChange(vector<int>& nums, vector<vector<int>>& operations) {
for(int i=0;i<operations.size();i++){
int new_num=operations[i][1];
int old_num=operations[i][0];
for(int j=0;j<nums.size();j++){
if(nums[j]==old_num){
nums[j]=new_num;
break;
}
}
}
return nums;
}
};
```
👶：Here is my code. The time complexity is $O(n^2)$ because of the double for loop, and the space complexity is $O(1)$.
🧔：For the second for loop, it's obviously not efficient enough when dealing with huge amount of data. Could you improve the speed searching for the position of the old_num?
👶：We can use unordered_map to store the numbers and its' positions since the time complexity searching for the element in unordered_map is $O(1)$.
```
nums[1 2]
map[1]=0
map[2]=1
operations{[1 3]}
search map[1]->0
replace num[0] with 3
update map
```
🧔：The example sounds clear, could you revise your code?
```cpp
# Time: O(n)
# Space: O(1)
class Solution {
public:
vector<int> arrayChange(vector<int>& nums, vector<vector<int>>& operations) {
unordered_map<int,int>map;
for(int i=0;i<nums.size();i++){
map[nums[i]]=i;
}
for(int i=0;i<operations.size();i++){
int old_num=operations[i][0];
int new_num=operations[i][1];
int location=map[old_num];
nums[location]=new_num;
map[new_num]=location;
map.erase(old_num);
}
return nums;
}
};
```
👶：Here is my code,the time complexity becomes $O(n)$ and the space complexity is $O(1)$
🧔：There are no significant issues, but I've notice that there are some variables that are unnecessary. Could you please streamline the code?
👶：No problem, the variables could be replaced by map and operations.
```cpp
# Time: O(n)
# Space: O(1)
class Solution {
public:
vector<int> arrayChange(vector<int>& nums, vector<vector<int>>& operations) {
unordered_map<int,int>map;
for(int i=0;i<nums.size();i++){
map[nums[i]]=i;
}
for(int i=0;i<operations.size();i++){
nums[map[operations[i][0]]]=operations[i][1];
map[operations[i][1]]=map[operations[i][0]];
map.erase(operations[i][0]);
}
return nums;
}
};
```
👶：I've done. The code has been more streamlined.
🧔：It looks good,I have no more questions, so the interview is finished. Thanks!
## 自評-interviewer
- 在出題時應該要包裝題目，避免面試者用背題的方式回答問題。
- 互動性有點低，感覺可以多引導讓面試者不要一開始就直接暴力解。
- 針對改進程式碼的部分，也應該用一些實際的舉例包裝
- 在面試者coding結束時，應該要驗證程式的正確性。
- 英文口說需要再多練習，增加流暢度和清晰度。
## 自評-interviewee
- 在舉例題目時，可以把例子和條件寫出來而且寫清楚。
- 說明想法時，感覺可以把SOP列出來。
- 寫程式碼時，應該要適時地用一些註解讓面試官知道寫到哪裡了。
- 寫完程式時，應該要去測試程式的正確性。
- 滿容易打錯字的。
---
## 第二次作業-他評
### Interviewer
- 應該把題目寫出來，而不是只是口頭講，會比較好。
- 事先或許可以主動給出example，再由interviewee考慮特殊input來補充。
- 都有做後續討論以及說明時間複雜度和空間複雜度。
- [7:54](https://www.youtube.com/watch?v=cOfrze2ppGI&t=7m54s): Thanks不夠正式，可以講Thank you for your participation之類的。
### Interviewee
- 最後的Test或許可以直接給example input，Run code或者人體compiler。
- [1:30](https://youtu.be/mfDstZAhoDs?si=dR-DmO618zMDdD9f&t=1m30s): 沒有提到初始化所有陣列的值為0。
- [1:35](https://www.youtube.com/watch?v=cOfrze2ppGI&t=1m30s): 感覺這句打了和沒打差不多，可以跑一次範例比較清楚。
## 第二次作業-他評02
### Interviewer:
* 在介紹題目的時候也許可以有一些圖文可能會讓interviewee更能理解題目。
* interviewer有試圖想要一步一步引導的感覺。不過有些引導感覺過於直白。引導的部分可以再給一些故事性，像是平常會遇到哪些運用，所以可以怎麼思考之類的。
* 感覺可以再多增加題目對應真實應用的討論
* 在interviewee解釋可能的作法後，可以不用太快讓interviewee直接開始coding，可多討論些不同做法或此做法可能存在的問題，就不會讓面試者一開始就都是暴力解。
### Interviewee:
* 有考量到Constraints的部分，很棒！
* 有分析空間和時間複雜度。
* 邊打程式碼的時候同時有做說明，不會讓人感覺冷場的感覺。
* 缺少reacto的test部分，有點可惜。
## 第二次作業-他評03
### interviewer
- 有明確指出Interviewee的問題，並進行有效溝通
### interviewee
- 在開始coding之前，有舉例並確認題意
### 可改進之處
- Interviewer應避免開頭直接說出有多少問題
- 在和interviewer溝通時，一口氣將問題問完，等待有回覆再繼續詢問可能會更好一點，也可以避免在實際溝通中讓對方感到混亂
## 第二次作業-他評04
### interviewer
- [ ] 優點
* 直接丟問題讓interviewee自己尋找路綫，適當時候有給hints拉回來
- [ ] 可改進之處
* 一般系統下long int 與 int 其實都是一樣 -2^32 ~ 2^32 - 1， 只有long long才是2^64
### interviewee
- [ ] 優點
* code是實作的時候有解釋清楚
- [ ] 可改進之處
* 一般系統下long int 與 int 其實都是一樣 -2^32 ~ 2^32 - 1， 只有long long才是2^64
Sign in with Wallet
Connect another wallet