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

清疚 2022-11-11 05:09 169阅读 0赞

[![百度LOGO][LOGO]][LOGO_LOGO]

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

# **一、公司的简介** #

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

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

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

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

**废话少说BATTMD哪个公司不是吹的天花乱坠，直接看工资**

**校招**

SP代表special offer

SSP的offer级别还在SP之上

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

是指1.8w一个月，一年总共15个月

其中15一般是13个月工资，包括2个月的年终奖

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 1][]

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

**社招**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 2][]

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

# **二、对公司的评价** #

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

**市值：1145亿美元（比去年翻了不止一倍，之前还以为他凉凉了）**

# **三、面试过程** #

**1）如何判断链表是否有环？**

像模像样的要我现场写了一遍，说了一遍思路。

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

示例 1：

输入：head = \[3,2,0,-4\], pos = 1  
输出：true  
解释：链表中有一个环，其尾部连接到第二个节点。

![20191207150640653.png][]

示例 2：

输入：head = \[1\], pos = -1  
输出：false  
解释：链表中没有环。

![20191207150711445.png][]

**进阶：**

你能用 *O(1)*（即，常量）内存解决此问题吗？

思路：首先我们要明白，链表不可能出现这种情况：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 3][]

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

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

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

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

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

**2）介绍一下堆这种数据结构**

大根堆要求

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

②为[完全二叉树][Link 14]。

注意这是递归定义的。

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

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

/*
    ================================================
    功能:堆排序
    输入:数组名称(也就是数组首地址)、数组中元素个数
    注：画画
    ================================================
    */
    /*
    功能:建堆
    输入:数组名称(也就是数组首地址)、参与建堆元素的个数、从第几个元素开始
    */
    void sift(int *x, int n, int s)
    {
        int t, k, j;
        t = *(x+s); /*暂存开始元素*/
        k = s;   /*开始元素下标*/
        j = 2*k + 1; /*左子树元素下标*/
        while (j<n)
        {
            if (j<n-1 && *(x+j) < *(x+j+1))/*判断是否存在右孩子，并且右孩子比左孩子大，成立，就把j换为右孩子*/
            {
                j++;
            }
            if (t<*(x+j)) /*调整*/
            {
                *(x+k) = *(x+j);
                k = j; /*调整后,开始元素也随之调整*/
                j = 2*k + 1;
            }
            else /*没有需要调整了,已经是个堆了,退出循环。*/
            {
                break;
            }
        }
        *(x+k) = t; /*开始元素放到它正确位置*/
    }
    /*
    功能:堆排序
    输入:数组名称(也就是数组首地址)、数组中元素个数
    注：
                *
             *     *
           *   -  *   *
          * * * 
    建堆时，从从后往前第一个非叶子节点开始调整，也就是“-”符号的位置
    */
    void heap_sort(int *x, int n)
    {
        int i, k, t;
    //int *p;
        for (i=n/2-1; i>=0; i--)
        {
            sift(x,n,i); /*初始建堆*/
        }
        for (k=n-1; k>=1; k--)
        {
            t = *(x+0); /*堆顶放到最后*/
            *(x+0) = *(x+k);
            *(x+k) = t;
            sift(x,k,0); /*剩下的数再建堆*/
        }
    }

**3）排序知道哪些？来介绍介绍？**

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

[全排序][Link 15]

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

二面：

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

**4)看我项目里用了redis，就问redis都有哪些数据结构。**

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

问：你说的这些Java以及其他语言基本也都有，你说了解redis，那这些数据结构到底是不是快？咋实现的呢？

我举例子说了一下：

*  **1） 字符串**

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

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

下面来具体看一下sds的实现：

1.  `struct sdshdr`
2.  `{`
3.  `int len;//buf已使用字节数量（保存的字符串长度）`
4.  `int free;//未使用的字节数量`
5.  `char buf[];//用来保存字符串的字节数组`
6.  `};`

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

这样的好处是，我们可以直接重用c中的一部分函数。比如printf；

**sds相对c的改进**

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

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

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

**redis内存分配：**

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

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

**二进制安全**

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

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

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

**5）聊点实际的吧，你一直在吹redis，知道用redis会给你带来什么问题吗？**

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

**缓存穿透**

一般的缓存系统，都是按照key去缓存查询，如果不存在对应的value，就去后端系统查找（比如DB）。

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70][]

**如何避免？**

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

2：对一定不存在的key进行过滤。具体请看[布隆过滤器][Link 16]

**缓存击穿**

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

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

**解决办法**

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

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

**缓存雪崩**

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

**解决办法**

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

2）构建多个redis实例，个别节点挂了还有别的可以用。

3）多级缓存：比如增加本地缓存，减小redis压力。

4）对存储层增加限流措施，当请求超出限制，提供降级服务（一般就是返回错误即可）

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

三面面试官看样子是某个领导，问的比较随意。

**6）输入网址到看到网页的过程**

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

**7）让手写快排（我寻思真就没别的可问了呗）**

然后就结束了。

# 四、感受 #

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

[LOGO]: https://img-blog.csdnimg.cn/img_convert/1fc8261f0c68d53fb03419cc0e57139c.png
[LOGO_LOGO]: /images/20221022/ad2fa16343b64a1780734787ac4bc93d.png
[Link 1]: https://baike.baidu.com/item/%E4%B8%AD%E5%85%B3%E6%9D%91/170054
[Link 2]: https://baike.baidu.com/item/%E6%9D%8E%E5%BD%A6%E5%AE%8F/125160
[Link 3]: https://baike.baidu.com/item/%E8%B6%85%E9%93%BE%E5%88%86%E6%9E%90/10661939
[Link 4]: https://baike.baidu.com/item/%E6%90%9C%E7%B4%A2%E5%BC%95%E6%93%8E/104812
[App]: https://baike.baidu.com/item/%E7%99%BE%E5%BA%A6App/8548470
[Link 5]: https://baike.baidu.com/item/%E7%99%BE%E5%AE%B6%E5%8F%B7/19730924
[Link 6]: https://baike.baidu.com/item/%E7%99%BE%E5%BA%A6%E6%99%BA%E8%83%BD%E5%B0%8F%E7%A8%8B%E5%BA%8F/22603550
[Link 7]: https://baike.baidu.com/item/%E7%99%BE%E5%BA%A6%E7%9F%A5%E9%81%93/92140
[Link 8]: https://baike.baidu.com/item/%E7%99%BE%E5%BA%A6%E7%99%BE%E7%A7%91/85895
[Link 9]: https://baike.baidu.com/item/%E7%99%BE%E5%BA%A6%E6%96%87%E5%BA%93/4928294
[Link 10]: https://baike.baidu.com/item/%E7%99%BE%E5%BA%A6%E5%A4%A7%E8%84%91/13333434
[Link 11]: https://baike.baidu.com/item/%E9%A3%9E%E6%A1%A8/23472642
[Link 12]: https://baike.baidu.com/item/%E7%99%BE%E5%BA%A6%E6%99%BA%E8%83%BD%E4%BA%91/23409424
[Link 13]: https://baike.baidu.com/item/%E5%B0%8F%E5%BA%A6/23331497
[Apollo]: https://baike.baidu.com/item/Apollo/20625961
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70]: /images/20221022/8f96788d02504d81bb76209cb12eab1a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 1]: /images/20221022/ff75793273eb4bdf9921f40e3658dd42.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210223153738237.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2,size_16,color_FFFFFF,t_70
[20191207150640653.png]: https://img-blog.csdnimg.cn/20191207150640653.png
[20191207150711445.png]: https://img-blog.csdnimg.cn/20191207150711445.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210223161521134.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2,size_16,color_FFFFFF,t_70
[Link 14]: https://baike.baidu.com/item/%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91/7773232
[Link 15]: https://blog.csdn.net/hebtu666/article/details/81434236
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2019101118452938.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70
[Link 16]: https://blog.csdn.net/hebtu666/article/details/92177826