面试复盘 | 百度正式批面试

记得七月份的时候百度提前批开始后就马上投了，经过一周的简历筛选，在官网看到状态变成了面试流程中，本以为很快就会有面试，没想到足足等了两周没有人联系，也没有邮件来约面试，再去官网看状态已经变成简历共享中了.....于是百度的提前批还没开始就结束了。当时感觉挺无语的，加上那时刚拿了字节跳动的意向书，所以就没管百度了。

后来百度提前批结束，官网直接把我转到了正式批，不久后开始发来面试邮件，刚好那时候挺闲的，就做了下笔试，没多久开始约面试。前几次约我没有时间就没有确认，后来九月中刚好中秋回家，就约了面试。百度的面试好像集中安排在双休，我在家一天连着面完了三轮面试。

下面记录下三轮面试的要点，欢迎大家交流讨论~

一面(80mins)

自我介绍

手撕代码

LeetCode 比较版本号

class Solution {
public:
    vector<int> convert_to_nums(string &s) {
        vector<int> nums;
        string tmp = "";
        for(auto &c : s) {
            if(c == '.') {
                nums.push_back(stoi(tmp));
                tmp = "";
            }
            else
                tmp += c; 
        }
        if(tmp.size() > 0)
            nums.push_back(stoi(tmp));
        return nums;
    }
    int compareVersion(string version1, string version2) {
        vector<int> nums1 = convert_to_nums(version1);
        vector<int> nums2 = convert_to_nums(version2);
        int n1 = nums1.size(), n2 = nums2.size();
        int p1 = 0, p2 = 0;
        while(p1 < n1 && p2 < n2) {
            if(nums1[p1] > nums2[p2])
                return 1;
            if(nums1[p1] < nums2[p2])
                return -1;
            p1++;
            p2++;
        }
        while(p1 < n1) {
            if(nums1[p1] > 0)
                return 1;
            p1++;
        }
        while(p2 < n2) {
            if(nums2[p2] > 0)
                return -1;
            p2++;
        }
        return 0;
    }
};

C++ 基础

一个 C++ 程序从代码实现到运行要经过哪些阶段？每个阶段有什么作用？

这里面试官主要是想问编译的那部分知识，所以就详细回答了预处理-编译-汇编-链接四个过程的原理。
为了使程序编译运行后效率高一些，在编程时需要注意哪些问题？

刚听到这个问题的时候很懵，完全不知道面试官在问什么，然后就问面试官需要在哪些方面来考虑，面试官说从编译器优化的角度来回答，想了半天，想起来在深入理解计算机原理书上好像有优化的一些方法，所以就回答了：循环外移、减少函数调用、避免内存引用和提高并行化这几个方面，还列举了个简单的代码例子，面试官说回答地不错就继续下一个问题了。
C++ 中的 new/delete 函数与 malloc/free 的区别？

主要是前者会调用相关对象的构造、析构函数，后者不会，前者不需要指定申请/释放的内存的大小，后者需要指定等。

面试官追问：使用 new 申请内存失败会怎么样？

答：会抛出异常。

问：如果我想使得申请失败后返回一个空指针，需要怎么做？

答：使用 nothrow new 来申请内存。
虚函数的原理和实现？
构造函数能否声明为虚函数或者纯虚函数，析构函数呢？

析构函数可以为虚函数，并且一般情况下基类析构函数要定义为虚函数，只有在基类析构函数定义为虚函数时，调用操作符 delete 销毁指向对象的基类指针时，才能准确调用派生类的析构函数（从该级向上按序调用虚函数），才能准确销毁数据。

构造函数不能定义为虚函数。在构造函数中可以调用虚函数，不过此时调用的是正在构造的类中的虚函数，而不是子类的虚函数，因为此时子类尚未构造好。虚函数对应一个 vtable (虚函数表)，类中存储一个 vptr 指向这个 vtable。如果构造函数是虚函数，就需要通过 vtable 调用，可是对象没有初始化就没有 vptr，无法找到 vtable，所以构造函数不能是虚函数。
为什么父类的析构函数必须是虚函数？

如果析构函数不被声明成虚函数，那么编译器将实施静态绑定，在删除基类指针时，只会调用基类的析构函数而不会调用派生类析构函数，这样就会造成派生类对象析构不完全，造成内存泄漏。

计算机网络

GET 和 POST 的区别？
TCP 拥塞控制原理？
Cookie 和 Session 的原理分别是什么？
TCP 粘包和粘包分别是什么？

粘包：在进行数据传输时，发送端一次性连续发送多个数据包，TCP 协议将多个数据包打包成一个 TCP 报文发送出去；

拆包：当发送端发送的数据包长度超过一次 TCP 报文所能传输的最大值时，就会将该数据包拆分成多个 TCP 报文分开传输。

问：如何解决粘包和拆包问题？

答：（1）设置消息定长（2）头部添加消息长度（3）消息尾部添加特殊字符进行分割（4）将消息分为消息头和消息尾。

操作系统

内存管理自由链表和内存池讲一下

这个问题回答的不太好，记得在学习 STL 内存配置器时候学过，不过太久没看了忘了好多。
虚拟内存原理？
逻辑地址怎么转换成物理地址？

二面(70mins)

自我介绍

项目介绍

介绍一下做过的项目；
研究生做过什么项目吗？

这里开始介绍研究生做的课题，讲的比较仔细，面试官问的也比较多，回答完了面试官问为什么没在简历上写研究生做的项目，我回答说研究生的项目和岗位不太匹配，所以就没写在简历上。面试官说这个想法不对，简历上应该写自己做过的、最擅长的项目，这样面试才能更综合地考察的你的能力和你解决问题的方式。这里算是积累了一些经验了。

数据库

你了解哪些索引？

主要介绍了 B+ tree 索引，也比较了一些其他数据结构作为索引的优缺点。
Redis 有哪些数据结构？
Redis 持久化机制？
缓存和数据库是如何实现同步的？

缓存和数据库双写，采用预留缓存模式。
- 读的时候，先读缓存，缓存没有再读数据库，然后取出数据后放入缓存，同时返回响应；
- 更新的时候，先删除缓存，然后再更新数据库；这样读的时候就会发现缓存中没有数据而直接去数据库中读取数据。
分布式和集群了解吗？

这个没有做过，直接回答了不了解，面试官也没多问。

情景题

如果有海量的手机号数据需要保存，但机器的性能有限，如何才能尽可能少的占用内存？

刚开始我的解决方案是将手机号依据字段的含义进行划分为三部分，即 aaa-bbbb-cccc，其中前两个部分有特定的含义，如号段、区号等，而第三部分是随机的，所以手机号的前两个部分会有大量的重复，因此可对前两部分进行压缩，使用少数几个字符来表示。

面试官说这样的话是可以减少部分的内存的，但是优化的效果不太明显，还有没有其他的方法？

想了一会儿，想到了前缀树这种数据结构，赶紧把思路告诉了面试官。没想到面试官让继续思考其他方法，我说可采用合适的编码方法进行压缩编码，比如霍夫编码。

面试官看我想不到其他方法了，就给我讲了一种方法，就是通过对号码进行排序，然后使每一个手机号减去最小的手机号得到一个差值，作为偏移，这样的话我们只需要记住最小的手机号和后面每个手机的偏移就可以了，这样可以大大减低内存占用。妙啊，妙！