腾讯 IEG 后台开发面试

一面

其实前一天就接到了电话，问了一下 ACM 获奖情况，对游戏开发的了解，最后问了一个 interesting 的问题，「王者荣耀怎么实现同步」，因为之前了解过同步机制并且实现过一个状态同步，于是稍微讲了一下，然后当晚在外面吃饭于是说明天下午面试了。

面试官刚开始就直接说了，我这几年几乎都在打 ACM-ICPC 比赛，于是先面数据结构和算法了。

• STL 容器使用过吗，deque 了解吗，他支持在首位插入删除和随机访问，你考虑过怎么实现吗？

  我在竞赛中实现过，开一个特别大的数组，并且使用指针指向数组的中央，一个首指针一个尾指针，并且通过首指针加一个偏移量实现随机访问。

• 当储存空间不够时怎么办？

  使用类似于 vector 的方式进行扩容。

• 如果按你这种方式，如果一直插入到首部，后面的好多空间没有用到，有优化方式吗？

  写一个循环队列，例如当首指针达到边界时，让他移到尾部，这样就可以利用全部的存储空间。

• 考虑游戏服务器的高并发场景，假设这个容器我 push 了许多元素之后又 pop 了许多元素，怎么回收空闲的内存？

  因为直接申请一整块内存的话，不容易直接回收部分内存，可以考虑牺牲一部分效率，使用一种块状链表的结构去实现 deque。

• 那你考虑过可以不使用链表这种结构去实现这个功能吗？

  emmm 接下来的问题没有答上来。

• 考虑有一个定时器，他到达某个时刻的时候会执行某个 callback，假设我现在需要一个容器去储存这些定时器，并且一直要查询有没有定时器需要执行，你会使用什么样的数据结构？

  可以用一个小根堆，并且把时间当作 key 来排序，那么堆顶的元素就是时刻最早的，每次可以 $O(1)$ 的查询堆顶。或者使用二叉平衡树也可以实现这个功能，查询是 $O(\log n)$的。

• 讲一下堆和二叉平衡树的删除操作吧，假设我有一个指向堆 or 平衡二叉树的指针，怎么高效的删除这个节点？

  emmm，因为比赛很少遇到这种情况，我只好和面试官讲了下 Splay 这种数据结构…感觉回答的不是很好。

• sort 了解过吗，你们比赛中怎么使用 sort，关于他的 < 语义或者比较函数有什么要求吗？

  基本上就用 std::sort 了，如果要求稳定排序的话把下标当作第二关键字用就好咯。关于比较函数的要求，数学上是要求定义一个严格的弱序关系，我当时说的是两个条件，可传递，并且非对称，a < b and b < c then a < c, a < b 和 b < a 有且只有一个条件成立。

• map 使用过吗，unordered_map 和 map 有什么区别？

  map 使用红黑树来实现的，我只了解过各种接口的复杂度，不清楚内部实现。unorder_map 使用哈希表来实现。

• 你可以自己实现一个 unordered_map 吗，讲一下怎么实现？

  最简单的一种实现就是开一个桶，然后用桶的大小对 hash 后的 value 取模，然后放入桶里面。

• 如果有 hash 碰撞怎么解决？

  开一张链表。

• 如果 hash 碰撞太高了怎么优化？

  可以从两方面入手，一个是 hash 函数本身的优化要做好。另外一点面试官提示了我一下，其实就是鸽巢定理，10 个抽屉放 11 个球，那么至少有一个抽屉有两个及以上的球。当我放入 100 个元素到 大小为 10 的 hash 表中，那么是很容易 hash 碰撞的。这时候我考虑了用之前的方法，对桶进行扩容，这里继续沿用 vector 的方式就 ok 了。

• 你了解过多线程吗，怎么实现一个线程安全的 hash 表？

  我了解过互斥锁，可以考虑给每个元素加一个互斥锁。

• 那我插入时，需要修改一个链表的结构，发生了冲突怎么办？

  给每个链表加一个互斥锁…

• 那我插入的时候，hash 表需要扩容怎么办？

  增加一个变量，用来标志当前是否正在扩容，如果扩容就让所有的插入查询操作阻塞。

• 这样扩容会阻塞掉所有的访问，有更好的做法吗？

  可以将扩容的锁放到每个链表上，然后这样扩容时只阻塞掉正在移动的元素。

• 好的接下来做一个编程题吧，逆转一个字符串？

  水题…

• 逆转单词？ hello world -> world hello

  水题，面试官要看如何分割字符串，于是简单的写了一下，被吐槽代码不规范了 orz。

• 加权随机数？给定一个权重表 [2, 1, 3, 5, 4]，编写一个输入函数 rand_select(weight[])，返回一个 1 - len(weight) 的整数，这个数是随机的，并且保证出现 0, 1, 2 ,3 ,4 , 5 的概率之比为 2, 1, 3, 5, 4。

  写了两个做法，思路都是把权重当作一个区间，然后根据权重区间长度不同，random 从总区间长度中选一个数，落到那个区间中，就把那个区间的编号当作随机的答案。

• 你有什么问题问我吗？

  • 假设我能实习的话，我能学到什么内容，在后台开发岗位的话？
  • 我的表现怎么样，有什么不足的地方？
  • 有什么开源项目推荐吗，或者好数推荐？

二面

感觉二面回答的不是很 OK，感觉凉凉的，但是官网上没给挂。

整体面试官问的问题比一面的多，并且贴近底层和基础，节奏也比较快，最后自己被问的有点懵，后面也没问面试官什么问题就结束了。

• vector 怎么实现？

  动态申请内存，然后倍增扩容。

• 考虑过怎么收缩空间吗？

  提供一个接口函数，重新分配一块恰好的空间。

• 如何使用这个 vector 储存不同大小的数据？

  vector 不直接储存数据，储存指针。

• 怎么用你实现的 vector 实现一个 queue ?

  queue 不用随机访问，我感觉使用链表来实现比较好，使用两个首尾指针。

• sort 算法了解过吗，std::sort 怎么实现的？

  因为 quick sort 是平均复杂度比较好，最差情况能退化到 $O(n^2)​$，具体 STL 源码我没有看过，了解过他使用多种排序结合的方式，比如对于大区间使用什么排序，小区间怎么排序，并且进行随机化，避免最差情况。

• C++ 了解吗，我在两个文件中定义了两个完全相同的函数有没有错？

  编译不会报错，当链接的时候会发生 redefine 错误。

• 怎么避免这个错误？

  使用命名空间或者 static 关键字。

• 模板了解过吗？

  了解过，但没怎么写过代码（然后面试官不继续问了…其实我想让他问一些的）。

• extern 关键字了解过吗？

  可以引用其他文件的变量，具体没怎么用过，竞赛一直写的单文件。（然后面试官不问 C++ 了 orz）

• 操作系统熟悉吗？

  熟悉，最近刚看完 CSAPP 感觉收获很多。

• 解释一下程序如何执行的吧，从命令行输入可执行文件开始。

  首先操作系统分配好程序运行的上下文环境，例如虚拟内存、页表、CPU 寄存器、堆栈等，将文件映射到内存中，然后处理器找到程序的入口地址，并且运行，通常刚开始执行第一行代码时发生缺页中断，然后 CPU 将硬盘中数据载入主存中。

• 可执行文件格式了解过吗？

  了解过 Unix 系统的 ELF 文件格式，影响比较深的有可重定向目标文件和可执行目标文件，通常编译后生成可重定向目标文件，链接后生成可执行文件。这两类文件大同小异，内部通常分为许多个段，主要有符号表，程序代码，全局变量等。对于可重定向目标文件，还会有一些需要重定向的变量、代码段。

• 解释一下链接过程吧？

  我认为链接过程就是将许多可重定向文件或静态库文件合并成一个可执行文件的过程，会把各个文件的代码、全局变量等数据段合并到一起。链接过程中会依次扫描每个文件，并且为引用但为定义的代码定位地址。

• 下面问你一个开放性问题，考虑有 100 个 10 万人的服务器，如何维护一个实时的全服排名？

  首先肯定要考虑并行，不能单线程处理所有服务器的访问的。这样我们根据排名划分成不同的数据段，用不同的服务器来维护，并且设置一个容易并行的代理服务器转发请求到下级储存数据的服务器。考虑到并发的话可以继续让服务器分级，直到划分为一个可以接受的程度。

• 假设有一个人反复改变自己的排名，考虑如何优化？

  这个好难啊…（然后面试官直接不问了…感觉应该随便说一下比较好的）

• 下面问个算法题，给 1000 万个手机号排序？

  直接基数排序吧，手机号 11 位的话时间复杂度就是 $O(11 \times 1000)$ 咯。或者插入到字典树中，然后遍历一遍也 ok。

• 好的我没有其他问题问你了，那….

  直接被问的自闭了，这里抢答了，“那，再见”。然后面试官就说了下再见就结束了。（感觉他可能是要说 “那你有什么问题问我吗”）

三面

隔了两周才接到了电话，面试官说大概只用二十分钟就 ok，然后就直接开始面试了。

• 你为什么参加 ACM 竞赛?

  一是为了可以和别的学校更更强的人同台竞技，二是本身就喜欢算法和数据结构。

• 你认为 ACM 竞赛中那些可以应用到工程中？

  应该是经典的数据结构和算法吧，对于一个工程的需求，我可以考虑用哪种算法和数据结构，可以实现怎样的时间复杂度和空间复杂度。

• 你学校课程中比较喜欢那几个?

  操作系统和计算机网络。

• 你认为编译原理中的知识对你有用吗？

  我认为我最受用的知识是状态机，在竞赛中就用到了 AC 自动机，SAM 等字符串自动机。另外工程中，服务器 IO 复用可以建立状态机的模型进行编程。

• 你讲一下从客户端发送一个 TCP 包到 服务器吧。

  首先先给需要发送的数据加上 TCP 首部，其中包含端口号、序列号等信息；然后将 TCP 包递交给网络层，网络层会加入 IP 首部，其中包括 IP 地址、校验和等信息；然后通过数据链路层发送出去。

  服务器收到数据包后递交给网络层，网络层拆掉 IP 首部，并且进行简单的校验，并且递交给传输层；传输层收到后拆掉 TCP 首部，并且验证数据包的是否正确（损坏、失序等），验证通过后讲数据包递交给对应端口号的程序。

• 子网掩码和网关了解吗？

  解释了一下子网掩码，因为之前都在看运输层，

• 那聊一下操作系统吧，介绍一下进程和线程吧？

  进程是操作系统进行分配资源的基本单位，线程是 CPU 调度的基本单位。（面试官问了一下用户态线程了解吗…直接没听说过）

  然后聊了下虚拟内存，进程间通信和线程通信。

• 总结

  面试官就直接说你基础不怎么好，如果我这过了的话，下一次就是 HR 面了。如果来实习的话一定要多看看基础知识，Unix 网络编程和 Unix 环境高级编程不错你可以看一下。剩下如果来的话需要补很多基础知识很费时间。

  这两本书正好前几天刚买，面试官说的东西正好是最近刚看的，如果能有实习的话，就安心啃书了。

HR 面

• 自我介绍一下。
• 为什么参加 ACM 竞赛？
• 参加比赛的时候怎么学习？
• 印象最深的比赛？
• 聊聊你的项目。
• 为什么选择我们事业群？
• 喜欢游戏吗？
• 个人状况 balbalbala…
• 你有什么问题问我吗？
  • 我的岗位大概是什么事业群？