完美世界暑期实习一面(引擎岗)

本人目前大二，想做游戏，遂投了几家公司的暑期实习。然由于水平较低。mhy客户端笔试被刷，完美世界引擎岗笔试做的很烂，被捞进了面试。以下是本次线上面试面经，基本没准备，答得较烂，但面试官人非常nice，很多没答上来的问题都给了细致的讲解。

C++

涉及基本特性和实现原理

• malloc 和 new 的区别
• 为什么需要拷贝构造函数，为什么不直接赋值成员变量？
• 拷贝构造函数的参数

类对象的引用，传值会导致递归调用

• 为什么会递归调用，具体的过程

传值参数的时候，由形参到实参会调用拷贝构造函数(压栈)，从而无休止地递归调用导致栈溢出

• 函数覆盖的实现
• 如何找到当前对象对应的虚函数
• 函数重载的实现：哪些些函数能重载，不同返回值的同名函数为什么不能重载？
• C++中多态的实现
• 类的对象所占的空间：一个父类有纯虚函数，子类实现了虚函数，有一个int变量和一个bool变量

stl和算法

涉及一些算法的本质，比如复杂度的推导，算法的局限性等。

• vector中扩容的过程，push n次所需时间复杂度
• 归并排序 描述+时间复杂度推导
• 如果分成3部分进行归并，复杂度推导
• 快速排序 描述+时间复杂度推导
• 堆的作用

堆排序，维护可变集合的极值

图论

• 最短路径dijkstra时间复杂度
• dijkstra的限制，为什么不能求有负权边的图中最短路径

在dijkstra中，每次能取当前未探索点中距离最近的点进行探索的默认前提是，由于距离最近，则不会再更新，但负权边破坏了这种前提

• 用来求有负权图中最短路径的算法 Floyed，Bellman
• 最小生成树算法 Kruskal，Prim

算法题

• 滑动窗口
• 将原本的k个连续子数组的最大值改成>=k个连续子数组的最大值

前缀和