岗位：C++/GO/PHP研发工程师
部门：搜索技术平台研发部

一面（86min）

该面筋尽可能真实还原我面试时作答的内容和状态。

八股部分

1. MySQL索引如何实现？

索引底层是用B+树实现的，B+树非叶子节点存储的都是索引，只有叶子节点才存储真正的数据，并且叶子节点用链表连接起来，主要是方便范围查找。

2. B+树与红黑树有什么区别？为什么MySQL索引不用红黑树？

经典八股文，我竟一时想不起来，沉默了一会儿我说忘记了，面试官继续下一个问题。

3. 谈谈你对I/O多路复用的理解？select与epoll有什么区别？

项目中有用到I/O多路复用，所以问了。

如果不使用I/O多路复用的话，服务器端就只能通过多进程多线程实现并发（这里忘了说线程池优化，不然还能多扯一点的），调用accept函数阻塞等待客户端请求，效率较低。使用I/O多路复用的话就相当于把检测就绪文件描述符的工作交给了内核，提高了效率。select第一个参数是监听套接字描述符，中间三个参数分别是读事件、写时间和错误文件描述符集合，最后一个参数是超时时间，poll的参数就比较少，用了一个结构体把三种文件描述符集合包含进去了。select是Linux与Windows平台通用的，poll与epoll是Linux独有的，而且select检测文件描述符个数有上限，是1024个，在内核中写死了，而poll与epoll中没有限制。

第二问我脑子突然宕机，想不起来了，面试官提示说select需要遍历文件描述符集合，我突然记忆恢复，赶紧接着说对对，select每次需要遍历整个文件描述符集合，才能找出就绪的文件描述符，效率低，而epoll会直接返回已就绪的文件描述符集合（这里还可以说epoll是通过红黑树来管理待检测集合的，我也忘了说了），而且select和poll都有在内核态与用户态的数据拷贝，而epoll使用了共享内存（mmap），省去了不必要的内存拷贝。

4. 实习项目中的解耦与优化具体是做了什么？

我是接手的一个QT项目，之前的开发人员把所有功能函数全都写在一个mainWindow文件中了，导致文件很臃肿，改起来很累，于是我把每个页面单独拆分成一个文件，函数根据功能分成字符串处理类、I/O类、按钮功能类等等，根据类拆分到不同的文件中，这样就是解耦了。

感觉答得也不是很好，实际上做的工作远没有达到我说的这种程度哈哈。

5. 聊天室项目最大的难点是？以及一些实现细节？

网上找的一个很简单的项目，总共只有六百行代码，基于命令行的项目。之前面试的时候面试官都不屑于问我项目相关的东西，没想到这次终于问了，结果因为太久没复习了，答得不是很好，项目具体用了哪些数据结构都记不清了。

6. 介绍快排原理？

• 首先快排是不稳定排序，因为它是通过交换元素来实现的，接着说了快排实现原理，这里就不详细展开了，然后说了快排适用于完全乱序的序列，不适用与基本有序或基本逆序的序列，最后我主动说了优化方法；
• 我之前看过侯捷老师的《STL源码剖析》，stl里面其实对快排做了一些优化，比如在选择哨兵的时候使用三数取中法，即取序列第一个元素、中间元素以及最后一个元素，再取这三个元素的中位数作为哨兵，这样可以避免取到边缘值而导致每次分割不均匀的情况；
• 第二种优化方法，因为在递归分割序列时，序列的长度会越来越短，又因为短序列排序中插入排序效率最高，所以可以设置一个阈值，当序列长度分割到阈值时切换到插入排序，提高效率；
• 第三种优化，当序列中存在大量相同元素，或者全是相同元素时，使用快排仍然会得到最低效率，这时可以采用聚集相等元素的方法，每次选择哨兵后，将与哨兵相同的元素放到序列中间，下次分割时中间这些值不参与分割；
• 其实还有第四种优化方法，我当时忘记了，没说。第四种优化，当递归层数过深的时候改用堆排序，虽然第一个优化方法避免了取到边缘哨兵，但还是有可能取到较边缘的哨兵，最坏的情况会导致递归层数过深，从而降低快排效率，所以每次递归要判断递归层数，达到一定深度就改用堆排序，这是stl源码里实现的方法。之所以要用堆排序，我猜想可能是因为快排和归并都是基于递归的排序，此时递归深度已经太深，肯定不能再用了，而对于较长的序列使用插入排序效率也不是太高，所以选择了堆排序。
• 最后的最后分析了快排的时间复杂度最好情况为O(NlogN)，最坏为O(N^2)，空间复杂度最好的情况为O(logN)，因为递归时函数压栈需要空间，最坏情况为O(N)，一个快排呱呱呱说十分钟感觉问题不大。

7. 介绍虚函数？

• 虚函数是为了实现C++的多态性，运行时多态。在基类中声明一个虚函数，在其派生类中重写该函数，在程序运行时就可以根据指针所指对象的类型来调用对应的方法，而不是根据指针本身的类型来调用方法，这是虚函数的一个用法；

• 还有一个用法是将类中的析构函数声明为虚函数，主要是为了应对这样一种情况，当基类指针指向派生类对象，删除这个指针时，如果没有声明虚析构函数，就不会调用派生类的析构函数，从而导致对象析构不完全造成内存泄漏。还有，并不是所有的析构函数都要声明为虚函数，只有在这个类意图作为一个基类时才需要为它声明虚析构函数，否则没有意义；

• 如果类中声明了虚函数，那么类中会生成一张虚表，存放在静态区（全局区）的.rodata段，也就是只读数据段，对象的开头几个字节会设置为虚指针地址，根据这个地址找到虚表，然后调用虚函数。

8. 一个大文件中存了很多URL，如何找出相同的URL（应该是问找出重复出现过的URL）？

我直接不问条件，一口气讲完，请看标准答案：

一般来说遍历文件对每个URL建哈希表，就可以得出重复出现过的URL。但是对于大文件，有可能几十甚至几百个G，不可能对其建哈希表，因为内存放不下，像这种大文件数据处理首先是要想到分而治之，将其拆分成若干个小文件，具体拆分成多少个，取决于文件大小以及所给内存大小。比如我要拆分成1000个小文件，先遍历整个大文件，对其中每个URL做哈希计算，或者其他单向散列算法，计算出一个数值，将这个值对1000取模，最后得到的值作为小文件编号，该URL存入此编号的小文件，因为是单向散列算法，所有的URL都会较均匀的分布到这1000个小文件中。又因为相同的URL计算出来的散列值相同，所以相同的URL必定会分到同一个小文件内，这时只要逐个遍历小文件建立哈希表就可以得到相同的URL了，因为小文件的话内存是能够装下的。

9. 在函数中能返回局部变量的地址吗？返回后在main函数中是否能根据此地址取到该局部变量的值？

不能，因为局部变量在函数返回后就销毁了，再到它的地址去取值是没有意义的；

追问：为什么局部变量在函数返回后会销毁？

答：我想是因为局部变量是存储在栈上的，栈空间由系统来分配，当局部变量离开作用域，其内存空间就会自动被释放，只有用new或者malloc分配在堆上的空间才是不会被自动释放的。

10. 你目前还面试了哪些公司？

秋招的话，百度是我第一家面试的公司，目前还没有面其他公司。

算法题部分

• 手撕反转链表

  本来想一边说一边写，面试官说你写完再给我说思路，手撕了老半天，差点翻车，好在最后调出来了。解说的时候反转链表循环里的三条语句面试官没看明白，我又打开画图，蹩脚地进行画图讲解，面试官好像还是没听明白，沉默了一会儿，还是继续下一个题了，可能我画的不太好，越看越懵逼。完整代码以及当时我画的图如下：

  #include <iostream>
  using namespace std;
  struct ListNode                            //链表节点的结构体
  {
    int val;
    ListNode* next;
    ListNode() :val(0), next(nullptr) {}
    ListNode(int _val) :val(_val), next(nullptr) {}
    ListNode(int _val, ListNode* _next) :val(_val), next(_next) {}
  };
  ListNode* create(int n)                    //自动建立链表函数
  {
    ListNode* dummy = new ListNode(0), * p = dummy;
    while (n--)
    {
        int tmp;
        cin >> tmp;
        p = p->next = new ListNode(tmp);
    }
    return dummy->next;
  }
  ListNode* reverseList(ListNode* head)      //反转链表函数
  {
    if (head == nullptr) return nullptr;
    auto pre = head, cur = head->next;
    while (cur)
    {
        auto ne = cur->next;
        cur->next = pre;
        pre = cur, cur = ne;
    }
    head->next = nullptr;
    return pre;
  }
  int main()
  {
    int n;
    cin >> n;
    ListNode *head = create(n);
    auto reverse_head = reverseList(head);
    auto p = reverse_head;
    while (p)                                //循环打印反转后的链表
    {
        cout << p->val << " ";
        p = p->next;
    }
    return 0;
  }

  

• 手撕约瑟夫环问题

  面试官问：“有N个小朋友排成一圈，轮流数k个数，数到k的那个小朋友出局，问最后剩下的是哪一个小朋友？想想用什么方法实现？”

  我直接说这就是约瑟夫环问题（但是我忘了这题该怎么写了，好久之前刷过），于是我故意试探性地问是要写公式来实现吗？面试官说也可以写一下公式，我抓耳挠腮半天没想出来，请面试官给点提示，面试官说你想想其他实现方式吧，我说要写代码实现吗，面试官说那你写一下代码吧（绕了半天还是绕回来了，哭泣）。

  我完全没思路，努力回忆当时力扣的题解是怎么做的，正当我要放弃说没思路的时候，面试官说不用想什么巧妙的解法，你就用最普通的方法想想，你会怎么做？

  我突然想起来这题估计跟上一题有联系，继而想到可以用循环链表来实现，于是把上一题的代码改了改，写出来了。写完面试官说有内存泄漏，我赶紧添了个delete tmp。完整代码如下：

  #include <iostream>
  using namespace std;
  struct ListNode                //链表节点结构体
  {
    int val;
    ListNode* next;
    ListNode() :val(0), next(nullptr) {}
    ListNode(int _val) :val(_val), next(nullptr) {}
    ListNode(int _val, ListNode* _next) :val(_val), next(_next) {}
  };
  ListNode* create(int n)        //自动建立链表的函数
  {
    ListNode* dummy = new ListNode(0), * p = dummy;
    while (n--)
    {
        int tmp;
        cin >> tmp;
        p = p->next = new ListNode(tmp);
    }
    p->next = dummy->next;    //尾节点接着头结点，构造循环链表
    return dummy->next;
  }
  void remove(ListNode* head, int k, int &n)    //删除第k个节点的函数
  {
    while (k -- )
    {
        head = head->next;
    }
    auto tmp = head->next;
    head->next = head->next->next;             //跳过下一节点
    delete tmp;                                //防止内存泄漏
    --n;                                       //每次删除，总元素个数减1
  }
  int main()
  {
    int n, k;
    cin >> n >> k;
    ListNode *head = create(n), *p = head;
    while (n != 1)                            //直到剩下一个元素为止
    {
        remove(p, k, n);
    }
    cout << p->val << endl;                   //输出这最后一个元素
    return 0;
  }

• 内存管理算法LRU思路

  刚做过这个题，印象还有，我直接说了原理，然后说用哈希表+双链表实现，然后就说不下去了。

  面试官说我应该先讲要实现哪些操作，再说具体实现。

  我马上反应过来说主要实现插入和查找操作，哈希表大小就是内存大小，双链表最前面的元素就是最新的元素，最后的元素就是最久未使用过应该要淘汰的元素。如果插入时哈希表满了就把双链表尾部元素删除，新元素插入到双链表头，同时更新哈希表，如果插入时哈希表没满，直接将新元素插入双链表头部再更新哈希表即可。查询操作就把查询到的元素移动到双链表头部即可。

  还好没让我手撕，这题手撕还是挺吃力的。

反问环节

• 请问您所在的是百度哪一个部门？

  百度阿拉丁。

  我又问阿拉丁是什么，第一次听说。面试官巴拉巴拉说了一些，我当时没记住。

• 请问您的部门主要用什么语言做开发？

  GO和PHP。

  我问那我进来也需要转GO和PHP了，面试官问我对转语言有什么看法？

  我说无所谓啊，语言只是工具而已，要转什么语言我都OK。

• 您在面试的时候会比较看重求职者哪方面的能力呢？

  我们最看重基础，以及把基础知识运用在解决实际问题上的能力。

总结

感觉现阶段确实没有必要花大力气去学Redis、Nginx这些东西，基础还是最重要的，简历上写了什么知识点，就把这些知识点记好。

二面（24min）

二面是电话面，面试官迟到了38分钟，有点离谱，我都以为被放鸽子了。

1、问项目

问了老半天，然后说我实习项目技术含量不是很高呀，又评价我我聊天室项目说基本上任何一本讲网络编程的书都有吧，我只能苦笑说是的是的哈哈。

2、你在实习的这个项目中最大的收获是什么？

因为这是我第一次实习，我觉得收获最大的地方在于跟Leader沟通具体功能的实现，对接任务，提升一些业务上的能力。技术上的话，因为我之前没接触过QT，而实习项目是用QT做的，我觉得提升了自己快速学习一门新技术，并将其应用到实际开发中的能力。
这段是我当时现场编的，感觉答得还不错哈哈，确实也是如此。

2、了解MySQL、Redis吗？

我说不了解，没学过，又说了一堆我没听过的词，我说没听过，就没继续问了。

3、C++里面public、private和protected的区别？

突然问个那么简单的我有点诧异，按照常规思路答了。

4、MySQL底层索引怎么实现的？有什么优点和缺点？（这个问题一面已经问过了）

5、MySQL一张表能存多少数据？

我说不知道，不太了解。后来百度也找不到一个具体的解答，有点懵。

6、了解大文件处理吗？比如我有8G的内存，但是需要处理10G的文件，怎么处理？

大文件处理的话，首先应该是分而治之，要把它拆分成若干个小文件在放到内存中进行处理。

追问：那怎么保证拆分后相关的数据能放在同一个小文件中呢？比如每一行是一条数据，把相同类型的数据归到一个小文件中。

可以用哈希算法或者其他单向散列算法，对该条数据表示类别的那个字段进行计算，对计算出来的值模以10（比如要分成十个小文件），最终得到的值就是要存放这条数据的小文件的编号，这样一个大文件就会按类别较均匀地拆分成10个小文件，再进行处理。

总结

二面因为是电话面，问得比较简单，最后给我说过了，后面会通知我进行三面。这是我离offer最近的一次，求求了，让我过吧！

三面（34min）8-25

百度提前批只有三面，没有HR面，三面是经理面，如果经理是技术出身，那么还是会问很多技术问题，但我约面时被告知是电话面，所以肯定是非技术面了，应该就是聊人生。于是也做了一些HR面的准备。

1、问实习做什么？实习遇到最大的困难是什么以及如何解决？实习过程收获最大的是什么？

2、你觉得你跟科班出身的同学比有什么优势？

灵魂拷问，我当时是真不知道该如何答，我反问是指计算机或开发方面的优势吗？面试官说其他方面都可以，我赶紧将话题转移到其他方面：

• 我善于观察和记录，因为平时有写日记的习惯，已经写了四年了，每天都写，所以每每遇到事情，无论大小我都会记录下来，这种习惯也延伸到工作中，每当解决一个问题，我都会详细记录，下次再遇到同样的问题能做到有据可查；
• 我比较专心，当时考研考了两年，第二年是在家里复习的，最后考上了。所以我觉得自己有能专心学习，不受外界干扰的能力；
• 快速学习的能力，实习所在的部门临时让我接手一个QT项目，但我之前不太了解QT，花了一个周末去学习，周一上班就开始做需求了，所以我觉得自己有快速学习一门新技术并将其应用到业务开发上的能力。

3、你的职业规划

短期的话我自己还是想做技术，多学一些技术栈，有时间也会往底层去学，感觉我还是想做技术吧，短期计划就以技术为主。

4、你不是计算机专业的，那你平时是怎么学习计算机的知识？如何规划的？

我还是以看书为主吧，我是去年10月份开始学的C++，到现在还没满一年。最开始也是看一些经典的书籍，配合一些技术博客，比如CSND等等，书与博客互补学习。

5、你还会用其他方式学习吗？

会，早期的时候还会看视频学习，比如B站，上面也有不错的学习视频。不过我觉得看视频太费时间了，讲得很啰嗦、抓不住重点甚至讲的是错的，后面我慢慢就不看视频了，转而看书，因为书是权威，肯定不会是错的。

6、刚才你提到了B站，你是如何看待B站的？你觉得B站为什么成功？

最开始我了解B站是因为它是一个二次元社区，我对这方面也比较感兴趣，但现在的B站已经不只是二次元了，有美食、科技、很多生活类、学习类的视频，是一个比较全面的网站；

首先是B站看视频没有广告吧，而且也不会有各种各样的弹窗，还有就是有激励计划，让很多新人积极参与到视频制作中来。

7、你用过抖音吗？说说B站和抖音的区别？

B站常用，但是抖音没用过。我觉得主要是用户群体不同吧，现在生活节奏快，大家都很忙，时间碎片化，所以短视频刚好可以用来填补这些碎片时间，而像B站这种动辄十几分钟甚至一个小时的视频往往是没有时间去看的。

8、刚才你提到了碎片时间，那你平时是怎么利用碎片时间的呢？

比如我在实习的时候，中午吃完饭还有一个小时的时间休息，除去睡午觉的半小时，剩下半小时我会打会儿游戏放松一下，或者看看自己的笔记，复习巩固，因为平时有用Markdown写笔记，有时间就会看一下。

9、你写的是什么笔记？笔记都是保存在本地的吗？

就是计算机的一些基础知识，计网、操作系统、数据结构这些，虽然书上和博客上都有，但我感觉需要自己总结一遍记下来，印象才会深。本地有存，我也经常在一个叫AcWing的算法网站上分享这些笔记，让更多人看到，或许大家会有不同意见，可以继续探讨。

10、你之前说自己对开发感兴趣，那么你为什么不本科毕业就出来做开发呢？既然感兴趣那你为什么不考计算机专业的研究生呢？为什么读了通信专业的研究生又来做开发？

本科的时候我就对程序设计挺感兴趣的，那时候自学了PHP，但当时感觉自己学得不是很精，可能没法找到好的工作，加上周围同学都考研，我就也去考研了；
当时考研也查过许多资料，因为自己没有系统学过计算机，直接跨考要补的东西太多，希望可能不是很大，所以选了比较稳妥的通信；
其实刚读通信研究生的时候我还是对学术抱有期望的，但是我发现通信专业的导师都不做通信的，全都在搞计算机，深度学习这些东西，我也开始往这个方向学。后来在一个师兄的建议下学起了C++，发现自己很感兴趣，就想以后也做开发了。

总结

其实这个环节我还是没有准备特别好，当时答得比较乱，每次不知道如何作答时都逼自己冷静，不要冷场，赶紧想想可不可以反问点什么东西。面完女经理加了我微信，不出意外的话应该能拿offer了！

9-13 收到百度意向书

11-15 收到hr谈薪电话，拿了百度后端研发的SP