3月21号字节跳到大数据实习的笔试

一共有五道单选10分、五道不定项选15分和三道编程题75分

单选（顺序不记得了）：

1. 下列算法的时间复杂度（）选项不记得了又Q(logn)

Int i=0；

While（i<n）{

i = i*2；

}

2. 下列排序算法，最好和最坏是一样的时间复杂度（）

A.冒泡排序B插入排序C快速排序D堆排序

3. hive sql中说的排名是1、2、3、4的顺序，其同样分数也是这种排名（）注意这里的描述不准确。

A. row_number     B row       C rank   D rank_number

4. n个顶点的无向图，其顶点度的总和最多是（）选项只记得了（n（n-1）/2）

5. 一个二叉树的后序遍历是3 2 5 4 1，中序遍历是3 2 1 5 4，下面说法错误的是（）只记得3和5是兄弟

不定项选择（顺序不记得了）

1. 栈的入栈顺序是abcde，则下列出栈顺序正确的是（）不记得了

2. 怎么改善spark shuffle的数据倾斜

3. 一个进程调度的题，具体不记得了

4. 文件采用多级目录的好处

5. 还有一个大数据方面的题（不记得了）

算法题

1. 动物园有猴子，每天需要给猴子们发香蕉，猴子会排成一列取香蕉，猴子铺张浪费，会多拿食物，但最多不会超过自身食量二倍且不会超过当前还存在的香蕉的一半，最后一个猴子除外（既最后一个猴子可以拿完剩余的所有香蕉）。最多需要准备多少香蕉，能保证所有猴子都能吃饱。

2. 为了回馈老顾客李华，蛋糕店老板准备了N块蛋糕，排成一排，并向李华赠送其中连续的若干蛋糕，李华想好平衡饮食控制体重，决定最多接受M块蛋糕。用美味值a[i]来衡量第i块蛋糕的美味程度。李华收获蛋糕的美味值总和的最大值。

3. 有一个文本编辑器，初始状态内容为空，请你计算把编辑器中的内容变成N个相同字符串S最少需要多少时间。只能通过以下3种操作编辑文件：

把现有的文本倍增（如果当前的本文有k个s，倍增后变成2k个s），要用A个单位时间（假设A固定，与现有文本的张度无关）

在末尾添加一个s（如果当前文本有k个s，添加后变成k+1个s），要用B个单位时间

删除末尾的一个s（如果当前文本非空，有k个s，删除后变成k-1个s），同样用B个单位时间

输入描述：

第一行输入为w，A和B。N表示需要复制a的次数，A表示一次倍增需要的时间，B表示一次添加/删除需要的时间

输出描述：

输出一行，包含的一个整数，完成编辑最少需要的时间