---
tags: info2023-homework2
---
# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FS11ooE4Rh)」作業2

## 1. 互評部分
### 同學一([埃默里-Emery](https://hackmd.io/@sysprog/rJO3aSTJ6))
#### interviewer
- [ ] 優點
* 有針對完成的程式碼提出回應，並且引導面試者提出更好的解法。
- [ ] 可改進的地方
* [00:10](https://www.youtube.com/watch?v=GlGLS3aAvOc):可以想想情境題，比如說這題可以假設在做市場調查，我們想知道在K個小時(索引值)內有沒有兩個人以上買過這個商品(元素)
#### interviewee
- [ ] 優點
* 整體在寫程式時都很順暢，讓面試官可以很清楚現在做到哪裡了。
- [ ] 可改進的地方
* [00:26](https://www.youtube.com/watch?v=GlGLS3aAvOc):在回答面試官問題時，把想法打在電腦上感覺會讓面試官比較好確認你的理解是否正確
*
### 同學二([查理-Charlie](https://hackmd.io/@sysprog/HyEYCSpyp))
#### interviewer
- [ ] 優點
- 題目解釋的很清楚，而且一開始就有出現在上面了，方便面試者閱讀。
- [ ] 可改進之處
- 在出題時的語調感覺可以再更自然一些。
#### interviewee
- [ ] 優點
- 可以邊寫程式邊解釋目前做到哪裡，很厲害!
- [ ] 可改進之處
- [01:54](https://youtu.be/dVpY2ObOC2I?si=H8wYc6e84M33XfuY&t=114): 在描述想法時可以把它打出來，可以讓面試官更理解。

### 同學三([月前龍馬-lonmu](https://hackmd.io/@sysprog/SkzGyUayT))
#### interviewer
- [ ] 優點
- 題目和條件都解釋得很清楚，語速也很順暢自然。
- [ ] 可改進的地方
- 面試者發現括號錯誤，可以提醒，增加互動性。
#### interviewee
- [ ] 優點
- 寫完時有針對example的部分做test。
- [ ] 可改進的地方
- [00:56](https://youtu.be/ylDgHkwjpIw?si=dKOBhKKc8KARn89T&t=55): for example是e.g.，用EX不太正式。
### 同學四([盲狗-Mango](https://hackmd.io/@sysprog/Syvm18aka))
#### interviewer
- [ ] 優點
- [13:18](https://youtu.be/sqPCM6ESEZg?si=igU6goXCf72nlWEy&t=798):針對程式碼有提供具體的問題，增加討論的空間。
- [ ] 可改進的地方
- 若可以用一些生活的例子或是情境來包裝題目會更好。
#### interviewee
- [ ] 優點
- 整個面試的過程很自然而且很流暢，說明也很清楚。
- [ ] 可改進的地方
- [00:56](https://youtu.be/sqPCM6ESEZg?si=7-QywUbm-qumvW0y&t=56):在打例子時我覺得可以稍微說明或是說點話，讓空氣不要太安靜
### 同學五([李一-Pear](https://hackmd.io/@sysprog/SkC2xITJT))
#### interviewer
- [ ] 優點
- [00:06](https://youtu.be/EHdy7qDeJoY?si=CfCE6-Ja8c41lzhq&t=6):題目有用情境題包裝，可以避免面試者背答案。
- [ ] 可改進的部分
- 面試官問問題時除了針對題目改善外，應該要想如何找出面試者的思維邏輯，譬如說，他是如何想到第二種解法，為什麼一開始想不到?
#### interviewee
- [ ] 優點
- 寫程式時的速度跟語速可以讓聽的人很清楚解題過程跟邏輯。
- [ ] 可改進的部分
- 有時候調整程式架構會太安靜，可以說些話，比如說接下來的步驟。

### 評論完心得

看完別人的面試後，我有很多部分需要改進
1.要包裝題目讓面試者無法一眼看出考題
2.雙方的討論性不夠強，所以做題都是直接暴力法，應該要討論到一個階段才寫code
3.英文還需要多練習講話

## 2. 模擬面試
### [2295. Replace Elements in an Array](https://leetcode.com/problems/replace-elements-in-an-array/description/)
> 貢獻者: 甲魚-baspis
> 🧔：interviewer 👶：interviewee
>
> ==[video](https://youtu.be/rtYpyDLbaTQ)==
### 面試過程
🧔：嗨同學你好，歡迎你來參加我們這次的線上面試，在這次的面試中我會給你一些問題，希望你可以提供想法並且試著實作出來，那麼我們就馬上開始吧!
🧔：我們公司想要加強保護資料的機制，我們想到了一個方法是使用加密的方式來讓原本的資料轉換成密文，這裡我們先給一個整數陣列$nums$當作是原資料，加密金鑰我們想要採用置換數字的方式，給予你多個置換的步驟，按照步驟將資料加密，最後就會出現所需要的密文。
🧔：舉例來說，原資料假設為[1 2 4 6]，給定加密金鑰為{[1,3]}，我們就將原資料的1置換，而成為[3 2 4 6]，加密金鑰可能有多組讓整個過程複雜化來提高保護性，也保證每個置換的步驟都可以正確地執行。請問到目前為止可以理解問題嗎?
👶：針對題目我想要舉個例子來確定我是否了解，假設原資料為[1 2 4 6]，加密金鑰為{[1,3],[4,5],[5,7]}，那加密過程就是..這樣對嗎?

Given nums[1 2 4 6] and operations{[1,3],[4,5],[5,7]}
run0=[1 2 4 6]
run1=[3 2 4 6]
run2=[3 2 5 6]
run3=[3 2 7 6]

🧔：你的理解沒錯，那想問你有什麼想法嗎?
👶：我目前初步的想法是使用for迴圈來取得金鑰中要置換的兩個數字，然後再利用for迴圈來拜訪原資料找到它的位置。

1. for() -> get old num,new num
2. for() -> find old num location and replace

🧔：聽起來可行，但我們公司的加密過程一定是很複雜的，這樣的方式會讓我們每次加密都需要花很長的時間，有沒有辦法讓你目前思維的某個架構變快，比如說找位置的速度變快或是置換速度變快之類的。
👶：如果要加快找位置的速度的話，我們可以使用unordered map來儲存原資料，因為使用unordered map找到數的時間複雜度為$O(1)$，相較於使用for迴圈是$O(N)$的速度來的快。

nums[1 2]
map[1]=0
map[2]=1

operations{[1 3]}
search map[1]->0
replace num[0] with 3
update map(我們要把舊的數字剔除map)

🧔：聽起來對於加速確實有幫助，那我們可以來將剛剛討論的結果寫出來看看嗎?

# 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;
    }
};

👶：我的程式碼完成了，接著用上面的例子[1 2 4 6]來測試的話...，確定這個程式碼可以運行。

nums[1 2 4 6] and operations{[1,3],[4,5],[5,7]}
1.建立map
map[1]=0
map[2]=1
map[4]=2
map[6]=3
2. for loop
run1: old=1 new=3
map[1]=0 -> map[3]=0 and del map[1]
nums -> [3 2 4 6]

run2: old=4 new=5
map[4]=2 -> map[5]=2 and del map[4]
nums -> [3 2 5 6]

run3: old=5 new=7
map[5]=2 -> map[7]=2 and del map[5]
nums -> [3 2 7 6]

👶：以上是我的程式碼，如果使用unordered map的話，可以讓整體時間複雜度變為$O(N)$，請問對於程式碼有什麼建議或是可以修改的地方嗎?
🧔：這裡看的出來你為了讓程式的每個步驟更清楚，因此使用了很多變數來區分，但我們希望這個加密的程式可以越簡單越好，可以請你調整一下裡面的內容讓程式碼可以精簡化嗎?
👶：如果要精簡程式的話，old_num和new_num和location其實都可以只使用operation表示就可以了，那我就直接調整程式碼。

# 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;
    }
};

👶：調整後的程式碼相較於上一個可以精簡三行，請問這裡還有什麼可以改進的地方或是建議嗎?
🧔：看起來程式碼對於我們的加密資料提供了不錯的想法，那我給你一些延伸的問題可以回去想想，像是如果解密要怎麼做，以及哪種加密方式的隱密性更高可以等等，今天的面試就到這裡，謝謝你今天的參與!