Bilibili笔试(内推)- 20200813 - Java后端开发

30道选择题,三道编程题。

若干选择题

一、以下说法正确的是( )。

A. 由先序序列、中序序列可以还原出树的原貌

B. 200,190,150,170,180,140,155,160,165,120是一个最大堆

C. 排序之前必须把所有待排数据加载到内存

D. 给定一组输入,可以输出一颗唯一的哈夫曼树

二、请选择正确的描述。( )

A. 静态变量和全局变量是在程序一开始时分配内存的,这部分内存无法回收,直至程序结束

B. 通常常来说,在堆上分配内存比在栈上分配内存效率更高

C. 当我预先知道待分配内存大小时,我就可以直接在栈上分配内存,只要不超过当前操作系统的可用内存大小,就永远会成功

D. 内存泄漏就是指当A程序申请一块内存时,有可能操作系统把B程序的一块内存先交给A程序使用,等A程序结束后再返回给B程序,在内存借用的这段时间内,B程序就产生了内存泄漏

【解析】栈上分配内存效率更高;栈上申请内存并不总是成功;内存泄露是使用完成之后未回收。

三、在公司局域网上ping www.bilibili.com 一定不涉及的网络协议是( )。

A. UDP

B. DNS

C. ICMP

D. RAAP

【解析】。

四、有Area和City两个表,两表的数据如下所示:

Area: City
ID Name ID Name AreaID
1 North 1 北京 1
2 South 2 上海 2
3 East 3 广州 3
4 West 4 深圳 4
null null 5 null null

关于下面的sql语句,描述正确的是( )。

select * form City left join Area on City_AreaID = Area.ID where AreaID>0 group by AreaID having count(Region)>0 order by count(Region) desc limit 1;

A.该SQL执行会形成City和Area两表的笛卡尔积

B.该语句执行顺序上,会先执行where再执行having再执行order by最后执行limit

C.该语句执行顺序上,会先执行from,再执行join,再执行where

D.select form City left join Area on City_AreaID = Area.ID 和select form City inner join Area on City_AreaID = Area.ID这两条SQL语句执行的结果是不同的

五、客户端C和服务器S之间建立了一个TCP连接,TCP最大段长度为2KB,客户端C当前的拥塞窗口是16KB,向服务器S连续发送2个最大段之后,成功接收到服务器S发送的第一段确认段,确认段中通告的接收窗口大小是8KB,那么此时客户端C还可以向服务器S发送最大字节数是( )。

A. 16KB

B. 14KB

C. 8KB

D. 6KB

【解析】 min(16, 8) - 2 = 8-2=6。

六、下列关于linux中kernel space和user space描述错误的是()

A.user space不能直接对文件进行写操作

B.程序代码能手动指定在哪个space中运行

C.user space不能直接创建进程

D.user space和kernel space的运行空间是相互隔离的

七、采用递归方式对顺序表进行快速排序,下列关于递归次数的叙述中,正确的是()

  • 递归次数与初始数据的排列次序无关
  • 每次划分后,先处理较长的分区可以减少递归次数
  • 每次划分后,先处理较短的分区可以减少递归次数
  • 递归次数与每次划分后得到的分区处理顺序无关

【解析】递归次数与各元素的初始排列有关,认为是固定的。如果每一次划分后分区比较平衡,则递归次数少;如果划分后分区不平衡,则递归次数多。递归次数与处理顺序无关。

每次划分后,先处理较短的分区可以减少递归深度

1. 24点游戏

给出4个1-10的数字,通过加减乘除,得到数字为24就算胜利。

1
2
3
4
5
Input:
7,2,1,10

Output:
true

暴力法求解,使用三层循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution{

public boolean Game24Points (int[] arr) {
// write code here
List<Double> list = new ArrayList<>();
for(int num : arr){
list.add((double) num);
}
return dfs(list);
}

private static boolean dfs(List<Double> list){
if(list.size() == 1){
if(Math.abs(list.get(0) - 24.0) < 0.001){
return true;
}
return false;
}
for(int i=0; i < list.size(); i++){
for(int j=i+1; j < list.size(); j++){
for(double c : calc(list.get(i), list.get(j))){
List<Double> nextStep = new ArrayList<>();

nextStep.add(c);
for(int k = 0; k < list.size(); k++){
if(k==j || k==i) continue;
nextStep.add(list.get(k));
}
if(dfs(nextStep)){
return true;
}
}
}
}
return false;
}

private static List<Double> calc(double a, double b){
List<Double> result = Arrays.asList(a+b, a-b, b-a, a*b, a/b, b/a);
return result;
}
}

2. 括号匹配

给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串,判断字符串是否有效。

1
2
3
4
5
6
7
8
9
10
Input:
([{}])]

Output:
false

有效字符串需满足:
1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

Leetcode / 力扣 简单问题,使用一个栈解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if (stack.isEmpty()) {
return false;
}
char cStack = stack.pop();
boolean b1 = c == ')' && cStack != '(';
boolean b2 = c == ']' && cStack != '[';
boolean b3 = c == '}' && cStack != '{';
if (b1 || b2 || b3) {
return false;
}
}
}
return stack.isEmpty();
}

3. 一个找零问题

某国的货币系统包含面值1元、4元、16元、64元共计4种硬币,以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为N的商品,请问最少他会收到多少硬币?

1
2
3
4
Input:
200
Output:
17

动态规划求解

  1. 利用背包问题进行参考,购买的物品价值为N,给定的面值选择的硬币种类选择,其额度是V = {1,4,16,64},剩余金额为M = 1024 - N;问应该如何选择硬币,使得到的硬币数量为最少??
  2. 将其转化为:令 dp[j] 表示在前 j 个硬币中能够等于在 i 的额度中的M的价值,则可以得到如下的动态规划函数:
    得到状态转移方程:
    (1) dp[0] = 0
    (2) dp[j] = min( dp[j], dp[ j - coins[i] ] + 1 ) j <= M
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int GetCoinCount (int N) {
// 需要找零的面值
int M = 1024 - N;

int[] dp = new int[1024];
for(int i = 1; i <= M; i++){
dp[i] = 99999;
}
dp[0] = 0;
int[] coins = new int[]{1,4,16,64};
for(int v : coins){
for(int j = v; j <= M; j++){
dp[j] = Math.min(dp[j], dp[j-v] + 1);
}
}
int ret = dp[M];

return ret;
}

直接求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int cnum1,cnum2,cnum3,cnum4;
cnum1=(1024-n)/64; //64元硬币的数量
cnum2=((1024-n)%64)/16; //16元硬币的数量
cnum3=(((1024-n)%64)%16)/4; //4元硬币的数量
cnum4=(1024-n)-(cnum1*64+cnum2*16+cnum3*4); //1元硬币的数量
int result = cnum1+cnum2+cnum3+cnum4;

or

N = 1024-N;
int count = 0;
int coins[4] = {64,16,4,1};
for(int i=0;i<4;i++){
count += N/coins[i];
N = N % coins[i];
}
int result = count;