每日大厂面试题分享

2024.04.27拼多多二面

  • 拼多多
  • 二面
大约 17 分钟全民制作人ikun

2024.04.27拼多多二面

1.索引的数据结构

在MySQL中，索引主要采用B+树这种数据结构。B+Tree 是一种多叉树，叶子节点才存放数据，非叶子节点只存放索引，而且每个节点里的数据是按主键顺序存放的。每一层父节点的索引值都会出现在下层子节点的索引值中，因此在叶子节点中，包括了所有的索引值信息，并且每一个叶子节点都有两个指针，分别指向下一个叶子节点和上一个叶子节点，形成一个双向链表。

  1. 数据结构:

    • B+树是一种平衡多叉树,每个节点包含多个关键字和指向子节点的指针。
    • 所有的数据记录都存储在叶子节点,内部节点只存储索引信息,用于快速定位记录。

  2. 特点:

    • B+树具有自平衡的特性,保证查找、插入和删除的时间复杂度为O(logN)。
    • 所有的数据记录都存储在叶子节点上,内部节点只存储索引信息,查找效率高。
    • 每个叶子节点都用链表连接起来,方便范围查找和排序操作。
    • 内部节点不存储数据,只存储索引信息,因此B+树的空间利用率更高。

  3. 索引维护:

    • 当数据发生变化时,B+树会自动进行节点分裂、合并等操作来维持平衡。
    • B+树的重组操作一般不会影响上层节点,因此更新操作的性能较好。

  4. 查询性能:

    • B+树的查找效率非常高,时间复杂度为O(logN)。
    • 范围查询和排序操作也能够高效地完成,因为叶子节点之间用链表相连。

2.为什么要用B+树？

链接open in new window

选择使用 B+ 树作为索引数据结构主要有以下几个原因:

  1. 磁盘 I/O 操作次数少:

    • B+ 树的非叶子节点只存索引,不存实际数据,因此在同样节点数的情况下,B+ 树的树高比 B 树低,访问叶子节点需要的磁盘 I/O 次数更少。

  2. 插入删除效率高:

    • B+ 树有大量冗余节点,删除节点时可以直接从叶子节点删除,不需要复杂的树平衡操作,效率更高。
    • 插入新节点时,也只需要在局部进行节点分裂,不会导致整棵树的大量变动。

  3. 范围查询效率高:

    • B+ 树的所有叶子节点用链表连接,方便进行范围查询,不像 B 树需要遍历多个节点。

  4. 适合磁盘存储:

    • MySQL 数据存储在磁盘上,B+ 树的矮胖结构能更好地利用磁盘读写的特点,减少磁盘 I/O 次数,提高查询效率。

从二分查找到 B+ 树的演进过程:

  1. 二分查找

    • 二分查找是最基本的查找算法,能在有序数组上快速定位目标数据,时间复杂度为 O(logn)。
    • 但数组有固定大小,插入新元素需要整体移动,效率低下,不适合作为索引结构使用。

  2. 二叉查找树

    • 为了解决数组插入效率低的问题,二叉查找树应运而生。
    • 它通过二叉树的结构保持有序,可以快速查找,时间复杂度仍为 O(logn)。
    • 但在最坏情况下会退化成链表,查找性能下降到 O(n)。

  3. 自平衡二叉树

    • 为了解决二叉查找树退化的问题,提出了 AVL 树、红黑树等自平衡二叉树。
    • 通过旋转等操作保持树的平衡,时间复杂度仍为 O(logn)。
    • 但二叉树的结构仍然限制了每个节点最多只有2个子节点,树高较高。

  4. B 树

    • B 树放宽了每个节点的子节点限制,允许更多子节点,从而降低了树的高度。
    • 在磁盘环境下,B 树的矮胖结构可以减少磁盘 I/O 操作,提升查询性能。

  5. B+ 树

    • B+ 树在 B 树的基础上做了进一步优化:
    • 非叶子节点只存索引,叶子节点存实际数据,进一步减少磁盘 I/O。
    • 叶子节点之间用链表连接,方便范围查询。
    • 插入删除操作也更简单高效。

3.为什么B+树要比二叉树好

  1. 更小的树高:

    • B+ 树是多叉树,每个节点可以有更多的子节点。
    • 在相同的节点数量下,B+ 树的树高会比二叉树小,访问叶子节点需要的磁盘 I/O 次数更少。

  2. 更高的查询性能:

    • 由于更小的树高,B+ 树的单点查询性能要优于二叉树,接近 O(1)。
    • 同时 B+ 树的所有数据都集中在叶子节点,查询过程更加简单高效。

  3. 更好的范围查询:

    • B+ 树的叶子节点通过链表连接,非常利于范围查询。
    • 二叉树需要遍历多个节点来完成范围查询,效率较低。

  4. 更高的插入删除效率:

    • B+ 树有大量冗余节点,插入删除时只需要局部调整,不会导致整棵树的大规模变动。
    • 而二叉树的插入删除可能会引发复杂的树平衡操作。

  5. 更适合磁盘存储:

    • 数据库索引通常存储在磁盘上,B+ 树的矮胖结构更能利用磁盘的特点,减少磁盘 I/O。
    • 二叉树由于树高较高,在磁盘环境下查询性能会大幅下降。

4.什么是线程安全？

参考链接open in new window

线程安全和不安全是在多线程环境下对于同一份数据的访问是否能够保证其正确性和一致性的描述。

  • 线程安全指的是在多线程环境下，对于同一份数据，不管有多少个线程同时访问，都能保证这份数据的正确性和一致性。
  • 线程不安全则表示在多线程环境下，对于同一份数据，多个线程同时访问时可能会导致数据混乱、错误或者丢失。

5.哪些方法保证线程安全？

线程不安全的原因主要有三个：

  1. 原子性：一个或者多个操作在CPU执行过程中被中断。
  2. 可见性：一个线程对象共享变量的修改，导致另一个线程不能立即看到。
  3. 有序性：程序执行的顺序没有按照代码的先后顺序执行。

如何保证：

  1. 保证原子性:
    • 使用Atomic类,如AtomicInteger等,它们通过CAS操作保证了原子性。
    • 使用synchronized关键字加锁,确保临界区代码的原子执行。
  2. 保证可见性:
    • 使用volatile关键字修饰共享变量,确保一个线程对变量的修改能被其他线程立即感知。
    • 使用synchronized关键字或Lock接口加锁,确保线程对共享资源的访问是可见的。
  3. 保证有序性:
    • 使用synchronized关键字或Lock接口加锁,确保线程访问共享资源的顺序与代码编写顺序一致。
    • 合理使用final关键字修饰不可变对象,降低指令重排对程序执行顺序的影响。

6.乐观锁和悲观锁

  1. 悲观锁:
    • 悲观锁总是假设最坏的情况,认为共享资源每次被访问的时候都会出现问题(比如数据被修改)。
    • 所以每次在获取资源前都会上锁,确保该资源在被使用的过程中不会被其他线程修改。
    • 典型的实现就是 synchronized 关键字和 ReentrantLock。
  2. 乐观锁:
    • 乐观锁总是假设最好的情况,认为共享资源在被访问时不会出现问题。
    • 所以不会上锁,而是在更新数据的时候去判断在此期间是否有其他线程更新了这个数据。
    • 如果没有其他线程更新数据,则直接更新,如果有其他线程更新了,则进行回滚等操作。
    • 乐观锁通常使用版本号机制或CAS算法实现。如Java中的 AtomicInteger、LongAdder等。

主要区别:

  1. 加锁方式不同:悲观锁每次使用资源前都会加锁,乐观锁不加锁。
  2. 适用场景不同:悲观锁适用于写并发较多的场景,乐观锁适用于读并发较多的场景。
  3. 实现方式不同:悲观锁通常使用synchronized或ReentrantLock实现,乐观锁通常使用版本号机制或CAS算法实现。

7.synchonized底层原理

synchronized 关键字的底层实现原理包括以下几个方面:

  1. monitorenter 和 monitorexit 指令
    • synchronized 同步代码块的实现使用的是 monitorenter 和 monitorexit 指令。
    • monitorenter 指令指向同步代码块的开始位置,monitorexit 指令则指明同步代码块的结束位置。
    • 执行 monitorenter 时,线程试图获取对象的锁,也就是获取对象监视器 monitor 的持有权。
    • 执行 monitorexit 时,线程释放对象的锁,也就是释放对象监视器 monitor 的持有权。
  2. 对象监视器 monitor
    • 每个Java对象都可以关联一个 monitor 对象,monitor 对象存在于Java虚拟机的内存中。
    • 线程在获取 synchronized 锁时,实际获取的就是对象监视器 monitor 的持有权。
    • 当一个线程请求获取一个对象的锁时,Java虚拟机会检查该对象是否有 monitor 与之关联。
  3. 锁的获取
    • 当一个线程执行到 monitorenter 指令时,会尝试获取对象的锁:
    • 如果对象没有 monitor 被其他线程占用,该线程会成功持有该 monitor,计数器值为1。
    • 如果 monitor 已经被其他线程占有,那这个线程会阻塞,进入 EntryList 队列,等待其他线程释放 monitor。
  4. 锁的释放
    • 当一个线程执行 monitorexit 指令时,它will释放它所持有的 monitor 的所有权。
    • 如果当前线程成功持有了 monitor 的所有权,那么monitor 的计数器会减1,如果计数器的值变为0,则释放该 monitor。
    • 如果当前线程未成功持有 monitor 的所有权,那么执行 monitorexit 就会抛出 IllegalMonitorStateException 异常。

8.抢占锁的过程

参考链接open in new window

抢占锁的过程可以简要描述如下：

  • 当一个线程尝试抢占锁时，它会首先尝试获取锁。如果成功获取到锁，线程就会进入临界区执行相关代码，执行完毕后会释放锁。如果线程没有成功抢占到锁，它会被加入阻塞队列中进行阻塞等待。若线程抢占到了锁，并且在临界区执行了wait()方法，那么线程会进入等待队列等待，同时会释放锁，让其他线程有机会竞争锁。

  • 在抢占锁的过程中，当调用notify()方法时，会按照先入先出的顺序将等待队列中的第一个线程唤醒并放入阻塞队列中等待执行。而调用notifyAll()则会唤醒等待队列中的所有线程，它们将直接竞争锁而不会被放入阻塞队列。

  • 当线程成功抢占锁后，会将owner指向当前线程，并增加重入次数。在重入锁时，每次重入会使重入次数加一。释放锁时，每次释放锁都会使重入次数减一，当重入次数减为0时，owner将被置为null（释放锁）。如果是通过wait()方法释放锁，则重入次数会被直接置为0，并释放锁。

  • notifyAll()会逐个唤醒等待队列中的线程，并将它们加入执行队列entryList中。

  • 可重入机制允许一个线程在持有锁的情况下再次进入同一把锁对象的同步块，而无需重新抢占锁，直接进入临界区。这种设计的目的是为了避免死锁情况，在Java中的锁都是可重入的。

9.ReentrantLock的实现原理

参考链接open in new window

好的，面试官，关于这个问题，我会从这几个方面来回答。

  • 什么是ReentrantLock
  • ReentrantLock的特性
  • ReentrantLock的实现原理

首先，ReentrantLock是一种可重入的排它锁，主要用来解决多线程对共享资源竞争的问题。

它的核心特性有几个：

  1. 它支持可重入，也就是获得锁的线程在释放锁之前再次去竞争同一把锁的时候，不需要加锁就可以直接访问。
  2. 它支持公平和非公平特性
  3. 它提供了阻塞竞争锁和非阻塞竞争锁的两种方法，分别是lock()和tryLock()。

然后，ReentrantLock的底层实现有几个非常关键的技术。

  1. 锁的竞争，ReentrantLock是通过互斥变量，使用CAS机制来实现的。
  2. 没有竞争到锁的线程，使用了AbstractQueuedSynchronizer这样一个队列同步器来存储，底层是通过双向链表来实现的。当锁被释放之后，会从AQS队列里面的头部唤醒下一个等待锁的线程。
  3. 公平和非公平的特性，主要是体现在竞争锁的时候，是否需要判断AQS队列存在等待中的线程。
  4. 最后，关于锁的重入特性，在AQS里面有一个成员变量来保存当前获得锁的线程，当同一个线程下次再来竞争锁的时候，就不会去走锁竞争的逻辑，而是直接增加重入次数。

10.为什么用CAS

CAS（Compare and swap），即比较并交换。我们平时所说的自旋锁或乐观锁，其中的核心操作实现就是CAS。

  1. 保证原子操作:
    • CAS 可以用于保证多线程环境下的原子操作,避免像 i++ 这样的操作被干扰。
    • 原子操作是最小不可拆分的操作,操作一旦开始就不能被中断,直到操作完成。
  2. 实现高性能的自旋锁:
    • 与使用锁或 synchronized 关键字相比,CAS 利用 CPU 指令实现,性能更高。
    • CAS 实现自旋锁,通过循环尝试 CAS 操作,直到操作成功退出循环,这样避免了加锁和解锁的开销。
  3. 无锁并发:
    • CAS 可以实现无锁并发,减少了锁竞争带来的性能损耗。
  4. 广泛应用:
    • CAS 在 JDK 中被广泛使用,如 ConcurrentHashMap 等,体现了它在并发编程中的重要性。

11.为什么用Spring

  1. 轻量级 Spring框架在透明度和大小方面都是轻量级的,与EJB容器相比更轻,可以在资源有限的计算机上开发和运行应用程序。
  2. 控制反转 (IoC) Spring通过控制反转(IoC)实现了松耦合,对象依赖关系由Spring容器管理,而不是由对象自己创建或查找依赖对象。
  3. 面向切面的编程 (AOP) Spring提供了丰富的AOP支持,允许将应用程序的业务逻辑与系统级服务(如审计、事务管理等)分离。
  4. 容器 Spring框架负责创建和管理应用程序对象的配置和生命周期。
  5. 组织良好的Web框架 Spring提供了一个优秀的Web MVC框架,是Struts等框架的一个很好替代方案。它让应用程序的开发变得更加清晰、可管理和易于测试。

12.除了Spring还有其他的框架吗

除了Spring还有微服务框架(Spring Boot、Quarkus、Micronaut)、Web框架(JSF、Struts、Play Framework、Spark Java)、ORM框架(Hibernate、MyBatis)、测试框架(JUnit、TestNG、Mockito)、安全框架(Spring Security、Apache Shiro)、数据传输/整合框架(Apache Kafka、Apache Camel、RxJava)、批处理框架(Spring Batch、Apache Spark)等。

13.Spring MVC包括哪些流程？

  1. 整个过程开始于客户端发出的一个HTTP请求,Web应用服务器接收到这个请求。如果匹配DispatcherServlet的请求映射路径,则Web容器将该请求转交给前端控制器DispatcherServlet处理。
  2. DispatcherServlet接收到这个请求后,将根据请求的信息(包括URL、HTTP方法、请求报文头、请求参数、Cookie等)及HandlerMapping的配置找到处理请求的处理器Handler,并且返回一个执行链。
  3. 当DispatcherServlet根据HandlerMapping得到对应当前请求的Handler后,通过HandlerAdapter对Handler进行封装,再以统一的适配器接口调用Handler。
  4. 处理器完成业务逻辑的处理后,将返回一个ModelAndView给DispatcherServlet,ModelAndView包含了视图逻辑名和模型数据信息。
  5. ModelAndView中包含的是"逻辑视图名"而非真正的视图对象,DispatcherServlet借由ViewResolver请求解析视图,完成逻辑视图名到真实视图对象的解析工作。
  6. 当得到真实的视图对象View后,DispatcherServlet就使用这个View对象对ModelAndView中的模型数据进行视图渲染。
  7. 最终客户端得到的响应消息可能是一个普通的HTML页面,也可能是一个XML或JSON串,甚至是一张图片或一个PDF文档等不同的媒体形式。

14.Spring boot是什么

Spring Boot 是一个建立在 Spring 框架之上的项目,它旨在简化 Spring 应用程序的开发和配置过程。它的主要特点包括:

  1. 自动配置: Spring Boot 会根据添加的依赖自动配置 Spring 应用程序,大大减少了手动配置的工作量。

  2. 嵌入式 Web 服务器: Spring Boot 可以将应用程序打包成一个可执行的 JAR 文件,内置了 Tomcat、Jetty 或 Undertow 等 Web 服务器,无需单独部署 Web 服务器。

  3. starter 依赖: Spring Boot 提供了许多"Starter"依赖项,它们可以帮助你快速整合常见的库,如 Spring MVC、Spring Data、Spring Security 等。

  4. 健康检查和指标收集: Spring Boot 提供了一个 Actuator 模块,允许你监控和管理应用程序,如健康检查、指标收集等。

  5. 无xml配置: Spring Boot 大量使用约定优于配置的原则,最小化了 XML 配置的需求。

总之,Spring Boot 通过简化配置、提供嵌入式 Web 服务器和自动配置等功能,大大提高了 Spring 应用程序的开发效率和部署便利性。它是 Spring 框架的一个重要补充。

手撕：排序链表 时间复杂度，空间复杂度，为什么

选择排序：O(n2)O(n^2)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if( head==nullptr) return head;
        ListNode* virtualNode =new ListNode(0);
        virtualNode->next=head;
        ListNode* last=head; //已经排好序的最后一个节点
        ListNode* cur=head->next; // 当前要排序哪个节点
        while(cur!=nullptr){
            if(last->val<=cur->val){
                last=last->next;
            }else{
                ListNode* t=virtualNode; //需要插入到哪个点后面
                while( t->next->val <= cur->val)  t=t->next;
                last->next=cur->next;
                cur->next=t->next;
                t->next=cur;
            }
            cur=last->next;
        }
        return virtualNode->next;
    }
};
欢迎您的参与
Copyright © 2024 全民制作人ikun