---
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:

# 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:

# 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:

# 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吧。

# 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所以要預先考慮

🧔：那麼請你把程式乘法的部分改用除法吧。

# 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吧

# 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?

# 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?

# 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.

# 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