58同城后端笔试复盘

下图是一个B+树的结构,做 range操作(26,35),总共需要查找()次

A. 8

B. 9

C. 10

D. 11

为什么我感觉是6。还是不知道选什么。

查找26、35在第一个磁盘块,各查找了1次;在第2个磁盘块查找26,第三个磁盘块查找35,各1次;在第7个磁盘块查找26,在第9块磁盘块查找35;一共6次啊。之后用B+树的叶子节点链表遍历,不用查找了吧。

机器间传输数据,发送端发送2096字节的数据,接收端会出现丢失部分数据情兄(传输协议使用:UDP),引起这问题最大可能原因()

A. 网络环境问题

B. 接收端网卡问题

C. 数据长度大于接收端缓冲区

D. 网络传输分包

C.
虽然UDP的报文长度最大可以达到64 kb,但是当报文过大时,稳定性会大大减弱。这是因为当报文过大时会被分割,使得每个分割块的长度小于MTU。以太网的MTU通常是1500 bytes,其他一些诸如拨号连接的网络MTU值为1280 bytes。 网络传输分包是要分割的,但不能分得太大。
发送的包较大,超过接受者缓存导致丢包:包超过mtu size数倍,几个大的udp包可能会超过接收者的缓冲,导致丢包。这种情况可以设置socket接收缓冲。调整接收缓冲设置的大小。

Socket 读缓冲区、写缓冲区 默认大小122k好像。通过以下配置修改:
/proc/sys/net/core/rmem_max
/proc/sys/net/core/wmem_max

下列哪种方法不能用来减小过拟合?

A. 更少的训练数据

B. L1正则化

C. L2正则化

D. 减小模型的复杂度

A.
减少过拟合的方法; https://www.zhihu.com/question/59201590

  • 获取更多数据
  • 使用合适的模型
  • 结合多种模型
  • 贝叶斯方法
假设电文A,B,C,D,E的权值为5,6,9,10,15则报文 AECDB的哈夫曼编码为()

A. 101001110010

B. 100110001101

C. 110011011010

D. 100101011010

B. A,B同为3个字符表示,哈夫曼编码必然前2个字符相同。

下边IPv6地址中写法正确的是?

A. fe80:0:b4f9:6c6f:b658:a4aa

B. fe80:0:0:0:b4u9:6c6f:b658:d4aa

C. fe80::04f9:6c6f:b658:d4aa

D. fe80::b4f9:6c6f:b658::d4aa

C. B中有u

IPv6地址为128位长,但通常写作8组,每组为四个十六进制数的形式。
如果四个数字都是零,可以被省略。
如果因为省略而出现了两个以上的冒号的话,可以压缩为一个,但这种零压缩在地址中只能出现一次

如果这个地址实际上是IPv4的地址,后32位可以用10进制数表示;因此: ffff:192.168.89.9 等价于 ::ffff:c0a8:5909, 但不等价于 ::192.168.89.9 和 ::c0a8:5909。
ffff:1.2.3.4格式叫做IPv4映像地址,是不建议使用的。而::1.2.3.4格式叫做IPv4一致地址(这也是混合符号(IPv4-compatible address)表示)。

以下哪项是对单核cpu执行程序时间的正确描述:

A. 程序CPU执行时间=指令数 × 时钟周期时间

B. 程序CPU执行时间=CPU时钟周期数 × 单条指令平均执行周期

C. 程序CPU执行时间=指令数 × 单条指令平均执行周期 × 时钟周期时间

D. 程序CPU执行时间=CPU时钟周期数 × 指令数 × 单条指令平均执行周期×时钟周期时间

C.

程序CPU执行时间=CPU时钟周期数*时钟周期时间
=指令数*单条指令平均执行周期*时钟周期时间

以下关于进程调度算法的描述中,错误的是

A. 优先级调度算法会引起进程的饥饿问题

B. 短作业优先调度算法的平均等待时间最少

C. 当系统最长响应时间一定时,时间片轮转调度算法的时间片大小与系统允许的最大进程数成正比

D. 高响应比优先调度算法综合考虑了进程等待时间和执行时间

C.

响应比 =(等待时间+要求服务时间)/ 要求服务时间,
即RR=(w+s)/s=1+w/s,因此响应比一定是大于1的。

采用快排对3 7 6 9 10 12 1进行排序( 第一个为基准数 ),第1轮探测结果为

A. 1 3 6 9 10 12 7

B. 9 1 6 3 10 12 7

C. 3 1 6 9 10 12 7

D. 1 3 6 7 9 10 12

A.

连接平台通过号码池来管理虚拟号码,如果每个号池管理15个号码,将有7个号码池每个号码池多2个号码;如果每个号码池管理12个号码,则会有11码没有号码池管理;如果每个号码池管理18个号码,将有一个号码池差1个号码。这批虚拟号码数量在500-600之间,这批虛拟号码有多少个()

A. 559

B. 539

C. 540

D. 541

运维同学通知我们台服务器(inux)存放日志的磁盘分区快满了,因此我们决定删除一些日志。但该服务器部醫了多个服务,我们想优先删除磁盘占用量比较大的服务的日志。已知所有服务都将日志打印到 /opt/scf/log/{服务名}/{服务名}.log,请帮忙选出一个命令来查看各个服务日志占用的空间

A. df -h /opt/scf/log

B. df -h /opt/scf/log/*

C. du -sh /opt/scf/log

D. du -sh /opt/scf/log/*

C.

du 本身就能递归显示到文件,其实 du -h /opt/scf/log 就可以了;
-s, --summarize display only a total for each argument,对每项大小总结,目录算一项。失去了递归显示,反而要加上通配符
du -sh /opt/scf/log ,就只显示 /opt/scf/log 大小
所以, du -sh /opt/scf/log/* 把每个服务名目录总结大小

现有长度分别为1,2,3,4,5,6,7,8,9,10的木棍各根,现要求用这些木棍(可以多根组合,但组合A=B=C=D,ABCD、ACDB等重排列算一种正方形)拼成一个正方形,可以有几种拼法

A. 18种

B. 19种

C. 20种

D. 15种

现有t表存在索引:idx a b c(a,b,c)下面那些SQL会被索引?

A. SELECT * FROM tI WHERE a!=1:

B. SELECT * FROM t1 WHERE b=1 AND a=4;

C. SELECT * FROM t1 WHERE b=2 OR c=3;

D. SELECT * FROM t1 WHERE a=1 AND b=2 AND c=3;

D.

or连接索引失效。!=不能用于索引项,也会失效。
最左前缀匹配原则,指的是查询从索引的最左前列开始并且不跳过索引中的列

以下关于web攻击手段错误的是

A. SQL注入攻击通过将任意SQL代码插入数据库查询,使攻击者能够完全控制web应用程序后面的数据库服务器

B. 对进入数据库的特殊字符等进行转义处理可有效预防SQL注入攻击

C. XSS攻击的主要方法是发送大量请求使服务器痒痪

D. XSS攻击可分为存储型XSS和反射型XSS两大类

C.

XSS攻击通常指的是通过利用网页开发时留下的漏洞,通过巧妙的方法注入恶意指令代码到网页,使用户加载并执行攻击者恶意制造的网页程序。 这些恶意网页程序通常是JavaScript

  • 存储型XSS,持久化,代码是存储在服务器中的,如在个人信息或发表文章等地方,加入代码,如果没有过滤或过滤不严,那么这些代码将储存到服务器中,用户访问该页面的时候触发代码执行。这种XSS比较危险,容易造成蠕虫,盗窃cookie等
  • 反射型XSS,非持久化,需要欺骗用户自己去点击链接才能触发XSS代码(服务器中没有这样的页面和内容),一般容易出现在搜索页面。
游戏中升级一把武器,假定每使用一个石头,有50%的概率会成功让武器升级,50%的概率会失败。如果武器等级大于等于5的话,升级失败会使得武器降1级。如果武器的级数小于5的话,失败没有效果。问:期望用多少个石头可以让一把初始为1级的武器升到级?()

A. 20

B. 26

C. 36

D. 48

在采用LRU算法的系统中,程序P的某次调用依次问8、7、6、5、4、3、2、1、2、3页。假设分配给P的最大内存是4页。则在该次调用中的缓存命中率

A. 0.6

B. 0.5

C. 0.4

D. 0.2

D.

第1道

给定个字符串,字符串是有序的整数集合,逗号相连,移除相同的数字,使每个数字只出现一次,输出最终的数字个数

输入描述:

1,2,2

输出描述:

2

示例1

输入:

0,0,1,1,1,2,2,3,3,4

输出:

5
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.next();
        sc.close();
        String[] splits = line.split(",");
        HashSet<Integer> s = new HashSet<>();
        for (String split : splits) {
            s.add(Integer.parseInt(split));
        }
        System.out.println(s.size());
    }
}

第2道

幼儿园老师给她班上的孩子分饼干。所有的孩子都坐在-条线上,每个孩子都根据在课堂上的表现得到评分。老师必须给每个孩子至少1个饼干。如果两个孩子坐在起,那么评分较高的孩子必须得到更多的饼干(孩子必须左右都比较)。输出老师购买的饼干总数的最小值。例如,假设她的学生的评分为[3,6,3,5,6,2]。她给学生饼干的数量如下: [1,2,1,2,3,1] 。她必须购买至少10个饼干

输入描述:

假设学生评分为:[1,2,3],则输入应为:
3
1
2
3
第1行为数组元素大小,2至n+1行为数组元素(每行一个)

输出描述:

可分配最小值

示例1

输入:

6
3
6
3
5
6
2

输出:

10

示例2

输入:

10
1
2
4
2
6
1
7
8
9
2
1

输出:

19

孩子数量为10,所以饼干数为1+2+1+2+1+2+3+4+2+1=19
(最后一个孩子获得一个饼干,但是他比前一个孩子评分小,所以前一个孩子饼干数加一)

没有通过所有测试用例,事后修改,不知道对不对

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        List<Integer> list = new ArrayList<>();
        int min = Integer.MAX_VALUE, minIdx = 0;
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            if (a[i] < min) {
                min = a[i];
                minIdx = i;
            }
        }
        for (int i = 0; i < n; i++) {
            if (a[i] == a[minIdx])
                list.add(i);
        }
        sc.close();
        Arrays.fill(b, 0);
        b[minIdx] = 1;
        int sum = 0;
        for (int i = minIdx - 1; i >= 0; i--) {
            if (a[i] < a[i + 1]) {
                b[i] = b[i + 1] - 1;
                if (b[i] == 0) {
                    for (int j = i; j < minIdx; j++) {
                        b[j] = b[j] + 1;
                    }
                }
            } else if (a[i] > a[i + 1]) {
                b[i] = b[i + 1] + 1;
            } else {
                b[i] = b[i + 1];
            }
        }
        for (int i = minIdx + 1; i < n; i++) {
            if (a[i] < a[i - 1]) {
                b[i] = b[i - 1] - 1;
                if (b[i] == 0) {
                    for (int j = i; j > minIdx; j--) {
                        b[j] = b[j] + 1;
                    }
                }
            } else if (a[i] > a[i - 1]) {
                b[i] = b[i - 1] + 1;
            } else {
                b[i] = b[i - 1];
            }
        }
        // fix
        if (b[n - 1] != 1) {
            int delta = b[n - 1] - 1;
            for (int i = n - 1; i > 0; i--) {
                if (a[i] > a[i - 1]) break;
                if (a[i] < a[i - 1]) {
                    b[i] = b[i] - delta;
                }
            }
        }
        if (b[0] != 1) {
            int delta = b[0] - 1;
            for (int i = 0; i < n; i++) {
                if (a[i] > a[i + 1]) break;
                if (a[i] < a[i + 1]) {
                    b[i] = b[i] - delta;
                }
            }
        }
        for (int i = 0; i < n; i++) sum += b[i];
        System.out.println(sum);
    }
}

第3道

现有一个地图,由横线与竖线组成(参考围棋棋盘),且两点之间有行走距离起点为左上角,终点为右下角在地图上,每次行走只能沿线移动到临近的点,并累加路径计算一个人从地图的起点走到终点的最小路径为多少

输入描述:

mxn地图表示如下:
3
3
1 3 4
2 1 2
4 3 1
其中m=3,n=3表示3*3的矩阵
行走路径为:下>右>右>下

输出描述:

路径总长:1+2+1+2+1=7

示例1

输入:

1
2
1 2

输出:

3

示例2

输入:

2
3
9 8 6
2 3 7

输出:

21

把i写成了 j , 行复制误大事,事后发现懊悔不已,我竟然犯这种错。
算了过去了。

搜索解题,会有测试用例超时。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int ans = Integer.MAX_VALUE;
    static int m;
    static int n;
    static int[][] a;
    static int[][] d = {{1, 0}, {0, 1}};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        a = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        sc.close();
        dfs(0, 0, 0);
        System.out.println(ans);
    }

    private static void dfs(int x, int y, int sum) {
        if (x < 0 || y < 0 || x >= m || y >= n) return;
        if (x == m - 1 && y == n - 1) {
            sum += a[m - 1][n - 1];
            ans = Math.min(ans, sum);
            return;
        }
        for (int i = 0; i < d.length; i++) {
            int posx = x + d[i][0];
            int posy = y + d[i][1];
            dfs(posx, posy, sum + a[x][y]);
        }
    }
}

这道题是一道经典的动态规划题。