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;