2021年抱着尝试的想法投递了百度的AIDU计划，有幸通过并在7月底8月初参与了若干部门的面试，在此将部分有印象的面经记录整理出来，有些是线上，有些是线下，以供大家参考。
推荐架构
自我介绍
语言，会c++么，能看懂，不太会写
c++11新增了什么…了解么，不了解就算了，不问这个了
复杂链表的复制
找到数组中第k个数（说了两种，计数排序思路，堆排序思路，写了第一种）最后面试官问知不知道快速排序的思想（才意识到原来想让我写快排partition求第k个数，然而感觉有点麻烦当时就没说）
操作系统方面，用户态内核态区别（说了执行效率，扯到select，epoll之类的答得不好）读取文件算不算内核态（我说不确定，感觉是内核态，其实是用户态）
Linux命令哪些用的比较熟（cd ls pwd mkdir不必多说，grep -e -A -B -C，less）知不知道awk？（只知道awk和sed是很厉害的两个命令，一个处理列一个处理行，但是还不会写）
数据库方面redis熟不熟（更多是理论学习，MySQL用的多点）
一条sql的执行过程（在数据库结果缓存的部分还有sql解析部分扯了一会）
自动驾驶事业部
一面
自我介绍
详细聊实习和项目
介绍了一波自动驾驶相关的技术方向，包括：
-
雷达的环境感知
-
PNC（路线规划）
-
离线仿真（降低成本）
- 高精度地图（厘米级别误差）
面试官是高精度地图组的，涉及到用Spark进行大数据处理，这里的数据不是指类似海量数目的用户行为日志那种数据，而是指雷达感知到的数据，雷达在短时间产生的感知数据就可到达TB级别，因此涉及到的存储和流式处理都会面临一些挑战。之前使用Hive数据仓库存储，现在开始过渡到K8s相关技术栈
问一些Java问题，，说一下垃圾回收（从垃圾的定义，引用计数，可达性分析，JVM内存区域，新老年代垃圾收集机制，几种垃圾回收算法说到G1垃圾收集器，然后扯了下jps，jinfo，jstack等命令和OOM可能的情况以及JVM优化方式）
Java中除了JVM实现并优化过的Synchronized，还有JUC中的可重入锁（ReentrantLock），它的实现原理是什么？（开始回答了CAS和乐观锁悲观锁，面试官说这是实现锁的方式之一，不是实现原理）
多线程用的多不多（不多）说一下线程池的工作原理（勉强大概说了下，下去以后要好好看下）
MySQL的ACID是什么，有哪些隔离级别
手写单例模式（几种方式的实现细节需要注意！）
//懒汉式-线程不安全，注意static别漏
public class Single {
private static Single single;
private Single() {}
public static Singleton getInstance() {
if (single == null)
single = new Single();
return single;
}
}
//饿汉式-线程安全，缺点：一开始就实例化，无法节约资源
public class Single {
private static Single single = new Single();
private Single() {}
public static Single getInstance() {
return single;
}
}
//懒汉式-线程安全，缺点：实例化后依然需要依次等待，有性能问题
public class Single {
private static Single single;
private Single() {}
public static Single getInstance() {
if (single == null)
single = new Single();
return single;
}
}
//双重校验锁-线程安全，注意volatile别漏，以及synchronized(Single.class)的写法
//volatile作用：禁止JVM指令重排，保证在多线程环境下也能正常运行
public class Single {
private volatile static Single single;
private Single() {}
public static Single getInstance() {
if (single == null) {
synchronized (Single.class) {
if (single == null)
single = new Single();
}
}
return single;
}
}
//静态内部类实现:既有延迟初始化的好处，而且JVM能确保INSTANCE只被实例化一次，保证了线程安全
public class Single {
private Single() {}
private static class SingleInstance {
private static final Single INSTANCE = new Single();
}
public static Single getInstance() {
return SingleInstance.INSTANCE;
}
} 思路：刚开始说错了说用堆存，面试官说需要几个堆呢，然后感觉不对就说用二叉平衡查找树（红黑树）存，这样add方法复杂度就是O(logN)，getMiddle方法复杂度就是O(N)。面试官说也可以，那么实现一下。问面试官能否用Java自带的数据结构实现，答曰可以。于是基于TreeSet开始写，手写getMiddle方法的时候比较乱，用中序遍历+计数的方式找到第size()/2个元素，如果size()是偶数的话，就先找到第size()/2个元素然后用floor方法找到比它小的第一个元素，再取平均值即可。但实际上我们是没法获取TreeSet中封装的树然后自己递归遍历的，如果要找到第k个元素，其实应该用iterator实现。不过面试官人很好，向他解释了这种思路也同意了。
反思：上述方法实现的时候感觉比较勉强，且无法存放重复，除非自己实现一个支持重复元素的二叉查找树（但这样又面临着不平衡的问题，除非能手写一个支持重复元素的红黑树…）那么还可以怎么做呢，一是用bitMap，用512MB就可以表示-2^31~2^31-1这么多的元素，但缺点同样是具体实现较复杂，也不能很好地支持多个重复元素；二是借鉴Redis中的有序链表Zset，用跳表实现，但缺点同样是具体实现较复杂；如果有更简单的做法欢迎指出。
二面
自我介绍
知不知道第一个面试官是谁（？黑人问号）然后说你的实习经历挺不错的，方向和他很match
看到我的项目想让我写最短路径，然而我感觉不够熟，说项目还在进行（确实还没做完）于是改成了图的bfs
follow question，假设微信10亿用户每个都有100好友，估算找到任意两人之间的路径需要多少内存（开始在int能不能表示10亿上纠结了半天，确认可以）然后一通估算说是10+GB，面试官指出图的存储还没算上，于是在联接表的情况下估算出需要1200+GB，又是follow question，一个节点不够存，怎么办，答曰假设一个节点存100GB，需要12个节点，问这样的情况下上述流程是如何进行的，这种情况下图的visited数组也需要分为12个部分，在bfs时添加一个节点的相邻节点时，需要根据其编号去不同的机器上查找。
一个数组第k个最大值，说了三个思想，面试官虽然也同意，但似乎想听大数据处理流之类的解法（然而我不了解）
k叉树中任意两个节点的公共父节点
想了一会没想出来，面试官提示暴力解法是什么，想到前序后续层次，不断找到父节点（并补充如果在k叉树数据结构中存父节点指针也可以）
三面
自我介绍
问实习项目
说说你对动态规划的理解，它适合什么样的问题（相同子结构，求最优值？）
leetcode123 两次股票买卖，求最大收益（刷题少了没做过，知道是动态规划但是dp推导式子还是没写出来，面试官说没关系）
无法一次读入内存的数据，找到第k个最大/最小值（分成n份依次读取，每次找到前k个最大/最小值，然后合并处理）那如果k也很大，无法将前k个存到内存中呢？（分成n份建堆，找到最大/最小值，然后n个值比较，弹出一个最大/最小值，依次重复上述步骤k次）（不知道是不是对的，感觉这个答案只能说过得去）
有没有follow through的经历
介绍一个你觉得有亮点的项目
AI平台部
一面 自我介绍
按顺序从后往前聊项目、实习和技术栈，把每个项目都聊了一遍
在项目中用到了哪些设计模式？
你说单例用的比较多，那么手写一个单例模式吧（几种方式的实现细节需要注意！）
你简历上写了熟悉排序算法，那么写一个快速排序吧（刚开始想了一会，面试官说如果感觉比较难可以换一个，写个冒泡，我说我觉得自己可以写出来快排（内心OS：冒泡就两个循环还需要写么…）然后用双指针的方式写出来了，是bobo老师的思路，指针都是从左边开始移动的。面试官说这个还比较少见，他看到的都是从两端开始从中间移动的写法）
二面
自我介绍
聊实习和项目，对实习K8s相关的工作很感兴趣，进行了很深入的探讨，除了算法，实现细节，部署方式还问了评估指标，特殊情况处理
对Redis的数据结构有多少了解（其实了解不多，于是先下手为强说了几种常见的数据结构，然后说自己对Zset的跳表实现比较感兴趣）
对消息队列有多少了解，它可以用来干什么（说了限流，消息传输，进程间通信等等，并和自己一个项目中的设计结合起来聊，于是话题转到了消息队列在那个项目中如何发挥作用的，最后问为什么要用消息队列，答曰一是为了项目架构的解耦和拆分，减少依赖之类的，二是能提升消息传递效率）
补充：网上说消息队列主要解决应用耦合，异步消息，流量削锋等问题。
进程和线程的区别？（没想到会问这样的经典八股，然而我还是没答好）
进程是资源分配的最小单位，线程是CPU调度的最小单位
进程之间的切换开销比较大，但是线程之间的切换开销比较小
来写个题目，两个一组反转链表（心想还好不是k个一组，得回去复习下了）
地图数据引擎部
一面
自我介绍
按照我简历上提到的知识点，详细问各种基础知识，不是纯八股，需要一些思考但相对较简单，想起来的如下（很多问题我不确定，就说不太确定但是我认为可能是blabla）：
TCP为什么是三次握手（还答了为什么比四次少一次）
ping的时候有时候很快就收到了不可达，这是谁发的（开始答了最大存活跳数，面试官说这是个偏门原因，后来想到了是路由器或三层交换机）
http的get请求从理论上讲能否通过http报文内容传输信息（不确定，答曰理论上可以，但一般都是通过url传或者cookie，一般get请求的http报文内容是空的，不知道为啥没人把参数放在http报文中）
为什么https比http慢（刚开始通过非对称加密得到对称加密的密钥，加密需要时间）
说一下redis中hyperloglog的应用（日活月活，uv之类的）为什么（少量存储空间就可以达到误差很小的数据）原理（不清楚细节，但知道是概率型数据结构）误差大概多少（之前看网上是一千多误差是十几，应该准确率在95%以上）
为什么redis的一些数据结构在数据量比较少的时候没有用那些专门的数据结构，而是就用数组存在一起？（大概这个意思）（因为redis追求速度，同时这样也能压缩空间，在数据量比较小的时候用数组形式存放和用专门数据结构存的时间复杂度差不多）（后来面试官说这样可以充分利用CPU缓存）
你的项目中为什么页式存储的每个页大小是16kb？（这个是自己定的，看你想定多少了…后来想到了磁盘的读取特征是一次读一片空间的）
分布式一致性协议的应用场景（就说了分布式数据库）
什么情况下对属性建索引的效果不好（重复度高的属性）
对索引范围查询的时候如何工作（两种方式，第一种是在b+树查范围两段，然后因为b+树叶子结点是链表连接的，直接取它们之间的元素即可；二是查一次范围左侧，然后一直遍历链表直到叶子结点元素不符合要求）
索引和记录的数据结构是什么，它们之间如何一起作用（说了b+树，聚簇索引和非聚簇索引）
一个数组，其中第i个值表示当前位置可以向后走的最大步数，问从第0个位置开始到最后的最少走几次（时间来不及没写代码，给出了动态规划思路，面试官说有没有时间复杂度更低的，说了贪心思路，然后说不确定贪心得到的是不是最优解，面试官说是，想了想应该是因为数组中值表示最大能走的步数，然后面试官问最好和最坏时间复杂度，刚开始卡壳了，收到提示后算出动态规划最优是O(N)最差是O(N^2)，贪心最优O（1）最差是O（N））
二面
需不需要自我介绍？不用
你对云原生的理解，它的特征是什么，什么样的应用/反问可以称之为云原生？（？黑人问号）
你对后端，算法，基础架构，策略等的理解？（？继续黑人问号）
你的数据库项目的组成部分，和MySQL的比较，在纸上写重点（问了各层的细节）
follow question：索引的实现，存储记录的数据结构，表的属性，类型等meta字段存在哪，sql语句的解析和执行过程（以join语句为例）
进程，线程和协程的区别，特征，应用场景？在纸上写重点
单调递增数组进行了一次偏移，现在给你一个元素，找到它在数组中的位置
百度地图出行部
一面
问实习项目，侧重算法细节
说一下虚拟内存
Linux用过吗，里面那些命令执行过程是怎样的
你的项目都是Java，会不会c++（能看懂代码，写比较吃力）
算法题：输入一个字符串，找到其中所有偶数长度的回文串并删除（没写代码，讨论思路，最开始想的是先搜索两个相邻的一样的字符，如aa或bb，然后向两段扩展搜索。面试官说对于dbaabccd这样的情况，删除baab后剩下的就是dccd，需要继续删除，于是提出在while循环中每次检测第一个aa这样的字符，然后向两端扩展，删除，然后反复执行，直到找不到；面试官说有没有优化空间，于是提出可以先一遍搜索所有aa这样的字符并标记，然后依次删除所在位置的回文串，再对下一个进行同样的操作，这样就避免了对字符串的重复搜索，且可以处理dbaabccd这样的情况。面试官说也可以不用先找到所有的aa这种情况，而是先找到第一个这种情况，向两端拓展，删除回文串后，拼接成新字符串后直接从这个位置继续向后查找aa这种情况即可）
场景题：百度地图中从出发点到终点可能有不止一条推荐路径，每条路径由若干条道路组成，不同的路径可能经过相同的道路。比如从1到7，给出3条路径：
1 2 4 5 7
1 3 4 6 7
1 6 7
其中前两条路径都经过4，后两条路径都经过6（两条路径可能经过不止一个相同的道路，这里的例子中是一个）那么如何求出从出发点到终点所有可能的道路？
（写之前问了个问题，为什么百度地图不给出来所有可能的路径而只给出部分路径，答曰计算开销太大。刚开始思路是组合，假设输入是两条路径的话，可以先排序+两指针同时遍历找到所有都经过的点，然后就可以变成规模更小的子问题。而且假如有一个都经过的点，那么就是4条路，有2个点就是8条路，以此类推。面试官说如果输入是多条路径，组合的方法就很复杂了，不同推荐路径之间的相交点也不同。于是想到建模成图论问题，相当于找到有向图中两点之间的所有路径，仅考虑一个联通分量。具体使用dfs遍历，因为bfs是找最短路径的，dfs可以找到不同的路径。于是开始写，包括表示图的类，以及这个算法。我是使用邻接表存储，先根据输入简历有向图，再调用方法求出所有路径。写的时候还不太熟，多花了些时间。写完后面试官问有没有优化的点，想了会，dfs这块想不出来有什么优化的点，但是图的存储可以优化，我是用链表数组来实现邻接表的，也可以用树的数组来存，这样能够更快地判断两节点间的前驱/后继关系。感觉有些没答到点上，于是请求面试官给点提示，他说节点的数目比较多，于是想到有向图图中如果节点多边少，那么用邻接矩阵存的话就相当于是稀疏矩阵了，而稀疏矩阵可以压缩存储。这个回答还算过得去，不过最后面试官说对于只有一个前驱或一个后继的节点，可以优化成一个节点，比如1 2 4 5 7 8 9和1 3 6 7 9，1 2 4 5 7可以简化成1 7，1 3 6 7也可以简化成1 7，那么具体中间经过哪些节点可以存在另外的数据库中。感觉这确实是一个很好的优化点）
地图业务部
二面
自我介绍
实现一个栈
follow question：实现栈的getMin功能
百度安全部
一面
面试官居然是老乡+校友，还请我吃了午饭
Linux虚拟地址和物理地址直接如何转化（说了mmu，页表）
用户态和内核态区别
Linux从磁盘读入一个文件到内存的过程（答不上来，面试官说有buffer空间，先拷贝到buffer空间再拷贝到内存）
k8s中有哪些组件（实习相关问题）
MySQL中InnoDB和MyISAM的区别
分布式一致性协议，介绍一个你熟悉的
Go和Java的区别
golang中的interface
dfs和bfs的区别（本质是遍历时使用了栈和队列）
二面
设计模式了解多少，假设工厂1和工厂2本来都可以生产产品A和产品B，如何通过设计模式，让工厂1只能生产产品A，工厂2只能生产产品B（这里对设计模式的理解不深，想了半天没答到点上，说了个low方法，就是给工厂类加一个标志位，根据标志位来判断能否生产产品。面试官提示在工厂的构造方法中传入一个接口（？好像是这样），然而还是没想到该怎么做）
Linux了解多少，软硬链接是什么（举了Windows快捷方式和镜像文件的例子，面试官顺便问了深拷贝和浅拷贝）
三次握手和四次挥手
算法题：判断链表是否有环
//我的代码
public boolean hasCircle(ListNode head){
if(head==null||head.next==nul)
return null;
ListNode slow = head;
ListNode fast = head.next;
while(fast!=null){
slow = slow.next;
if(fast!=null&&fast.next!=nul)
fast = fast.next.next;
else
return false;
}
return true;
}
//面试官尝试了各种情况来检验我的代码，最终证明是没有问题的
//后来他说while循环那段逻辑在有些情况下不会执行，他想看到的代码逻辑如下
//这样所有情况都会进入while循环
public boolean hascircle(ListNode head){
ListNode slow = head;
ListNode fast = head;
while(fast!=null&&fast.next!=null){
slow = slow.next;
fast = fast.next.next;
if(slow==fast)
return true;
}
return false;
} 搜索架构部
一面
自我介绍
实习项目
TCP拥塞控制
什么是自旋锁
讲一讲hashmap
讲一讲avl
事务
动态库和静态库
智能指针？
手写单例
从左侧查看二叉树，如何优化以使用更小空间
二面
实习项目
背包问题（没准备，刚开始答错了，后来面试官提醒才改过来）
圆中两条线相交概率
三面
相交链表，时间复杂度和空间复杂度最优解法，以及如何判断没有交点，判断后如何继续找到相交点
数组中的中位数（快排partition）
如果数据量很大呢，存放在多个机器中（mapreduce，具体还是不太清楚）
张三有两个孩子，其中一个是女孩，另外一个是女孩的概率（条件概率，1/3）
未来几年职业规划
怎么看加班
压力大会如何处理
做的工作内容自己不感兴趣会怎么办
（灵魂三问……）
反问：部门业务+一天如何度过
内容技术架构部
一面
有点尴尬，视频面试软件有问题不能用，重启电脑结果电脑更新…折腾20分钟，最终用网页链接面试的
聊实习项目
问你点基础的，说一说Linux内存分配（？完全不知道，说了逻辑内存地址到物理内存地址转换）
如何实现一个内存控制的方法类，或者说有什么思路可以管理内存（？懵逼，说了页式文件系统中内存划分成缓冲区数组的思想，扯到了Java堆内存分配）
如何实现一个同步队列，简单实现下（想到AQS然而不知道如何实现，就硬着头皮说用普通队列加上锁来实现，入队出队的方法都是synchronized修饰的，同时也可以看成是生产者消费者问题，需要使用互斥量。实现的时候写得很low）
二叉树前序遍历的非递归实现
进程间通信的方法
同步，异步，阻塞，非阻塞的区别（经典题目，然而说的很一般，最后举了烧开水的例子）
和我说通过了，约二面时间（？）
补充：为充分利用和管理系统内存资源，Linux采用虚拟内存管理技术，让每个进程都有4GB互不干涉的虚拟地址空间。当进程要访问实际内存资源时，会建立虚拟地址和物理地址的映射，调入物理内存页。虚拟地址到物理地址的转换会使用MMU内存管理单元对虚拟地址进行分段和分页转换。
4GB的进程虚拟地址空间被分成用户空间和内核空间，用户空间被“划分成5个区域：代码段（存放可执行文件的操作指令，只读），数据段（存放静态变量、全局变量），BSS段（存放未初始化的全局变量，全置0），堆（存放动态分配的内存段，大小不固定调用malloc等函数时扩张，调用free等函数时缩减），栈（寄存交换临时数据的内存区域）
内核空间分为直接映射区，以及动态/永久/固定内存映射区，用于对整个物理地址范围的寻址
import java.util.*;
public class Solution {
private static class TreeNode{
int val;
TreeNode leftChild;
TreeNode rightChild;
public TreeNode(int val) {
this.val = val;
leftChild = null;
rightChild = null;
}
}
public ArrayList preTraverse(TreeNode root){
ArrayList<Integer> arrayList = new ArrayList<>();
if (root==null)
return arrayList;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop();
if (node.rightChild!=null)
stack.push(node.rightChild);
if (node.leftChild!=null)
stack.push(node.leftChild);
arrayList.add(node.val);
}
return arrayList;
}
public static void main(String[] args) {
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
node2.leftChild = node3;
node2.rightChild = node4;
node1.leftChild = node2;
node1.rightChild = node5;
System.out.println(new Solution().preTraverse(node1));
}
} 二面
自我介绍
问实习项目
问你点基础的，线程安全是什么
.a和.so有什么区别（静态链接库和动态链接库的概念）
算法：单调递增数组循环移位后找最大值
刚开始写了O(N)时间复杂度的解法，后来面试官说用更快的，于是改成二分
import java.util.*;
public class Solution {
public int findMax(int[] arr){
if (arr.length==0)
throw new IllegalArgumentException("arr's length is 0.");
return findMax(arr, 0, arr.length-1);
}
//[start, end]
private int findMax(int[] arr, int start, int end){
if (start==end)
return arr[start];
int mid = arr[start]+(arr[end]-arr[start])/2;
if (arr[mid]>arr[start])
return findMax(arr, mid, end);
else if (arr[mid]<arr[start])
return findMax(arr, start, mid);
return arr[start];
}
} 用redis实现定时调度任务队列，怎么实现，存时间（不知道redis有没有表示时间的数据结构，说了可以序列化和存字符串，后来面试官提示用zset）
大流量访问数据库，有什么解决思路（用redis之类的缓存，nginx负载均衡，反向代理，削峰）
用redis缓存有什么缺点（复杂度提升，缓存穿透，血崩，失效）
用了还是要面临很多流量怎么办（redis集群，请求hash后给每个redis实例）
给单个redis实例的请求还是很多怎么办（一主多从，多副本）
这种情况下还是很多请求怎么办（把数据前置，尽量减少到缓存的请求，比如用cdn之类的，然后再加上多级缓存）
内容架构部的内容中台，主要负责搜索和feed的数据存储，组织等一系列流程
全部评论
(2) 回帖