你可能需要的字节跳动三轮面经
前言
本菜鸡20年提前批收获了字节的意向书，正好今天字节研发提前批开启，把面经整理出来分享给大家，也借此把好运分享给大家。
简单介绍下面试前的个人情况：
面试前：剑指 offer 刷完，Leetcode 大概 70 道。操作系统复习完毕，数据库不会，计网不会。
后来：一面前一周学了数据库，三面前三天学了计网。两周时间陆续刷了 80 道 Leetcode。
希望这篇文章能对大家有所帮助，祝各位 offer 多多！
小小打个广告：
字节跳动校招内推码: SGRHD7E
（免笔试！优先筛选简历！多一次投递机会）
投递链接: https://jobs.toutiao.com/s/YKGk76E
有任何问题欢迎评论哦，12小时内必定回复~
三轮面经
本人无实习，故而没有被问到关于项目的问题。
问题构成：手撕代码、基础知识、场景题。
「基础知识」都是固定答案，因此本篇中只分享题目，不分享答案。
一面
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 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 9 5。不强制加班，做完就可以走，但工作量一般要加班完成。因人而异，也有摸鱼的。
福利：三餐全包，下午茶，房补 1000，免费健身房（基本上工作一年后都会吃胖，hhh）
氛围：扁平化管理，网传风评都挺不错的。
新人培养：mentor 制，一对一带领新人熟悉。公司内也有各种技术文档和视频可以学习。
字节校招的考察重点：后端的话，基本上是要转 go/python 的，所以不怎么考察语言。
主要考察「操作系统」、「数据库原理」、「计网」和「手撕代码」，字节是非常重视手撕的，这个一定要好好准备。当然项目做得好的同学，也是有加分的。
点评：工作强度大，面对的挑战多，薪酬也给力。适合能力强、抗压能力强的同学，扛得住压成长会很快。不过对新人确实有点考验，因人而异吧。
彩蛋
虽然字节的手撕代码比较难，但题库是有限的，多刷面经中的算法题，会有很大概率碰上原题。
内推码: SGRHD7E，投递链接: https://jobs.toutiao.com/s/YKGk76E。（免笔试！优先筛选简历！多一次投递机会）
祝点赞的各位小伙伴 offer 多多。没点赞的小伙伴嘛，也 offer 多多吧。嘻嘻～
听说发一句 “一切都会好起来的！”，就真的一切都好起来了！