《关于我的那些面经》——百度后端（附答案）

作者保证&＃xff0c;本系列全是纯干货真实记录&＃xff0c;绝对不是某些营销号瞎编乱造的面试。

一、公司的简介

百度是全球最大的中文搜索引擎&＃xff0c;是中国最大的以信息和知识为核心的互联网综合服务公司&＃xff0c;更是全球领先的人工智能平台型公司。2000年1月1日创立于中关村&＃xff0c;公司创始人李彦宏拥有“超链分析”技术专利&＃xff0c;也使中国成为美国、俄罗斯、和韩国之外&＃xff0c;全球仅有的4个拥有搜索引擎核心技术的国家之一。

百度作为全球最大的中文搜索引擎&＃xff0c;百度每天响应来自100余个国家和地区的数十亿次搜索请求&＃xff0c;是网民获取中文信息的最主要入口。百度以“用科技让复杂的世界更简单”为使命&＃xff0c;不断坚持技术创新&＃xff0c;致力于“成为最懂用户&＃xff0c;并能帮助人们成长的全球顶级高科技公司”。

百度是中国最大的以信息和知识为核心的互联网综合服务公司。在AI驱动下&＃xff0c;百度的移动生态是中国最大的以信息和知识为核心的移动生态&＃xff0c;以百家号、智能小程序和托管页为主要支柱。2019年百度用户规模突破10亿。百度App日活跃用户2.22亿&＃xff0c;信息流位居中国第一。百家号创作者达到300万。百度智能小程序是国内唯一完全开源的小程序平台&＃xff0c;月活用户规模破3.54亿。百度知道、百度百科、百度文库等六大知识类产品累计生产超10亿条高质量内容&＃xff0c;构建了中国最大的知识内容体系。

百度是全球领先的人工智能平台型公司。百度大脑是中国唯一的“软硬一体AI大生产平台”&＃xff0c;是百度AI的集大成&＃xff0c;对外全方位输出超过250多项AI能力。飞桨是中国首个全面开源开放、功能完备的产业级深度学习平台&＃xff0c;是中国自主研发的“智能时代的操作系统”。百度智能云是百度AI To B业务的重要承载者和输出者&＃xff0c;是产业智能化领导者。小度助手是中国最大的对话式人工智能操作系统&＃xff0c;拥有中国市场规模最大、最繁荣的对话式人工智能生态&＃xff0c;2020年3月&＃xff0c;小度助手语音交互次数超过65亿次。作为全球最大自动驾驶开放平台&＃xff0c;Apollo代表中国最强自动驾驶实力&＃xff0c;被知名研究公司Navigant Research列为全球四大自动驾驶领域领导者之一。目前已形成自动驾驶、车路协同、智能车联三大开放平台。自动驾驶方面&＃xff0c;超过十项中国第一&＃xff0c;技术实力领跑行业。智能交通方面&＃xff0c;百度“ACE交通引擎”是全球首个车路行融合的全栈式智能交通解决方案。

废话少说BATTMD哪个公司不是吹的天花乱坠&＃xff0c;直接看工资

校招

SP代表special offer

SSP的offer级别还在SP之上

一般情况下薪资专栏中的18*15

是指1.8w一个月&＃xff0c;一年总共15个月

其中15一般是13个月工资&＃xff0c;包括2个月的年终奖

简单科普结束以后我们来看看数据吧

这是硕士的薪资&＃xff0c;本科的自行减去1-2k&＃xff0c;测试岗也是从研发减去1-2k。

社招

薪资方面呢&＃xff0c;在BATTMD中不算很有竞争力&＃xff0c;但是今年还是涨了不少&＃xff0c;算是很有诚意&＃xff0c;适合喜欢所谓“技术”以及没有更好选择的同学去。

二、对公司的评价

产品之神俞军在移动互联网前夕走了&＃xff0c;百度在10-20掉队了&＃xff0c;这是不可否认的事实。但是最近两年&＃xff0c;百度一直在改变&＃xff0c;押宝在无人车上。去年股票也确实表现不错&＃xff0c;暂时可以坚持下去。

市值&＃xff1a;1145亿美元&＃xff08;比去年翻了不止一倍&＃xff0c;之前还以为他凉凉了&＃xff09;

三、面试过程

1&＃xff09;如何判断链表是否有环&＃xff1f;

像模像样的要我现场写了一遍&＃xff0c;说了一遍思路。

为了表示给定链表中的环&＃xff0c;我们使用整数 pos 来表示链表尾连接到链表中的位置&＃xff08;索引从 0 开始&＃xff09;。 如果 pos 是 -1&＃xff0c;则在该链表中没有环。

示例 1&＃xff1a;

输入&＃xff1a;head &＃61; [3,2,0,-4], pos &＃61; 1
输出&＃xff1a;true
解释&＃xff1a;链表中有一个环&＃xff0c;其尾部连接到第二个节点。

示例 2&＃xff1a;

输入&＃xff1a;head &＃61; [1], pos &＃61; -1
输出&＃xff1a;false
解释&＃xff1a;链表中没有环。

进阶&＃xff1a;

你能用 O(1)&＃xff08;即&＃xff0c;常量&＃xff09;内存解决此问题吗&＃xff1f;

思路&＃xff1a;首先我们要明白&＃xff0c;链表不可能出现这种情况&＃xff1a;

因为一个结点只有一个指针&＃xff0c;所以链表只可能向实例一那样&＃xff0c;在末尾出现一个环。

慢指针一次一步&＃xff0c;快指针一次两步。能相遇就是有环&＃xff0c;反之没有环。就像操场跑步&＃xff0c;跑的快的总有一天可以追慢的一圈&＃xff0c;相遇。

/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val &＃61; x;* next &＃61; null;* }* }*/
public class Solution {public boolean hasCycle(ListNode head) {if (head &＃61;&＃61; null || head.next &＃61;&＃61; null) {return false;}ListNode slow &＃61; head;ListNode fast &＃61; head.next;while (slow !&＃61; fast) {if (fast &＃61;&＃61; null || fast.next &＃61;&＃61; null) {return false;}slow &＃61; slow.next;fast &＃61; fast.next.next;}return true;}
}

那么&＃xff0c;这对于懂算法的人来说可能是烂大街的问题&＃xff0c;有些人可能不屑于看了&＃xff0c;那么&＃xff0c;第二个问题来了&＃xff1a;如果让那个快指针一次走三步&＃xff0c;还能不能做正确的答案呢&＃xff1f;一次四步呢&＃xff1f;五步呢&＃xff1f;

如果看的人多&＃xff0c;我会在下一期公布答案哈哈&＃xff0c;大家不要以为应试被题就可以过关。

2&＃xff09;介绍一下堆这种数据结构

大根堆要求

①根节点的关键字既大于或等于左子树的关键字值&＃xff0c;又大于或等于右子树的关键字值。

②为完全二叉树。

注意这是递归定义的。

对于大根小根堆&＃xff0c;递归定义&＃xff0c;实现&＃xff0c;空间复杂度&＃xff0c;各种操作的时间复杂度&＃xff0c;真实写二叉树的情况和数组模拟的情况都要会。

有人要问了&＃xff0c;会这些算法有啥用&＃xff1f;其实Java的优先队列就是堆结构。八大排序之一的堆排序也是数组上堆结构&＃xff0c;面试官让我手动实现一个&＃xff0c;以下是实现。

/*
&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;
功能:堆排序
输入:数组名称(也就是数组首地址)、数组中元素个数
注&＃xff1a;画画
&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;
*/
/*
功能:建堆
输入:数组名称(也就是数组首地址)、参与建堆元素的个数、从第几个元素开始
*/
void sift(int *x, int n, int s)
{int t, k, j;t &＃61; *(x&＃43;s); /*暂存开始元素*/k &＃61; s; /*开始元素下标*/j &＃61; 2*k &＃43; 1; /*左子树元素下标*/while (j}
/*
功能:堆排序
输入:数组名称(也就是数组首地址)、数组中元素个数
注&＃xff1a;** ** - * ** * *
建堆时&＃xff0c;从从后往前第一个非叶子节点开始调整&＃xff0c;也就是“-”符号的位置
*/
void heap_sort(int *x, int n)
{int i, k, t;
//int *p;for (i&＃61;n/2-1; i>&＃61;0; i--){sift(x,n,i); /*初始建堆*/}for (k&＃61;n-1; k>&＃61;1; k--){t &＃61; *(x&＃43;0); /*堆顶放到最后*/*(x&＃43;0) &＃61; *(x&＃43;k);*(x&＃43;k) &＃61; t;sift(x,k,0); /*剩下的数再建堆*/}
}


3&＃xff09;排序知道哪些&＃xff1f;来介绍介绍&＃xff1f;

答&＃xff1a;全知道&＃xff0c;全会写&＃xff0c;然后只说了冒泡的所有思路和优化、和快排BFPRT就被叫停了。我就把所有排序介绍和实现分享给大家。

全排序

一面结束&＃xff0c;面试小哥表示对我很满意&＃xff0c;说马上让另外一个人二面。

二面&＃xff1a;

二面小哥说&＃xff0c;一面说你算法贼强&＃xff0c;咱们这次就不聊算法了&＃xff0c;说说项目。

4)看我项目里用了redis&＃xff0c;就问redis都有哪些数据结构。

我说有string、list、hash、set、zset。

问&＃xff1a;你说的这些Java以及其他语言基本也都有&＃xff0c;你说了解redis&＃xff0c;那这些数据结构到底是不是快&＃xff1f;咋实现的呢&＃xff1f;

我举例子说了一下&＃xff1a;

• 1&＃xff09; 字符串

redis并未使用传统的c语言字符串表示&＃xff0c;它自己构建了一种简单的动态字符串抽象类型。

当需要一个可以被修改的字符串时&＃xff0c;redis就会使用自己实现的SDS&＃xff08;simple dynamic string&＃xff09;。比如在redis数据库里&＃xff0c;包含字符串的键值对底层都是SDS实现的&＃xff0c;不止如此&＃xff0c;SDS还被用作缓冲区&＃xff08;buffer&＃xff09;&＃xff1a;比如AOF模块中的AOF缓冲区以及客户端状态中的输入缓冲区。

下面来具体看一下sds的实现&＃xff1a;

1. struct sdshdr

2. {

3. int len;//buf已使用字节数量&＃xff08;保存的字符串长度&＃xff09;

4. int free;//未使用的字节数量

5. char buf[];//用来保存字符串的字节数组

6. };

sds遵循c中字符串以&＃39;\0&＃39;结尾的惯例&＃xff0c;这一字节的空间不算在len之内。

这样的好处是&＃xff0c;我们可以直接重用c中的一部分函数。比如printf&＃xff1b;

    sds相对c的改进

    获取长度&＃xff1a;c字符串并不记录自身长度&＃xff0c;所以获取长度只能遍历一遍字符串&＃xff0c;redis直接读取len即可。

    缓冲区安全&＃xff1a;c字符串容易造成缓冲区溢出&＃xff0c;比如&＃xff1a;程序员没有分配足够的空间就执行拼接操作。而redis会先检查sds的空间是否满足所需要求&＃xff0c;如果不满足会自动扩充。

    内存分配&＃xff1a;由于c不记录字符串长度&＃xff0c;对于包含了n个字符的字符串&＃xff0c;底层总是一个长度n&＃43;1的数组&＃xff0c;每一次长度变化&＃xff0c;总是要对这个数组进行一次内存重新分配的操作。因为内存分配涉及复杂算法并且可能需要执行系统调用&＃xff0c;所以它通常是比较耗时的操作。   

    redis内存分配&＃xff1a;

1、空间预分配&＃xff1a;如果修改后大小小于1MB&＃xff0c;程序分配和len大小一样的未使用空间&＃xff0c;如果修改后大于1MB&＃xff0c;程序分配  1MB的未使用空间。修改长度时检查&＃xff0c;够的话就直接使用未使用空间&＃xff0c;不用再分配。 

2、惰性空间释放&＃xff1a;字符串缩短时不需要释放空间&＃xff0c;用free记录即可&＃xff0c;留作以后使用。

    二进制安全

c字符串除了末尾外&＃xff0c;不能包含空字符&＃xff0c;否则程序读到空字符会误以为是结尾&＃xff0c;这就限制了c字符串只能保存文本&＃xff0c;二进制文件就不能保存了。

而redis字符串都是二进制安全的&＃xff0c;因为有len来记录长度。

这就是redis中string的实现和要点&＃xff0c;我大概都给他讲了一遍。然后他说你不用说了&＃xff0c;又说到算法数据结构了&＃xff0c;咱们聊点别的。

5&＃xff09;聊点实际的吧&＃xff0c;你一直在吹redis&＃xff0c;知道用redis会给你带来什么问题吗&＃xff1f;

我有点懵&＃xff0c;就给他说nosql和传动数据库的区别之类的&＃xff0c;然后他说你不要给我说这些比较&＃xff0c;举个例子&＃xff0c;缓存雪崩听说过吗&＃xff1f;我就明白他想聊什么了&＃xff0c;又给他说了说以下内容。

缓存穿透

一般的缓存系统&＃xff0c;都是按照key去缓存查询&＃xff0c;如果不存在对应的value&＃xff0c;就去后端系统查找&＃xff08;比如DB&＃xff09;。

一些恶意的请求会故意查询不存在的key,请求量很大&＃xff0c;就会对后端系统造成很大的压力。这就叫做缓存穿透。

如何避免&＃xff1f;

1&＃xff1a;对查询结果为空的情况也进行缓存&＃xff0c;这样&＃xff0c;再次访问时&＃xff0c;缓存层会直接返回空值。缓存时间设置短一点&＃xff0c;或者该key对应的数据insert了之后清理缓存。

2&＃xff1a;对一定不存在的key进行过滤。具体请看布隆过滤器

缓存击穿

是针对缓存中没有但数据库有的数据。

场景是&＃xff0c;当Key失效后&＃xff0c;假如瞬间突然涌入大量的请求&＃xff0c;来请求同一个Key&＃xff0c;这些请求不会命中Redis&＃xff0c;都会请求到DB&＃xff0c;导致数据库压力过大&＃xff0c;甚至扛不住&＃xff0c;挂掉。

解决办法

1、设置热点Key&＃xff0c;自动检测热点Key&＃xff0c;将热点Key的过期时间加大或者设置为永不过期&＃xff0c;或者设置为逻辑上永不过期

2、加互斥锁。当发现没有命中Redis&＃xff0c;去查数据库的时候&＃xff0c;在执行更新缓存的操作上加锁&＃xff0c;当一个线程访问时&＃xff0c;其它线程等待&＃xff0c;这个线程访问过后&＃xff0c;缓存中的数据会被重建&＃xff0c;这样其他线程就可以从缓存中取值。

缓存雪崩

是指大量Key同时失效&＃xff0c;对这些Key的请求又会打到DB上&＃xff0c;同样会导致数据库压力过大甚至挂掉。

解决办法

1&＃xff09;让Key的失效时间分散开&＃xff0c;可以在统一的失效时间上再加一个随机值&＃xff0c;或者使用更高级的算法分散失效时间。

2&＃xff09;构建多个redis实例&＃xff0c;个别节点挂了还有别的可以用。

3&＃xff09;多级缓存&＃xff1a;比如增加本地缓存&＃xff0c;减小redis压力。

4&＃xff09;对存储层增加限流措施&＃xff0c;当请求超出限制&＃xff0c;提供降级服务&＃xff08;一般就是返回错误即可&＃xff09;

他说作为一个学生&＃xff0c;知道这些知识就可以了&＃xff0c;对我比较满意&＃xff0c;说让三面。

三面面试官看样子是某个领导&＃xff0c;问的比较随意。

6&＃xff09;输入网址到看到网页的过程

答&＃xff1a;&＃xff08;能多细就多细&＃xff0c;你背答案估计就死了&＃xff0c;要理解&＃xff09;域名解析 --> TCP3次握手 --> 发http请求 --> 响应http请求&＃xff0c;浏览器得到html代码 --> 浏览器解析代码&＃xff0c;请求html代码中的资源&＃xff08;js、css、图片等&＃xff09; --> 浏览器对页面进行渲染呈现给用户

7&＃xff09;让手写快排&＃xff08;我寻思真就没别的可问了呗&＃xff09;

然后就结束了。

四、感受

感觉总体难度一般&＃xff0c;问链表环问题改成三四步&＃xff0c;我是没想到的&＃xff0c;证明面试官有点东西。二面面试官给我的感觉应该也读过redis源码&＃xff0c;我记录的应该不全&＃xff0c;俩人这方面谈的挺投机。整体是挺好的体验&＃xff0c;可能因为也是学长内推的关系&＃xff0c;三次面试都像聊天一样就过去了。手写算法也基本没卡壳&＃xff0c;平时因为很重视代码风格。自以为手撸代码他们也比较满意。结果就是通过所有面试发了offer&＃xff0c;最后没去。