头条后端面试记录

Posted1 by 呼延十 on April 24, 2019 Hot:

前言

最近参加了一下头条后端工程师的面试,很惨,一面就挂掉了。

回来之后也对面试过程做了一些总结,就不夹带私货了,这篇文章主要对面试过程中的技术问题做一个复盘。

1. 求二叉树的最远节点的距离

这是一道 LeetCode 原题,原题链接

求二叉树的最远距离节点间的节点。 首先总结几个规律:

  1. 一棵树的直径要么完全在其左子树中,要么完全在其右子树中,要么路过根节点。
  2. 一棵树的直径 = 以该树中每一个节点为根节点,求 路过根节点的最大直径,所有节点的最大值就是这棵树的直径。
  3. 求经过根节点的直径,可以分解为:求左子树的最深叶子 + 右子树的最深叶子。

所以我们要做:

  1. 递归的求 每一个节点的 路过根节点的直径(求当前节点的左子树最深叶子和右子树的最深叶子), 取其最大值。
  2. 求某一个节点的最深叶子,就等于 他的 左子树最深叶子 + 1 和 右子树最深叶子 + 1 的较大值。
  3. 在求最深叶子的时候,其实是求出了当前节点直径的(左边最深叶子 + 右边最深叶子 + 2), 为了避免重复计算,我们在递归求最深叶子的时候,把直径也记录下来。)

代码如下:

    public int diameterOfBinaryTree(TreeNode root) {
        AtomicReference<Integer> ret = new AtomicReference<>(0);
         find(root, ret);
        return ret.get();
    }

    private int find(TreeNode node, AtomicReference<Integer> result) {
        if (node == null) return 0;
        int left = 0, right = 0;
        if (node.left != null) left = find(node.left,result) + 1;
        if (node.right != null) right = find(node.right,result) + 1;
        int tmp = Math.max(result.get(), left + right);
        result.set(tmp);
        return Math.max(left, right);
    }

代码很简单,就是递归的求节点的左子树最远叶子和右子树最远叶子。然后在 计算过程中,将 当前节点的直径 作为一个备选项存储,最后求最大直径即可。

2. Java 的装箱与拆箱

Java 在 1.5 添加了自动装箱和拆箱机制。总的来说基本就是基本类型和对应的包装类型之间的自动转换。

如下面的代码中:

public class BoxTest {
    public static void main(String [] args){
        Integer a = 10; // 装箱
        int b = a; // 拆箱
    }
}

我们将代码编译之后进行反编译,可以看到

2019-10-24-14-32-50

很明显在 代码中的 #2 ,#3 处进行了装箱和拆箱。

分别调用了 Integer 的 valueOf 方法和intValue 方法。

3. CMS 垃圾收集器的收集过程中,什么时候会暂停用户线程?

这里不对所有的垃圾收集器展开讲解,有兴趣的朋友们可以移步 JVM 的数据区域与垃圾收集.

众所周知,CMS 的垃圾收集过程如下:

2019-08-10-21-19-28

所以在初始标记和重新标记两个阶段还是需要暂停用户线程的。

4. ConcurrentHashMap 在读取的过程中为什么不需要加锁?

查看ConcurrentHashMap 的源码可以发现,Node 节点的定义是:

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;
}

可以看到,里面定义了几个属性,分别如下:

  1. final 修饰的 hash 值,初始化后不能再次改变。
  2. final 修饰的 key, 初始化后不能再次改变。
  3. volatile 修饰的值
  4. volatile 修饰的下一节点指针

get(Ojbect)方法的调用过程中。

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    //获取 hash 值
    int h = spread(key.hashCode());
    //通过 tabat 获取 hash 桶,tabAt 是一个线程安全的操作,有 UnSafe 来保证的。
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        //如果该 hash 桶的第一个节点就是查找结果,则返回
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        //第一个节点是树的根节点,按照树的方式进行遍历查找
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        //第一个节点是链表的根节点,按照链表的方式遍历查找
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

在这个过程中,

  1. 获取 hash 桶的根节点,通过 tabAt 来操作,线程安全。
  2. 遍历的时候用到了 node 的 next 属性,由于其与 volatile 修饰的,所以线程间可见,出现并发问题。
  3. 返回时读取 node 的 volatile 属性 val.

所以 get 过程中不用加锁也可以正确的获取对象。

5. Redis 的字典 rehash 和 JDK 中 hashmap 等 rehash 有什么不同?

这个问题比较宽泛,我个人的理解有以下两点。

  1. hashmap rehash 的时候的 另外一张 table 是临时创建的。而 redis 是时刻保持两张表的引用的。只是在需要 rehash 的时候才分配足够的空间。
  2. hashmap rehash 是一次性的,集中的完成 rehash 过程,而 redis 是渐进式 hash.

hashmap 的 rehash 过程想必大家都是了解的,那么这么稍微说一下 redis 的渐进式 hash.

首先,rehash 是要将原来表中的所有数据重新 hash 一遍,存放到新的表格中,以进行扩容。

而 redis 是一个单线程的高性能的服务,如果一个 hash 表中有几亿条数据,rehash 花费的时间将比较长,而在此期间,redis 是无法对外提供服务的,这是不可接受的。

因此,redis 实现了渐进式 hash. 过程如下:

  1. 假如当前数据在 ht[0] 中,那么首先为 ht[1] 分配足够的空间。
  2. 在字典中维护一个变量,rehashindex = 0. 用来指示当前 rehash 的进度。
  3. 在 rehash 期间,每次对 字典进行 增删改查操作,在完成实际操作之后,都会进行 一次 rehash 操作,将 ht[0] 在rehashindex 位置上的值 rehash 到 ht[1] 上。将 rehashindex 递增一位。
  4. 随着不断的执行,原来的 ht[0] 上的数值总会全部 rehash 完成,此时结束 rehash 过程。

在上面的过程中有两个问题没有提到:

  1. 假如这个服务器很空余呢?中间几小时都没有请求进来,那么同时保持两个 table, 岂不是很浪费内存?

解决办法是:在 redis 的定时函数里,也加入帮助 rehash 的操作,这样子如果服务器空闲,就会比较快的完成 rehash.

  1. 在保持两个 table 期间,该哈希表怎么对外提供服务呢?

解决办法:对于添加操作,直接添加到 ht[1] 上,因此这样才能保证 ht[0] 的数量只会减少不会增加,才能保证 rehash 过程可以完结。而删除,修改,查询等操作会在 ht[0] 上进行,如果得不到结果,会去 ht[1] 再执行一遍。

渐进式 hash 带来的好处是显而易见的,他采用了分而治之的思想,将 rehash 操作分散到每一个对该哈希表的操作上,避免了集中式 rehash 带来的性能压力。

与此同时,渐进式 hash 也带来了一个问题,那就是 在 rehash 的时间内,需要保存两个 hash 表,对内存的占用稍大,而且如果在 redis 服务器本来内存满了的时候,突然进行 rehash 会造成大量的 key 被抛弃。

参考文章

《Redis 设计与实现(第二版》

完。

ChangeLog

2019-05-19 完成

以上皆为个人所思所得,如有错误欢迎评论区指正。

欢迎转载,烦请署名并保留原文链接。

联系邮箱:huyanshi2580@gmail.com

更多学习笔记见个人博客或关注微信公众号 < 呼延十 > ——>呼延十