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