字节跳动2017秋招编程题汇总
时长:120分钟 总分:100分
203浏览 0人已完成答题
题型介绍
| 题型 | 填空题 | 简答题 |
|---|---|---|
| 数量 | 3 | 8 |
字典序
对于n=11, m=4, 按字典序排列依次为1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9, 因此第4个数是2.
对于n=200, m=25, 按字典序排列依次为1 10 100 101 102 103 104 105 106 107 108 109 11 110 111 112 113 114 115 116 117 118 119 12 120 121 122 123 124 125 126 127 128 129 13 130 131 132 133 134 135 136 137 138 139 14 140 141 142 143 144 145 146 147 148 149 15 150 151 152 153 154 155 156 157 158 159 16 160 161 162 163 164 165 166 167 168 169 17 170 171 172 173 174 175 176 177 178 179 18 180 181 182 183 184 185 186 187 188 189 19 190 191 192 193 194 195 196 197 198 199 2 20 200 21 22 23 24 25 26 27 28 29 3 30 31 32 33 34 35 36 37 38 39 4 40 41 42 43 44 45 46 47 48 49 5 50 51 52 53 54 55 56 57 58 59 6 60 61 62 63 64 65 66 67 68 69 7 70 71 72 73 74 75 76 77 78 79 8 80 81 82 83 84 85 86 87 88 89 9 90 91 92 93 94 95 96 97 98 99 因此第25个数是120… 输入描述： 输入仅包含两个整数n和m。
数据范围:
对于20%的数据, 1 <= m <= n <= 5
对于80%的数据, 1 <= m <= n <= 10^7
对于100%的数据, 1 <= m <= n <= 10^18.
输入样例： 11 4 输出描述： 输出仅包括一行, 即所求排列中的第m个数字.输出样例 2
头条校招
a<=b<=c
b-a<=10
c-b<=10
所有出题人一共出了n道开放性题目。现在我们想把这n道题分布到若干场考试中（1场或多场，每道题都必须使用且只能用一次），然而由于上述条件的限制，可能有一些考试没法凑够3道题，因此出题人就需要多出一些适当难度的题目来让每场考试都达到要求，然而我们出题已经出得很累了，你能计算出我们最少还需要再出几道题吗？ 输入描述： 输入的第一行包含一个整数n，表示目前已经出好的题目数量。
第二行给出每道题目的难度系数d1,d2,...,dn。
数据范围
对于30%的数据，1 &le n,di &le 5
对于100%的数据，1 &le n &le 10^5,1 &le di &le 100。
在样例中，一种可行的方案是添加2个难度分别为20和50的题目，这样可以组合成两场考试：（20 20 23）和（35,40,50）。输入样例： 4 20 35 23 40 输出描述： 输出只包括一行，即所求的答案。输出样例 2
异或
第二行给出n个整数A1，A2，...，An。
数据范围
对于30%的数据，1 <= n, m <= 1000
对于100%的数据，1 <= n, m, Ai <= 10^5
输入样例： 3 10 6 5 10 输出描述： 输出仅包括一行，即所求的答案输出样例 2
找出函数的最宽尖峰
找出函数的最宽尖峰
【题目描述】按数组的形式给出函数f(x)的取值，即数组A的A[0]元素为f(0)的取值，数组的取值都为整数，函数在每个点都是严格单调递增或者严格递减（即A[i-1] != A[i] != A[i+1]），要求找出最宽的先上升后下降的区间（这个区间内函数的值必须先上升到一个点然后下降，区间的上升段和下降段长度必须都大于0）。
1. 如果找到符合条件的最大区间输出数组对应的左右下标（保证只有一个最大区间）
2. 找不到那么输出-1 -1
输入格式
n
n长度的整数数组
输出格式
区间的范围
输入样例
10
1 3 1 2 5 4 3 1 9 10
输出样例
2 7
数据规模
对于 100% 的数据，1 <=n <=10, 000, 000
Paragraph
Paragraph
【问题描述】给定一个段落，由 N 个句子组成。第 i 个句子的长度为 L[i]，包含的单词个数为 W[i]。
句子不包含任何除字母和空格( ) 外的符号。
每个句子内部，含有若干个单词，由空格( ) 分隔。句子不会包含连续的空格。
随后给定 M 个查询，每个查询包含一个句子，需要在段落中寻找相同单词数量最多的句子。重复的单词只计一次，且不区分大小写。
输入数据将保证结果是存在且唯一的。
输入格式
第一行是两个整数 N 和 M。
接下来的 N+M 行，每行包含一个句子。
前 N 行代表段落中的句子，后 M 行表示查询。
输出格式
输出 M 行，每行代表查询的结果。
输入样例
6 3
An algorithm is an effective method that can be expressed within a finite amount of space and time
Starting from an initial state and initial input the instructions describe a computation
That when executed proceeds through a finite number of successive states
Eventually producing output and terminating at a final ending state
The transition from one state to the next is not necessarily deterministic
Some algorithms known as randomized algorithms incorporate random input
Next to the transition
Wormhole, infinite time and space
The transition from one state to the next is not necessarily deterministic
输出样例
The transition from one state to the next is not necessarily deterministic
An algorithm is an effective method that can be expressed within a finite amount of space and time
The transition from one state to the next is not necessarily deterministic
数据规模
0 < L[i] < 512
0 < W[i] < 32
对于 30% 的数据，0 < N < 30，0 < M < 30。
对于 100% 的数据，0 < N < 500，0 < M < 800。
绘制括号序列
绘制括号序列
【题目描述】垂直绘制一个中括号的序列 并用中括号的大小表示层次关系绘制 [[[]]][] 这个括号序列
如图：
+-----+
|+---+|
|+-+|
| |
| |
|+-+|
|+---+|
+-----+
+-----+
| |
| |
+-----+
绘图遵守以下原则：
各个括号之间没有空格 只有在左右括号在最里层配对时 中间才会有一条空行
里层的括号必定小于外层的括号
同一层次的括号大小相同（比如上述的样例 最下面的括号和上面的大括号相同大小）
输入
一个以括号组成的字符串
输出
绘制的图形 保证括号匹配序列合法
样例输入：
[][][]
样例输出：
+-+
| |
| |
+-+
+-+
| |
| |
+-+
+-+
| |
| |
+-+
数据范围：
30%的数据 括号层数只有1
100%的数据 括号层数 <= 6
100%的数据 字符串长度 <= 100
数列
数列
【题目描述】给定两个长度为 n 的整数数列 A 和 B。再给定 q 组查询，每次查询给出两个整数 x 和 y，求满足 Ai >= x 且 Bi >= y 这样的 i 的数量。
输入格式
第一行给定两个整数 n 和 q。
第二行给定数列 A，包含 n 个整数。
第三行给定数列 B，包含 n 个整数。
接下来 q 行，每行两个整数 x 和 y，意义如上所述。
输出格式
对于每组查询，输出所求的下标数量。
输入样例
3 2
3 2 4
6 5 8
1 1
4 8
输出样例
3
1
数据规模
对于 30% 的数据，1 <= n, q <= 100。
对于 100% 的数据，1 <= n, q, Ai, Bi <= 10^5。
两数组找相同的元素
两数组找相同的元素
【题目描述】给两个整数(int)数组，输出相同的元素。
输入格式
m n
a1 a2 … am
b1 b2 … bn
输出格式
相同的的元素，用空白分开
输入样例
5 4
11 15 9 12 3
1 8 3 7
输出样例
3
数据规模
对于30%的数据, 0 < m < 30, 0 < n < 30
对于100%的数据，0 < m < 100000, 0 < n < 100000
想考察当m,n 超过一定规模之后不能直接用暴力求解
DAU 统计
DAU 统计
【题目描述】日活跃用户数 (DAU) 是衡量一个产品表现的重要指标。
需要编写程序，根据给定的某一天的 N 条访问记录，对当天的用户总数 M 进行统计。每个用户可能访问多次。为了方便，我们用数字 (uid) 唯一标识每个用户。
输入格式
每一行包含一个 uid，遇到 0 时认为输入结束。
输入共包含 N+1 行，可认为是无序的。
输出格式
一个数字：去重后 uid 的数量 M。
输入样例
12933
111111
59220
69433
59220
111111
0
输出样例
4
数据范围
0 < uid < 2^63
时间 < 1s, 内存 < 32MB
对于 30% 的数据，0 < N < 100,000, 0 < M < 100,000
对于 100% 的数据，0 < N < 1,000,000, 0 < M < 800,000
形式化算式
形式化算式
【题目描述】我们有如下形式化的数字：
* *** *** * * *** *** *** *** *** ***
* * * * * * * * * * * * * *
* *** *** *** *** *** * *** *** * *
* * * * * * * * * * * * *
* *** *** * *** *** * *** *** ***
分别表示 1 2 3 4 5 6 7 8 9 0
有如下形式化的符号：
* * * * ****
*** *** * *
* * * * **** **
**
分别表示 + - * ／ = 小数点
现在 将输入一个算式
你要将该算式计算之后按照上述形式化的方式输出
各个数字和符号之间空两格
无法整除则保留两位小数
样例输入1：
10 + 31
样例输出1：
* *** *** * * * *
* * * * * * **** * * *
* * * *** *** * *** *
* * * * * * **** * *
* *** *** * * *
样例输入2：
2 ／ 5
样例输出2：
*** *** *** * *
* * * **** * * * *
*** * *** * * ***
* * * **** * * ** *
*** *** *** ** *
数据范围：
20%的数据 输入的数字和运算结果都是个位数
100%的数据保证 输入数字和答案都小于10000
100%的数据保证 输入数字不会出现小数
80%的数据保证 运算结果不会出现小数
任务执行策略
任务执行策略
【题目描述】我们有一批任务在 mesos 当中。这批任务要么不依赖其它任务，要么一定恰好依赖于两个任务，并且整个依赖关系会构成一个三角模型：
Job(1, 1)
Job(2, 1) Job(2, 2)
Job(3, 1) Job(3, 2) Job(3, 3)
……
Job(n, 1) Job(n, 2) …… Job(n, n)
如上图，Job(1, 1) 依赖于 Job(2, 1) 和 Job(2, 2)；Job(2, 2) 依赖于 Job(3, 2) 和 Job(3, 3)；对于任意 1 <= i < n, 1 <= j <= n，Job(i, j) 依赖于 Job(i + 1, j) 和 Job(i + 1, j + 1)。最后一行的任务没有任务依赖。
这批任务有一个特点，每个任务都需要配合它所依赖的任务来执行。也就是说，一个任务某次运行是有效的，当且仅当至少满足下列一个条件：
1. 该任务不依赖其它任务；
2. 该任务依赖的两个任务都是有效的。
每个任务都预先设定了一个权重 weight(i, j)。现在由于资源上的限制，我们只能挑选其中的 k 个任务来运行。我们希望所有被运行的任务都是有效的，并使得所有运行过的任务的权重之和最大。
输入格式
第一行是两个整数 n 和 k。
接下来 n 行，其中第 i 行 (1 <= i <= n) 包含 i 个整数，给出各个任务的权重。这个三角形也同时描述了任务的依赖关系。
输出格式
输出仅包含一个整数，即所求的最大权重和。
输入样例
3 4
1
2 3
1 1 1
输出样例
6
数据规模
对于 30% 的数据，1 <= n, k <= 50；
对于 100% 的数据，1 <= n <= 100，1 <= m <= C(n + 1, 2)，1 <= weight(i, j) <= 1000。
