最近參加了字節(jié)跳動的后臺開發(fā)工程師面試，記錄一下面經(jīng)。（ps：社招兩年經(jīng)驗）
1. 一面（1小時）
一面主要是基礎(chǔ)考察，包括簡歷中提到的以及一些標準的基礎(chǔ)問題。
VUE和React區(qū)別（因為簡歷中提到了VUE）
VUE的內(nèi)部機制（問一下前端技術(shù)是因為我簡歷提到自己是全棧工程師，正常情況下是不會出現(xiàn)前端問題的）
CRSF的機制
Spring IOC和BEAN循環(huán)依賴
Kafka和Cassandra內(nèi)部機制（簡歷中提及）
算法題：有 2n 個人，序號為 0 到 2n-1，要求兩兩握手，但是握手不能存在交叉線，求最后一
共存在多少種握手可能，寫出 f(2n)表達式。
思路：假設(shè)0號和i號點握手，那么整張圖就分為了0 ~ i-1和i+1 ~ 2n這兩部分。
- 算法題：給定一個二維整數(shù)矩陣，找出最長遞增路徑的長度。對于每個單元格，你可以往上，下，左，右四個方向移動。 你不能在對角線方向上移動或移動到邊界外（即不允許環(huán)繞）。
思路：記憶化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[][] cache = 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, cache));
}
}
return res;
}
private int dfs(int[][] matrix, int i, int j, int[][] cache) {
if (cache[i][j] != 0) {
return cache[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, cache));
}
}
cache[i][j] = max;
return max;
}
}
- 在另一個事業(yè)部一面時，遇到了三個水壺的問題：三個水壺，粉筆為 8L，3L，5L，給一個 num，判斷能否量出這個指定 num 的水。
思路：BFS窮舉所有可能性，直到出現(xiàn)目標水量。
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小時）
- 項目介紹（半小時）
準備好一些工作中解決的問題，盡可能詳細的闡述給面試官，告訴他你主要解決了什么問題。
- 系統(tǒng)設(shè)計題：上海地鐵線縱橫交錯（線路與線路之間存在交叉，并且每一條線路站與站之間的發(fā)車間隔可能是不一樣的），現(xiàn)在做一個 app，輸入是起點和終點已經(jīng)出發(fā)時間，輸出一條耗時最短的線路。
從數(shù)據(jù)庫表，到緩存，到算法的設(shè)計。
3. 三面（40分鐘）
三面是抖音上海負責人的面試，因此著重在系統(tǒng)設(shè)計。
項目介紹（15分鐘）
系統(tǒng)設(shè)計：抖音里每秒都產(chǎn)生大量視頻，現(xiàn)在要求持續(xù)計算一段時間內(nèi)的 top k 個最熱門的視頻，你怎么設(shè)計。
這個問題類似于下面這個問題：
實現(xiàn)前5分鐘，1小時，24小時內(nèi)分享最多的feed
從算法的角度，可以簡單的稱之為 Top K Frequent Elements in Recent X mins。算法的角度，本質(zhì)就是設(shè)計一個數(shù)據(jù)結(jié)構(gòu)，支持給某個key的count+1（有一個post被分享了），給某個key的count-1（有一個分享的計數(shù)已經(jīng)過期了），然后查詢Top k。
做法是維護一個有序序列（用鏈表來維護），每個鏈表的節(jié)點的key是 count，value是list of elements that has this count，也用linked list串起來。 比如 a出現(xiàn)2次，b出現(xiàn)3次，c出現(xiàn)2次，d出現(xiàn)1次。那么這個鏈表就是：
{3: [b]} --> {2: [a ->c]} --> {1: [d]}
然后另外還需要一個hashmap，key是element，value是這個element在鏈表上的具體位置。
因為每一次的操作都是 count + 1和 count - 1，那么每次你通過 hashmap 找到對應的element在數(shù)據(jù)結(jié)構(gòu)中的位置，+1的話，就是往頭移動一格，-1的話，就是往尾巴移動一格?？偠灾畯碗s度都是 O(1)。當你需要找 Top K 的時候，也是 O(k)的時間可以解決的。
算法實現(xiàn)請參考：https://github.com/cheergoivan/leetcode/blob/master/src/leetcode/problem460/LFUCache.java
工程角度的優(yōu)化：
如果我要去算最近5分鐘的數(shù)據(jù)，我就按照1秒鐘為一個bucket的單位，收集最近300個buckets里的數(shù)據(jù)。如果是統(tǒng)計最近1小時的數(shù)據(jù)，那么就以1分鐘為單位，收集最近60個Buckets的數(shù)據(jù)，如果是最近1天，那么就以小時為單位，收集最近24小時的數(shù)據(jù)。那么也就是說，當來了一個某個帖子被分享了1次的數(shù)據(jù)的時候，這條數(shù)據(jù)被會分別存放在當前時間(以秒為單位），當前分鐘，當前小時的三個buckets里，用于服務(wù)之后最近5分鐘，最近1小時和最近24小時的數(shù)據(jù)統(tǒng)計。
你可能會疑惑，為什么要這么做呢？這么做有什么好處呢？這樣做的好處是，比如你統(tǒng)計最近1小時的數(shù)據(jù)的時候，就可以隨著時間的推移，每次增加當前分鐘的所有數(shù)據(jù)的統(tǒng)計，然后扔掉一小時里最早的1分鐘里的所有數(shù)據(jù)。這樣子就不用真的一個一個的+1或者-1了，而是整體的 +X 和 -X。當然，這樣做之后，前面的算法部分提出來的數(shù)據(jù)結(jié)構(gòu)就不work了，但是可以結(jié)合下面提到的數(shù)據(jù)抽樣的方法，來減小所有候選 key 的數(shù)目，然后用普通的 Top K 的算法來解決問題。
另外，在分布式環(huán)境下，哪些帖子被分享了多少次這些數(shù)據(jù)，首先在 web server 中進行一次緩存，也就是說web server的一個進程接收到一個分享的請求之后，比如 tweet_id=100 的tweet被分享了。那么他把這個數(shù)據(jù)先匯報給web server上跑著的 agent 進程，這個agent進程在機器剛啟動的時候，就會一直運行著，他接受在臺web server上跑著的若干個web 進程(process) 發(fā)過來的 count +1 請求。
這個agent整理好這些數(shù)據(jù)之后，每隔510秒?yún)R報給中心節(jié)點。這樣子通過510s的數(shù)據(jù)延遲，解決了中心節(jié)點訪問頻率過高的問題。
還可以通過數(shù)據(jù)抽樣進行優(yōu)化。因為那些Top K 的post，一定是被分享了很多很多次的，所以可以進行抽樣記錄。如果是5分鐘以內(nèi)的數(shù)據(jù)，就不抽樣，全記錄。如果是最近1小時，就可以按照比如 1/100 的概率進行 sample。
最后是使用Cache進行緩存計算結(jié)果。對于最近5分鐘的結(jié)果，每隔5s才更新一次。對于最近1小時的結(jié)果，每隔1分鐘更新一次。對于最近24小時的結(jié)果，每隔10分鐘才更新一次。用戶需要看結(jié)果的時候，永遠看的是 Cache 里的結(jié)果。另外用一個進程按照上面的更新頻率去逐漸更新Cache。
總結(jié)：算法方面使用LFU算法來解決。而工程方面使用分段統(tǒng)計，抽樣法和Cache緩存進行優(yōu)化。
以上方案參考自：https://www.jiuzhang.com/qa/219/
4. 總結(jié)
網(wǎng)絡(luò)和操作系統(tǒng)需要復習，復習一些常見的網(wǎng)上都能搜到的字節(jié)考題就行，不用太深入。
算法 leetcode 刷 200~300 道差不多了，另外面試前搜一下字節(jié)考過的算法題，很有可能遇到相同的。
系統(tǒng)設(shè)計題就看平時積累，有想法就說出來，即使不是最優(yōu)解也要說出來。
