分享字节2021春招客户端开发笔试经历

字节2021春招客户端开发笔试

A

题意:输入一个数组,输出一个相同长度的数组,每个相同位置的元素对应了输入数组的后一个比自己大的元素与当前位置的间隔,若没有比自己大的数,输出-1 Input:

5  [3, 1, 2, 4, 5]

Output:

[3, 1, 1, 1, -1]

解题结果:AC,leetcode基本原题

https://leetcode-cn.com/problems/next-greater-element-ii/

B

题意:输入n个人的身高,这n个人围着站成一圈,输出在它所有可能的排序中,最大身高差的最小值

Input:

4 100 150 200 250

Output:

100

Hint:

最后的可能排序为100 150 250 200

解题结果:AC

原理:与当前元素最近的元素的距离是最小的,与当前元素次近的元素的距离是永远可以被满足的,所以我们取整个数组的所有元素与其次近的元素的距离(有两个,前后次近距离中取小)的最大值

排序后,记录整个数组中当前元素与前第二个元素和后第二个元素的差的最小值的最大值。

特例:n==3时直接输出最大值而不取最小值

C

题意:输入M条指令,指令形式为"op x y",

  • 当op == 1,说明我们希望将号码为x和号码为y的书放在同一个书架上

  • 当op == 2,说明我们不希望将号码为x和号码为y的书放在同一个书架上

求在所有op==1的指令满足之后,op==2的指令有多少个不能被满足?

Input:

4 1 1 2 2 1 3 1 2 3 2 1 4

Output:

1

解题结果:AC

经典并查集,但是题目规定书号码x, y <= 1e9,所以不能直接建数组,而是使用哈希表

D

题意:输入少于24000个长度小于16的字符串,我们定义两个字符串s1和s2是相似的,如果它满足:

  • s2字符串可以由s1字符串增加、删除、更改一个字符得到

求满足相似的字符串的最长子序列的长度

Input:

cat  dig dog fig fin fine  fog wine

Output:

5

解题结果:约等于15%,不记得了

不会,直接遍历了一遍,求子串(子串和子序列不一样)的最长长度,可能是用dp,没想到状态转移方程

直接print 1能得到30%
欢迎大神指导


#笔试题目##字节跳动#
全部评论
第四题是图论 + 记忆化搜索 建图: 时间复杂度取决于建图,n = 25000,若a 可以指向 b,则可以a对b连一条有向的边,如果直接暴力枚举时间复杂度是O(n^2),首先将所有单词存入哈希表中,然后枚举所有的单词,假设枚举到单词是s,下标是a,计算出s可以连接的所有单词,添加最多次数是16 * 26左右,删除16左右,插入16左右,若计算出来的单词在哈希表中存在,对应下标是b,则a对b连一条有向边即可,大概时间复杂度上限400 * 25000次左右 记忆化搜索: 计算出所有的点x,从x点出发能到达的最大长度,去最大值即可
2 回复
分享
发布于 2021-03-07 21:53
同最后一题不会
1 回复
分享
发布于 2021-03-07 22:03
秋招专场
校招火热招聘中
官网直投
大佬A了几道啊
点赞 回复
分享
发布于 2021-03-07 21:36
大佬啥时候投的啊 啥时候收到笔试通知的😭
点赞 回复
分享
发布于 2021-03-07 22:12
第二题是怎么个思路啊,没看明白,求大佬指点
点赞 回复
分享
发布于 2021-03-07 22:18
tql,tql
点赞 回复
分享
发布于 2021-03-08 13:06
为什么第三题能用hashmap不能用数组呀
点赞 回复
分享
发布于 2021-03-08 14:19

相关推荐

9 54 评论
分享
牛客网
牛客企业服务