最近參加了字節(jié)跳動的后臺開發(fā)工程師面試如失，記錄一下面經(jīng)。（ps：社招兩年經(jīng)驗(yàn)）
1. 一面（1小時）
一面主要是基礎(chǔ)考察送粱，包括簡歷中提到的以及一些標(biāo)準(zhǔn)的基礎(chǔ)問題复斥。
VUE和React區(qū)別（因?yàn)楹啔v中提到了VUE）
VUE的內(nèi)部機(jī)制（問一下前端技術(shù)是因?yàn)槲液啔v提到自己是全棧工程師嘁捷，正常情況下是不會出現(xiàn)前端問題的）
CRSF的機(jī)制
Spring IOC和BEAN循環(huán)依賴
Kafka和Cassandra內(nèi)部機(jī)制（簡歷中提及）
算法題：有 2n 個人，序號為 0 到 2n-1，要求兩兩握手惨缆，但是握手不能存在交叉線，求最后一
共存在多少種握手可能捧弃，寫出 f(2n)表達(dá)式拿诸。
思路：假設(shè)0號和i號點(diǎn)握手，那么整張圖就分為了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)目標(biāo)水量。
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小時）
- 項目介紹（半小時）
準(zhǔn)備好一些工作中解決的問題闪盔，盡可能詳細(xì)的闡述給面試官弯院，告訴他你主要解決了什么問題。
- 系統(tǒng)設(shè)計題：上海地鐵線縱橫交錯（線路與線路之間存在交叉泪掀，并且每一條線路站與站之間的發(fā)車間隔可能是不一樣的）听绳，現(xiàn)在做一個 app，輸入是起點(diǎn)和終點(diǎn)已經(jīng)出發(fā)時間异赫，輸出一條耗時最短的線路椅挣。
從數(shù)據(jù)庫表头岔，到緩存，到算法的設(shè)計贴妻。
3. 三面（40分鐘）
三面是抖音上海負(fù)責(zé)人的面試切油，因此著重在系統(tǒng)設(shè)計。
項目介紹（15分鐘）
系統(tǒng)設(shè)計：抖音里每秒都產(chǎn)生大量視頻名惩，現(xiàn)在要求持續(xù)計算一段時間內(nèi)的 top k 個最熱門的視頻澎胡，你怎么設(shè)計。
這個問題類似于下面這個問題：
實(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。
做法是維護(hù)一個有序序列（用鏈表來維護(hù)）呼寸，每個鏈表的節(jié)點(diǎn)的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在鏈表上的具體位置捐祠。
因?yàn)槊恳淮蔚牟僮鞫际?count + 1和 count - 1，那么每次你通過 hashmap 找到對應(yīng)的element在數(shù)據(jù)結(jié)構(gòu)中的位置桑李，+1的話踱蛀，就是往頭移動一格，-1的話芙扎，就是往尾巴移動一格√畲螅總而言之復(fù)雜度都是 O(1)戒洼。當(dāng)你需要找 Top K 的時候，也是 O(k)的時間可以解決的允华。
算法實(shí)現(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ù)。那么也就是說庶弃，當(dāng)來了一個某個帖子被分享了1次的數(shù)據(jù)的時候衫贬，這條數(shù)據(jù)被會分別存放在當(dāng)前時間(以秒為單位），當(dāng)前分鐘歇攻，當(dāng)前小時的三個buckets里固惯，用于服務(wù)之后最近5分鐘，最近1小時和最近24小時的數(shù)據(jù)統(tǒng)計缴守。
你可能會疑惑葬毫，為什么要這么做呢？這么做有什么好處呢屡穗？這樣做的好處是贴捡，比如你統(tǒng)計最近1小時的數(shù)據(jù)的時候，就可以隨著時間的推移鸡捐，每次增加當(dāng)前分鐘的所有數(shù)據(jù)的統(tǒng)計栈暇，然后扔掉一小時里最早的1分鐘里的所有數(shù)據(jù)。這樣子就不用真的一個一個的+1或者-1了箍镜，而是整體的 +X 和 -X源祈。當(dāng)然，這樣做之后色迂，前面的算法部分提出來的數(shù)據(jù)結(jié)構(gòu)就不work了香缺，但是可以結(jié)合下面提到的數(shù)據(jù)抽樣的方法，來減小所有候選 key 的數(shù)目歇僧，然后用普通的 Top K 的算法來解決問題图张。
另外，在分布式環(huán)境下诈悍，哪些帖子被分享了多少次這些數(shù)據(jù)祸轮，首先在 web server 中進(jìn)行一次緩存，也就是說web server的一個進(jìn)程接收到一個分享的請求之后侥钳，比如 tweet_id=100 的tweet被分享了适袜。那么他把這個數(shù)據(jù)先匯報給web server上跑著的 agent 進(jìn)程，這個agent進(jìn)程在機(jī)器剛啟動的時候舷夺，就會一直運(yùn)行著苦酱，他接受在臺web server上跑著的若干個web 進(jìn)程(process) 發(fā)過來的 count +1 請求售貌。
這個agent整理好這些數(shù)據(jù)之后，每隔510秒?yún)R報給中心節(jié)點(diǎn)疫萤。這樣子通過510s的數(shù)據(jù)延遲颂跨，解決了中心節(jié)點(diǎn)訪問頻率過高的問題。
還可以通過數(shù)據(jù)抽樣進(jìn)行優(yōu)化扯饶。因?yàn)槟切㏕op K 的post恒削，一定是被分享了很多很多次的，所以可以進(jìn)行抽樣記錄帝际。如果是5分鐘以內(nèi)的數(shù)據(jù)蔓同，就不抽樣，全記錄蹲诀。如果是最近1小時斑粱，就可以按照比如 1/100 的概率進(jìn)行 sample。
最后是使用Cache進(jìn)行緩存計算結(jié)果脯爪。對于最近5分鐘的結(jié)果则北，每隔5s才更新一次。對于最近1小時的結(jié)果痕慢，每隔1分鐘更新一次尚揣。對于最近24小時的結(jié)果，每隔10分鐘才更新一次掖举。用戶需要看結(jié)果的時候快骗，永遠(yuǎn)看的是 Cache 里的結(jié)果。另外用一個進(jìn)程按照上面的更新頻率去逐漸更新Cache塔次。
總結(jié)：算法方面使用LFU算法來解決方篮。而工程方面使用分段統(tǒng)計，抽樣法和Cache緩存進(jìn)行優(yōu)化励负。
以上方案參考自：https://www.jiuzhang.com/qa/219/
4. 總結(jié)
網(wǎng)絡(luò)和操作系統(tǒng)需要復(fù)習(xí)藕溅，復(fù)習(xí)一些常見的網(wǎng)上都能搜到的字節(jié)考題就行，不用太深入继榆。
算法 leetcode 刷 200~300 道差不多了巾表，另外面試前搜一下字節(jié)考過的算法題，很有可能遇到相同的略吨。
系統(tǒng)設(shè)計題就看平時積累集币，有想法就說出來，即使不是最優(yōu)解也要說出來翠忠。
