对线面试官 | 字节跳动一面

2022-07-08 14:51:34 浏览数 (1)

本期是【对线面试官】系列文章的第1期，题目改编自2022年秋招字节跳动一面。

面试现场

面试官：你好，我是字节跳动的面试官xxx，请问是大彬吗？

大彬：面试官，您好，我是大彬

面试官：现在方便面试吗？

大彬：嗯嗯，可以的

面试官：那我们现在开始面试吧

面试官：看你简历上写了熟悉集合相关内容，你了解HashMap吗？讲一下HashMap的put方法？

独白：果然一上来就是HashMap...

大彬：HashMap 实现了Map接口，用于保存键值对映射。其底层是使用数组 链表 红黑树（JDK1.8增加了红黑树部分）实现的。

大彬：它的put方法过程如下：

  1. 如果table没有初始化就先进行初始化过程
  2. 使用hash算法计算key的索引
  3. 判断索引处有没有存在元素，没有就直接插入
  4. 如果索引处存在元素，则遍历插入，有两种情况，一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入
  5. 链表的数量大于阈值8，就要转换成红黑树的结构
  6. 添加成功后会检查是否需要扩容

面试官：嗯，刚刚你提到HashMap的扩容，详细讲一下？

独白：emm，给自己挖坑了...

大彬：以JDK1.8为例，当往HashMap放入元素时，如果元素个数大于threshold时，会进行扩容，使用2倍容量的数组代替原有数组。

大彬：由于数组的容量是以2的幂次方扩容的，那么一个Entity在扩容时，新的位置要么在原位置，要么在原长度 原位置的位置。

大彬：原因是数组长度变为原来的2倍，表现在二进制上就是多了一个高位参与数组下标计算。

大彬：也就是说，在元素拷贝过程不需要重新计算元素在数组中的位置，只需要看看原来的hash值新增的那个bit是1还是0，是0的话索引没变，是1的话索引变成“原索引 oldCap”（根据e.hash & (oldCap - 1) == 0判断） 。

大彬：这样可以省去重新计算hash值的时间，而且由于新增的1bit是0还是1可以认为是随机的，因此resize的过程会均匀的把之前的冲突的节点分散到新的bucket。

面试官：小伙子，基础还算不错。看你简历上写了精通MySQL，来讲讲一下MySQL的索引结构？

独白：卧槽，以后再也不敢写精通了....还好昨天背了大厂面试手册，现在一点都不慌

大彬：MySQL 数据库使用最多的索引类型是BTREE索引，底层基于B 树数据结构来实现。

大彬：B 树是基于B 树和叶子节点顺序访问指针进行实现，它具有B树的平衡性，并且通过顺序访问指针来提高区间查询的性能。

大彬：进行查找操作时，首先在根节点进行二分查找，找到key所在的指针，然后递归地在指针所指向的节点进行查找。直到查找到叶子节点，然后在叶子节点上进行二分查找，找出 key 所对应的数据项。

面试官：为什么索引要用B 树来实现呢，而不是用二叉树？

大彬：B 树有个特点，就是够矮够胖，能有效地减少访问节点次数从而提高性能。

大彬：虽然二叉树也有很好的查找性能log2N，但是当N比较大的时候，树的深度比较高。数据查询的时间主要依赖于磁盘IO的次数，二叉树深度越大，查找的次数越多，性能越差。最坏的情况会退化成链表。所以，B 树更适合作为MySQL索引结构。

面试官：那又为什么不用B树呢？

独白：现在面试也太卷了趴，这是要造火箭啊...

大彬：因为B树的分支结点存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫。而由于B 树的数据都存储在叶子结点中，叶子结点均为索引，方便扫库，只需要扫一遍叶子结点即可。所以B 树更加适合在区间查询的情况，而在数据库中基于范围的查询是非常频繁的，所以B 树更适合用于数据库索引。

面试官：知道聚集索引吗？

大彬：聚集索引严格来说并不是索引类型，而是一种数据存储方式，具体细节依赖于其实现方式。如innodb聚集索引的叶子节点存放了整张表的行记录。

大彬：聚集索引类似字典的拼音目录。表中的数据按照聚集索引的规则来存储的。就像新华字典，整本字典是按照A-Z的顺序来排列。这也是一个表只能有一个聚集索引的原因。

面试官：那聚簇索引相比非聚簇索引有什么优点？

大彬：1. 数据访问更快，因为聚簇索引将索引和数据保存在同一个B 树中，因此从聚簇索引中获取数据比非聚簇索引更快。

大彬：2. 聚集索引叶子节点的存储是逻辑上连续的，所以对于主键的排序查找和范围查找速度会更快。

面试官：嗯，问点其他的，线程池知道吧？

大彬：线程池，顾名思义，就是一个管理线程的池子。

面试官：那为什么使用线程池呢？

大彬：之所以使用线程池，主要有三点原因：

  • 降低资源消耗。通过重复利用已创建的线程降低线程创建和销毁造成的消耗。
  • 提高响应速度。当任务到达时，可以不需要等到线程创建就能立即执行。
  • 提高线程的可管理性。统一管理线程，避免系统创建大量同类线程而导致消耗完内存。

面试官：嗯，那你讲一下线程池的几个参数？

独白：老八股文了嘿嘿~

大彬：先来看看ThreadPoolExecutor的通用构造函数：

代码语言：javascript复制
public ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, long keepAliveTime, TimeUnit unit, BlockingQueue<Runnable> workQueue, ThreadFactory threadFactory, RejectedExecutionHandler handler);

大彬：其中有7个参数。分别是corePoolSize, maximumPoolSize, keepAliveTime, timeUnit, workQueue, threadFactory, rejectedExecutionHandler

大彬：corePoolSize。当有新任务时，如果线程池中线程数没有达到线程池的基本大小，则会创建新的线程执行任务，否则将任务放入阻塞队列。当线程池中存活的线程数总是大于 corePoolSize 时，应该考虑调大 corePoolSize。

大彬：maximumPoolSize。当阻塞队列填满时，如果线程池中线程数没有超过最大线程数，则会创建新的线程运行任务。否则根据拒绝策略处理新任务。非核心线程类似于临时借来的资源，这些线程在空闲时间超过 keepAliveTime 之后，就应该退出，避免资源浪费。

大彬：BlockingQueue。存储等待运行的任务。

大彬：keepAliveTime。非核心线程空闲后，保持存活的时间，此参数只对非核心线程有效。设置为0，表示多余的空闲线程会被立即终止。

大彬：TimeUnit。时间单位，具体如下：

代码语言：javascript复制
TimeUnit.DAYS
TimeUnit.HOURS
TimeUnit.MINUTES
TimeUnit.SECONDS
TimeUnit.MILLISECONDS
TimeUnit.MICROSECONDS
TimeUnit.NANOSECONDS

大彬：ThreadFactory。每当线程池创建一个新的线程时，都是通过线程工厂方法来完成的。在 ThreadFactory 中只定义了一个方法 newThread，每当线程池需要创建新线程就会调用它。

代码语言：javascript复制
public class MyThreadFactory implements ThreadFactory {
    private final String poolName;
    
    public MyThreadFactory(String poolName) {
        this.poolName = poolName;
    }
    
    public Thread newThread(Runnable runnable) {
        return new MyAppThread(runnable, poolName);//将线程池名字传递给构造函数，用于区分不同线程池的线程
    }
}

大彬：RejectedExecutionHandler。当队列和线程池都满了时，根据拒绝策略处理新任务。

代码语言：javascript复制
AbortPolicy：默认的策略，直接抛出RejectedExecutionException
DiscardPolicy：不处理，直接丢弃
DiscardOldestPolicy：将等待队列队首的任务丢弃，并执行当前任务
CallerRunsPolicy：由调用线程处理该任务

面试官：好的。你了解 Spring AOP 吗？

大彬：AOP，其实就是面向切面编程，将一些公共逻辑（事务管理、日志、缓存等）封装成切面，跟业务代码进行分离，可以减少系统的重复代码和降低模块之间的耦合度。切面就是那些与业务无关，但所有业务模块都会调用的公共逻辑。

大彬：Spring AOP是通过动态代理技术实现的。

面试官：哦，那动态代理的实现方式有哪些？

大彬：动态代理技术的实现方式有两种：

  1. 基于接口的 JDK 动态代理。
  2. 基于继承的 CGLib 动态代理。在Spring中，如果目标类没有实现接口，那么Spring AOP会选择使用CGLIB来动态代理目标类。

面试官：你刚刚提到CGlib动态代理，能详细介绍下吗？

大彬：CGLIB，就是Code Generator Library，它是一个强大的、高性能的代码生成库，被广泛应用于AOP框架中，用以提供方法拦截操作。

大彬：CGLIB代理主要通过对字节码的操作，为对象引入间接级别，以控制对象的访问。

大彬：CGLIB 动态代理相对于 JDK 动态代理局限性就小很多，目标对象不需要实现接口，底层是通过继承目标对象产生代理子对象。

面试官：来做道题吧。求根节点到叶节点数字之和（LeetCode129）。

独白：没有困难的题目，只有勇敢的刷题人！

大彬：思路：深度优先搜索。从根节点开始，遍历每个节点，如果遇到叶子节点，则将叶子节点对应的数字加到数字之和。如果当前节点不是叶子节点，则计算其子节点对应的数字，然后对子节点递归遍历。

代码语言：javascript复制
//  输入: [1,2,3]
//     1
//    / 
//   2   3
// 输出: 25
class Solution {
    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return sumNumbersHelper(root, 0);
    }

    private int sumNumbersHelper(TreeNode node, int sum) {
        if (node == null) {
            return 0;
        }
        if (sum > Integer.MAX_VALUE / 10 || (sum == Integer.MAX_VALUE / 10 && node.val > Integer.MAX_VALUE % 10)) {
            throw new IllegalArgumentException("exceed max int value");
        }
        sum = sum * 10   node.val;

        if (node.left == null && node.right == null) {
            return sum;
        }

        return sumNumbersHelper(node.right, sum)   sumNumbersHelper(node.left, sum);
    }
}

面试官：不错，好好准备二面吧~

点关注，不迷路

我是大彬，非科班转码，校招拿了多家互联网大厂offer，专注分享Java技术干货。

hashmap aop 编程算法 spring jdk

0 人点赞