> 暱稱: 呆呆獸 Slowpoke
> :man:： Interviewer
> :baby:： Intreviewee
>
## [2605. Form Smallest Number From Two Digit Arrays](https://leetcode.com/problems/form-smallest-number-from-two-digit-arrays/)
> * 有些微更改原題，因此 input type 和 output type 有不一樣
> * 在擴展題目的過程中，我發現會演變成一個 NP-hard 的問題，自己有盡量做一些推導，但沒辦法確定是對的，歡迎各位同學指教
[影片](https://youtu.be/V0oGllieCSY)
:man:： 呆呆獸先生您好，歡迎你參加今天的面試，我這邊有個問題想跟你討論，我們可以藉此來更進一步的了解彼此，過程中你有什麼問題，可以隨時跟我溝通。
:baby:：好的。
:man:：假設我們要開發一個調查系統，調查的對象是同時使用新產品的某兩家客戶，我們希望客戶提供一些改善產品的意見，藉此來不斷更新產品，以達到敏捷式開發。
:man:：我們會列出 9 項修改需求供客戶做選擇，客戶可以選擇複數個需求，我們要依據客戶的需求去做改進。但由於我們希望盡快更新我們的產品，並推出下一個改良後的版本給客戶，好得到下一次的反饋，所以我們需要從中選出最少數量的需求，且必須滿足每個客戶至少一個需求，同時，盡量符合公司偏好執行的優先度，我們會給需求編號，數字越小的越優先。
:man:：我希望這個系統的輸入是 A 和 B 兩家客戶選擇的需求，輸出要能告訴我接下來要先完成的需求有哪些。可能有點難懂，我這邊舉幾個例子。
``` cpp
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]
```
:baby:：請問客戶會提出重複的需求? 比如說 A = [3, 3]。
:man:：不會，客戶不會提出重複的需求。
:baby:：請問如果客戶的需求為空的話呢? 因為他沒有需求，所以我沒辦法完成他的需求，那我要 output 什麼呢?
:man:：那我們再加一個限制，假定每個客戶至少都要提出一個需求，先不要讓這個問題太複雜。
``` cpp
Constraints:
1(最優先) <= A[i], B[i] <= 9(較不優先)
1 <= nums1.length, nums2.length <= 9
```
:baby:：還想請問 output 的順序有規定嗎? 我想再舉個例子... 像是這個例子，output 會是 [3,1] 還是 [1,3]?
``` cpp
=== Exaple 3. ===
Input: A = [4,5,3], B = [1,7]
Output: [3,1] or [1, 3]?
```
:man:：我們依據公司定義的優先順序排列好了，這個例子的 output 是 [1,3]。
:baby:：好的，由於這個問題的答案，需要完整看過 A, B 兩家客戶的需求才能決定，所以我需要兩個 for 迴圈來分別看過這些需求。 另外我還需要一個 hash table 來幫助我判斷兩家客戶是否有提出相同的需求。當有相同時，就輸出兩家都有相同的最小值，若皆不相同，就輸出兩家分別的最小值。
:man:：了解，那請你在 google document 實作一下吧。
```cpp
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)});
}
```
:baby:：因為最多只有 9 種需求，A 跟 B 的長度都小於 10，hash_table 也僅需要固定的長度 10，因此時間複雜度為跟空間複雜度皆為 $O(1)$。
:man:：Okay，那請你用剛剛的例子來跑一次程式。
:baby:：好的，...(略)
:man:：Okay，那我們現在再討論得廣泛一點，假設今天不只兩位客戶，有 N 位客戶，N $\geq$ 2，你會怎麼做呢?
:baby:：我一樣會使用一個 hash table，用來統計各個需求被客戶指定的次數，次數最多的需求，代表完成他就可以滿足最多的客戶，所以我們就挑選這個需求，接著再觀察剩下還沒被滿足的客戶，重複上面的步驟，直到所有客戶都被滿足。
:man:：那請你再 Google documents 實作一下吧！
```cpp
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;
}
```
:baby:：這個演算法的 while 迴圈最多只會執行 9 次，因為如果跑完 9 次，代表所有的需求都被挑選了。 每一次迴圈，所有的客戶最多只會被看過二次，分別在統計 hash table 跟刪除的客戶的步驟，因此總共時間複雜度是 $O(1)\times O(N) = O(N)$,空間複雜度是 $O(1)$ 因為只有一個固定大小的 hash table。
:man:：我覺得你的做法很值觀，蠻好理解的，但沒辦法完整解決這個問題，我舉個例子:
```cpp
=== Exaple 4. ===
Input: clients = [[2,1],[2,5],[3,1],[3,6],[4,1],[4,7]]
Output: [2,3,4]
```
:man:：在這個例子中，你的程式碼的 output 是 [1,2,3,4]，但其實正確答案卻是 [2,3,4]，你有什麼修改或更好的想法嗎?
:baby:：那我的演算法應該只能算是一個 Greedy 的演算法... 我現在有個想法，我覺得這個問題可以轉換成圖論的問題，我先把這個例子畫出來！
:baby:：圖中上排的 node 是需求的種類，下排的 node 是客戶的需求清單，客戶的清單會跟對應的需求相連。而我們要求的解，相當於在圖的上排 node 中，挑選最少數量的子集，讓所有的客戶至少與子集中的一個 node 相連。
:baby:：這讓我想到 Minimun Dominant Set 這個問題，這個問題是說，給定一個圖，存在一組 node 子集，使得圖中的每個 node 都在這個子集中，或者與這個子集中的某個 node 相鄰，則這個子集稱為 Dominant Set。如果這個子集是所有 Dominant Set 中最小的，則稱為 Minimun Dominant Set。
:baby:： 因為 Minimun Dominant Set 是個 NP-hard 的問題，與我們的問題非常相似，所以我認為我們的問題也是一個 NP-hard 的問題。
:man:：但在我們的例圖中可以發現，正解跟 Minimun Dominant Set 有一些差距，[2,3,4] 並沒有跟 [1,5~9] 相連，你有辦法證明嗎?
:baby:：我嘗試看看... 剛剛我們知道客戶需求問題，可以轉化成一張圖，接下來我要這張圖上做一些小小的改動，我希望讓客戶需求問題等同於求解 dominant set 問題。
:baby:：首先，我們在第一張圖可以發現，第二排要與 dominant set 相連，而第一排卻沒有，所以我想新增一個 head 去連接所有第一排的 node，為了要讓這個 head 一定會被選進集合裡面，我在第一排新增足夠數量的 node，迫使我們不得不選 head，這個足夠數量，可以設定成原圖所有 node 的數量。
:baby:：接下來，我們可以發現，這個問題變成了 dominant set 的問題，求解客戶需求問題，等同於求解 dominant set，所以客戶問題是個 NP-hard 的問題。
:man:：恩... 雖然你不是用很理論的證法，但是用例子來推，我能大致理解你的想法了，想法還不錯。
:man:：Ok，那我們今天的面試就到這裡吧。
### 初步檢討
* 邊寫程式邊講解的時間花太久了，要多練習
### 同儕檢討心得
* 挑選的同學
* [肥俠-Billy]((https://hackmd.io/@sysprog/BkdWsHpkT)) 他評 01
* [姆咪-MUMI](https://hackmd.io/@sysprog/HJmI6rpy6) 他評01
* [布撥-Pawmi](https://hackmd.io/@sysprog/S1ZLuL616) 他評02
* [牙塑-Wind](https://hackmd.io/@sysprog/r1JYgOakp) 他評02
* [追光者-Aegleseeker](https://hackmd.io/@sysprog/r1vSe_py6) 他評01
* 通常我給的建議分為以下幾種類型
* 針對優點
* 對 REACTO 的完整度給於讚賞
* 敬佩編寫程式邊講解的同學 (因為我第一次作業沒有做到，第二次作業有嘗試，但還做的不太好)
* 讚美表達或表演方面 (我自己還有待加強)
* 針對缺點
* 若缺少應用場景的設定，我會提出我自己想到的應用場景供參考
* 提出覺得邏輯上有問題的地方
* 提供覺得可以更優化的演算法版本
* 對 interviewer 跟 interviewee 如何更加有"討論、非上對下"的氛圍給予建議
Sign in with Wallet
Connect another wallet