每日大厂面试题分享

2024.04.28美团后端日常一面

  • 美团
  • 一面
大约 14 分钟全民制作人ikun

2024.04.28美团后端日常一面

1、HashMap 原理、为什么线程不安全、红黑树的结构

  1. HashMap原理:

    • HashMap使用哈希表实现,其中包含一个Entry数组(桶数组)作为数据存储结构。
    • 当向HashMap中添加一个Key-Value对时,会根据Key的哈希码计算出数组索引,然后将Key-Value对添加到对应索引的链表中。
    • HashMap通过拉链法解决哈希冲突,即当两个Key的哈希值相同时,会将它们以链表的形式存储在同一个桶中。
    • 当桶中的链表长度超过阈值时,HashMap会将链表转换为红黑树,以提高查找效率。

  2. HashMap线程不安全:

    • 由于HashMap是非线程安全的,在多线程环境下可能会出现数据丢失或死循环的问题。
    • 主要问题出现在扩容rehash过程中,多个线程同时对HashMap进行扩容,可能会导致链表形成环形结构,造成死循环。
    • 此外,在put()、get()等方法中也可能出现并发修改异常(ConcurrentModificationException)。

  3. 红黑树结构:

    • 红黑树是一种自平衡二叉查找树,能够保证查找、插入、删除的时间复杂度为O(logn)。
    • 红黑树有以下特性:
      1. 每个节点要么是红色,要么是黑色。
      2. 根节点必须是黑色。
      3. 每个叶子节点(NIL节点)都是黑色。
      4. 如果一个节点是红色的,则它的子节点必须是黑色的。
      5. 从任一节点到其每个叶子节点的所有简单路径都包含相同数目的黑色节点。
    • 通过这些特性,红黑树能够很好地维持平衡,避免退化为链表,从而保证高效的查找性能。

2、ConcurrentHashMap 怎么保证线程安全、1.8 版本做了什么优化、为什么把 ReentrantLock 改成了 CAS + synchronized

  1. ConcurrentHashMap如何保证线程安全:

    • ConcurrentHashMap使用分段锁的机制来实现线程安全。
    • 它将底层的HashMap分成若干个Segment,每个Segment都有自己的锁。
    • 当一个线程访问ConcurrentHashMap的某个Segment时,只有这个Segment会被锁定,其他Segment不受影响,大大提高了并发性。
    • 在get操作时,ConcurrentHashMap不需要加锁,只需要读取对应Segment的HashEntry即可,提高了读取效率。

  2. ConcurrentHashMap 1.8版本的优化:

    • 1.8版本抛弃了分段锁的设计,改用CAS + synchronized来保证线程安全。
    • 采用了单一的 sizeCtl 字段来控制初始化和扩容,避免了分段锁的复杂度。
    • 使用CAS来更新 sizeCtl,大多数操作不需要加锁,只有真正需要修改数据结构时才需要加锁。
    • 当链表长度超过8时,会将链表转换为红黑树,提高查找效率。

  3. 为什么把ReentrantLock改为CAS + synchronized:

    • ReentrantLock相比synchronized有更高的并发性和灵活性,但是也有一定的性能开销。
    • CAS + synchronized的方式可以在大多数情况下避免使用ReentrantLock,减少了性能开销。
    • CAS操作是乐观锁,只有在数据没有被修改的情况下才会成功,可以减少不必要的锁竞争。
    • synchronized是悲观锁,当一个线程获取到锁时,其他线程必须等待,但是synchronized的性能已经得到了很大的优化。
    • 结合CAS和synchronized,可以在性能和线程安全之间达到较好的平衡。

3、hashcode 和 equals，只重写一个会有什么问题

equals相等的两个对象的hashCode也一定相等，但hashCode相等的两个对象不一定equals相等。

  • 重写了equals方法，不重写hashCode方法时，可能会出现equals方法返回为true，而hashCode方法却返回不同的结果。
  • 重写了 hashCode 方法,但是没有重写 equals 方法,会出现两个对象可能会通过 hashCode 的比较被认为是相等的,但是通过 equals 方法比较却返回 false。这种情况下,违背了 hashCode 和 equals 方法应该一致的原则。

4、最左匹配原则

联合索引 (a, b, c)，查询条件：①a= 1 and c = 2 and b = 3、②a = 1 and b > 2 and c =3

  • 最左匹配原则要求查询条件必须按照索引定义的顺序进行匹配,才能充分利用索引。
  • 第一个 不会失效，可以充分利用索引
  • 第二个可以匹配到a，后面失效

5、为什么用 B+ 树作为索引

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

  1. 查找效率高:
  • B+树是一种多叉平衡树,其查找时间复杂度为 O(log n),相比于二叉树,查找效率更高。
  • B+树的所有数据都存储在叶子节点,查找时只需要traversal到叶子节点即可,不需要回溯。
  1. 支持范围查找:
  • B+树的所有叶子节点用指针连接,形成有序链表,非常适合范围查找和排序操作。
  • 对于 B 树,只有叶子节点保存数据,内部节点仅存索引值,不适合范围查找。
  1. 磁盘友好:
  • B+树的内部节点只存储索引信息,不存储实际的数据,这样每个节点能容纳更多的索引,使得 B+树的分支因子更大,树高更低。
  • 更少的树高意味着查找过程中读取的磁盘块数更少,减少了磁盘 I/O,更适合用于操作系统的文件索引和数据库索引。
  1. 节省存储空间:
  • B+树的所有数据都存储在叶子节点,而内部节点只存储索引信息,不存储实际数据,相比于其他索引结构,可以大幅减少索引占用的存储空间。
  1. 支持高并发:
  • B+树进行数据插入和删除时,仅需要对局部进行调整,不会引起全局的调整,相比于 AVL 树,并发度更高。

6、事务隔离级别、可重复读解决了什么问题

读未提交、读已提交、可重复读、串行化。

可重复读解决了脏读和不可重复读的问题，没有解决幻读的问题。

7、MySQL 实现的可重复读怎么解决脏读和不可重复读问题

启动事务时生成一个 Read View，然后整个事务期间都在用这个 Read View，这样就保证了在事务期间读到的数据都是事务启动前的记录。

8、JVM 内存结构

img

JVM 内存结构包括以下几个主要部分:

  • 堆(Heap)：存放对象实例和数组,是垃圾回收的主要区域。
  • 方法区(Method Area)：存储类信息、常量、静态变量等。
  • 方法栈(JVM Stack)：每个线程私有,存储局部变量、操作栈等。
  • 本地方法栈(Native Method Stack)：为使用到的本地方法(C/C++编写)服务。
  • 程序计数器(Program Counter Register)：指向下一条要执行的指令。

9、Redis 常用数据类型

String、List、Hash、Set、Zset、BitMap、HyperLogLog、GEO、Stream

10、Redis 实现分布式锁

在Redis中实现分布式锁主要是使用setnx 命令（setif not exists）

最简单的实现：

加锁：

setnx key  value

释放锁时，先比较锁对应的 value 值是否相等，避免锁的误释放

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

如果系统出现问题，这种加锁的方式可能会导致锁没有释放、死锁等问题

  • 解决办法：设置锁的超时时间：set key val ex time nx

新的问题：如果操作共享资源的时间大于锁的释放时间，就会导致锁提前过期，分布式锁失效，超时时间 设置得过长，会影响性能。因此需要 用到锁的续期。

  • 解决办法：使用Redisson分布式锁 ，Redisson中关于锁的续期有看门狗机制，会自动续期锁，保证锁不会提前释放。默认情况，每10s续期一次，超时时间为30s
RLock lock = redissonClient.getLock("my-lock");
lock.lock(); //阻塞式等待，默认加的锁都是30s时间
//1.锁的自动续期，如果业务超长，运行期间自动给锁续上新的30s，不用担心业务时间长，锁自动过期被删掉
//2.加锁的业务只要运行完成，就不会给当前锁续期，即使不手动解锁，锁也会在30s后自动删除
try {
    System.out.println("加锁成功，执行业务..." + Thread.currentThread().getId());
    Thread.sleep(30000);
} catch (Exception e) {
    throw new RuntimeException(e);
} finally {
    lock.unlock();
}

11、缓存穿透、缓存雪崩、缓存击穿

缓存穿透是指查询一个不存在的数据，由于缓存中不存在，请求会直接到达数据库，如果大量这样的请求发生，会对数据库造成压力，甚至可能导致服务不可用。

  • 缓存空值：即使数据不存在，也将一个空值或默认值缓存起来，设置一个较短的过期时间。
  • 布隆过滤器：使用布隆过滤器（Bloom Filter）来过滤不存在的数据，减少对数据库的查询。
  • 请求限流：对一定时间内的请求进行限制，防止大量请求攻击数据库。
  • 参数验证：对传入的参数进行合法性验证，过滤掉明显不合理的请求。

缓存击穿是指一个热点数据在缓存过期时，大量请求同时访问数据库，导致数据库压力瞬间增大。

  • 互斥锁：当缓存过期时，只有第一个请求可以获取到锁，去数据库中加载数据，然后更新缓存。其他请求等待锁释放后，直接从缓存中获取数据。
  • 永不过期：对于热点数据，可以设置永不过期，或者过期时间足够长，同时在后台定期更新这些数据。
  • 缓存预热：针对热点数据提前预热，将其存入缓存中并设置合理的过期时间比如秒杀场景下的数据在秒杀结束之前不过期。

缓存雪崩是指缓存中大量数据在同一时间过期，导致大量请求直接到达数据库，数据库因承受不住压力而崩溃。

  • 过期时间分散：为不同的键设置不同的过期时间，避免同一时间大量键过期。
  • 熔断机制：当数据库压力过大时，熔断机制可以使一部分请求快速失败，保护数据库。
  • 多级缓存：使用多级缓存策略，例如本地缓存和分布式缓存，减少对数据库的直接访问。
  • 服务降级：在数据库压力过大时，可以返回降级数据，保证服务的可用性。

12、缓存空值和布隆过滤器的区别、优缺点

缓存空值:

  1. 优点: 简单易实现，可以快速判断 key 是否存在于缓存中
  2. 缺点: 占用缓存空间。

布隆过滤器:

  1. 优点: 节省缓存空间，可以精准判断 key 是否存在于数据库中
  2. 缺点: 存在误判概率，无法删除已存在的 key，需要提前知道所有可能存在的 key

区别:

  1. 存储方式: 缓存空值直接将 key-value 存储在缓存中，布隆过滤器使用位数组存储 key 的哈希值
  2. 判断 key 存在性: 缓存空值直接查询缓存中是否存在该 key，布隆过滤器通过计算哈希函数判断 key 是否存在
  3. 空间占用: 缓存空值占用更多缓存空间，布隆过滤器占用空间较小

13、用过什么 mq、RocketMQ 的结构

RabbitMQ、RocketMQ、Kafka

RocketMQ 是一款分布式消息中间件，由阿里巴巴集团开发并开源，主要用于支撑阿里巴巴的双十一等大规模活动的消息通信。RocketMQ 架构主要包括以下几个组件：

  1. Namesrv（Name Server）：
    • Namesrv 是 RocketMQ 的命名服务，负责管理整个 RocketMQ 集群中所有 Broker 节点的地址信息。
    • 客户端在发送消息时会先从 Namesrv 获取到 Broker 的地址信息，然后再与 Broker 建立连接。
  1. Broker：
    • Broker 是 RocketMQ 的消息存储节点，负责存储消息数据和提供消息的读写服务。
    • 一个 RocketMQ 集群可以包含多个 Broker，每个 Broker 都会负责存储一部分的消息数据，并提供消息的发送和消费服务。
  1. Producer（生产者）：
    • Producer 是消息的生产者，负责向 Broker 发送消息。
    • Producer 将消息发送到指定的 Topic 中，然后由 Broker 负责将消息存储起来，并将消息发送给订阅了该 Topic 的 Consumer。
  1. Consumer（消费者）：
    • Consumer 是消息的消费者，负责从 Broker 订阅消息并消费。
    • Consumer 可以订阅多个 Topic，并从 Broker 中拉取消息进行消费。RocketMQ 支持 Push 模式和 Pull 模式两种消费模式。
  1. Topic（主题）：
    • Topic 是消息的分类，每条消息都属于一个 Topic。
    • Producer 发送消息时需要指定消息发送到的 Topic，Consumer 订阅消息时也需要指定订阅的 Topic。
  1. Message Queue（消息队列）：
    • Message Queue 是一个逻辑概念，表示一个 Topic 下的分区。
    • 每个 Topic 可以分成多个 Message Queue，每个 Message Queue 负责存储一部分消息数据，以提高消息的并发处理能力。

RocketMQ 的整体架构是分布式的，支持水平扩展和高可用性，能够满足高并发、大规模的消息通信需求。通过 Namesrv 管理 Broker 地址信息，实现了解耦和动态扩展；通过 Producer、Consumer 和 Message Queue 实现了消息的生产和消费，支持多种消费模式和消息过滤机制，提供了丰富的消息传输功能。

14、怎么保证不重复消费、消费失败了怎么办

RocketMQ 通过以下方式来保证消息不重复消费：

  1. 消息消费确认机制：消费端在处理消息后，需要向 RocketMQ 发送消费确认。RocketMQ 会记录消费状态，如果消费成功，则标记该消息已被消费。如果消费端由于异常崩溃等原因未能发送消费确认，RocketMQ 会重新将消息投递给消费端，确保消息被正确消费。
  2. 消费端幂等性设计：为了应对消费端处理消息时的异常情况，需要设计消费端的业务逻辑具备幂等性。即使同一条消息被消费多次，也不会对系统产生副作用。这可以通过在消费端使用唯一标识来实现，比如数据库表的唯一索引、分布式锁等。

可以给消息设置一个唯一ID，当消费者消费消息时就将这个ID存储在数据库中，每次消费者消费消息次就用这个ID去数据库里查找是否有相同ID来确保是否要消费消息，这样就实现了消息幂等。

Rocket消费失败了怎么办？

  1. 消费失败重试机制:
  • 如果消费失败,消费者可以返回 RECONSUME_LATER 状态,RocketMQ 会在一定时间后自动重试该消息。
  • 默认最大重试次数为 16 次,每次重试的延时时间会递增,从1s、5s、10s等逐步增加。
  • 可以通过 setMaxReconsumeTimes() 方法设置最大重试次数。超过重试次数后,消息会进入死信队列。
  1. 死信队列处理:
  • 当消息重试多次仍然失败时,RocketMQ 会将其投递到 %DLQ%+ConsumerGroup 的死信队列中。
  • 死信队列中的消息需要人工干预处理,可以查看失败原因,然后将消息重新发送到正常的topic进行消费。
  • 如果不需要再次消费,可以直接丢弃死信消息。

15、简单聊项目

16、LC143 重排链表

链接open in new window

将链表转化为数组做

/**
 * 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:
    void reorderList(ListNode* head) {
        if(head==nullptr) return;
        vector<ListNode*> v;
        ListNode* cur=head;
        while(cur) v.push_back(cur),cur=cur->next;
        int i=0,j=v.size()-1;
        while(i<j){
            v[i]->next=v[j];
            v[j]->next=v[i+1];
            i++,j--;
        }
        v[i]->next=nullptr;
    }
};
欢迎您的参与
Copyright © 2024 全民制作人ikun