字节跳动抖音社招后台开发工程师面经

作者：伊凡的一天

来源：简书

最近参加了字节跳动的后台开发工程师面试，记录一下面经。（ps：社招两年经验）

1. 一面（1小时）

一面主要是基础考察，包括简历中提到的以及一些标准的基础问题。

VUE和React区别（因为简历中提到了VUE）
VUE的内部机制（问一下前端技术是因为我简历提到自己是全栈工程师，正常情况下是不会出现前端问题的）
CRSF的机制
Spring IOC和BEAN循环依赖
Kafka和Cassandra内部机制（简历中提及）
算法题：有 2n 个人，序号为 0 到 2n-1，要求两两握手，但是握手不能存在交叉线，求最后一
共存在多少种握手可能，写出 f(2n)表达式。

思路：假设0号和i号点握手，那么整张图就分为了0 ~ i-1和i+1 ~ 2n这两部分。

算法题：给定一个二维整数矩阵，找出最长递增路径的长度。对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

思路：记忆化DFS

public class Solution {
    private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        int m = matrix.length, n = matrix[0].length;
        int[][] *** = new int[m][n];
        int res = 1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                res = Math.max(res, dfs(matrix, i, j, ***));
            }
        }
        return res;
    }

    private int dfs(int[][] matrix, int i, int j, int[][] ***) {
        if (***[i][j] != 0) {
            return ***[i][j];
        }
        int max = 1;
        int m = matrix.length, n = matrix[0].length;
        for (int[] dir : dirs) {
            int x = i + dir[0], y = j + dir[1];
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[i][j] > matrix[x][y]) {
                max = Math.max(max, 1 + dfs(matrix, x, y, ***));
            }
        }
        ***[i][j] = max;
        return max;
    }
}

在另一个事业部一面时，遇到了三个水壶的问题：三个水壶，粉笔为 8L，3L，5L，给一个 num，判断能否量出这个指定 num 的水。

思路：BFS穷举所有可能性，直到出现目标水量。

public class ThreeBottles {

    private int[] capacity;

    public ThreeBottles() {
        capacity = new int[] { 8, 5, 3 };
    }

    public boolean canMeasure(int n) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        int initialState = getState(new int[] { 8, 0, 0 });
        queue.add(initialState);
        visited.add(initialState);
        while (!queue.isEmpty()) {
            int state = queue.poll();
            if (match(state, n)) return true;
            int[] water = getWater(state);
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    int next = transfer(i, j, water);
                    if (next != -1 && !visited.contains(next)) {
                        queue.add(next);
                        visited.add(next);
                    }
                }
            }
        }
        return false;
    }

    private int getState(int[] water) {
        return water[0] << 8 | water[1] << 4 | water[2];
    }

    private int[] getWater(int state) {
        return new int[] { state >>> 8 & 15, state >>> 4 & 15, state & 15 };
    }

    private boolean match(int state, int n) {
        return (state >>> 8 & 15) == n || (state >>> 4 & 15) == n || (state & 15) == n;
    }

    private int transfer(int i, int j, int[] water) {
        int[] next = new int[] { water[0], water[1], water[2] };
        if (i != j && water[i] > 0 && water[j] < capacity[j]) {
            int transmission = Math.min(water[i], capacity[j] - water[j]);
            next[i] -= transmission;
            next[j] += transmission;
            return getState(next);
        }
        return -1;
    }
}

2. 二面（1小时）

项目介绍（半小时）

准备好一些工作中解决的问题，尽可能详细的阐述给面试官，告诉他你主要解决了什么问题。

系统设计题：上海地铁线纵横交错（线路与线路之间存在交叉，并且每一条线路站与站之间的发车间隔可能是不一样的），现在做一个 app，输入是起点和终点已经出发时间，输出一条耗时最短的线路。

从数据库表，到缓存，到算法的设计。

3. 三面（40分钟）

三面是抖音上海负责人的面试，因此着重在系统设计。

项目介绍（15分钟）
系统设计：抖音里每秒都产生大量视频，现在要求持续计算一段时间内的 top k 个最热门的视频，你怎么设计。

这个问题类似于下面这个问题：

实现前5分钟，1小时，24小时内分享最多的feed

从算法的角度，可以简单的称之为 Top K Frequent Elements in Recent X mins。算法的角度，本质就是设计一个数据结构，支持给某个key的count+1（有一个post被分享了），给某个key的count-1（有一个分享的计数已经过期了），然后查询Top k。

做法是维护一个有序序列（用链表来维护），每个链表的节点的key是 count，value是list of elements that has this count，也用linked list串起来。比如 a出现2次，b出现3次，c出现2次，d出现1次。那么这个链表就是：

{3: [b]} --> {2: [a ->c]} --> {1: [d]}

然后另外还需要一个hashmap，key是element，value是这个element在链表上的具***置。
因为每一次的操作都是 count + 1和 count - 1，那么每次你通过 hashmap 找到对应的element在数据结构中的位置，+1的话，就是往头移动一格，-1的话，就是往尾巴移动一格。总而言之复杂度都是 O(1)。当你需要找 Top K 的时候，也是 O(k)的时间可以解决的。

算法实现请参考：https://github.com/cheergoivan/leetcode/blob/master/src/leetcode/problem460/LFUCache.java

工程角度的优化：

如果我要去算最近5分钟的数据，我就按照1秒钟为一个bucket的单位，收集最近300个buckets里的数据。如果是统计最近1小时的数据，那么就以1分钟为单位，收集最近60个Buckets的数据，如果是最近1天，那么就以小时为单位，收集最近24小时的数据。那么也就是说，当来了一个某个帖子被分享了1次的数据的时候，这条数据被会分别存放在当前时间(以秒为单位），当前分钟，当前小时的三个buckets里，用于服务之后最近5分钟，最近1小时和最近24小时的数据统计。

你可能会疑惑，为什么要这么做呢？这么做有什么好处呢？这样做的好处是，比如你统计最近1小时的数据的时候，就可以随着时间的推移，每次增加当前分钟的所有数据的统计，然后扔掉一小时里最早的1分钟里的所有数据。这样子就不用真的一个一个的+1或者-1了，而是整体的 +X 和 -X。当然，这样做之后，前面的算法部分提出来的数据结构就不work了，但是可以结合下面提到的数据抽样的方法，来减小所有候选 key 的数目，然后用普通的 Top K 的算法来解决问题。

另外，在分布式环境下，哪些帖子被分享了多少次这些数据，首先在 web server 中进行一次缓存，也就是说web server的一个进程接收到一个分享的请求之后，比如 tweet_id=100 的tweet被分享了。那么他把这个数据先汇报给web server上跑着的 agent 进程，这个agent进程在机器刚启动的时候，就会一直运行着，他接受在台web server上跑着的若干个web 进程(process) 发过来的 count +1 请求。

这个agent整理好这些数据之后，每隔5_{10秒汇报给中心节点。这样子通过5}10s的数据延迟，解决了中心节点访问频率过高的问题。

还可以通过数据抽样进行优化。因为那些Top K 的post，一定是被分享了很多很多次的，所以可以进行抽样记录。如果是5分钟以内的数据，就不抽样，全记录。如果是最近1小时，就可以按照比如 1/100 的概率进行 sample。

最后是使用Cache进行缓存计算结果。对于最近5分钟的结果，每隔5s才更新一次。对于最近1小时的结果，每隔1分钟更新一次。对于最近24小时的结果，每隔10分钟才更新一次。用户需要看结果的时候，永远看的是 Cache 里的结果。另外用一个进程按照上面的更新频率去逐渐更新Cache。

总结：算法方面使用LFU算法来解决。而工程方面使用分段统计，抽样法和Cache缓存进行优化。