「面經」你可能需要的字節跳動三輪面經
目錄
前言
七月收穫了位元組的意向書，今日得空把面經整理出來分享給大家，也藉此把好運分享給大家。
簡單介紹下個人情況：
面試前：劍指 offer 刷完，Leetcode 大概 70 道。作業系統複習完畢，資料庫不會，計網不會。
後來：一面前一周學了資料庫，三面前三天學了計網。兩周時間陸續刷了 80 道 Leetcode。
希望這篇文章能對大家有所幫助，祝各位 offer 多多！
三輪面經
本人無實習，故而沒有被問到關於項目的問題。
問題構成：手撕程式碼、基礎知識、場景題。
「基礎知識」都是固定答案，因此本篇中只分享題目，不分享答案。
一面
-
手撕程式碼
easy 題：中文字元串轉成數字。例：「五百三十萬六千零三」 -> 5306003。約束：輸入金額在一億以內。要求：做一定的容錯處理，bug free。
這題比較簡單，方法大家應該都能想到。只是要求 bug free 和容錯處理，因此寫程式碼的時候要考慮完善點。比如說輸入異常的情況（字元串是否合法，「五五百」這種就不合法，「3百五」也不合法）。
-
手撕程式碼
leetcode medium 原題：判斷字元串是否滿足斐波那契規則，如：「199100199」。由於 1 + 99 = 100，99 + 100 = 199。
這題老汪是在面試官的引導下才一步一步想到最優解的。（吹爆面試體驗，面試官很耐心的在引導，nice！）
這題的關鍵點就在於如何找到開頭兩個數字 n1, n2。找到了這兩個數字，後面就可以用 n = n1 + n2 的規則通過一次遍歷來判斷是否符合斐波那契規則。找開頭倆數字只能暴搜了，程式碼如下：
public boolean solve(String str){
if(str == null) return false;
int n = str.length();
for(int i = 1; i < n; i++){
int n1 = Integer.parseInt(str.substring(0, i)); //獲得第一個數
for(int j = i + 1; j < n; j++){
int n2 = Integer.parseInt(str.substring(i, j)); //獲得第二個數
if(judege(str, n1, n2, start)) return true;//判斷是否符合規則
}
}
return false;
}
//給定 n1, n2，判斷字元串是否符合斐波那契規則
boolean judge(String str, int n1, int n2, int start){
int n = str.length();
for(int i = start; i < n;){
int n3 = n1 + n2;
int len = (n3 + "").length();
if(start + len > n || n3 != Integer.parseInt(str.substring(i, i + len))) return false; // 下標超了,或者後一個數字不等於 n3
i += len;
}
return true;
}
時間複雜度：O(n^3)，找到開頭兩個數字需要 O(n^2)，判斷字元串是否符合規則需要 O(n)。
這題可以剪枝來稍微降低一些時間消耗，大家可以自行優化。
-
手撕程式碼
10億個無序整數找出中位數。
這題老汪也是在面試官的引導下才一步步想到最優解的。（再次吹爆面試體驗）
由於是 10 億個整數，因此無法在記憶體中處理。也就是說要採用合適的外排序演算法。
這裡可以使用桶排序，使用 n 個區間均勻的桶，遍歷一遍整數，將它們存入對應區間的桶中，並統計桶中數字個數。這樣就可以找到中位數所在的桶，如果桶中數字還是很多，再進行桶排序，否則進記憶體中排序即可。
二面
-
事務的 ACID 特性
-
Innodb 使用的索引結構
-
b+ tree 的優點，為什麼要用它
-
給定複合索引 (a, b, c)，查詢語句中用 where a = 1 and c = 1，索引是否會失效？（最左前綴匹配的相關知識）
-
一條 SQL 語句的執行流程 （不會）
-
進程和執行緒的區別
-
並發和並行的區別
-
進程調度的策略
-
死鎖發生的原因
-
leetcode 原題 41 （不會，換了一題）
給你一個未排序的整數數組，請你找出其中沒有出現的最小的正整數。
思路：要找最小的正整數，數組中有 n 個數字，那麼缺失的最小正整數一定在 [1, n + 1] 內。
因此可以利用數組本身做哈希，遍歷一遍數組，將 [1, n] 內的數字 i 放到對應下標 i - 1 上。
再遍歷一遍數組，第一個 nums[i] != i + 1 的數字 i + 1即為缺失的最小正整數。
程式碼如下：
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for(int i = 0; i < n; i++){
while(nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]){ //(0, n] 的數字放到對應下標上
int temp = nums[i] - 1;
nums[i] = nums[temp];
nums[temp] = temp + 1;
}
}
int i = 0;
for(; i < n && nums[i] == i + 1; i++); // 找到第一個未出現的正整數
return i + 1;
}
時間複雜度：O(n)，雖然有 while 循環，但每個數字最多被交換一次即可到對應下標上。
-
leetcode 原題 3
給定一個字元串，請你找出其中不含有重複字元的 最長子串 的長度。
思路：很經典的一道題了，滑動窗口即可解決。
程式碼如下：
public int lengthOfLongestSubstring(String s) {
if(s == null) return 0;
Map<Character, Integer> map = new HashMap<>();
int start = 0, ans = 0;
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if(map.getOrDefault(c, -1) >= start) start = map.get(c) + 1;
map.put(c, i);
ans = Math.max(ans, i - start + 1);
}
return ans;
}
三面
-
手撕程式碼
演算法題：二維數組，按行遞增，按列遞增，問是否能找到某個數字（劍指offer原題）
思路：利用遞增的特性，從最左下角開始遍歷(該列最大值，該行最小值)。和目標數字比較：
< 目標數，說明這一列都 < 目標數，因此列下標 + 1
> 目標數，說明這一行都 > 目標數，因此行下標 – 1
這樣，每次比較都可以排除一行/一列。
程式碼如下：
public boolean canFind(int[][] matrix, int target){
if(matrix == null || matrix.length == 0) return false;
int rows = matrix.length, cols = matrix[0].length;
int row = rows - 1, col = 0;
while(row >= 0 && col < cols){
if(matrix[row][col] == target) return true;
if(matrix[row][col] > target) row--;
else col++;
}
return false;
}
-
手撕程式碼
演算法題：
2 * 1的小矩形填充滿2 * n的大矩形有多少種方案？
思路：挺簡單的動態規劃題
程式碼如下：
public int nums(int n){
if(n < 0) return 0;
int[] dp = new int[Math.max(n, 2)];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i < n; i++) dp[i] = dp[i - 2] + dp[i - 1];
return dp[n];
}
這裡空間複雜度是 O(n)，也可以通過 狀壓 dp 將空間複雜度降到 O(1)。
-
場景設計
1000 億個無符號整數，找最大的 100 個。記憶體不夠的情況下用什麼方案？記憶體充足的情況下呢？ partition 的方案不穩定，有什麼穩定的方法嗎？
記憶體不夠堆排序，記憶體夠用計數排序。
-
https 如何加密的
-
os 中的 pagefault （缺頁中斷）
-
mysql 中的底層索引結構？為什麼用這個結構
-
hashmap 是執行緒安全的嗎？想要執行緒安全怎麼辦？
-
場景設計
大文件的斷點續傳
這題網上也有很多方案。老汪是參照 tcp 的滑動窗口和重傳機制來回答的。
把大文件分塊並打上編號，接收端對塊進行有序確認，如果有某塊沒收到，就告知發送端讓其重發。
發送端記錄最後一次發送的編號，斷點續傳時從這個編號開始傳。
因為負載均衡，續傳的時候要確定從哪個伺服器拿的，這個可以讓接收端記錄發送端的標識。
關於位元組
-
工作強度：大小周，10 10 5.5。不強制加班，做完就可以走，但工作量一般要加班完成。因人而異，也有摸魚的。
-
福利：三餐全包，下午茶，房補 1500，免費健身房（基本上工作一年後都會吃胖，hhh）
-
氛圍：扁平化管理，網傳風評都挺不錯的。
-
新人培養：mentor 制，一對一帶領新人熟悉。不過和老牌 BAT 相比，文檔不夠完善，新人培養流程還是有些欠缺的。
-
位元組校招的考察重點：後端的話，基本上是要轉 go/python 的，所以不怎麼考察語言。
主要考察「作業系統」、「資料庫原理」、「計網」和「手撕程式碼」，位元組是非常重視手撕的，這個一定要好好準備。當然項目做得好的同學，也是有加分的。
老汪點評：工作強度大，面對的挑戰多，薪酬也給力。適合能力強、抗壓能力強的同學，扛得住壓成長會很快。不過對新人確實有點考驗，因人而異吧。
彩蛋
-
雖然位元組的手撕程式碼比較難，但題庫是有限的，多刷面經中的演算法題，會有很大概率碰上原題。 -
有三面掛了的，想投上海 data 部門的，老汪可以幫忙聯繫 HR 直撈。 -
祝點贊的各位小夥伴 offer 多多。沒點贊的小夥伴嘛，也 offer 多多吧。嘻嘻～ -
聽說發一句 「一切都會好起來的！」，就真的一切都好起來了！
