網易2021暑期實習 遊戲開發 一面

筆試是在5月6日晚間完成的，試卷标題上寫着“零散批”，估計是因為投遞履歷太晚了。

筆試情況前文已經說過，3題我做出來倆。11日收到預約面試通知，讓我選擇一個時間進行面試。網易的面試預約流程是我感覺最好的，首先是可供選擇的時間比較多，有4個，分别是12日和13日這兩天的上午9:30和10:30；其次是操作比較簡單，去官網選一個時間就行，别家的面試都是打電話/發郵件，用自然語言溝通。

面試流程也如同預先通知的那樣，是半小時代碼+一小時交流。

算法

一共出了3個算法題。

題目1：數組最大距離

這是一開始那半小時的代碼題。

定義兩個數組A, B之間的距離是 max ⁡ { ∣ a − b ∣ ∣ a ∈ A , b ∈ B } \max\{ |a-b|| a\in A, b\in B\} max{∣a−b∣∣a∈A,b∈B}，即兩數組裡各挑選一個元素，內插補點的絕對值的最大值。

實作一個函數，輸入m個已經按升序排好的數組，輸出它們之間的距離的最大值。

這題看起來是出乎意料的簡單，隻要把最大的和最小的都找出來就可以了吧。而且順序已經都排好了，找到他倆隻需要 O ( m ) O(m) O(m)的時間周遊一遍所有數組的首尾元素。

然後我發現沒有處理一個特殊情況，就是最大和最小元素在同一個數組裡。于是我引入了次大和次小元素。由于最終使用的最大值不可能是某個數組裡的次大值（肯定不如用最大值好），小的方面同理，是以這裡的次大/次小指的是所有數組的最大/小值裡的次大/小值。

很快我就寫完了，半小時還剩下大概15分鐘。我看來看去，想不出可以改正的地方，面試官也還沒發起語音通話，于是剩下的時間就磨蹭過去了。

後面面試官問我思路，我就如實告知。

題目2：等機率随機排列

輸入一個數組，輸出它的一個随機排列。要求該數組的所有排列能等機率地出現。

我一看是大喜過望，因為幾個月之前看《算法導論》的時候，開頭就講到這個問題，并且講到高德納提出的一種非常高效的算法：洗牌算法。這算法過于巧妙，以至于我後來又看了好幾次，一直記到今天。

于是我很快寫了大概的代碼：

void RandomShuffle(vector<int>& m){
	int n = m.size();
	for(int i=0; i<n; i++){
		int j=rand(i, n);
		swap(i, j);
	}
	return;
}
           

實際上很有瑕疵，比如我不知道在{i, i+1, ……, n-1}裡取一個随機數具體應該怎麼寫，比如我

swap

的參數錯了……

不過面試官沒有糾結這些細節，而是讓我用數學的方法證明這樣是對的。

我當初看這個算法的證明看了不少次，印象還算深刻。分情況一讨論，很快就說明了每個數字出現在每個位置的機率都是 1 / n 1/n 1/n。

我突然又想到，即使每個數字出現在每個位置的機率都是 1 / n 1/n 1/n，結果也未必會等機率地輸出所有排列。

比如，一個算法把所有元素都往後移動随機位數，越界的就循環地補到前面，這樣也能滿足上面說的機率條件，但能輸出的排列隻有 n n n個。《算法導論》書上有這道習題，我看到解答時驚訝不已，于是明白了應該嚴格證明所有排列都可能等機率地輸出。

但面試官并沒有繼續追問，我也隻是想到了證明的不足，并沒有想到怎麼完善……就沒再多嘴）

題目3：設計定時器

實作兩個函數：

void RegisterFunc(int time, void* Function);

該函數輸入一個絕對時間和一個函數指針，功能是将一個函數注冊進定時器。

void UpdateTimer(int time);

該函數輸入目前的時間，功能是觸發定時器，将所有已經注冊進定時器的、對應的絕對時間小于目前時間的函數拿出來調用。如果有多個函數被找到，則按時間順序調用它們。

實作基本功能後，考慮兩種極端情況：

RegisterFunc

被頻繁調用；

UpdateTimer

被頻繁調用。

具體怎麼調用的細節應該是不重要的，最主要的是如何降低兩種操作的時間複雜度。那麼核心的問題就是如何設計定時器的資料結構，使得每次注冊和每次觸發都能很快完成。

我首先想到的是隊列，因為已經注冊的任務是按照時間順序排程的，和隊列的性質差不多。

隊列的缺點也很明顯：要實作在中間插入而非尾部插入，我隻能想到用連結清單，那麼每次插入都可能要 O ( n ) O(n) O(n)的時間；每次觸發也要從前往後周遊，時間也可能要 O ( n ) O(n) O(n)。

那麼能不能在連結清單之外多一些指針，指向連結清單中某些節點，每兩個指針之間都有固定的時間間隔呢？這恐怕還是同樣級别的時間複雜度，隻是常數項會随着額外指針的密度增加而降低。

如果要降低時間複雜度的級别，似乎要給這些額外指針之外再增加指針，一層層不斷地加，一直加到隻有一個為止。我隐隐感覺，這對應某種樹的結構，像是n叉搜尋樹之類的……但這種進階資料結構我了解的特别少，于是隻能勉勉強強說思路說到這裡為止。

小題：快排的原理

這也是老題目了，沒什麼好重複的。無非是說說快排的過程，最壞情況，如何避免，中間元素的選擇方法……之類的罷了。

作業系統

一如既往地不會。

但這次面試官甚至沒有提問，而是讓我知道啥就說啥……我就說了堆和棧的差別和這種差別的意義之類的比較基礎的内容。

網絡

又是經典題目：三次握手，四次揮手。我雖然沒學過計網，但這題我都快背爛了，因為問的實在是太多了……

其他

讓我介紹一下自己最熟悉的項目，問了一下其中的細節。這基本也是每次面試都會問到的題目，我也越答越熟練了。

不過這次面試官借題發揮。他問我，如果你的應用要同時給成千上萬使用者推送的話，伺服器容易當機，有什麼辦法解決嗎？我一時語塞，實在沒轍，勉強說了個“把使用者分類”的方法。

關于遊戲：面試官并沒有提問太多，隻是知道我喜歡玩爐石，說了一句“爐石是需要很多計算的”。我立即有很多話想滔滔不絕地說出來，比如爐石在技術和運氣之間做到很好的平衡啦，爐石給硬核玩家準備的特殊環節啦……但我說到一半，感覺他似乎不太想聽，隻是想随便提一下而已……于是就住口了。

我對爐石的架構有這麼多了解，也許我應該去試試遊戲策劃的職位，而非開發工程師。

初次之外，幾乎沒有關于遊戲的問題。我還有很多關于遊戲的優缺點的頭頭是道的分析沒說出來呢。