巨人网络游戏开发面经

巨人网络园区包住宿,对于我这个穷小伙还是很有吸引力的!对了他们两面的面试官应该一个是搞客户端,一个是服务端,而我碰到的一面估计是客户端,二面估计是服务端
巨人一面
1.设计一下内存管理器(上来第一个问题我就懵逼了,用链表把内存碎片连起来?不对链表这样一个个访问下去不是很慢。。。gg)

内存碎片的产生:

1.动态内存分配问题:

内存分配有静态分配和动态分配两种
静态分配在程序编译链接时分配的大小和使用寿命就已经确定,而应用上要求操作系统可以提供给进程运行时申请和释放任意大小内存的功能,这就是内存的动态分配。
因此动态分配将不可避免会产生内存碎片的问题,那么什么是内存碎片?内存碎片即“碎片的内存”描述一个系统中所有不可用的空闲内存,这些碎片之所以不能被使用,是因为负责动态分配内存的分配算法使得这些空闲的内存无法使用,这一问题的发生,原因在于这些空闲内存以小且不连续方式出现在不同的位置。因此这个问题的或大或小取决于内存管理算法的实现上。

为什么会产生这些小且不连续的空闲内存碎片呢?

实际上这些空闲内存碎片存在的方式有两种:a.内部碎片 b.外部碎片
内部碎片的产生:因为所有的内存分配必须起始于可被 4、8 或 16 整除(视处理器体系结构而定)的地址或者因为MMU的分页机制的限制,决定内存分配算法仅能把预定大小的内存块分配给客户。假设当某个客户请求一个 43 字节的内存块时,因为没有适合大小的内存,所以它可能会获得 44字节、48字节等稍大一点的字节,因此由所需大小四舍五入而产生的多余空间就叫内部碎片。
外部碎片的产生: 频繁的分配与回收物理页面会导致大量的、连续且小的页面块夹杂在已分配的页面中间,就会产生外部碎片假设有一块一共有100个单位的连续空闲内存空间,范围是0~99。如果你从中申请一块内存,如10个单位,那么申请出来的内存块就为0~9区间。这时候你继续申请一块内存,比如说5个单位大,第二块得到的内存块就应该为10~14区间。如果你把第一块内存块释放,然后再申请一块大于10个单位的内存块,比如说20个单位。因为刚被释放的内存块不能满足新的请求,所以只能从15开始分配出20个单位的内存块。现在整个内存空间的状态是0~9空闲,10~14被占用,15~24被占用,25~99空闲。其中0~9就是一个内存碎片了。如果10~14一直被占用,而以后申请的空间都大于10个单位,那么0~9就永远用不上了,变成外部碎片。

2.系统内存回收机制问题:

内存碎片是一个系统问题,反复的malloc和 free,而free后的内存又不能马上被系统回收利用。这个与系统对内存的回收机制有关。

内存碎片带来的问题: 大量的内存碎片会使系统缓慢,原因在于虚拟内存的使用会使内存与硬盘之间的数据交换称为系统缓慢的根源,最终造成内存的枯竭!

如何避免内存碎片的产生:

1>少用动态内存分配的函数(尽量使用栈空间)

2>分配内存和释放的内存尽量在同一个函数中

3>尽量一次性申请较大的内存2的指数次幂大小的内存空间,而不要反复申请小内存(少进行内存的分割)

4>使用内存池来减少使用堆内存引起的内存碎片

内存池管理:

Step1:重载new/delete运算符,接收到程序需要申请内存的大小。
Step2:编写内存池管理类,用于有针对性的管理内存分配。接收到程序需要申请内存的大小后,判断在哪个链中进行内存分配。(如果小于64字节,直接在第一个链进行内存分配;如果是65-128字节,在第二链进行内存分配)

内存池代码实现

1、内存块类
链式内存池的结点,维护了结点所需的信息和指向下一个结点的指针。

2、内存池类

一个内存池相当于一个链表,结点是内存块单元。内存池类维护了4个成员,MemoryBlock* _pHead; //内存块头部 size_t _nBlockSize; //内存块的大小 size_t _nSize; //内存块的数量 char* _pBuff; //内存池首地址
主要提供3个接口,内存分配:allocMemory(size_t nSize)、内存释放freeMem(void* pMem)、初始化内存池void initMemory()。

侯捷老师经常讲:学习C++程序设计要做到"心中自有丘壑",其实只要明白内存池是一个类似链表的结构,当需要分配内存时,分配一个内存块;当需要回收内存时,释放一片内存区域,并管理好内存块。

需要特别注意的是:上面的图中也表达出了,内存块由头部信息+内存空间组成,申请内存的人(程序员/用户)关心的不是内存块,而是他们想要申请的内存。因此,申请内存的人操作的是内存块 - 头部信息的部分,而内存池类维护的是整个内存块的单元。 比如说在分配内存函数中,void* allocMemory(size_t nSize),返回值是return ((char*)pReturn + sizeof(MemoryBlock));,返回给用户申请的内存空间是内存块的首地址向后偏移一个头部大小的位置。

内存池原理

内存池的思想是,在真正使用内存之前,预先申请分配一定数量、大小预设的内存块留作备用。当有新的内存需求时,就从内存池中分出一部分内存块,若内存块不够再继续申请新的内存,当内存释放后就回归到内存块留作后续的复用,使得内存使用效率得到提升,一般也不会产生不可控制的内存碎片。


2.知不知道反射(不知道唉。。。。又gg)
3.知不知道点乘和叉乘的区别(what?em。。。点乘就是数值相乘,不对,哦点乘是数值相乘再乘以cos,对,那叉乘呢,我讲成了向量相加。。。我也服了自己,不对,那我不知道了,叉
乘就是垂直向量方向啊,哦哦,我立马想到了电磁场的方向。。。毕竟通信的。。。 )
这个时候我觉得我可以回去了。。。
4.非递归讲一下前序遍历(吧啦吧啦)
5.redis怎么负载均衡(一致性hash吧啦吧啦)
6.地图上一个玩家一个npc(npc怎么判断是否看到了玩家,用点乘来整)
8.智能指针讲一下

巨人二面
1.多个客户端怎么同步(帧同步)
2.那客户端太多,怎么减小服务器的压力(别整什么集群负载均衡,人家问的不是这个,将地图画格子,然后格子内部做同步,这是做米哈游笔试的时候学来的哈哈,那格子边缘的玩家岂不是很奇怪,em,那按照玩家
来画格子,反正我就只会画格子,嗯接近了,还有吗,没了,可以按照玩家的视野范围来做同步,哦哦扇形做同步,其实还是要在圆形区域做同步,其实就是玩家视野为圆的最大半径)这里要感谢一下米哈游,虽然他们家连面试机会都不给我——米哈游喜欢985而本硕只是个211菜鸡硕士,但做他们家笔试还是学到一些东西的
3.redis怎么做持久化呀,分布式锁怎么设计呀,怎样把不常用的数据从缓存里淘汰掉呀(缓存数据分页?不常用的持久化到数据库?),不同的redis节点怎么做同步呀?
4.25个人5个跑道,找出前三名(最少用几次跑道跑几次),这不跑6次完事了吗?这有啥好说的?我也不太懂大佬们帮忙想想面试官到底想问啥

反问:游戏服务器和web服务器的区别(游戏服务器需要保存状态,web服务器只需要对访问做反馈就行,游戏服务器的实时性比较高)
巨人很有效率,2面技术+hr,从上午10点50***中午12点半就结束了,还给了我一张15块的饭票吃饭nice,就是太远了,在松江大学城那边。。。对了再感谢一下那个完事去面网易游戏的老哥,让我搭顺风车,谢谢!


#巨人网络##游戏研发工程师##面经##校招#
全部评论
7次
1 回复
分享
发布于 2019-09-20 17:48
赛跑那题明显是8次啊,25人每个赛道5个人跑一次就是5次,把每个赛道的第一名找出来跑一次就可以确定第一名,这就是6次,接着把第一名那个跑道的第二名拉出来和刚才的4个人跑,确定第二名,同理确定第三名,一共是5+3 = 8次
4 回复
分享
发布于 2020-08-31 15:37
百信银行
校招火热招聘中
官网直投
第一次分组跑不一定是第一就是最强的,有可能强的都被分到一队了。第一次分组只能淘汰后两名,剩下15个,然后再拿每组的第一名跑,这次跑的最后两名所在组全员淘汰淘汰,而第三名组后面的肯定也不能晋级,第二名组也可以淘汰一个,这时剩下六个,第一名稳坐第一,后面五个再跑一次排个名就行,所以答案是7
3 回复
分享
发布于 2022-08-02 14:29
好难呀.....
点赞 回复
分享
发布于 2020-03-27 08:58
。。。那题就是先跑5次,然后拉第一跑一次。最后貌似还有一次。
点赞 回复
分享
发布于 2020-03-27 09:01

相关推荐

新大陆软件 开发 转正薪资开到7500 base
点赞 评论 收藏
转发
15 117 评论
分享
牛客网
牛客企业服务