暱稱: 呆呆獸 Slowpoke

： Interviewer
： Intreviewee

2605. Form Smallest Number From Two Digit Arrays

• 有些微更改原題，因此 input type 和 output type 有不一樣
• 在擴展題目的過程中，我發現會演變成一個 NP-hard 的問題，自己有盡量做一些推導，但沒辦法確定是對的，歡迎各位同學指教

影片

： 呆呆獸先生您好，歡迎你參加今天的面試，我這邊有個問題想跟你討論，我們可以藉此來更進一步的了解彼此，過程中你有什麼問題，可以隨時跟我溝通。
：好的。
：假設我們要開發一個調查系統，調查的對象是同時使用新產品的某兩家客戶，我們希望客戶提供一些改善產品的意見，藉此來不斷更新產品，以達到敏捷式開發。
：我們會列出 9 項修改需求供客戶做選擇，客戶可以選擇複數個需求，我們要依據客戶的需求去做改進。但由於我們希望盡快更新我們的產品，並推出下一個改良後的版本給客戶，好得到下一次的反饋，所以我們需要從中選出最少數量的需求，且必須滿足每個客戶至少一個需求，同時，盡量符合公司偏好執行的優先度，我們會給需求編號，數字越小的越優先。
：我希望這個系統的輸入是 A 和 B 兩家客戶選擇的需求，輸出要能告訴我接下來要先完成的需求有哪些。可能有點難懂，我這邊舉幾個例子。

Constraints: 1(最優先) <= A[i], B[i] <= 9(較不優先)


=== Exaple 1. === 

Input: A = [4,1,3], B = [5,7]
Output: [1,5]

=== Exaple 2. === 

Input: A = [3,5,2,6], B = [3,1,7]
Output: [3]

：請問客戶會提出重複的需求? 比如說 A = [3, 3]。
：不會，客戶不會提出重複的需求。
：請問如果客戶的需求為空的話呢? 因為他沒有需求，所以我沒辦法完成他的需求，那我要 output 什麼呢?
：那我們再加一個限制，假定每個客戶至少都要提出一個需求，先不要讓這個問題太複雜。

Constraints:
    1(最優先) <= A[i], B[i] <= 9(較不優先)
    1 <= nums1.length, nums2.length <= 9

：還想請問 output 的順序有規定嗎? 我想再舉個例子… 像是這個例子，output 會是 [3,1] 還是 [1,3]?

=== Exaple 3. === 

Input:  A = [4,5,3], B = [1,7]
Output: [3,1] or [1, 3]?

：我們依據公司定義的優先順序排列好了，這個例子的 output 是 [1,3]。
：好的，由於這個問題的答案，需要完整看過 A, B 兩家客戶的需求才能決定，所以我需要兩個 for 迴圈來分別看過這些需求。 另外我還需要一個 hash table 來幫助我判斷兩家客戶是否有提出相同的需求。當有相同時，就輸出兩家都有相同的最小值，若皆不相同，就輸出兩家分別的最小值。
：了解，那請你在 google document 實作一下吧。

vector<int> minRequest(vector<int>& A, vector<int>& B) {
    array<int, 10> hash_table = {0};
    int minB = INT_MAX; int minA = INT_MAX;
    int min_both = INT_MAX; // minimum of toth array
    bool flag = false; // whether there is the same number in A and B

    // scan A
    for (int i = 0; i < A.size(); i++) {
        hash_table[A[i]] += 1;
        if (A[i] < minA) {minA = A[i];}
    }

    // scan B
    for (int j = 0; j < B.size(); j++) {
        // if A has this number
        if (hash_table[B[j]] && B[j] < min_both) {
            min_both = B[j];
        }
        else if (B[j] < minB) {minB = B[j];}
    }

    if (min_both != INT_MAX) return vector<int>({min_both});
    return vector<int>({min(minA, minB), max(minA, minB)});
}

：因為最多只有 9 種需求，A 跟 B 的長度都小於 10，hash_table 也僅需要固定的長度 10，因此時間複雜度為跟空間複雜度皆為

$O(1)$。
：Okay，那請你用剛剛的例子來跑一次程式。
：好的，…(略)
：Okay，那我們現在再討論得廣泛一點，假設今天不只兩位客戶，有 N 位客戶，N

$\ge$ 2，你會怎麼做呢?
：我一樣會使用一個 hash table，用來統計各個需求被客戶指定的次數，次數最多的需求，代表完成他就可以滿足最多的客戶，所以我們就挑選這個需求，接著再觀察剩下還沒被滿足的客戶，重複上面的步驟，直到所有客戶都被滿足。
：那請你再 Google documents 實作一下吧！

vector<int> minRequest(vector<vector<int>>& clients) {
    array<int, 10> hash_table = {0};
    vector<int> result = {};
    
    // whether all the clients are satisfied
    while (clients.size()){
        // compute the number of each request
        for (int i = 0; i < clients.size(); i++) {
            vector<int> client = clients[i];
            for (int j = 0; j < client.size(); j++) {
                hash_table[client[j]] += 1;
            }
        }
            
        // get the most important request
        int max_count = *max_element(hash_table.begin(), hash_table.end());
        int best_request;
        for (int i = 0; i < hash_table.size(); i++) {
            if (hash_table[i] == max_count) {
                best_request = i; 
                break;
            }
        }
          
        // push the request into result
        result.push_back(best_request);
            
        // remove the satisfied clients
        auto satisfied_client  = [best_request](vector<int> const& client) { 
            return (find(client.begin(), client.end(), best_request) != client.end());
        };
        auto it = remove_if(clients.begin(), clients.end(), satisfied_client);
            clients.erase(it, clients.end());
    }
        
    return result;
}

：這個演算法的 while 迴圈最多只會執行 9 次，因為如果跑完 9 次，代表所有的需求都被挑選了。 每一次迴圈，所有的客戶最多只會被看過二次，分別在統計 hash table 跟刪除的客戶的步驟，因此總共時間複雜度是

$O(1)\times O(N)=O(N)$,空間複雜度是

$O(1)$ 因為只有一個固定大小的 hash table。
：我覺得你的做法很值觀，蠻好理解的，但沒辦法完整解決這個問題，我舉個例子:

=== Exaple 4. === 

Input: clients = [[2,1],[2,5],[3,1],[3,6],[4,1],[4,7]]
Output: [2,3,4]

：在這個例子中，你的程式碼的 output 是 [1,2,3,4]，但其實正確答案卻是 [2,3,4]，你有什麼修改或更好的想法嗎?
：那我的演算法應該只能算是一個 Greedy 的演算法… 我現在有個想法，我覺得這個問題可以轉換成圖論的問題，我先把這個例子畫出來！

：圖中上排的 node 是需求的種類，下排的 node 是客戶的需求清單，客戶的清單會跟對應的需求相連。而我們要求的解，相當於在圖的上排 node 中，挑選最少數量的子集，讓所有的客戶至少與子集中的一個 node 相連。
：這讓我想到 Minimun Dominant Set 這個問題，這個問題是說，給定一個圖，存在一組 node 子集，使得圖中的每個 node 都在這個子集中，或者與這個子集中的某個 node 相鄰，則這個子集稱為 Dominant Set。如果這個子集是所有 Dominant Set 中最小的，則稱為 Minimun Dominant Set。
： 因為 Minimun Dominant Set 是個 NP-hard 的問題，與我們的問題非常相似，所以我認為我們的問題也是一個 NP-hard 的問題。
：但在我們的例圖中可以發現，正解跟 Minimun Dominant Set 有一些差距，[2,3,4] 並沒有跟 [1,5~9] 相連，你有辦法證明嗎?
：我嘗試看看… 剛剛我們知道客戶需求問題，可以轉化成一張圖，接下來我要這張圖上做一些小小的改動，我希望讓客戶需求問題等同於求解 dominant set 問題。

：首先，我們在第一張圖可以發現，第二排要與 dominant set 相連，而第一排卻沒有，所以我想新增一個 head 去連接所有第一排的 node，為了要讓這個 head 一定會被選進集合裡面，我在第一排新增足夠數量的 node，迫使我們不得不選 head，這個足夠數量，可以設定成原圖所有 node 的數量。
：接下來，我們可以發現，這個問題變成了 dominant set 的問題，求解客戶需求問題，等同於求解 dominant set，所以客戶問題是個 NP-hard 的問題。
：恩… 雖然你不是用很理論的證法，但是用例子來推，我能大致理解你的想法了，想法還不錯。
：Ok，那我們今天的面試就到這裡吧。

初步檢討

• 邊寫程式邊講解的時間花太久了，要多練習

同儕檢討心得

• 挑選的同學

  • 肥俠-Billy 他評 01
  • 姆咪-MUMI 他評01
  • 布撥-Pawmi 他評02
  • 牙塑-Wind 他評02
  • 追光者-Aegleseeker 他評01

• 通常我給的建議分為以下幾種類型

  • 針對優點
    • 對 REACTO 的完整度給於讚賞
    • 敬佩編寫程式邊講解的同學 (因為我第一次作業沒有做到，第二次作業有嘗試，但還做的不太好)
    • 讚美表達或表演方面 (我自己還有待加強)
  • 針對缺點
    • 若缺少應用場景的設定，我會提出我自己想到的應用場景供參考
    • 提出覺得邏輯上有問題的地方
    • 提供覺得可以更優化的演算法版本
    • 對 interviewer 跟 interviewee 如何更加有"討論、非上對下"的氛圍給予建議