---
# System prepended metadata

title: info2023-homework2

---

# 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 提出改進問題時，有提到在現實可能造成的影響，我在第二次的作業中，也有模仿出類似的概念。
