「面经」你可能需要的字节跳动三轮面经（代号零三）

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

前言

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

简单介绍下个人情况：

面试前：剑指 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 的规则通过一次遍历来判断是否符合斐波那契规则。找开头俩数字只能暴搜了，代码如下：

publicbooleansolve(Stringstr){ if(str==null)returnfalse; intn=str.length(); for(inti=1;i<n;i ){ intn1=Integer.parseInt(str.substring(0,i));//获得第一个数 for(intj=i 1;j<n;j ){ intn2=Integer.parseInt(str.substring(i,j));//获得第二个数 if(judege(str,n1,n2,start))returntrue;//判断是否符合规则 } } returnfalse; } //给定n1,n2，判断字符串是否符合斐波那契规则 booleanjudge(Stringstr,intn1,intn2,intstart){ intn=str.length(); for(inti=start;i<n;){ intn3=n1 n2; intlen=(n3 "").length(); if(start len>n||n3!=Integer.parseInt(str.substring(i,i len)))returnfalse;//下标超了,或者后一个数字不等于n3 i =len; } returntrue; }

时间复杂度：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即为缺失的最小正整数。

代码如下：

publicintfirstMissingPositive(int[]nums){ intn=nums.length; for(inti=0;i<n;i ){ while(nums[i]>0&&nums[i]<=n&&nums[nums[i]-1]!=nums[i]){//(0,n]的数字放到对应下标上 inttemp=nums[i]-1; nums[i]=nums[temp]; nums[temp]=temp 1; } } inti=0; for(;i<n&&nums[i]==i 1;i );//找到第一个未出现的正整数 returni 1; }

时间复杂度：O(n)，虽然有 while 循环，但每个数字最多被交换一次即可到对应下标上。

leetcode 原题 3

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

思路：很经典的一道题了，滑动窗口即可解决。

代码如下：

publicintlengthOfLongestSubstring(Strings){ if(s==null)return0; Map<Character,Integer>map=newHashMap<>(); intstart=0,ans=0; for(inti=0;i<s.length();i ){ charc=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); } returnans; }三面

手撕代码

算法题：二维数组，按行递增，按列递增，问是否能找到某个数字（剑指offer原题）

思路：利用递增的特性，从最左下角开始遍历(该列最大值，该行最小值)。和目标数字比较：

< 目标数，说明这一列都 < 目标数，因此列下标 1

> 目标数，说明这一行都 > 目标数，因此行下标 - 1

这样，每次比较都可以排除一行/一列。

代码如下：

publicbooleancanFind(int[][]matrix,inttarget){ if(matrix==null||matrix.length==0)returnfalse; introws=matrix.length,cols=matrix[0].length; introw=rows-1,col=0; while(row>=0&&col<cols){ if(matrix[row][col]==target)returntrue; if(matrix[row][col]>target)row--; elsecol ; } returnfalse; }