Google Hash Code For Intern 解題分享

介紹

暑假我在 Google 實習的期間，Google 舉辦了一場名為 Hash Code For Intern 的比賽讓實習生參加。據說題面會跟某年 Hash Code 一樣，但測資會改。

Hash Code 和 Code Jam 非常不一樣，比較像 CAD Contest at ICCAD，題目是 NP 問題，雖然題面格式跟一般的演算法題目類似，但若要得到最佳解就必須要用 exponential time 的窮舉搜索。因此這樣的比賽通常會設計一個合理的計分公式來衡量我們給的解有多好，並以此來決定排名，有點類似像是 ML 類的比賽會用準確率之類的來決定排名。順道一提， Hash Code 或 CAD 的題目好像都不太適合用 ML 解決。

不同於 CAD，Hash Code 的測資會完全釋出給參賽者，總分通常是五筆測資的分數加總，而這五筆測資會各有特別的性質。參賽者完全可以針對每一筆測資去設計高針對性的演算法來獲得高分，應該說 Hash Code 本就非常鼓勵參賽者去分析測資的特性藉以設計特殊的演算法。也因為這樣，儘管 Hash Code For Intern 的題目會用舊題，只要測資重新針對不同的性質生出新的五筆，就還是能避免以前看過題目/題解的人有太大的優勢。(而且比賽前我們並不知道是和哪一年題面一樣)

不過 Hash Code For Intern 和 Hash Code 不太一樣的地方是，Hash Code 限時 4 個小時，而 Hash Code For Intern 則是有 24 小時可以作題。我覺得滿可能是因為各地的 Google 實習生都能參加 (例如歐洲)，考量公平性而決定的時間。我覺得既然這樣的話，Hash Code 也應該要辦 24 小時，不然對應台灣的時間是凌晨 2 點到 6 點，對於住在台灣的人太不利了。

比賽結果

比賽好像還滿少人參加的，除去只有報名沒有提交過答案的隊伍之後，就只剩 159 隊而已。雖然這是組隊報名的比賽，但我根本找不到隊友，幸好還是順利單人參加了。我的成績是第三名，運氣真的滿好的，也是因為我真的很喜歡這種 NP 最佳化的問題，所以整個比賽過程都很有熱忱的在想解法，出去買晚餐過馬路都在想，好像找回大二參加 CAD contest 時的熱情。

接下來會介紹題目跟我的作法，有興趣的話可以往下看哦~~

題目

Hash Code For Intern 的題面和 2017 年 Hash Code 的 Qualification round 的題面一樣，但我完全不清楚當年的測資跟這次的測資分別有什麼特質，因為我只來得及生出通用的解法，沒有多餘的時間針對各別的測資做研究跟優化。分析 data 真是一門很高深的學問呢，QQ

Data Center 資料中心

我們有一個資料中心，裡面有各式各樣的影片(至多10000個)，分別有不同的檔案大小

Cache Servers 快取伺服器

我們有一堆快取伺服器(至多1000個)，一開始通通是空的，並且有一個固定的容量

Endpoints 客戶端

我們有一堆客戶端(至多1000個)，客戶端可以從資料中心拿影片，也可以從和它有連接的任何快取伺服器拿影片。

• 每一個客戶端從資料中心拿影片的所需時間都不同
• 每一個客戶端都連接了某些快取伺服器，並且從每個快取伺服器獲取影片的所需時間也都不同 (但一定比資料中心快！)

Requests 請求

我們收到了一堆請求(至多1000000個)，每一個請求都闡述了「某個客戶端」要獲取「某部影片」總共「多少次」

我們要進行的操作

我們要做的事情是：「對於每一個快取伺服器，決定要放哪些影片進去」，每部影片都可以重複放在不同的伺服器裡，但每個快取伺服器所含的影片的檔案大小總和不能超過快取伺服器的容量限制。

一旦我們將某部影片放進某個快取伺服器後，有和該伺服器連線的客戶端就可以從這個伺服器拿影片了，因此如果該客戶端和該伺服器之間的傳輸時間很短，這個操作就能讓該客戶端大量減少拿這部影片的時間。

我們的目標就是根據所有請求 (request)，盡量減少每個請求中客戶端拿影片的時間。

計分

當我們決定好每一個快取伺服器要包含哪些影片之後，就可以計算我們總共省下了多少時間。

對於每一個請求(用戶端、影片、次數)，原本所需要花的時間就是該用戶端從資料中心拿影片的時間，乘以次數，稱為 $T$

假設我們的答案裡，某些伺服器擁有該影片，那麼現在所需要花的時間則是該用戶端從「有和它連線」且「傳輸給它所需時間最少」的伺服器拿影片的時間，乘以次數，稱為 $t$

因此，這個請求所被我們省下的時間就是$(T-t)$。把每一個請求被省下的時間加總，就是答案的分數了！

舉例

• 0號用戶端想看
  • 3號影片 1500次
  • 4號影片 500次
  • 1號影片 1000次
• 1號用戶端想看
  • 0號影片 1000次

我們用個表格來計算，如果通通沒有快取，都從資料中心拿的話，需要多少時間

因此總共所需時間是 3,500,000

而上圖的答案配置為

• 0號快取放：2號影片
• 1號快取放：1號影片、3號影片
• 2號快取放：0號影片、1號影片

我們用個表格來計算，透過最快的影片來源(快取或資料中心)，需要多少時間

這樣一來所需的時間會是 1,650,000

因此，在這筆測資上，這樣的答案配置所賺的分數是 $3,500,000-1,650,000=1,850,000$ 分

我的作法

我覺得要處理這種 NP 最佳化的問題，有兩個重點
1. 維護精密通達的資料結構，讓每個操作或計算都可以盡量壓低複雜度
2. 針對計分公式決定 Greedy 做法

以下為了書寫簡潔，我定義了一些符號和函數：

• $V_i$ 代表 $i$ 號影片，$C_j$ 代表 $j$ 號快取

• $V_iC_j$ 代表「把 $i$ 號影片放進 $j$ 號快取」的動作，例如「把 $2$ 號影片放進 $0$ 號快取」就寫作$V_2C_0$

• $S=[V_{i_1}C_{j_1}, V_{i_2}C_{j_2}, …,V_{i_n}C_{j_n}]$ 一連串的動作即集結為一組解$S$
  
  例如此圖代表的解即為$[V_2C_0, V_1C_1, V_3C_1, V_0C_2, V_1C_2]$，順序並不重要

• $score(S)$ 代表 $S$ 這組解的分數。如果 $S$ 不合法(例如某個快取超載了)的話，定義$score(S)=-\infty$
  注意，$score(S)$ 的值完全不受 $score(S)$ 裡的動作順序影響

Immediate Reward

我所使用的 Greedy 策略是不斷計算「將某影片放進某快取」這個動作有「多好」，並且從中選出「最好的」
而「動作多好」的定義是「可以把目前的分數增進多少分」，所以我把這個策略稱為「Immediate Reward」

用符號表示的話，以 $S_t$ 表示「目前已選的動作」，那麼新動作 $V_iC_j$ 的 Immediate Reward 則計算為

$R(S_t, V_iC_j)=score(S_t\cup V_iC_j)-score(S_t)$

要注意的是一個動作 $V_iC_j$ 可帶來的效益是受「已選動作」影響的。舉例來說

• 把$V_0$影片只放進$C_0$快取裡的分數是50
• 把$V_0$影片只放進$C_1$快取裡的分數是80
• 把$V_0$影片同時放進$C_0$和$C_1$裡的分數是100

那麼當$V_0$還沒放進任何快取時，$V_0C_0$所帶來的效益是$50$ (可能有許多客戶想從$C_0$獲取$V_0$！)
但如果$V_0$已經存在快取$C_1$了，那麼$V_0C_0$所帶來的效益就只有$20$了 (可能有許多客戶已經滿足於從 $C_1$ 拿影片了，只剩一些客戶會受益於從 $C_0$ 拿影片)

因此計算效益時要基於「目前已選$S$」，而我的 Greedy 策略就是基於$S_t$不斷選擇$R(S_t, V_iC_j)$值最大的$V_iC_j$，並將他併入$S_t$中，重複直到再也沒有$V_iC_j$值得選為止。

以下是這個 Greedy 演算法的 Pseudo code:

St 初始化為空集合 {}
WaitingList 初始化為所有「影片對快取」的組合 {ViCj | 0 ≤ i ≤ Nv, 0 ≤ j ≤ Nc}
重複迴圈: // 尋找最好的 VxCy
    對於每個 ViCj ∈ WaitingList，計算 R(St, ViCj) 
    若所有的 R(St, ViCj) 都不大於 0，則結束迴圈
    選出 R(St, ViCj) 最大的 VxCy
    St 更新為 St ∪ VxCy
    把 VxCy 移出 WaitingList
回傳 St 即為答案

演算法本身的觀念還滿簡單的，但如果沒有特別處理的話，複雜度其實大得滿崩潰的，因為每算一個 $R(S_t, V_iC_j)$ 時都要遍歷所有的 request、所有的快取、所有的影片等等。雖然程式運算時間不影響評分，但寫出跑得慢的程式還是令人煩惱，因此我有特別費心處理資料結構，例如維護每個 request 目前是從哪個 cache 拿影片最快、維護每個影片分別影響哪些 request 等等。這樣一來計算單一 $R(S_t, V_iC_j)$ 的時間就可以大幅減少。

Efficiency Improvement - Use Priority Queue

還有一個很棘手的問題是「對於每個 $V_iC_j \in WaitingList$ 都重新計算 $R(S_t, V_iC_j)$」太花時間，畢竟影片最多有一萬部，快取最多有一千個。不過因為每一輪我只在乎「哪個 $R(S_t,V_iC_j)$ 值最大」，所以我並沒有真的每次都把所有組合的 reward 值算出來，而是用 Priority queue 來維護每個 $V_iC_j$ 對應的 reward 值。

Priority Queue (PQ) 其實就是 Heap，就是個可以在 $O(logn)$ 時間取出最大值的 STL 容器。順道一提我實作所用的程式語言是 C++。
我會選擇使用 Priority Queue 來處理這個問題的原因有兩個：
1. 每一輪都只需知道「誰是最大值」
2. 對於所有的 $V_iC_j$ 而言，每經過一輪，它的 reward 值 $R(S_t, V_iC_j)$ 永遠都只會不變或遞減

由於我使用了 PQ 取代一般的二維陣列來儲存 $R(S_t, V_iC_j)$ ，並且只關注PQ.top，因此最需要擔心的是裡面的 $R(S_t, V_iC_j)$ 隨著 $S_t$ 的更新變得 outdated。然而因為 reward 遞減的性質，我完全可以只確認 PQ.top 是否 up-to-date 就好，如果 PQ.top 是 up-to-date 的，儘管其他在 PQ 裡的值是 outdated 的，我也能夠確定 PQ.top 就是我要的最大值。這樣一來，就可以大量省下重新計算所有 $R(S_t, V_iC_j)$ 的時間。

以下是這個 Greedy 演算法配上 PQ 的 Pseudo code:

St 初始化為空集合 {}
把所有「影片對快取」的組合 {ViCj | 0 ≤ i ≤ Nv, 0 ≤ j ≤ Nc} 放進 PQ
重複迴圈: // 尋找最好的 VxCy
    重複迴圈： // 尋找第一個 up-to-date 的 PQ.top
        從 PQ.top 拿出 VxCy
        重新計算 R(St, VxCy) 
        若新的 R(St, VxCy) 等於 PQ.top 的值，則帶著此 VxCy 離開此迴圈
        否則，將新的 R(St, VxCy) 放回PQ，繼續迴圈
    St 更新為 St ∪ VxCy
回傳 St 即為答案

至此，程式已經能跑得又快又好了，不過為了更高分我還加了一些修改。

Unit Reward

我的 Greedy 策略永遠是很貪心地選擇讓 Immediate reward 最大的 $V_iC_j$，完全不顧可能留下的爛攤子，像是拿到 size 太大的影片一下就把快取佔滿等等。

以這個例子來說，我的 Greedy 策略會選擇把 $V_0$ 放進快取裡，然後快取就放不下任何其他影片了。但更高分的做法是選擇 $V_1+V_2$。為了解決這個問題，我把原本的 Immediate reward 修正為 Unit reward，也就是將原本的 reward 除以影片的 size

$UR(S, V_xC_y)=\frac{R(S, V_xC_y)}{size(V_x)} = \frac{score(S \cup V_xC_y)-score(S)}{size(V_x)}$

注意儘管計算 reward 的函數改了，它仍然是個遞減的函數，所以仍然適用原本的 PQ 技法。改完這個 reward 函數後，分數果然又有了一波大躍進。

Randomness

最後是進入前五名後的掙扎XD，到這個時候距離比賽結束應該只剩幾個小時了。我的演算法仍有一個致命的缺點，那就是它是 deterministic 的，沒有任何機制去探索更好的可能性。為了打破這個缺點，我在演算法裡面加入了隨機的成分。

在剛才提到的 Greedy 演算法中，我每一輪都會選出擁有最大 reward 的 $V_xC_y$；而加了隨機成分後，在一定的機率之下，我會直接把這個 $V_xC_y$ 丟棄不用。我相信有時候放棄一些看似好的 $V_xC_y$，可以把快取的空間留給剩下一些不那麼好的 $V_iC_j$ 使用，並且達到更高的分數。

這時已經差不多是清晨，隔天還要上班，因此我把程式改成一直重複試隨機演算法，如果有得到更高分的答案就覆寫舊的答案，然後設定鬧鐘讓自己在結束前半小時醒來上傳最新的答案。不過其實這真的只是個掙扎的策略而已，分數只有提高一些而已，沒什麼大躍進了XD

結語

比賽結束後，因為拿到前三名而收到了在賽後活動向大家分享解法的邀請。除了分享解法之外，Hash Code Team 的員工們也來分享他們在這次比賽中設計了什麼樣性質的測資。我猜他們應該很期待聽到我們針對他們設計的測資來設計了什麼演算法，但我看大家好像都跟我一樣只有設計通用的演算法而已。我覺得主要因為是 24 小時真的太短了，分析 data 也不是個能隨便做做就有成果的事情(也許需要強力的隊友!?)。

我也很好奇 Hash Code Team 是個怎麼樣的團隊，如果有機會參與設計 Hash Code 題目應該滿有趣的，希望以後我有機會也能去一探究竟。