可恶，为什么每次笔试都有好多选择题不会！

磁盘调度算法

• 1.FIFO/FCFS：先来先服务算法；
• 2.SSTF： 最短寻道时间算法；
• 3.SCAN：电梯调度算法；(这样命名很形象)
• 4.CSCAN： 循环扫描算法
• 5.FSCAN：分步电梯调度算法(分两个队列)
• 6.LOOK算法，也称为“寻道”（Look-Ahead）算法,是SCAN算法的一种变种，主要用于优化磁盘读写操作的顺序，从而提高磁盘的性能和效率。

MySQL: find_in_set

MySQL提供了一个名为FIND_IN_SET()的内置字符串函数，允许您在逗号分隔的字符串列表中查找指定字符串的位置。

下面说明了FIND_IN_SET()函数的语法。

FIND_IN_SET(needle,haystack);

FIND_IN_SET()函数接受两个参数：

• 第一个参数needle是要查找的字符串。
• 第二个参数haystack是要搜索的逗号分隔的字符串列表。

FIND_IN_SET()函数根据参数的值返回一个整数或一个NULL值：

• 如果needle或haystack为NULL，则函数返回NULL值。
• 如果needle不在haystack中，或者haystack是空字符串，则返回零。
• 如果needle在haystack中，则返回一个正整数。

ARP 协议

• ARP（Address Resolution Protocol）即地址解析协议， 用于实现从 IP 地址到 MAC 地址的映射，即询问目标IP对应的MAC地址。
• 每个主机都会有自己的ARP缓存区中建立一个ARP列表，以表示IP地址和MAC地址之间的对应关系
• 主机 A 想要获取主机 B 的 MAC 地址：广播 -> 封装 ARP 响应 -> 返回给主机
• 通过主机 A 会通过广播 的方式向以太网上的所有主机发送一个 ARP 请求包，这个 ARP 请求包中包含了主机 A 想要知道的主机 B 的 IP 地址的 MAC 地址。
• 主机 A 发送的 ARP 请求包会被同一链路上的所有主机/路由器接收并进行解析。每个主机/路由器都会检查 ARP 请求包中的信息，如果 ARP 请求包中的目标 IP 地址 和自己的相同，就会将自己主机的 MAC 地址写入响应包返回主机 A
• 由此，可以通过 ARP 从 IP 地址获取 MAC 地址，实现同一链路内的通信。

ARP 攻击分类

ARP 主要攻击方式分为下面这几种

• ARP 泛洪攻击：通过向网关发送大量 ARP 报文，导致网关无法正常响应。首先发送大量的 ARP 请求报文，然后又发送大量虚假的 ARP 响应报文，从而造成网关部分的 CPU 利用率上升难以响应正常服务请求，而且网关还会被错误的 ARP 缓存表充满导致无法更新维护正常 ARP 缓存表，消耗网络带宽资源。
• ARP 欺骗主机攻击：ARP 欺骗主机的攻击也是 ARP 众多攻击类型中很常见的一种。攻击者通过 ARP 欺骗使得局域网内被攻击主机发送给网关的流量信息实际上都发送给攻击者。主机刷新自己的 ARP 使得在自己的ARP 缓存表中对应的 MAC 为攻击者的 MAC，这样一来其他用户要通过网关发送出去的数据流就会发往主机这里，这样就会造成用户的数据外泄。
• 欺骗网关的攻击: 欺骗网关就是把别的主机发送给网关的数据通过欺骗网关的形式使得这些数据通过网关发送给攻击者。这种攻击目标选择的不是个人主机而是局域网的网关，这样就会攻击者源源不断的获取局域网内其他用户韵数据．造成数据的泄露，同时用户电脑中病毒的概率也会提升。
• 中间人攻击: 中间人攻击是同时欺骗局域网内的主机和网关，局域网中用户的数据和网关的数据会发给同一个攻击者，这样，用户与网关的数据就会泄露。
• IP地址冲突攻击: 通过对局域网中的物理主机进行扫描，扫描出局域网中的物理主机的 MAC 地址，然后根据物理主机的 MAC 进行攻击，导致局域网内的主机产生 IP 地址冲突，影响用户的网络正常使用。

进程的阻塞和就绪

• 就绪状态：进程已准备好运行，等待操作系统调度分配CPU时间片，以便开始执行。
• 阻塞状态：进程因为某些条件无法继续执行，等待特定事件发生或条件满足，从而转换回就绪状态。

计算机攻击

• 计算机蠕虫（Computer Worm）：计算机蠕虫是一种恶意软件，通常是一个自我复制的程序，可以在计算机网络中传播，并且不需要附加于其他程序。蠕虫可以利用计算机网络的漏洞，自动传播到其他主机，从而迅速扩散。它们的主要目标是在不同计算机之间传播自身，可能会导致网络拥塞、资源耗尽等问题。蠕虫通常不会修改或损坏文件，但它们可能会对系统和网络造成严重的影响。
• 计算机病毒（Computer Virus）：计算机病毒是一种恶意软件，它通过将自身附加到合法程序或文件中来传播。当被感染的程序或文件运行时，病毒也会被激活，并开始执行恶意操作，如损坏文件、窃取数据或传播给其他文件。与蠕虫不同，病毒需要一个宿主程序或文件来传播。病毒通常需要用户的干预才能传播，例如，通过共享受感染文件或使用受感染的存储设备。
• 流氓软件（Malware）：流氓软件是一种通用术语，用于描述恶意软件的各种形式，包括病毒、蠕虫、间谍软件、广告软件等。流氓软件的目的可能是窃取敏感信息、损坏系统、干扰正常操作、显示广告或滥用计算机资源等。它们可能通过下载、感染文件、社交工程等方式传播，对个人、组织和计算机系统造成威胁。
• 后门入侵（Backdoor Intrusion）：后门是一种被插入计算机系统或软件中的安全漏洞或代码，允许攻击者绕过正常的身份验证和安全措施，远程访问受感染的系统。后门可能是由开发人员故意插入的（例如，为了进行维护或远程访问），也可能是恶意人员通过漏洞插入的。后门入侵可能导致攻击者访问系统、窃取数据、操纵系统功能等，而用户通常对这种未经授权的访问毫不知情。

平衡二叉树

平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree），又被称为AVL 树，可以保证查询效率较高。 它是解决二叉排序可能出现的查询问题。

它的特点：是一颗空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一颗平衡二叉树。

P2P网络服务器上传速度200bps，对等方150bps，下载速度均为100bps，问 1000bit 的文件最小分发时间是？

BufferedReader 和 BufferedInputStream

BufferedReader：

BufferedReader 是用于读取字符流的缓冲输入流。它继承自 Reader 类，主要用于文本数据的读取。BufferedReader 可以提高读取文本数据的效率，因为它会在内存中创建一个缓冲区，逐块读取字符，从而减少了频繁的文件读取操作。它还提供了一些方便的方法来读取文本行、字符等。

BufferedReader br = new BufferedReader(new FileReader("file.txt"));
String line;
while ((line = br.readLine()) != null) {
    System.out.println(line);
}
br.close();

BufferedInputStream：

BufferedInputStream 是用于读取字节流的缓冲输入流。它继承自 InputStream 类，主要用于二进制数据的读取。类似于 BufferedReader，BufferedInputStream 也会在内存中创建一个缓冲区，以块的形式读取字节数据，从而提高了读取效率。

BufferedInputStream bis = new BufferedInputStream(new FileInputStream("file.bin"));
byte[] buffer = new byte[1024];
int bytesRead;
while ((bytesRead = bis.read(buffer)) != -1) {
    // 处理读取的字节数据
}
bis.close();

综上所述，BufferedReader 适用于读取字符流，用于文本数据的高效读取，而 BufferedInputStream 适用于读取字节流，用于二进制数据的高效读取。在处理文件输入时，使用缓冲流可以减少频繁的磁盘访问，从而提高程序的性能。

乐观锁与悲观锁

• 乐观锁的获取与释放都在用户态完成
• 对象锁的四种状态【https://blog.csdn.net/zmh458/article/details/93053867】

• 乐观锁可以基于 CAS 实现
• 悲观锁一定发生用户态到内核态的转变
• 当一个线程使用悲观锁尝试获取锁时，如果锁当前由其他线程持有，那么该线程会被阻塞。这时，操作系统的调度器可能会触发用户态到内核态的切换，将阻塞的线程置于等待状态。
• 也就是说，有冲突的时候会发生用户态到内核态的转变；没冲突的时候不会发生。

这题也不知道选啥，感觉都对了。第四个好像太绝对了。

List 的构建

    public static void main(String[] args) {
        List<String> list1 = new ArrayList<>(Arrays.asList("a", "b", "c", "d", "e"));
        List<String> list2 = new ArrayList<>(list1);
        List<String> list3 = list1.subList(1, 3);
        list2.set(1, "update2");
        list3.set(1, "update3");
        for (String s: list1) System.out.print(s + " ");  // a b update3 d e 
        for (String s: list2) System.out.print(s + " ");  // a update2 c d e
        for (String s: list3) System.out.print(s + " ");  // b update3
    }

• new ArrayList<>(list1); 构建了一个新的 list，与原来的 list 无关
• list1.subList(1, 3); 记录了 list1 及其指针，所以修改 list3 就是修改 list1

具体解释可见：https://www.cnblogs.com/dolphin0520/p/3933551.html

如果对 list1 进行排序，打印 list3 的时候会报错 java.util.ConcurrentModificationException。

ThreadLocal

• ThreadLocal 底层基于同步锁？ThreadLocal并不是基于同步锁实现的。
• 通过ThreadLocalMap实现数据的读写，这个ThreadLocalMap的key可以简单的看成是ThreadLocal，实际是并不是ThreadLocal的本身，而是它的一个弱引用。
• 线程中的 ThreadLocal 可以复用吗？可以，但是必须特别注意在代码运行完后，显式地去清空设置的数据。

关于序列化

下列说法错误的是？

• 对象的类名、实例变量会被实例化，方法、类变量不会被实例化。
• 某个变量不想被序列化，可以使用transient修饰
• 反序列化时可以不需要序列化对象的class对象
• 当通过文件、网络来读取序列化后的对象时，必须按照实际写入的顺序读取。

不知道选啥，好像都对。第三个错的倾向大一点。

笔试

前两题比较简单，第三题考察了动态规划和乘法取模的知识。

第一题：模拟

第二题：模拟

    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int t = in.nextInt();
            in.nextLine();
            for (int i = 0; i < t; i++) {
                String str1 = in.nextLine();
                String str2 = in.nextLine();

                int[] types = new int[3];
                extracted(types, str1, 1);
                extracted(types, str2, 2);

                int sim = (str1.length() == str2.length()) ? 1 : 0;
                
                boolean flag = true;
                for (int ty: types) {
                    if (ty == 2 || ty == 1) {
                        // 其中一种字符集只有一个字符串拥有
                        flag = false;
                        break;
                    }
                }
                sim += flag ? 1 : 0;
                System.out.println(sim);
            }
        }
    }

    private static void extracted(int[] types, String str, int mul) {
        // 判断字符串中使用的字符集合种类

        for (char c: str.toCharArray()) {
            if (Character.isDigit(c)) {
                types[0] = types[0] | mul;
            }
            else if (Character.isAlphabetic(c)) {
                types[1] = types[1] | mul;
            }
            else {
                types[2] = types[2] | mul;
            }
        }
    }

第三题：动态规划

核心思路是从个位开始，计算当前位数的余数的方案数目是多少。dp[i] 表示余数为 i 的方法数目，最终返回结果 dp[0]。

要点有如下几点：

• 当字符为 ？ 时，说明可以选择从 0-9 十个数字；当字符为具体的数字时，就只能选择当前数字。
• 当前数位所在的数字 num 对 p 的余数的计算方式：

余数
= (num * 10 ^ mul) % p
= ((num % p) * (10 ^ mul % p)) % p

10 ^ mul % p = mul 个 (10 % p) 相乘，mul 表示 10 的多少次方。

我的代码比较丑陋，主要流程是1. 先把个位数初始化，然后从十位数往高位计算。

final static int MOD = (int)1e9 + 7;

    public static void main3(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String pattern = in.next();
            int p = in.nextInt();

            int n = pattern.length();
            // dp[j] 表示余数为 j 时，字符串的方案数目
            long[] dp = new long[p];  // 余数为 [0, p-1]

            // 处理个位数
            char number0 = pattern.charAt(n - 1);
            if (number0 == '?') {
                for (int i = 0; i < 10; i++) {
                    dp[i % p] += 1;
                }
            } else {
                dp[(number0 - '0') % p]++;
            }

            int remainModBy10 = 10 % p;
            for (int i = n - 2; i >= 0; i--) {
                char c = pattern.charAt(i);
                long[] newDP = new long[p];
                if (c == '?') {
                    for (int number = 0; number <= 9; number++) {
                        process(p, dp, newDP, remainModBy10, number);
                    }
                } else {
                    int number = c - '0';  // 一个具体的数字
                    process(p, dp, newDP, remainModBy10, number);
                }
                dp = newDP;
                remainModBy10 = (remainModBy10 * (10 % p)) % p;  // 这里很重要，多了一个十位
            }

            System.out.println(dp[0]);
        }
    }

    private static void process(int p, long[] dp, long[] newDP, int remainModBy10, int number) {
        // 具体加上来的数字应该是 num * 10 的 mul 次方
        // 余数 = (num * 10 ^ mul) % p
        // = ((num % p) * (10 ^ mul % p)) % p
        // = ((num % p) * remainModBy10) % p
        int remain = ((number % p) * remainModBy10) % p;
        
        // update dp
        for (int j = 0; j < p; j++) {
            newDP[(j + remain) % p] = (newDP[(j + remain) % p] + dp[j]) % MOD;
        }
    }