目录

• 前言
• 三轮面经
• 关于字节
• 彩蛋

前言

七月收获了字节的意向书，今日得空把面经整理出来分享给大家，也借此把好运分享给大家。

简单介绍下个人情况：

面试前：剑指 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 个区间均匀的桶，遍历一遍整数，将它们存入对应区间的桶中，并统计桶中数字个数。这样就可以找到中位数所在的桶，如果桶中数字还是很多，再进行桶排序，否则进内存中排序即可。

二面

1. 事务的 ACID 特性
2. Innodb 使用的索引结构
3. b+ tree 的优点，为什么要用它
4. 给定复合索引 (a, b, c)，查询语句中用 where a = 1 and c = 1，索引是否会失效？（最左前缀匹配的相关知识）
5. 一条 SQL 语句的执行流程 （不会）
6. 进程和线程的区别
7. 并发和并行的区别
8. 进程调度的策略
9. 死锁发生的原因
10. 手撕代码

• 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 的方案不稳定，有什么稳定的方法吗？

内存不够堆排序，内存够用计数排序。

1. https 如何加密的
2. os 中的 pagefault （缺页中断）
3. mysql 中的底层索引结构？为什么用这个结构
4. hashmap 是线程安全的吗？想要线程安全怎么办？
5. 场景设计

大文件的断点续传

这题网上也有很多方案。老汪是参照 tcp 的滑动窗口和重传机制来回答的。

把大文件分块并打上编号，接收端对块进行有序确认，如果有某块没收到，就告知发送端让其重发。

发送端记录最后一次发送的编号，断点续传时从这个编号开始传。

因为负载均衡，续传的时候要确定从哪个服务器拿的，这个可以让接收端记录发送端的标识。

关于字节

1. 工作强度：大小周，10 10 5.5。不强制加班，做完就可以走，但工作量一般要加班完成。因人而异，也有摸鱼的。
2. 福利：三餐全包，下午茶，房补 1500，免费健身房（基本上工作一年后都会吃胖，hhh）
3. 氛围：扁平化管理，网传风评都挺不错的。
4. 新人培养：mentor 制，一对一带领新人熟悉。不过和老牌 BAT 相比，文档不够完善，新人培养流程还是有些欠缺的。
5. 字节校招的考察重点：后端的话，基本上是要转 go/python 的，所以不怎么考察语言。

主要考察「操作系统」、「数据库原理」、「计网」和「手撕代码」，字节是非常重视手撕的，这个一定要好好准备。当然项目做得好的同学，也是有加分的。

老汪点评：工作强度大，面对的挑战多，薪酬也给力。适合能力强、抗压能力强的同学，扛得住压成长会很快。不过对新人确实有点考验，因人而异吧。

彩蛋

1. 虽然字节的手撕代码比较难，但题库是有限的，多刷面经中的算法题，会有很大概率碰上原题。
2. 有三面挂了的，想投上海 data 部门的，老汪可以帮忙联系 HR 直捞。
3. 祝点赞的各位小伙伴 offer 多多。没点赞的小伙伴嘛，也 offer 多多吧。嘻嘻～
4. 听说发一句 “一切都会好起来的！”，就真的一切都好起来了！