关键词：
字节跳动这家公司，应该是所有秋招的公司中，对算法最重视的一个了，每次面试基本都会让你手撕算法，今天这篇文章就记录下当时被问到的几个算法题，并且每个算法题我都详细着给出了最优解，下面再现当时的面试场景。看完一定让你有所收获
一、小牛试刀：有效括号
大部分情况下，面试官都会问一个不怎么难的问题，不过你千万别太开心，因为这道题往往可以拓展出更多有难度的问题，或者一道题看起来很简单，但是给出最优解，确实很不容易的。这道题是这样的
给定一个只包括 ‘(‘，‘)‘的字符串，判断字符串是否有效。注：空字符串属于有效字符串
示例 1:
输入: "(())"
输出: true
实例 2：
输入: "())("
输出: false
第一眼看到这道题，我去，这么简单，稳了（因为一面的时候，刚刚被面试官怼过勇者斗恶龙的DP题，在 leetcdoe 属于 hard 级别）。
其实这道题的 leetcode 第 20 题的简化版，属于 easy 级别
于是我也不假思索直接用栈来解决了，相信 99% 都会用栈解决吧？这里我稍微说以下过程吧，步骤如下：
1、在遍历字符串的过程中，遇到 "(" 就让它入栈，遇到 ")" 就判断下栈里面有没有 "(" ：
（1）、如果有，则把处于栈顶的 "(" 弹出，相当于和 ")" 进行匹配，然后继续往后遍历字符串
（2）、如果没有，则匹配失败。相当于字符串的最前面出现了 ")"，显然这是不合理的。2、当字符串遍历完成，判断栈是否为空，如果为空则表示字符串有效，否则无效。
为了兼顾小白，我该给你们画了个图演示，，，，我太良心了。
代码如下所示（Java，不过不是学Java也能看懂）
public static boolean isValid(String s)
if(s == null || s.length() < 1)
return true;
int n = s.length();// 字符串长度
// 创建一个栈来装字符
Stack<Character> stack = new Stack<>();
// 遍历字符串
for(int i = 0; i < n; i++)
// 获取字符串的第 i 个字符
char c = s.charAt(i);
if(c == '(')
stack.push(c);
else
if(stack.isEmpty())
return false;
else
stack.pop();
// 判断是否为空
if(stack.isEmpty())
return true;
return false;
二、优化
接着面试官说我这道题的空间复杂度是 O(n)，问我能优化一下吗？
说实话，如果你做过 leetcode 的第 20 题，可能你的脑子会被定向也不一定，因为那道题用栈来处理就是最优解的了。不过这道题属于简化版，其实可以把空间复杂度优化成 O(1)，大家可以想一下哦。
由于我们栈里面存放的都是同一种字符 "(" ，其实我们可以用一个变量来取代栈的，这个变量就记录 "(" 的个数，遇到 "(" 变量就加 1，遇到 ")" 变量就减 1，栈为空就相当于变量的值为 0。
当时脑子有点不知为啥，就马上相当这个方法了，于是一分钟就修改好了代码，如下：
public static boolean isValid(String s)
if(s == null || s.length() < 1)
return true;
int n = s.length();// 字符串长度
// 用来记录遇到的 "(" 的个数
int sum = 0;
// 遍历字符串
for(int i = 0; i < n; i++)
// 获取字符串的第 i 个字符
char c = s.charAt(i);
if(c == '(')
sum++;
else
if(sum == 0)
return false;
else
sum--;
return sum == 0 ? true : false;
这样子的话，时间复杂度为 O(n)，空间复杂度为 O(1)。
三、最长有效括号
接着面试官就继续就这道题继续加大难度，问题改为如下
给定一个只包含 ‘(‘ 和 ‘)‘ 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"其实这道题就是 leetcode 的原题，第 32 题，难度为 hard。
这道题由于我之前做过，微微一笑，假装用严肃的表情思考一下，然后马上给出了思路，刚开始我是用暴力法的。
1、暴力法
暴力法其实很简单，就是最开始把第一个字符当做最长有效括号的首字符来遍历字符串，接着把第二个字符当做最长有效括号的首字符来遍历字符串，接着把第三个字符......
例如对于 s = "( ) ) ( ( ) )"。
把第一个字符作为首字符，则 max = 2 （遇到第三个字符 ‘)‘ 就匹配不了了）
把第二个字符作为首字符，则 max = 0 （一开始就是 ‘)‘，显然啥也匹配不了）
把第三个字符作为首字符，则 max = 0
把第四个字符作为首字符，则 max = 4
.....
这种做法的时间复杂度为 O(n^2)，空间复杂度为 O(1)
基本上面那道题一样，只是做了 n 次遍历。
接着面试官问，还能优化吗？
早就知道会问优化的了，我自己之前也做过这道题，于是假装思考了一下，马上给出了优化。
2、优化
这道题的优化版本我们仍然是用栈来做，不过入栈的时候，不是让 "(" 入栈，而是让 "(" 的下标入栈。步骤如下：
1、先把 -1 放入栈内。（至于为什么？看到后面你就知道了）
2、、对于遇到的每个 ‘(‘ ，我们将它的下标放入栈中。
3、对于遇到的每个 ‘)’ ，我们弹出栈顶的元素并将当前元素的下标与弹出元素下标作差，得出当前有效括号字符串的长度。
通过这种方法，我们继续计算有效子字符串的长度，并最终返回最长有效子字符串的长度。
看不懂？没事，我弄个例子画几个图，例如 s = "( ) ) ( ( ) )"，并且用变量 max 来保存最长有效字符串的程度，i 表示当前字符串的下标
0、初始化：max = 0; i = 0。-1 放入栈内
1、i = 0，s[i] = ‘(‘，下标 i = 0 入栈
2、i = 1，s[i] = ‘)‘，出栈; i - 栈顶元素 = 1 - (-1) = 2，此时 max = 2
3、i = 2，s[i] = ‘)‘，出栈；这个时候要注意：由于 -1 出栈后，栈顶没有元素了，所以这个时候我们必须把 ‘)‘ 的下标入栈，相当于最开始的初始化。
4、i = 3，s[i] = ‘(‘，入栈;
5、i = 4，s[i] = ‘(‘，入栈;
6、i = 5，s[i] = ‘)‘，出栈；i - 栈顶 = 5 - 3 = 2；此时 max = 2;
7、i = 6，s[i] = ‘)‘，出栈；i - 栈顶 = 6 - 2 = 4；此时 max = 4;
8、遍历结束，最长有效括号为 4。
看不大懂？没事，看下代码加深理解勒，代码如下：
public int longestValidParentheses(String s)
int max = 0;
Stack<Integer> stack = new Stack<>();
stack.push(-1);
for (int i = 0; i < s.length(); i++)
if (s.charAt(i) == '(')
//下标入栈
stack.push(i);
else
// 出栈
stack.pop();
// 看栈顶是否为空，为空的话就不能作差了
if (stack.empty())
stack.push(i);
else
// i - 栈顶，获得档期有效括号长度
max = Math.max(max, i - stack.peek());
return maxans;
这种做法的时间复杂度为 O(n)，空间复杂度为 O(n)，能想到用栈来处理，算是很不错的了。
4、最后一击
我以为我给出这个解法算是可以的了，面试官应该换一道题的了，然后，面试官又来了一句：还能再优化吗？。这个时候我陷入了沉思.......
看文章的各位大佬们可以想一想在空间上是否还能优化，因为在时间上是不可能优化的了。
想了一会，居然不可以用栈，优化的方案肯定是类似于上面那道题一样，用记录数量的变量来代替栈，然后就被我想出了，具体如下：
实际上，这道题仍然可以像上面那样，用变量来代替栈来优化，不过这个时候我们需要两个变量，我们假设变量为 left 和 right。
我们在从从左到右遍历字符串的过程中，用 left 记录 ‘(‘ 的数量，用 right 记录 ‘)‘ 的数量。并且在遍历的过程中：
1、如果 left == right，显然这个时候 right 个 ‘)‘ 都将一定能够得到匹配。所以当前的有效括号长度为 2 * right。然后更新 max。
2、如果 left < right，显然这个时候部分 ‘)‘ 一定得不到匹配，此时我们把 left 和 right 都置为 0。
当遍历完字符串，我们是否就得到最大长度的有效括号了呢？大家可以想一下
答是不可以的，我们还需要从右到左遍历计算一下。
为什么呢？
因为实际上 ‘(‘ 和 ‘)‘ 其实是等价的，为什么就不可以倒过来遍历计算呢？所以，千万别忽略了哈。
最后的代码如下：
public int longestValidParentheses(String s)
if(s == null || s.length() < 1)
return 0;
int left = 0, right = 0, max = 0;
// 从左到右
for (int i = 0; i < s.length(); i++)
if (s.charAt(i) == '(')
left++;
else
right++;
if (left == right)
max = Math.max(max, 2 * right);
else if(right > left)
left = right = 0;
left = right = 0;
// 从右到左
for (int i = s.length() - 1; i >= 0; i--)
if (s.charAt(i) == '(')
left++;
else
right++;
if (left == right)
max = Math.max(max, 2 * left);
else if (left > right)
left = right = 0;
return max;
这种做法的时间复杂度为 O(n)，空间复杂度为 O(1)。
总结
说时候，最后一种方法还是比较难想到了，从这次面试中也可以看出，千万不要看一道题很简单，有些题要做出来很简单，但是，如果要以最优解的方式做出来，难度马上指数上升。。
如果你后面看不大懂，建议多看几遍哦，这道题考的频率还是挺高的，主要是可以做的方法多，每种方法的效率又不一样，不过我这里必须给你们的提醒，就是平时在做题的时候，一定要寻找最优解，而不是 ac 了就不管了，应该多看看别人的解法。
有收获？希望老铁们来个三连击，给更多的人看到这篇文章
1、点赞，可以让更多的人看到这篇文章
2、关注原创微信公众号『苦逼的码农』，为了巩固计算机基础知识（计算机网络+ 操作系统+数据库+Linux）以及算法，最近开了个微信公众号『苦逼的码农』，感兴趣的可以关注，重点讲解算法相关文章，嘻嘻。后台回复『电子书』送你一份精选电子书大礼包，包含各类技能的优质电子书
字节跳动面试笔试总结——算法岗位
目录1.一棵二叉树，求最大通路长度（即最大左右子树高度之和） 查看详情
第一次面试字节跳动
...========================本人南京某985渣渣研究生一枚，生平第一次面试。。。说出来你们可能不信虽然基本上是GG的节奏，还是写下这个帖子来记录一下吧，大家也可以参考一下。======================================================================... 查看详情
字节跳动面试——图形图像算法实习
目录项目C++图形学编程题主要涉及的问题有项目、C++、图形学和编程题，大概还记得下面这些。项目1.项目的目的2.项目的创新性3.你的职责4.项目细节，具体每个部分怎么实现的，用了哪些技术C++1.重载和重写2.参数传递时，传值... 查看详情
字节跳动面试——算法
...表合并二面1.我看你简历上都是CV项目，你愿意转到推荐算法这边还是坚持你的CV2.你对于机器学习很多东西都不了解么？3.说说过拟合和欠拟合的概念吧4.过拟合怎么处理？5.如何降低模型的容量6.你用过dropout么？介绍一下7.逻辑... 查看详情
字节跳动2-1算法二轮面试202203-29(代码片段)
罗马数字包含以下七种字符： I， V， X， L，C，D 和 MI 1V 5X 10L 50C 100D 500M 1000这道题对应的是leetcode 中的12.整数转罗马数字packageexample;publicclass... 查看详情
2019字节跳动面试时手撕代码题(持续更新~)(代码片段)
1.N阶乘末尾0的个数。输入描述:输入为一行，n(1≤n≤1000)输出描述:输出一个整数,即题目所求解法：要判断末尾有几个0就是判断可以整除几次10。10的因子有5和2，而在0~9之间5的倍数只有一个，2的倍数相对较多，所以本题也... 查看详情
记一次某公司面试题：合并有序数组(代码片段)
来源2021/09/24：接到某公司面试，手撕一到合并有序数组的题，当时做的差不多了，面试官时间给的相对短了一些，临界值处理有问题，没完全写出来有些遗憾，不过至少自己思路没错，参考网上给... 查看详情
记一次某公司面试题：合并有序数组(代码片段)
来源2021/09/24：接到某公司面试，手撕一到合并有序数组的题，当时做的差不多了，面试官时间给的相对短了一些，临界值处理有问题，没完全写出来有些遗憾，不过至少自己思路没错，参考网上给... 查看详情
面经1：字节跳动：22年实习生大数据开发面试（一面凉经）
...里到外都透漏着我啥也不是首先进行了自我介绍，第一次面试并不是特别了解，自我介绍说了好久，以至于面试官已经听的不耐烦了，还没说完，在我换气的间隙面试官插话进来，强行结束了自我介绍... 查看详情
为什么面试狂问redis，阿里面试官把我问到哑口无言…
...新浪、阿里、腾讯、百度、美团、小米等。Redis也是大厂面试最爱问的，尤其是Redis客户端、Redis高级功能、Redis持久化和开发运维常用问题探讨、Redis复制的原理和优化策略、Redis分布式解决方案等。Redis我们在工作中经常会... 查看详情
java面试者的经历，吐血分享字节跳动的java面试经验技巧
...在哪里？你们的sessioncookie在项目里运用到哪里？算法题：[删除链表中重复的节点]在一个排序的链表中,存在重复的节点, 查看详情
字节跳动面经——实习算法岗
目录一面二面三面一面一面是一个特别和蔼的面试官，我们用Q来代表面试官。A表示我。A：面试官，你好Q：你好，先坐一下自我介绍吧A：好的,balabala。（这个地方大家千万不要紧张，放平心态，在下面先准备好自我介绍，上去... 查看详情
2022字节跳动数据仓库实习面经(代码片段)
👊先和大家说一下情况，3月4号面试的字节跳动数据研发岗位直接把我挂了，我满脸疑惑，但是抱着学习和提升自我的心态，打电话问问hr，像看看面试官给我面试的评价，hr说，面试官就两行，... 查看详情
字节跳动测试岗面试挂在二面，我复盘总结了失败原因，决定再战一次
...不是科班出身没有问太多计算机相关的问题，因为第一次找工作，字节的游戏专场又是最早开始的，就投递了，投递的是游戏测试开发岗，字节是自己投的第一家公司，也是第一家笔试面试的公司。一般 查看详情
为了这一次字节跳动java面试机会，我准备了158天，一个疏忽让我前功尽弃！
简历内推面试是走的内推途径，因为内推的简历通过率远高于其他方式；我的内推的途径有：联系我在字节跳动工作的一个大学学长。在线面试，有个线上文本编辑器，类似leetcode那种，可以在线编程。然... 查看详情
去了字节跳动，回来聊一聊字节跳动的面试...(代码片段)
一、算法题一面：1.lc里最长上升子序列的变形题2.实现输入英文单词联想的功能二面：1.矩阵旋转，要求空间复杂度O(1)2.无序的数组的中位数。要求时间复杂度尽可能的小二、计算机网络tcp怎么保证数据包有序主机每... 查看详情
我经历的字节跳动后台开发实习二面，面试官说叫我补补操作系统和算法(代码片段)
...！！在一面过了9天之后开始了，二面，这一次不同，是一个看起来就，嗯，看起来就觉得肯定很强的人，开始先是问我可以实习多久，以及未来的 查看详情
字节跳动面试经验汇总
...己，所以就投了字节的简历，Java研发方向的，之后接到面试通知，总共耗时了2个星期，一共4轮面试，整个过程比较紧张，提心吊胆的，不过好在最后终于拿到了offer，所以特分享一下字节跳动Java 查看详情