网易互娱游戏研发2020实习面经（offer已到手）

笔试

笔试是在牛客做的，三道编程题。

顺子

第一题是给定一副手牌（A、2-10、J、Q、K，可重复），五张以上连续为顺子，最高连到K。问这副手牌有多少可能的顺子。（同样数字不同花色算不同的顺子）这道题我先卡在读入。输入有数字有字符，数字又有二位数。读char也不是读int也不是。最后只能cin.get逐位读然后空格与空格之间为读入的牌然后再做识别。读入之后就还算简单，各位自己思考吧。

编码转换

第二题是现有一个大整数，以字符串读入然后做转换。先将这个大数从低位开始每三位分一组，高位补0，然后转为二进制。转为二进制后每五位一组，同样高位补零。五位二进制可以表示范围是0-31，那么就将这些二进制数对应地转成0-9、A-V。然后输出。这个其实就是大数转32进制，中间的转二进制是迷惑人的。实现不难。

充电池

第三题是沙雕科学家搞发明，弄了n个不同容量的电池，然后用导线给电池充电。他只有一个功率输出口，接在特定一个电池上，然后其余电池都用单向导线连接，形成一个有向无环图。现在开始给电池充电，每个电池充满后才会向后方输出电能。输出电能会平均分到它屁股上的所有导线。如果一个电池充满了屁股上又没有导线，它接收到的电能就浪费了。问过多久才能充满所有电池。这个题我一开始以为很简单，实际写才发现很复杂。因为每个电池头顶可以接收多个导线，所以一个电池接收到的功率会多次变动。我大概有个思路，但最后时间不够就放弃了。

一面

笔试ac了两题应该还算是可以，所以过两天hr小姐姐就打给我约面试了。我还有点紧张，疯狂翻STL剖析。面试约的下午3点，我午饭后就坐着一边看书一边等电话。

自我介绍

面试一开始先是让我自我介绍。我说我叫【打码】，【打码】人，本科是【打码】大学软工，现在在【打码】大学读研。呃……还有什么别的需要了解的吗。对面就笑了笑说行。（感觉自我介绍应该还是稍微准备一下，但是应该介绍什么也拿捏不太准。表达一下自己对游戏的热爱？但又会不会太啰嗦？）

多态定义

然后对面问我主要是用什么语言，我说现在主要学C++。他就问你怎么理解多态？我说多态就是通过实现继承让程序可以在运行时决定被调用的方法是哪一个。虽然这个问题我上次面另外一家也被问过，但我还是没有准备这个答案，所以实际说得比较乱。不过还好听对面的语气他好像也还算满意，意思是表达出来了。他说你就举个例子吧。我就举例子说比如有个职员类，它有个发工资方法，现在再实现它的两个子类经理类和普通员工类，它们各自有不同的发工资方法。然后在程序执行时就可以用一个职员类的指针指向经理类或者普通员工类对象，然后用这个父类指针调用发工资就会触发动态绑定，调用到指向对象自己的方法。（虽然回答重点是突出多态的思想就行，但是事后想想要是举的例子是英雄类，子类是战士和法师，方法是攻击就更完美了。职员发工资太无聊了）

虚函数

再然后他就顺势问虚函数，问虚函数调用是怎么实现的。动态绑定发生时是怎么调用到子类的函数。多继承的子类有几个虚函数表。虚函数这个部分我看了应该不下十遍了。学C++应该都会仔细看过这个部分我就不详细说了。

STL容器

然后就是问C++的容器，STL的容器我有没有用过。当然实际上我没怎么用过，但是我全都看过，所以就说了几个vector、list、deque之类的。他就问vector和list有什么区别。向量和链表区别大了去了，一个是连续内存一个是链表。一个动态空间靠重分配一个本身就是离散的理论上没有空间限制。一个可以随机访问一个不行……等等等等，不详细列了。
他又问map用过吗，我说也用过。他map底层是怎么实现的？我说就是红黑树嘛。每个值是key-value对，然后他们按key值存在红黑树里。他就问红黑树定义，我凭印象大概给他说了一遍。说的时候我说红黑树不同于平衡二叉树，他就问那为什么有平衡二叉树了还要红黑树？红黑树有哪里好吗？我这里就卡住了，毕竟我没有思考过这个问题，我就凭想象说红黑维护代价应该比平衡二叉树简单一点吧。毕竟红黑再重新调整时只涉及单边子树，平衡涉及整棵树。这个因为是我临时诌出来的答案，我说的时候也没那么自信，他也反复追问“是指写程序的时候方便一些？”“你是说平衡效率更高？”最后我才整理出单边子树的说法。事后网上查了查，好像确实大概是这么回事，lucky。
红黑树结束后他又问了大小顶堆，问这是怎么实现的。我说说是堆实际上是个数组。第i个数的左子节点是2i+1，右是2i+2，每次插入新元素就从最后一个分支节点也就是n/2开始检查它和子节点的大小关系。这是我面试前专门看过的。他听了挺满意，然后问了个用大小顶堆做的问题。给定一个数组，求前n大的数。（这问题我研究生面试也被问过，当时我还不知道大顶堆……）我就很顺口，那就维护一个长度为10的大顶堆嘛。他说你确定是大顶堆？我还觉得奇怪，找最大不是大顶堆？然后他就要我详细讲，我说着说着才反应过来，哦应该是小顶堆……我改过来后他又详细问了一遍，我就详细说了实现过程。改了过来应该也算是可以……吧？

类型转换

接下来问C++有几种类型转换。静态动态const和重编译四种，这个定义到处都是，这里就不写了。

static

他又问static关键字是什么用。我说类里面就是静态成员函数，无论有几个类实例都只会有这一份拷贝。他说除了这个还有别的用处吗？我又说在方法里同样也是方法无论调用几次都只有这一份拷贝，而且只能在方法内被访问。他问还有吗？我想想说大概还能作为全局静态吧……记不太清了。（这个我确实没有认真记住，这部分答得也不算好。static具体用法请到别处搜索）

算法题

接下来一个算法题，给一个英语句子，每个单词用空格隔开，怎么将这些单词按倒转的顺序输出。
我第一反应当然是栈啊。用cin逐个单词读入压栈再逐个pop出来。他说这可以，但如果不能用额外的容器呢？
我想了想说那用一个临时的char数组，从后向前遍历将字符插到临时的char数组的头部，遍历到空格就输出临时数组并清空。他说那你这个临时数组要声明多大？如果我这个字符串有3个G呢？
不让用临时那就是本地转换咯。万幸还是让我想出个办法，先将整个字符串倒转，再逐个单词倒回来。他听上去不知道是否满意这个方案，不过也没有继续问下去了。

3d图形

C++他就问到这里了，接下来问我有没有接触过3d渲染，我说基本没有，他就跳过了。这个是我短板，没办法。

网络

再然后他问socket编程用过吗？我说我在本科用java写了个局域网棋牌游戏，那时候用过一点，之后没怎么用过了。他问那网络你了解吗？我说我就只大概看了TCP和UDP什么的。他就问那你说说二者区别。我就大概说TCP需要连接比较安全，UDP不需要连接，比较高效，发出去也不保证送达。一般聊天就是TCP游戏用UDP（我看文章看回来的，就顺口一说……）他一下就抓住了后半句，你确定游戏都用UDP吗？我说游戏数据交换量大嘛，用UDP更快速。他说那我玩推箱子，向前向左向前，向左指令发丢了会发生什么？我说那你就向前了两次，这就是玩游戏丢包嘛。他说那你觉得这可以吗？我说像推箱子这种数据量小的可以用TCP嘛，数据量实在大的才用UDP。他说那moba游戏呢？比如我的英雄放两个互相配合的技能，前一个技能丢包了，你觉得可以接受吗？我说不能接受，但游戏丢包没办法嘛，我玩英雄联盟就经历过丢包。他说那你想想办法改进一下。接下来就开始了我长达十分钟的痛苦的UDP改进之旅。我其实想说那要不用回TCP吧，但他一直说“既然你那么坚持UDP”，弄得我都不好意思回头了。不过这部分应该就是他引导我思考的一个过程，看我能拿出怎么个解决方案吧。不过网络编程我是真不熟，根据他的意思反复改了几次，他才放过了我。