腾讯WXG日常实习一面（63min）

不得不说腾讯的面试质量是真的高，这次面的部门是WXG微信支付，难度爆炸。

1、EPOLL的水平模式和边沿模式有何区别？

因为自我介绍时，项目中用了EPOLL，所以问了这个，我按照常规思路答了。

2、ET和LT模式各自应用场景是什么？为什么有了高效的ET还需要LT？

这个问题没准备过，被问傻了，后来查了下：

LT的编程更符合用户直觉，业务层逻辑更简单，不易出错，但效率较低；
ET的编程可以做到更加简洁，某些场景下更加高效，但另一方面容易遗漏事件，容易产生bug；
对于nginx这种高性能服务器，ET模式是很好的，Redis使用的是LT，避免使用的过程中出现bug；
当并发量比较小时，比较推荐LT，因为LT模式下应用的读写逻辑比较简单，不容易遗漏事件，代码不易出错好维护，而且性能损失不大。当并发量非常大时，推荐使用ET模式，可以有效提升EPOLL效率。

3、string是如何存储数据的，具体过程？为什么会扩容2倍或1.5倍？

以前的编译器是用写时复制（COW）技术，每当字符串发生复制构造或赋值时进行浅拷贝，只复制指针并增加一个引用计数，只有对其中一个字符串进行修改时才会执行真正的复制。既然用到了引用计数，那么就要考虑在多线程环境下的线程安全问题，而且string会把operator[]和at()都认定为修改“语义”，即使我们只是访问字符串也会触发COW，这就导致string的COW实现存在诸多弊端；
现在编译器大多采用SSO（Small String Optimization）短字符串优化，当字符串长度小于15字节时直接存放在栈中，大于15字节时，栈中存放指针，指针指向堆中的完整字符串。这样的好处是，当字符串较短时，直接将其数据存在栈中，而不用去堆中动态申请空间，避免了申请堆空间的开销；
在g++环境下，string的扩容机制跟vector一样是两倍扩容，最初分配的capacity是15字节；
如果扩容倍率太低，继续插入字符的话会出现频繁扩容的现象，效率降低；如果倍率太高，又会造成空间浪费，所以我想2倍或1.5倍是一个折中的考虑，兼顾了效率与空间利用率；

4、算法题： 141. 环形链表

只让我说思路，我说用快慢指针，详细说了思路。又问我有没有别的方法，我想了半天没想出来，面试官说抛开时间复杂度和空间复杂度，你再想想，我直接说哈希表，哈希表每个元素存指针的val和next指针，这样每个元素都是唯一的，只要出现重复元素就说明有环。然后在让我想想 $O(1)$ 空间复杂度的方法，提示了可以做标记，但我短时间没想出来，就给我继续出了两道题，让我边做题边想，最后再问我。

5、算法题： 234. 回文链表

直接给我这道题和下一道题，让我预估需要多少时间，我看了看说大概25分钟，面试官说给我30分钟，他先离开一会儿，到时间了再回来看我。离开前问了我第这个题的思路，我说用栈，把链表遍历入栈，再遍历一遍链表同时与栈顶元素一一比较，全部相同则为回文链表。面试官说空间复杂度太高了，能不能实现 $O(1)$ 的空间复杂度，这题其实我不久前做过，以为用栈已经是很不错的方法了，结果还差得远呢。

6、算法题： 442. 数组中重复的数据

还好这个题也做过，我直接就想到空间复杂度 $O(1)$ 的做法了，可惜最后没调出来，忘了取绝对值，不过面试官好像不怎么在乎，他更在意你的思路是否正确。
面呗平台的面试，算法题都要写一个完整的cpp文件，需要自己处理输入输出，自己写ListNode结构体，自己构造链表。
现在想起来，在遍历链表过程中可以把链表的val修改成范围之外的val，这样第二次遍历到相同节点时，就能判环了。

7、面试官回来了

继续问我第六题的优化，问我是否有必要把整个链表存入栈中，提示了我一下，我突然想起来回文链表前后段是对称的，那么只需要让一半的链表入栈即可，大喜！然而面试官说还不够，你怎么确定链表的一半是多长？我答先把链表遍历一遍就知道了，面试官提示说不遍历整个链表也可以知道长度，又提示了下我第4题提到的判环方法，我突然又想到了快慢指针，快指针走到链表尾的时候，慢指针刚好指向链表中间，大喜！然而面试官说还是不够，接着他说了最终解法：快慢指针向前走，慢指针一边走一边反转链表，快指针走完就分成了两个链表，直接比较两个链表即可！我直呼妙啊妙啊！

8、反问

您的部门属于后台开发，是不是对网络编程这块要求很高，那我应该如何提高自己网络编程的能力呢？
面试官说其实他们还是更注重基础，基础一定要扎实，要有钻研精神，遇到问题要多想为什么，比如你知道ET和LT两种模式有区别，但你却没有继续去了解他们为什么有区别，他们的存在有何必要，适用于哪些应用场景等。其实网络编程这块你知道少一些也行，最最重要的是基础。