游戲測試工程師面試題

　　1、返回兩個有序數(shù)組合并后的第K個的數(shù)。

　　思路：折半查找法

　　分別找兩個數(shù)組中的第K/2的位置的元素(假設(shè)數(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;

　　(假設(shè)下標從1開始)

　　A[2]=3，B[2]=4，A[2]<b[2]，那么a的前mid(mid=2)個元素可以不考慮(這里是說不考慮，并不是要刪除它)，因為他們必定比第5個數(shù)小< p="">

　　現(xiàn)在，

　　A={5,7,9}

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

　　接下來，就要在A、B中要找第(left=left-mid=5-2=3)個元素;

　　left=3，mid=3/2=1;

　　A[1]=5，B[1]=2，A[1]>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.< p="">

　　同樣，如果K=10，要找第10個元素，那么就將A[5]與B[5]進行比較，發(fā)現(xiàn)A[5]<b[5]，那么就不考慮a前面的5個元素，此時< p="">

　　A={}

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

　　left=5，

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

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

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

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

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

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

　　總結(jié)的一點心得就是，面試官并非總是引導(dǎo)你找到正確的方法，有時候也會誤導(dǎo)你，讓你的思維比較混亂，所以時刻要保持清醒的頭腦，思維要清晰，當(dāng)有些混亂的時候，就要從頭理一理，多動筆。我想面試也是一場博弈吧，希望下次好運!

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

　　思路：反向遞推法

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

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

　　依次類推，

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

　　最小是100%6=4個球，(100對6取余為4)

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

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

　　另外，還問了一個問題，面試官問我桌子上的那個裝抽紙的木盒子還能用來干什么，發(fā)動你的思維充分想象一下。這個問題見仁見智吧!主要看思維夠不夠活躍，夠不夠創(chuàng)新!

【游戲測試工程師面試題】相關(guān)文章：

網(wǎng)易游戲部門的面試題11-19

網(wǎng)絡(luò)工程師 最新面試題11-20

外企面試游戲測試大揭秘02-18

測試開發(fā)工程師筆試題09-25

軟件測試工程師職業(yè)規(guī)劃12-01

2011.10.29英偉達筆試（應(yīng)用工程師、測試工程師）11-21

面試題精選02-18

軟件工程師面試題小練帶參考答案12-21

分享面試題目 教育職業(yè)面試題11-20

剛剛收到電話面試了上海測試工程師11-20