2022网易游戏测试工程师面试题-2023修改整理

千里之行，始于足下让知识带有温度。第第2页/共2页精品文档推荐2022网易游戏测试工程师面试题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[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]举行比较，发觉A[5]<B[5]，那么就不考虑A前面的5个元素，此时

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）个。

另外，还问了一个问题，面试官问我桌子上的那个装抽纸的木盒子还能用来干什么