网易互娱 游戏研发实习 二面 部分复盘
---------------------------4/1日更新-------------------------------------------------------------
4/1日更新，增加了部分网络题目的复盘，关于游戏方面的知识过两天
-----------------------------原文------------------------------------------------------------------
二面全是场景题，被问到头皮发麻，求小伙伴们一起解答一下。
面试官人挺好，奈何自己有点菜。很多知识前一天恶补的，没吃透，比如四叉树。
1. 出现过，一个虚函数继承和函数指针转换的问题，但额外问了base和derive的内存空间，64位平台，8字节内存对齐。https://www.nowcoder.com/discuss/734061?type=post&order=recall&pos=&page=1&ncTraceId=&channel=-1&source_id=search_post_nctrack&gio_id=EB3C6A80002608A9F1FA4C98FE80F1BA-164****493204
复盘：没啥好讲的，只要了解虚函数继承后的内存（重点要明白，从类的虚指针到虚函数这是一个二级指针，作两次指针强转），以及typedef的一些知识应该就能明白。
2. 也在上面的出现过，1server，100client，单进程，如果一个client应用层不收数据(即不调用recv了)会发生什么，阻塞和非阻塞形式都讲讲。
我大概只想到一半的程度。client应用层不收，但server持续发送，会导致client缓冲区满，client缓冲区满后会告知server缓存空间为0。
然后server只能不断重试尝试向client发送探测报文，client也再次告知server没缓冲空间了。
后面面试官似乎想把我往server缓冲区满的方向引导，他提问一个client和100个client缓冲区有什么区别？是共用还是独立的？
我？？？？？后面实在分析不出来了...
复盘：可以看这个关于缓冲区的介绍的文章https://www.cnblogs.com/traditional/p/11806454.html
大致过程跟就是server不断发送数据，但client应用层不接收，将导致server发送缓存区满，server发送缓存区满后将根据io类型来决定如何处理。
如果是阻塞IO，则整个进程阻塞。如果是非阻塞IO，将返回错误码EAGAIN，此时虽然那个有问题的client不能发送了，但与其他client建立的socket是没问题的，有独立的发送缓冲区，因此不受影响。
3. epoll底层红黑树，效率很高对吧。但是我有个需求，将100M文件发送出去。但发送缓存有限，我肯定要进行分割出来分批次发送吧，那么一次发1K，每次发送都要通过epoll侦听缓存空间是否就绪，然后就绪后发出去，这变成轮询了不是吗，怎么改进呢（应该仍旧是单进程情况下，面试官还是想让我往缓冲区方向思考）。
我？？？？？？？？？？？这题真的不懂
复盘：（自己的想法不一定对）其实分析思路跟上面那个差不多，我们直接写大文件很可能会导致发送缓冲区满，因此需要不时的通过epoll侦听相应socket可写。我们可以以非阻塞的形式进行send，当写入时产生EAGAIN时，表明发送缓冲区已满，这个时候我们通过epoll out侦听socket是否可写，若可以，那么我们这个时候再去重试一下send，而不必每次发送1KB就去侦听一下。
4. 一个很大地图，很多人，给一个x,y位置点和技能半径r，如何在大量用户情况下找到你攻击半径下的用户列表。
我：可以用分区的方法，如100*100地图，我拆分成100个1*1区块，然后以r所在区块为中心做dfs/bfs，并以r作为深度进行搜索。
面试官：每个区块上面人的密度不一样，会产生很多无人的区块，你遍历空区块实际上做了无用功，对这类区块的存储怎么优化。
我：可以采用四叉树的方法，将地图分割，然后密度越大的区域划分出来的区块越多，密度较低的区域只需要用1个区块存储用户列表就可以了。
似乎没达到点子上，面试官还想问我如何对四叉树进行存储优化，奈何四叉树只是学了皮毛，不懂面试官想问啥...
复盘：还是不会...等过两天再看看。
5. 力扣hard题381（更正，有些区别，面试需求是随机删除，381是随机获取），如何实现一个key value存储，以O(1)复杂度提供插入，删除，查找和随机删除？https://leetcode-cn.com/problems/insert-delete-getrandom-o1-duplicates-allowed/
我：用一个vector<ListNode>模拟哈希表，能够以O(1)复杂度提供前三个功能，另启用一个数组vector keys存储相应的key，然后通过rand 一个keys中索引来实现随机删除。
面试官：但是你如果使用了一个额外的数组，如何在对哈希表进行维护时，同时删除数组中的key呢。
我：emmmm(一时半会没反应过来)
面试官：比如我们哈希表中存了key value是{{1,3}, {2, 4}}，你的数组里面存了{1,2}，这时候我删掉key = 2的哈希表，你肯定也要维护keys数组
我：（思考了大概一分钟）为哈希表的value添加一个迭代器，指向数组对象中的相应位置，从而一并删除。
面试官：不对吧，迭代器删除也要考虑后续迭代器失效问题
我：emmmm，那就指针吧，将数组keys中要删除的Key其和最后一个元素swap一下，然后pop_back()。
复盘：思路应该没问题，用一个冗余数组来记录键值，从而提供随机删除的功能；但增加冗余数组后，需要同时对哈希表中存储的value进行一些更改（如插入指针或者是索引），使得删除时能对数组进行更新。
面完后人有点蒙，反问的话问了面试官这场面试的评价，面试官不方便讲...
建议我去牛客上多刷刷面经。
然后问了游戏行业的现状...emmmmmmm这就不讲了
#网易互娱游戏研发工程师暑期实习面经##实习##面经##C/C++#
查看11道真题和解析
投递牛客等公司10个岗位 >