天天看點

網易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叉搜尋樹之類的……但這種進階資料結構我了解的特别少,于是隻能勉勉強強說思路說到這裡為止。

小題:快排的原理

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

作業系統

一如既往地不會。

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

網絡

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

其他

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

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

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

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

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

繼續閱讀