- 相關推薦
游戲測試工程師面試題
1、返回兩個有序數組合并后的第K個的數。
思路：折半查找法
分別找兩個數組中的第K/2的位置的元素(假設數組中的元素下標從1開始)，然后進行比較，較小的則前K/2個元素可舍棄，不用考慮(因為他們必定比第K個數小)，接下來在剩余的元素中找第(K-K/2)個數，依次類推。如果某一個數組到頭了，就直接從另一個數組中取出指定的數。
舉例說明，
A={1,3,5,7,9}
B={2,4,6,8,10}
K=5，
首先令剩下需要找的元素個數為 left，初始化為left=5;
折半的位置mid=5/2=2;
(假設下標從1開始)
A[2]=3，B[2]=4，A[2]<b[2]，那么a的前mid(mid=2)個元素可以不考慮(這里是說不考慮，并不是要刪除它)，因為他們必定比第5個數小< p="">
現在，
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]進行比較，發現A[5]<b[5]，那么就不考慮a前面的5個元素，此時< p="">
A={}
B={2,4,6,8,10}
left=5，
那么就可以直接從B數組中提取第5個元素10，即，要找的元素就是10.
2、判斷帶頭結點的單鏈表中是否有環。
判斷一個單鏈表是否有環及環的鏈接點
主要思想：追趕法，采用兩個指針，快指針每次走兩步，慢指針每次走一步，當兩個指針相遇，就表示有環。
這里面試官提出了一個問題，為什么不是一個走4步，一個走3步。當時被繞進去了沒想明白，其實拿筆畫一下就明白了，
兩個指針一個走4步，一個走3步也可以，最終也能找到環，但是可能要走好幾圈兩個指針才能相遇。而采用一個走2步，一個走1步，快指針走一圈或一圈多一點(不到兩圈)就可以與慢指針相遇。
總結的一點心得就是，面試官并非總是引導你找到正確的方法，有時候也會誤導你，讓你的思維比較混亂，所以時刻要保持清醒的頭腦，思維要清晰，當有些混亂的時候，就要從頭理一理，多動筆。我想面試也是一場博弈吧，希望下次好運!
3、箱子里面有一百個球，甲和乙分別拿球，每次最少一個，最多5個，拿到第一百個球的人獲勝。若甲先拿，請問他第一次要拿幾個，怎么保證他能拿到第一百個球。
思路：反向遞推法
要拿到第100個球，必須保證拿到第94個球，
要保證拿到第94個球，必須保證拿到第88個球，
依次類推，
每次都要保證拿到第100-6*N個球，
最小是100%6=4個球，(100對6取余為4)
那么最開始要拿4個球。后來每次確保拿到的個數與乙拿的球的個數和為6.比如，乙拿1個，甲就拿5個;乙拿2個，甲就拿4個，依次類推。
總結一下，一般式：如果N個球，甲和乙分別拿球，每次最多拿K個，最少拿一個，甲先拿，要確保甲拿到最后一個球，那么，甲第一次就要拿(N%(K+1))個，后來每次確保與另一方拿的球的個數和為(K+1)個。
另外，還問了一個問題，面試官問我桌子上的那個裝抽紙的木盒子還能用來干什么，發動你的思維充分想象一下。這個問題見仁見智吧!主要看思維夠不夠活躍，夠不夠創新!
【游戲測試工程師面試題】相關文章：
網易游戲部門的面試題11-19
網絡工程師 最新面試題11-20
外企面試游戲測試大揭秘02-18
測試開發工程師筆試題09-25
軟件測試工程師職業規劃12-01
2011.10.29英偉達筆試（應用工程師、測試工程師）11-21
面試題精選02-18
軟件工程師面試題小練帶參考答案12-21
分享面試題目 教育職業面試題11-20
剛剛收到電話面試了上海測試工程師11-20