# info2023-homework2
##### tags: `資訊科技產業專案設計`
> 作者：克勞迪（Cloudy）
> 👨💻: **Interviewer**
> 👨💼: **Interviewee**
## 影片
> Video Link: https://youtu.be/LHPH4KmyTR4
> Question
> - Contains Duplicate
- 👨💻 (Interviewer)
克勞迪您好，歡迎參加本公司的面試，我是負責本次面試的人員。
如果沒有什麼問題，我們就直接開始今天的面試吧。
- 👨💼 (Interviewee)
您好，我沒有任何問題，隨時都能開始，謝謝。
- 👨💻 (Interviewer)
好的。
假設有一個非常熱門的付費制的影片串流平台，他們目前發現了一個嚴重影響營收的問題：有許多的使用者會共用同一個帳號。
共用的意思是，帳號雖然有正常繳納費用，但卻有超過一位的使用者，通過同時登入這個帳號，從而共享這個帳號觀看影片的權利。
基於一些特別的考量，這個平台的管理層希望防堵帳號共用問題不要採用互斥鎖的概念，也就是在使用者登入時，檢查目前帳號的狀態是否在線或離線，從而允許登入或拒絕登入。
他們希望能先讓使用者登入，系統再週期性地檢查當前在線的帳號是否有重複登入的情形，最後才針對檢查到重覆登入的連線進行後續處理。
您現在要負責根據管理層的想法，開發檢查帳號是否重複登入的功能，想請問您有什麼想法？
- 👨💼 (Interviewee)
我的任務是定期從當下在線的帳號中，找出重複登入的連線。
想先與您確認，關於這個問題，是否有既有的資料結構需要遵循？
以及我可以取得什麼和帳號有關的資訊用來實作功能？
- 👨💻 (Interviewer)
該平台的伺服器上已有紀錄當前存在哪些連線的功能，您可以將其想成是一個陣列。
這個陣列儲存了當前在線的帳號以及其登入時的基本資訊，像是帳號的 ID、來源 IP 等等，只要是伺服器有儲存的資訊，您都能自由運用。
- 👨💼 (Interviewee)
了解。
也就是說，這個紀錄當前連線的陣列是只要有新的登入請求，都會添加一筆新資料進來。
請問我的理解正確嗎？
- 👨💻 (Interviewer)
沒錯。
另外想補充一下，伺服器有能力在極短時間內深複製當前的所有連線資訊，您只要專注於利用伺服器提供的連線資訊，找出重複登入的連線即可，不需要考慮檢查時連線增減的問題。
- 👨💼 (Interviewee)
感謝您的補充說明。
為了方便說明，我先定義簡化的資料結構
```cpp=
struct LoginData {
int uid;
string ip;
};
vector<LoginData> connections;
```
`uid` 指的是帳號的唯一識別碼、`ip` 是登入端的對外 IP，`connections` 則是一個儲存 `LoginData` 的一維陣列。以您的解釋來說，是伺服器深複製當前連線資訊所得到的資料。
我假設使用者在登入、登出時，伺服器都能即時且正確的更新連線資訊。也就是說，伺服器能保證同一位使用者不會有重複的紀錄在連線資訊中。
舉個例子來說，如果現在有三個不同的在線帳號，他們的連線資訊分別為 u1, u2, u3，且不存在重複登入的情況，`connections` 就會是 [u1, u2, u3]，檢查完的結果應為空，因為沒有重複的帳號在 `connections` 裡面。
如果同樣是有三個不同的在線帳號，但存在重複登入的情況，例如 `connections` 等於 [u1, u2, u1*, u3]，檢查後的輸出就應該是 [u1, u1*]，因為 u1 和 u1* 都是同一個帳號，但登入資訊不同。
請問我的舉例是否符合您對於檢查的要求？
- 👨💻 (Interviewer)
是的，您的舉例沒有任何問題。
看起來您打算通過檢查是否存在重複的 `uid`，從而找到重複登入的連線。
請問您目前有想到什麼作法嗎？
- 👨💼 (Interviewee)
我目前想到最直觀的方法是使用兩層的巢狀迴圈，分別檢查每個 LoginData 的 `uid` 和其他 LoginData 的 `uid` 是否相同。
```cpp=
vector<LoginData> findDuplicateConnections(vector<LoginData> connections) {
vector<LoginData> outputs;
for(int i = 0; i < connections.size(); i++) {
for(int j = 0; j < connections.size(); j++) {
if(i == j) {
continue
}
if(connections[i].uid == connections[j].uid) {
outputs.push_back(connections[i])
break;
}
}
}
return outputs;
}
```
代入上面的例子，驗證這支程式是否正確。
令 u1, u2, u3 的 `uid` 分別為 `1`, `2`, `3`，`connections` 為 [u1, u2, u3]。
兩層迴圈會驗證過不包含本身的所有兩兩組合，且由於 `connections` 中不存在相同 `uid` 的元素，因此在迴圈中的所有檢查都不會使 isDuplicate 變成 true，這會導致沒有任何元素被存進 `outputs` 中。
`outputs` 為空和我們預期的結果相同。
同樣令 u1, u2, u3 的 `uid` 分別為 `1`, `2`, `3`，但 `connections` 變成 [u1, u2, u1*, u3]。
兩層迴圈一樣會驗證過不包含本身的所有兩兩組合，但由於 `connections` 中存在 u1, u1* 的 `uid` 相同，因此當次迴圈中的檢查會使 u1, u1* 被存進 `outputs` 中。
`outputs` 為 [u1, u1*] ，和我們預期的結果也相同。
- 👨💻 (Interviewer)
這個作法很直觀，確實能解決問題，不過時間複雜度很明顯是 O(n^2)。
熱門線上影片串流平台流量很大，因此不適合以這樣的作法檢查重複登入。
想請問您對加速計算過程有沒有什麼想法？
例如先對資料進行處理再檢驗，而不是單用迴圈暴力解？
- 👨💼 (Interviewee)
有的！
在我的假設中，`uid` 是一個整數型態的資料，因此可以排序。
我想可以使用任意排序演算法先對 `connections` 進行大小排序。
只要 `connections` 內的元素依照 `uid` 的大小被排好之後，我們只要從頭到尾遍歷一次，對 `connections` 中的每一個元素檢查它們相鄰元素的 `uid` 和本身的 `uid` 是否相等，就能知道 `connections` 中是否有相同的元素。
這樣的作法可行的原因是，如果存在兩個元素的 `uid` 相等，那經過排序後，他們理應會相鄰。
```cpp=
bool myCompare(LoginData u1, LoginData u2) {
return u1.uid > u2.uid;
}
vector<LoginData> findDuplicateConnections(vector<LoginData> connections) {
vector<LoginData> outputs;
sort(connections.begin(), connections.end(), myCompare);
for(int i = 0; i < connections.size() - 1; i++) {
if(connections[i] == connections[i + 1]) {
if(!outputs.empty()) {
if(outputs.back() != connections[i]) {
outputs.push_back(connections[i])
}
}
else {
outputs.push_back(connections[i])
}
outputs.push_back(connections[i + 1])
}
}
return outputs;
}
```
同樣以上面的例子驗證這支程式。
令 u1, u2, u3 的 `uid` 分別為 `1`, `2`, `3`，`connections` 為 [u1, u2, u3]。
經過排序之後，`connections` 內的元素順序同樣還是 [u1, u2, u3]。
接著進入迴圈，檢查兩兩元素。由於這個例子中，`connections` 不存在 `uid` 相同的元素，因此絕不可能執行到將元素存到 `outputs` 的部分，故 `outputs` 會為空，這符合我們的預期結果。
同樣令 u1, u2, u3 的 `uid` 分別為 `1`, `2`, `3`，但 `connections` 改成 [u1, u2, u1*, u3, u1**]。
經過排序之後，`connections` 內的元素順序會變成其中一種可能的順序 [u1, u1*, u1**, u2, u3]。
接著進入迴圈，檢查兩兩元素。這個例子中，u1、u1*, u1** 都有相同 `uid`。
在 i = 0 時，由於 `outputs` 為空，因此會將 u1 和 u1* 都存進 `outputs` 內。
在 i = 1 時，由於當前 `outputs` 的最後一個元素是 u1*，因此不需要重複儲存 u1*，只要將 u1** 存進 `outputs` 就好。
後面其他步驟，由於元素的 `uid` 皆不相同，因此絕不會執行到和 `outputs` 有關的程式。`outputs` 的最終結果為 [u1, u1*, u1**]，和我們的預期結果相同。
這個作法的時間複雜度其實會取決於前面的排序演算法，因為在這支程式中，耗時主要有兩部份，第一個部份是排序演算法，第二部份則是後面的 for 迴圈。
不過其實能很明顯的發現，for 迴圈的時間複雜度是 O(n)，如果排序演算法的時間複雜度比 for 迴圈高，就會影響到整體的時間複雜度。
排序演算法的時間複雜度通常都會大於 O(n)，以這邊寫的程式為例，我是用的語言是 C plus plus，sort 使用的是 standard library 裡面的 sort function，它的平均時間複雜度會是 O(nlog(n))，所以整支程式的時間複雜度就會是 O(nlog(n))。
- 👨💻 (Interviewer)
通過排序簡化檢索是很不錯的想法，不過這個題目其實最好的做法可以做到線性時間，不知道您是否能夠提供一個時間複雜度也是線性時間的作法呢？
- 👨💼 (Interviewee)
嗯...
我目前有一些想法，不過想與您對照一下，確認方向是否正確，不知道方不方便請您先說說看？
- 👨💻 (Interviewer)
如果能在遍歷的時候，將已經遍歷過元素都紀錄起來，也許能很有效率的排查是否有重複的元素在陣列裡面？
- 👨💼 (Interviewee)
我想到了！
可以建一個表格，表格的索引值對應到的是 `uid` 的值，要紀錄時，只要在表格相應的位置記數，也就是紀錄 `uid` 出現的次數，當我們對所有元素都進行資料處理後，只要再遍歷整個表格一次，如果發現有 `uid` 的出現次數大於一，就代表該帳號重複登入，反之就沒有，如此就能很輕鬆的知道陣列內是否有重複的元素值！
除此之外，我有想到一些問題，如果當前在線的帳號 `uid` 值域很大，假設有一個 `uid` 是一億，但另一個 `uid` 是一，而且在線的帳號數量遠小於一億，以這個例子來說，如果依照前面的方式建表，就會浪費很多空間，也會增加遍歷表格的時間。
針對這個問題，我認為也許可以利用字典，也就是把 `uid` 當成字典的 key，計數的值則當成 value，這樣就能同時優化時間和空間的效能。
```cpp=
vector<LoginData> findDuplicateConnections(vector<LoginData> connections) {
vector<LoginData> outputs;
unordered_map<int, int> map;
for(int i = 0; i < connections.size(); i++) {
map[connections[i].uid] += 1;
}
for(int i = 0; i < connections.size(); i++) {
if(map[connections[i].uid] > 1) {
outputs.push_back(connections[i])
}
}
return outputs;
}
```
也是以上面的例子驗證這支程式。
令 u1, u2, u3 的 `uid` 分別為 `1`, `2`, `3`，`connections` 為 [u1, u2, u3]。
經過第一個迴圈後，程式便已計算好所有 `uid` 出現的次數了，在這個例子中會是 {uid: count} = {1: 1, 2: 1, 3: 1}
在第二個迴圈中，程式會檢查每一個連線的 uid 的次數是否有超過一，若有超過一則代表重複連線。這個例子中，所有 `uid` 的次數皆為一，因此 `outputs` 會為空，這符合我們的預期結果。
同樣令 u1, u2, u3 的 `uid` 分別為 `1`, `2`, `3`，但 `connections` 為 [u1, u2, u1*, u3, u1**]。
經過第一個迴圈後，map 會等於 {uid: count} = {1: 3, 2: 1, 3: 1}
在第二個迴圈中，迴圈會檢查出 u1, u1* 以及 u1** 的 `uid` 次數大於一，其餘則沒有。因此 `outputs` 會為 [u1, u1*, u1**]，這符合我們的預期結果。
上面的程式碼的時間複雜度是 O(n)，主要能分成兩個部份分析，第一個部份是迴圈，兩個迴圈都會跑過所有元素，因此時間複雜度是 O(n)；第二部份則和 unordered_map 的建立和搜尋有關，unordered_map 是基於 hash table 的一種資料結構，處理碰撞的策略，它大多使用 Closed Addressing，也就是說，當沒有任何碰撞情況發生時，時間複雜度最好能達到常數時間，也就是 O(1)，當有碰撞發生時，最壞的情況則是 O(n)。
綜合以上敘述，整體的時間複雜度會是 O(n)。
空間複雜度部份，在最壞的情況下，也就是輸入的元素每個都不一樣時，每一個元素都會分別佔用一個 hash bucket，因此空間複雜度會是 O(n)。
- 👨💻 (Interviewer)
最後有使用到 hash table 進一步優化建表可能造成的時間和空間負擔非常好！
今天的面試差不多到這邊結束，關於今天的面試結果再請您留意個人信箱。
如果沒有問題的話，感謝您今天的參與，再見！
- 👨💼 (Interviewee)
也非常謝謝您！
再見！
## 給他人的回饋簡介
### 正面
1. 有同學扮演 interviewer 時，給予 interviewee 的提示恰到好處（不是直接說作法，但能讓人思考到作法）。
2. 有同學扮演 interviewer 時，對於 interviewee 的回饋（針對程式碼能改進的地方進行提問並提出建議），很認真的 interviewer。
3. 有同學扮演 interviewer 時，在提出問題的同時，有提到問題在現實世界中的影響，與現實連結感覺很好。
4. 有同學扮演 interviewee 時，邊撰寫程式碼邊講解的很順暢、詳細。
5. 有同學扮演 interviewee 時，在驗證的步驟設計了發現自己程式寫錯的橋段，並當場解決，這樣的練習很棒。
### 反面
1. 引用老師上課所言，利用情境包裝題目，會比直接詢問原題好。
2. 驗證作法是否正確時，要盡量考慮特例。
3. 驗證作法是否正確時，舉例代入說明會比直接執行結果好（畢竟不能保證每一場面試都能有可執行環境）。
4. 口語用語要注意，盡量讓自己不要有贅字、口頭禪或有失禮貌的發言。
5. 有同學提到中文科技用語時講錯了用法，專有名詞也是需要注意的一環。
## 我學到的東西
1. 我在第一次作業中，完全沒有一邊寫程式一邊講解的部分，都是先講解完，然後就默默地把程式寫完。在觀看他人作業的過程中，看到了很多示範，也順利在第二次作業努力讓自己一邊寫程式一邊講解了。
2. 我在第一次作業中，疏忽了很多驗證的部分（因為覺得很花時間），不過同樣是觀看了大家驗證的方法，也順利在第二次作業中努力嘗試驗證的部分了。
3. 有一位同學的某一題影片，在 interviewer 提出改進問題時，有提到在現實可能造成的影響，我在第二次的作業中，也有模仿出類似的概念。
Sign in with Wallet
Connect another wallet