【腾讯】C++岗-IEG部门（两轮技术+一轮HR）
前些天完成了腾讯互娱的面试，时间大概一周左右，不得不说腾讯的效率还是挺高的，不过面试流程有
些诡异。
楼主之前内推的WXG，结果一面GG，正式实习招聘被IEG捞了起来，前两轮都是深圳的电话面试，HR
面在武汉现场。岗位是后台开发。
总的来讲，面试体验还是非常好的，面试官水准很高。
一面：
一面直接从做的东西开始聊，中间穿插着问了很多C++内容，计算机网络一点没问（我提到自己没有写
过后台的东西），算法没问。
Q：你的这个游戏，自己做的核心内容是什么。
A：我自己实现了怪物AI的有限状态机，后面又使用行为树进行了重写，寻路算法部分，我这一块用的
是自己写的A*算法。
Q：A*算法是自己写的对吧，具体怎么实现的。
A：我使用哈希表作为地图的基本结构，openlist和closelist都采用的这种数据结构，启发式部分，使用
的是最简单的曼哈顿距离作为启发式第二项的值，第一项的值就是根据parent结点进行更新的距离起点
的值。
Q：有没有比较过自己的实现和其它实现，具体的区别在哪里。
A：这个有比较过，我感觉最大的区别之处就在于两个点的处理，第一个点，openlist的插入，我的实
现是哈希表，所以插入是O（1）的，对方维护的openlist是一个有序数组，插入二分查找，是O
（logN)（这里实际上答错了，后面追问的时候更正了），第二个点，找出openlist里启发式值最小的结
点，我的方法需要遍历所有点，因此是O（N），而对方因为是有序数组，只需要取第一个结点就可以
了，因此是O（1）。
Q：如果维护的是一个有序数组的话，那插入一定会有数组部分的后移，还会是O（logN）吗？如果取
第一个结点，那么删除之后，也会有移动。（这里面试官真的非常好，点出你的错误，让你有挽回空
间）
A：我上面的答案有错误，数组也可以是一个最小堆，对方的写法应该是最小堆，插入是O（logN），
删除也是O（logN）。
Q：嗯，如果是最小堆，那两种方法的效率对比？
A：这个要看具体的情况，需要实验性的评估，因为不能够确认两者的具体时间消耗对比。
Q：最小堆的话，删除是怎么做的？
A：删除最小堆顶的元素后，把堆末尾的元素放到堆顶，与其余两个元素比较，进行下沉操作，因此复
杂度是O（logN）。
Q: C++的两种map？
A：unordered_map和map。前者是哈希表实现，后者是红黑树。
Q：红黑树的性质？
A：5个性质
Q：红黑树和AVL树相比呢，优势在哪里？
A：两者都是特殊的BST，相比AVL，红黑树不要求严格的1的高度差，对于插入操作，两个树类似，最
多旋转两次，对于删除，红黑树最多旋转3次，而AVL树则是O（logN）。
Q：那红黑树的高度差最多？
A:2.(这个问题其实很简单，但自己蠢了，半天没答上来，原因就是高度两倍的性质，因此高度差最多、
2）
Q：问一些C++的内容。sizeof空类的值？
A：不包含虚函数就是1，包含虚函数4或8（虚表指针，32位4，64位8）。
Q：C++多态？
A：这个问题已经重了，答到虚函数表就OK。
Q：多重继承下的内存结构？
A：简单来讲，多重继承的子类本身会有多个虚表指针，分别指向多个不同父类的虚表。如果有新的虚
函数定义，则会在第一个虚表的末尾增加新的函数地址。（这里庆幸没问菱形继承，这个是真的不
懂）。
Q；C++ 11的新特性了解吗，讲一些。
A：最常用的是自动类型推导，其实跟模板类型推导类似，右值引用，lambda表达式，智能指针等。
Q：讲讲智能指针吧。
A：三种智能指针， shared，unique，weak
Q：shared的原理？
A：shared维护了一个指向control block的指针，control block内部包含了智能指针对象的引用个数。
Q：避免死锁？
A： weak
Q：weak_ptr原理？
A：weak count, weak count是弱引用的个数，弱引用个数不影响shared count和对象本身，
sharedcount为0时则直接销毁。
Q：如何判断weak_ptr的对象是否失效？
A：我个人认为应该使用的函数是lock()，lock会返回shared指针，判断该指针是否为空。use_count()
也可以得到shared引用的个数，但是速度较慢。
Q：shared和unique区别？
A：unique具有唯一性，对指向的对象只存在唯一的unique_ptr. unique_ptr不可复制，赋值，局部变
量的返回值除外。与shared_ptr相比，若自定义删除器，需要在声明处指定删除器类型，而shared不需
要，shared自定义删除器只需要指定删除器对象即可，在赋值时，可以随意赋值，删除器对象也会被赋
值给新对象。
Q：原因是什么？
A：unique的实现中，删除器对象是作为unique_ptr的一部分，而shared_ptr，删除器对象保存在
control block中。
C++的部分大概就问到这里了，接下来15分钟就是问研究的东西。之后的一个没答好的问题，面试官
问，多线程和多进程比，为什么消耗更小，假设他们的调度策略类似。
A：这个问题真的没答好，当时的回答是，线程切换时，需要保存的信息更少，而进程切换时，换页过
程，重新从磁盘将进程换入内存的过程都很耗时，进程间的通信也更加复杂。
最后面试官的意思是，要多准备一些关于并发的内容，如果从事后台的话。
二面：
二面非常短，大概15分钟结束，面试官应该是项目总监，没有问具体问题，就是简单问了下项目，然后
具体探讨了要做什么的问题，因为我自己的想法是从事C++相关的开发，然而并没有后台经验，可能面
试官对于这一点还是有疑虑，最后说的是可以先过来写后台，如果不合适再转到前端。（大概了解到是
用Unity，我个人不喜欢这个引擎）
HR面：
一些常见的问题，遇到的最大挫折之类，对游戏沉迷的看法，玩过哪些游戏，怎么看待腾讯游戏的负面
等等。最后问到offer情况，我提到已经拒了蚂蚁，手上有网易互娱，之后的问题就是比较一下这俩公
司。然后大概的后续就是说腾讯的企业文化更加开放包容之类，希望能够来腾讯实习。