面经

腾讯

一面

疫情期间，电话面试。

1. 大数据问题。给定4G内存，以及16亿个QQ号，这些QQ号里面有重复的，找出重复次数排名前100个QQ号。

   经典的大数据topn问题，采用分治再归并，每个qq号大约是10位左右，大约占10个字节，4G=4000MB=4000000KB=4^9B=40亿B，可以容纳4亿个QQ号

   将16亿个QQ号分为四组，每组在内存内进行count，然后分两个策略

   1. count结果全量的持久化到磁盘上，优点是精准，缺点是慢

   2. count结果取前一千万放在内存里，剩余的丢弃，优点是快，但是可能不太准

   让我写我会选择综合两个，先剩1KW放内存，然后四组数据互相join，没有匹配到的数据再从磁盘里捞出来计算

2. 聊了下微服务，服务注册发现是怎么做的？微服务的监控是怎么做的？

   服务注册：

   1. 直接和中心服务器（比如SpringCloud当中的eruka）使用长连接进行心跳保持

   2. 使用http进行非长连接的注册和留活

   服务发现：

   1. 在中心服务器维护当前服务的所有真实服务数据

   2. 在每个consumer中维护所调用服务的副本，在请求时都走本地缓存进行请求路由

   3. 在真实服务数据发生变更（机器上下线，版本变动等）操作的时候，由中心服务器向consumer进行元数据的推送

   4. consumer设置一个定时的后台进程每隔N分钟重新请求

   监控：

   1. 机器监控

      在监控中心维护某provider的所有机器IP，然后去拉去其sar的数据并可视化

   2. 服务监控

      1. 监控机器的服务提供成功率

      2. 全链路trace调用监控

      实现思路都是一样的，打日志然后从监控中心拉机器IP去采日志，成功率通过常规日志即可获得，全链路跟踪在获取全链路id后可生成调用链（此处注意调用链不可依赖时间戳，应该有自己的逻辑调用先后顺序）

   3. sc里也有能监控endpoint的组件（具体记不太清了）

3. 实现一个线程安全的阻塞队列。

   阻塞队列用法：FIFO，在队列满的时候让线程等待

   则将put方法加一个ReenterLock的ConditionA，然后维护一个volatile的isFull字段，在put之前判断volatile是否true，若为true则直接ConditionA.await，put成功后尝试唤醒pull的condition

   将pull方法加一个ReenterLock的ConditionB，然后维护一个volatile的isEmpty字段，在pull之前判断是否空，若空则ConditionB.await，pull成功后尝试唤醒put的condition

4. 给定两个数组，每个数组中都有重复的数字。不用类库函数，对这两个数组排序。

   两个数组append一下直接快排不就完事儿了吗= =，还是说要加个SET去重

5. 多路复用是什么？怎么用？

   多路复用定义：一个线程监听多个端口or文件描述符，减轻cpu线程切换压力

   select:监听多个IO任务，但是存在描述符个数限制，所有存在一个上限，并且在每次有事件发生的时候需要遍历持有的描述符列表来确定具体是哪个描述符发生了事件

   poll:去除了文件描述符的限制

   epoll:监听的描述符完事儿后会回调注册到就绪队列，可以直接从中获得对应的描述符，并且使用了mmap进行zerocopy提升性能，而select/poll都存在在内核空间与用户空间的拷贝

6. Linux中的文件节点是什么？（这个不太会）

   我也不太会- -

7. 聊了下项目架构

   这个各凭本事吧，主要是考虑以下几个点

   1. 对于大流量是否有应对措施

   2. 对于异步同步怎么考虑的

   3. 异步丢消息怎么处理

   4. 在什么地方存在提高性能的trick

   5. 异常情况怎么考虑，怎么做补偿

   6. 数据库设计、缓存设计、其他数据源的设计

二面

视频面试

1. 给定一个数组，求该数组所有的自子数组

   lc原题，DFS可解

2. 去掉一个字符串中的所有空格（送分题）

   送分

3. 两个系统A和B，如果A调用B的时候发生超时，这个时候A会重试，那么怎么确保B只调用一次？

   幂等，设计考虑要点

   1. 是否完全幂等，即是否要保存这次调用记录但是不改变状态

   2. 幂等键的定义，该幂等键是否只match这个请求，幂等键又该如何存储

   3. 返回值的定义，是返回创建失败还是成功，若是成功，是否要告知该次是幂等成功

4. 项目中的数据库分表是怎么做的？

   水平：根据某个key进行水平拆分，设计要点

   1. 如何规避跨库事务

   2. 分表键如何设计

   3. 如何防止热点

   4. 是否有库可以不拆

   5. UUID如何生成

   垂直：一库拆多库，schema不同，使用库间外键进行关联，涉及分布式事务的时候很恶心，可以使用DDD进行拆分，每个库的核心是一个聚合根

三面

电话面试

1. 给定一个数组，元素的大小0~25，有重复元素。按出现频次的高低输出所有的数字。

   送分，直接map+sort，on扫两编

2. 聊一下项目中HBase的RowKey是怎么设计的？

   设计原则

   1. 需要保证唯一，若没用到基于timestamp的version字段则每次查询相同key都会返回最新值，所以要在业务上保证唯一

   2. 是否满足查询条件，rowkey实际上充当索引的功能

      1. rowkey只支持全名的get或者range查找，在java客户端中可以只用prefix的filter

      2. 若进行复杂查询，可以新建一张表做索引表

      3. 考虑查询热点，需要分散热点

         1. md5

         2. hash

         3. 取模

         4. +随机数

   3. 考虑变的更短来节省存储空间：比如用编码代替字符串

   4. rowkey冲突：使用占位符或者特殊分隔符

3. 项目中的事务消息是怎么做的？

   RocketMq中的事务消息:

   1. producer发送一个half消息

   2. 执行本地逻辑

   3. 本地逻辑执行失败：rollback

   4. 本地逻辑执行成功：commit

   5. 在commit之后这个消息才算是投递成功并且能被consumer所消费

4. 对加班怎么看？表示自己可以996

   钱到位人到位

四面

电话面试，这里好像已经到腾讯的面委会了

1. 给定一个二叉树，依次打印出每一行。

   层序遍历

2. 聊一下Redis的zset？实现原理是什么？为什么不用红黑树来实现？

   hashtable/skiplist+关联一个double的score

   红黑树是特殊二叉平衡树，插入场景下会需要旋转树造成额外开销

3. redis哨兵怎么选举主节点？

   1. 任意一个发现主服务器客观下线之后向所有的sentinel请求成为主节点

   2. 每个sentinel只认最早来发起请求的主sentinel

   3. 过半投票投向某个sentinel则成为主

   4. 若在这次配置纪元中不存在过半投票的则在一段事件后发起新的一轮选主

4. 为什么IP分组到达的时间不一样？

   这啥啊没看懂

5. 有什么要问我的？

   加班吗，干啥活的，为什么招人，我进去后做啥业务

五面

电话面试，我真的已经忘记聊什么了。很快，没聊什么技术。聊了下为什么想换工作？以及自己的职业规划

快手

一面

视频面试

1. leetcode 2

   2sum，set+一边for循环，on

2. 自我介绍

   show一下学历、经验以及主要owner的业务和团队定位

3. 线程池实现原理，用法

   核心设计思想：

   1. 持久化的维护一些线程在内存当中，减小初始化以及关闭线程的损耗（大部分的线程池、连接池的核心思路）

   2. 存在三级结构来maintain线程

      1. 核心线程池：该线程池当中的线程不会消亡，所有任务优先使用里面的线程

      2. 任务队列：当核心线程池满的时候添加到任务队列当中，队列满了则会开启新的线程（无界队列除外），队列种类

         1. LinkedBlockingQueue:基于链表

         2. ArrayBlockingQueue:基于数组，吞吐量比linked高（因为基于数组嘛）

         3. SynBlokcingQueue:单元素阻塞

         4. PriorityBlockingQueue:无限阻塞

      3. 最大线程池大小：在阻塞队列满了之后开启新的线程池进行处理

   使用考虑要点：

   1. 核心线程数的设定：

      1. 若是IO密集型，可以将线程数多设一些（比如2*cpu核数），因为大量的线程会hang在等待IO上面，不会争抢cpu时间片

      2. 若是计算密集型，则将其设计为cpu核数，这样保证在没有其他任务运行时能全量抢占cpu，减少上下文切换

   2. 重写线程工厂类：在线程工厂中可以对线程进行命名以及打印Log等操作

   3. 提交任务的时候可以使用Future进行提交，可以获取线程的运行结果，Future当中的Callable实现类可以自行拓展，主要考虑继承主线程的一些属性（全链路TraceID，RPC上下文，ThreadLocal等，ThreadLocal可以用InheritedThreadLocal进行继承）

4. JVM内存结构，垃圾回收机制

   内存结构：虚拟机栈、native栈（这俩在hotspot里其实是同一个东西）、方法区（1.8后改为meta space，里面存了方法签名、class信息、hot code cache等）、堆、计数器

   GC器：

   serial：串行

   parnew：并发串行

   CMS：并发清理，不会始终stw

   G1：分块清理

   GC机制：

   ROOT：对应上文则是线程栈上的对象、native方法栈上的对象、静态变量、堆中的常量、class锁机制中的monitor、system class loader以及bootstrap class loader中的加载的类

   YGC：分s1s0以及eden，比例一般是1:1:8，对象放到eden当中（过大的直接升级到old），当eden满了之后和s1当中的对象merge并且执行清理然后放到s0当中，每一次清理都stw并且会把对象的age+1，若age抵达设置的age则晋升old区

   FGC：由YGC晋升来的对象触发，当old区在FGC之后还是无法容纳需要晋升上来的对象则会直接OOM，此处的常规清理流程以CMS举例

   CMS：

   1. 并发初始标记（stw）：将GCROOT以及young区关联到Old区的根对象找出来

   2. 并发标记：以1中的根对象为根，将所有存活对象进行标记

   3. 预清理：可以设置次数，因为在并发标记阶段会有并行的对象改动，改动完的对象会被标记为dirty，预清理会重新检查这些对象以及相关的对象

   4. 最终标记（stw）：检查所有dirty对象

   5. 并发清理：清楚不需要存活的对象

   6. reset：将程序初始化等待下一轮

   优点：只在标记阶段进行stw，在最终的标记前采取预清理机制，多线程标记提速

   缺点：多线程会增加cpu负担

   附赠小知识：在JVM做垃圾回收的时候并不会将内存即时归还给OS，频繁的申请和归还内存可能会导致堆内存的不稳定，所以在启动JVM时我们一般将xmx和xms设置成相同的值来稳定堆内存空间

5. Synchronized加锁原理。偏向锁、轻量级锁、重量级锁。

   Syn的加锁原理通过占用和退出对象的monitor中，monitor的信息存储在对象头当中

   锁升级过程：

   1. 在第一次获取对象的锁的时候直接偏向锁，即在monitor中保存当前的线程ID

   2. 有第二个线程来争抢的时候升级为轻量级锁并进入自旋获取该锁

   3. 若自旋超出一定次数没拿到这个锁则升级成重量级锁，线程进入等待状态，等待唤醒

6. AQS原理。公平锁和非公平锁。

   AQS是一个双向队列，通过一个volatile的state来标志当前资源的状态，用当前ownerThread以及状态来确定是否共享以及排他

   公平锁：若检测到当前资源被使用则直接进入等待队列

   非公平锁：检测到当前资源被使用，先cas自旋一次，获取不到再等待

7. MySQL索引什么时候失效？

   最左前缀匹配失效或者mysql计算这次query根本不需要走索引

8. RocketMQ生产消息，存储消息，生成索引，消费消息全流程。

   生产消息：
   在producer处组装消息，通过timestamp以及当前机器维护的一个AtomicInteger来生成msgid，拉取当前Topic可用的所有broker然后轮询发送给对应的某台Broker
   顺序写入物理队列，开放逻辑队列给每个consumer消费，逻辑队列只允许一个consumer进行消费
   优势在于使用了mmap的zerocopy来进行读写，减少IO开销，并且写入都是顺序的，提升刷盘性能
   生成索引：
   通过slot（就是hash）+链表的方式维护commitQueue到commitLog的映射
   消费消息：
   push方式里，consumer把轮询过程封装了，并注册MessageListener***，取到消息后，唤醒MessageListener的consumeMessage()来消费，对用户而言，感觉消息是被推送过来的。
   pull方式里，取消息的过程需要用户自己写，首先通过打算消费的Topic拿到MessageQueue的集合，遍历MessageQueue集合，然后针对每个MessageQueue批量取消息，一次取完后，记录该队列下一次要取的开始offset，直到取完了，再换另一个MessageQueue。
   

9. ConcurrentHashMap扩容算法

   先判断元素size是否抵达0.75倍的容量，超过阈值则进行扩容，扩容时先获取老table里面的队列，然后初始化一个forwardNode放到该队列的下面，然后将老table里的队列使用头插法迁移到新数组当中，在此期间如果其他线程的有读写操作都会判断head节点是否为forwardNode节点，如果是就帮助扩容，并block。

10. 有什么要问我的？

    啥部门啥业务为啥招人

二面

视频面试

1. 求N内的所有素数；

   素数定义：无法被除了一以外的整除，奇数只需要除以奇数，偶数不需要判断，大于该数1/2的数不用除

2. 给定一个乱序数组，求数组内最大连续的数；

   基础滑窗

3. 自我介绍

4. 聊项目。项目中的难点是什么？如何解决，我讲了RocketMQ的调优

   各凭本事

5. 分布式ID实现，不准用UUID

   持久化取号+内存atomicInteger

6. MySQL间隙锁的机制？主要解决的问题是什么？

   锁一个range，解决幻读问题（RR隔离下）

7. 课余时间怎么学习？

   11点下班熬夜学习到两点

8. 有什么要问我的？

   同上

三面

视频面试

1. 讲项目，redis的作用，HBase RowKey的设计。项目主要做了些什么？有什么难点？

   各凭本事

   redis做缓存的话注意击穿、穿透、雪崩以及缓存失效流程（先改持久层再更新redis）与更新失败的补偿机制

   redis做分布式锁设计的话注意锁的可重入，续约，跨线程释放时的错误释放问题以及淘汰机制（禁止淘汰、过期随机淘汰、过期LRU淘汰、过期TTL淘汰、全量随机淘汰、全量LRU淘汰）

   hbase的rowkey设计同上

2. Leetcode 146

   基础LRU

3. Leetcode 470

   拒绝采样

4. 有什么要问我的？

   同上