已删除

2021-06-30 20:39 已编辑

关注

刷Leetcode没用？大四仅3面，就斩获字节跳动offer，怎么做到的？

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

简单介绍下个人情况：

面试前：剑指 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 直捞。
祝<stron>的各位小伙伴 offer 多多。没点赞的小伙伴嘛，也 offer 多多吧。嘻嘻～</stron>
听说发一句 “一切都会好起来的！”，就真的一切都好起来了！

刷Github时发现了一本阿里大神的算法笔记！标星70.5K

作者是ios开发工程师，校招进入阿里巴巴后，转做Go语言服务端开发。

他在校期间连续三年参加ACM-ICPC竞赛。从参赛开始，原计划每天刷一道算法题，实际上每天有时候不止一题，一年最终完成了 600+：

凭借三年刷题经验，他在校招中很快拿到了各大公司的offer，最终他选择了阿里巴巴。
入职前，他把他的刷题经验总结成书，作为礼物赠送给他的学弟学妹，希望同学们都能在最短时间内掌握校招常见的算法及解题思路。
整本书，我仔细看了一遍，作者非常细心地将常见核心算法题和汇总题拆为两部分。
对于急于面试的小伙伴，只需要看完第二部分算法专题中，常见的核心算法题即可。这部分共150页。

文章篇幅有限，如果有需要完整PDF版的朋友，可以点赞此文后 点击此处 凭截图免费获取

而对于有时间的同学，作者还给出了他结合众多数据结构算法书籍，挑选出的一千多道题的解题思路和方法，以供有需要的同学慢慢研究。

这本笔记总共1120页，涵盖了常见笔试面试算法和所有类型算法题的题解思路。
整本书排版非常精美，每个题目先给出解题思路，然后再给出源代码，必要时会用插图展示解题逻辑。

而且所有的题目作者还给出了源代码，读者可以直接运行。

如何阅读本笔记：

先自己读题，思考如何解题。如果15分钟还没有思路，那么先看笔者的解题思路，但是不要看代码。有思路以后自己用代码实现一遍。如果完全不会写，那就看笔者提供的代码，找出自己到底哪里不会写，找出问题记下来，这就是自己要弥补的知识漏洞。如果自己实现出来了，提交以后有错误，自己先 debug。AC以后没有到100%也先自己思考如何优化。如果每道题自己都能优化到100%了，那么一段时间以后进步会很大。所以总的来说，实在没思路，看解题思路;实在优化不到100%，看看代码。

文章篇幅有限，如果有需要完整PDF版的朋友，可以点赞此文后 点击此处 凭截图免费获取

好了，今天就分享到这里了，希望大家能够好好学习，把算法这一块儿给提升上来，也希望本文能够得到大家的喜欢！！