|
|
8月，互联网大厂们的校招已经陆续打响！不少童鞋们也喜迎了字节跳动第一批难不死人的研发类笔试题~笔试结束，哀嚎声一片。当然也有解题高手淡定的表示”可以准备下一轮面试了“。相信参加了/将要参加研发笔试的旁友们都想知道神秘的出题人到底是怎么想的？
为此，我们特地化作出题人肚里的小字节虫，为大家奉上干货：研发笔试的题目类别以及解题思路！
第一类：世界杯开幕式
题目大意：01矩阵，求其中的八连通块的数量。
题解：经典题，BFS 或 DFS。
第二类：文章病句标识
题目大意：求区间合并问题。
题解：经典题，排序后合并区间。
第三类：积分卡牌游戏
题目大意：有n张卡牌，每张上面有两个数字x,y，两人各自选择若干张卡牌，求他们各自选择的卡牌的x的总和相等时，所有选择的卡牌的y的总和的最大值。
题解：动态规划。
d[i][j] 表示前i张牌，两人所选择的牌的差值为j时的最大值，转移方程为:
d[i][j] = max(d[i-1][j], d[i-1][j-x[i]] + y[i], d[i-1][j+x[i]] + y[i])
注意: 空间可能不够用，由于状态 d[i] 只与状态 d[i-1] 有关，可以使用滚动数组来优化空间。
时间复杂度 O(n*Σx)
第四类：区间最大最小值
题目大意：给定两个序列a、b，求有多少个区间[l, r]满足，区间a[l, r]的最大值小于区间b[l, r]的最小值
题解：
解法1
1.通过观察发现，固定区间的左端点 l，随着右端点 r 的右移，区间 a[l,r] 的最大值只会变大，区间 b[l,r] 的最小值只会变小，具有单调性
2.因此我们枚举区间的左端点 l，使用二分查找的方法，找到 a[l,r] 的最大值小于 b[l,r] 的最小值的临界点 r，此时答案增加计数 (r - l + 1)
3.其中区间最值可以使用 ST 表查询，单次查询复杂度为常数
4.时间复杂度 O(n*log(n))
解法2
1.通过观察发现，对于两个满足条件的区间 [l, r]和 [l', r']，若 l'>=l，那么 r'>=r。
2.因此我们可以使用两个指针 l 和 r，初始都在序列的第一个位置，并重复以下过程:
1.一直向右移动l，直到满足 a[l,r] 的最大值 < b[l,r] 的最小值或者 l>r 为止
2.答案增加计数 (r - l + 1)
3.r 向右移动一个单位
3.使用两个单调队列分别维护 a[l,r] 的最大值和 b[l,r] 的最小值。
4.时间复杂度 O(n)
第五类：直播爱好者
题目大意：本题是区间调度问题，可以用贪心算法实现。
题解：
解法1
1.本题需要注意的是直播可能跨天，因此我们可以将原始输入复制一份，使其扩展到2*M的时间区间内，再进行贪心算法求解
2.贪心算法基于优先选择结束时间最早的直播节目。因此我们可以将将输入数据按照结束时间排序
3.排序后，我们可以用两层循环，外层循环选定一个直播节目作为起点，内层循环用贪心算法获取这个节目结束到第二天该节目的开始时间之前，能够尽早结束的节目。时间复杂度为 O(n^2)
解法2
1.解法1在确定第一个区间之后使用的贪心算法存在大量的重复计算，而对于某个区间 i 的下一个满足 t[i]≤s[j] 的所有 j 中 t[j] 最小的那个区间是确定的，可以预处理并记录对应关系，此部分时间复杂度为 O(n*logn)
2.得到对应关系后我们可以使用倍增法，维护一个数组 next[i][j] 表示区间 i 在走 2^j 步后所到达的区间，再利用倍增函数对于每个区间只需要 O(logn) 的复杂度即可找到答案，因此整个算法的复杂度降为 O(n*logn)
解法3
1.本题还有一种除去排序外只需时间复杂度 O(n) 的解法。有兴趣的同学可以试着思考一下并在本文下讨论哦
看完以上笔试解密，是不是顿时觉得杨超越上身，充满力量！
已经参加了第一场研发笔试的童鞋，可以对个人的笔试结果做个判断~即将要迎战之后几场笔试的朋友们，相信经过认真总结和反复练习，优秀的你一定能斩获字节跳动的offer！
之后几场研发类岗位笔试安排：
8月25日；9月9日、20日；10月07日、20日；11月11日；12月2日；1月6日
有其他招聘问题，欢迎点击字节跳动招聘Q&A页面：job。bytedance.com/campus/q&a 了解更多信息~
我们提供研发、产品、运营、职能等各类岗位5000+offer，欢迎点击文末“了解更多”投递简历给我们！记住，要快！先到先得哦！
|
|
发表于 2018-8-17 09:38:48