2022網(wǎng)易游戲測試工程師面試題-2023修改整理

千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦2022網(wǎng)易游戲測試工程師面試題1、返回兩個有序數(shù)組合并后的第K個的數(shù)。

思路：折半查找法

分離找兩個數(shù)組中的第K/2的位置的元素（假設數(shù)組中的元素下標從1開頭），然后舉行比較，較小的則前K/2個元素可舍棄，不用考慮（由于他們必然比第K個數(shù)?。?，接下來在剩余的元素中找第（K-K/2）個數(shù)，依次類推。假如某一個數(shù)組到頭了，就直接從另一個數(shù)組中取出指定的數(shù)。

舉例說明，

A={1,3,5,7,9}

B={2,4,6,8,10}

K=5，

首先令剩下需要找的元素個數(shù)為left，初始化為left=5；

折半的位置mid=5/2=2;

(假設下標從1開頭)

A[2]=3，B[2]=4，A[2]B[1]，那么B的前mid(mid=1)個元素可以不考慮，那么，

A={5,7,9}

B={4,6,8,10}

接下來，就要在A、B中要找第（left=left-mid=3-1=2）個元素;

left=2，mid=2/2=1；

A[1]=5，B[1]=4，A[1]>B[1]，那么B的前mid(mid=1)個元素可以不考慮，那么，

A={5,7,9}

B={6,8,10}

接下來，就要在A、B中要找第（left=left-mid=2-1=1）個元素;

找第1個元素很容易，只要比較A,B的第一個元素就可以了，哪個小就是哪個。

A[1]=5，B[1]=6，A[1]<B[1]，所以要找的元素就是5.

同樣，假如K=10，要找第10個元素，那么就將A[5]與B[5]舉行比較，發(fā)覺A[5]<B[5]，那么就不考慮A前面的5個元素，此時

A={}

B={2,4,6,8,10}

left=5，

那么就可以直接從B數(shù)組中提取第5個元素10，即，要找的元素就是10.

2、推斷帶頭結點的單鏈表中是否有環(huán)。

推斷一個單鏈表是否有環(huán)及環(huán)的鏈接點

主要思想：追逐法，采納兩個指針，快指針每次走兩步，慢指針每次走一步，當兩個指針相遇，就表示有環(huán)。

這里面試官提出了一個問題，為什么不是一個走4步，一個走3步。當初被繞進去了沒想明了，其實拿筆畫一下就明了了，

兩個指針一個走4步，一個走3步也可以，終于也能找到環(huán)，但是可能要走好幾圈兩個指針才干相遇。而采納一個走2步，一個走1步，快指針走一圈或一圈多一點（不到兩圈）就可以與慢指針相遇。

總結的一點心得就是，面試官并非總是引導你找到正確的辦法，有時候也會誤導你，讓你的思維比較混亂，所以時刻要保持蘇醒的頭腦，思維要清楚，當有些混亂的時候，就要從頭理一理，多動筆。我想面試也是一場博弈吧，希翼下次好運！

3、箱子里面有一百個球，甲和乙分離拿球，每次最少一個，最多5個，拿到第一百個球的人獲勝。若甲先拿，請問他第一次要拿幾個，怎么保證他能拿到第一百個球。

思路：反向遞推法

要拿到第100個球，必需保證拿到第94個球，

要保證拿到第94個球，必需保證拿到第88個球，

依次類推，

每次都要保證拿到第100-6*N個球，

最小是100%6=4個球，（100對6取余為4）

那么最開頭要拿4個球。后來每次確保拿到的個數(shù)與乙拿的球的個數(shù)和為6.比如，乙拿1個，甲就拿5個；乙拿2個，甲就拿4個，依次類推。

總結一下，普通式：假如N個球，甲和乙分離拿球，每次最多拿K個，最少拿一個，甲先拿，要確保甲拿到最后一個球，那么，甲第一次就要拿（N%（K+1））個，后來每次確保與另一方拿的球的個數(shù)和為（K+1）個。

另外，還問了一個問題，面試官問我桌子上的那個裝抽紙的木盒子還能用來干什么