游戲測試工程師面試題

時間：2024-08-14 04:54:02 面試筆試我要投稿

相關推薦

游戲測試工程師面試題

　　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)個。

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

【游戲測試工程師面試題】相關文章：

2011.10.29英偉達筆試（應用工程師、測試工程師）11-21

面試題精選02-18

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

分享面試題目教育職業面試題11-20

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