记录秋招做的笔试中遇到的选择题和编程题补漏学习

2025-08-24-小红书

选择题

1.局部变量中的基本数据类型变量存储在栈内存中

分析：考察的是JVM-运行时数据区-虚拟机栈保存的东西

一般来说如果不考虑JIT，这个是正确的，虚拟机栈中保存了局部变量表，动态链接，方法出口等；

2.快排模拟

对于{8,12,15,9,20,22,18}，以8为中枢，经历一轮快排后是什么样子？

分析：快排的算法流程还是不太清晰

3.MySQL的查询缓存

查询缓存在表结构或数据发生变化时会自动失效需要重新缓存，对吗？✅！

查询缓存是以 key-value 形式保存在内存中的，key 为 SQL 查询语句，value 为 SQL 语句查询的结果。

注意，同一条SQL语句，不同的参数会通过哈希映射为不同的key！！所以这个功能很鸡肋。

4.Linxu命令

1
2
3
4
5
6
7
8
9

#!/bin/bash
str="Hello,World!"
echo ${str:3:5}

运行的结果是什么？
A.无法运行
B.lo,
C.lo
D.lo,W

编程题

1、

题目：行为权重

小红是小红书的用户行为分析师。平台将每次用户行为映射为一个正整数权重序列[a1,a2,…,an] ，以便后续关联推荐时关键“红色”行为。

为了保证标记的行为具有足够的共性，必须选出的所有“红色”行为权重的最大公约数大于 1；同时，为了避免相邻生冗余，所选下标不得相邻。

现给定用户的一次行为序列，求最多可以染成红色的行为数量。

【名词解释】

最大公约数：指一组整数共有约数中最大的一个。例如，12、18 和 30 的公约数有 1, 2, 3, 6，其中最大的约数是 6，因此 gcd(12,18,30) = 6。

输入描述

在一行上输入一个整数n （1<=n<=10^5），表示行为序列长度。

在第二行输入 n 个整数 a1,a2,…an（1<=ai<=100），表示每次行为的权重值。

输出描述

在一行上输出一个整数，表示最多可染红的行为数量。

样例输入 1

5

1 2 3 2 6

样例输出 1

2

样例解释 1

在这个样例中，可将下标 2 与 4 对应的权重染红，它们的最大公约数为 2，且不相邻，故答案为 2。

我做的

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
43
44
45
46

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    sc.nextLine();
    String s = sc.nextLine();
    String[] s1 = s.split(" ");
    int[] nums = new int[n];
    for (int i = 0; i < n; i++) {
        nums[i] = Integer.parseInt(s1[i]);
    }
    System.out.println(slove(nums));
}

    private static int slove(int[] nums) {
        int n = nums.length;
        if(n <= 2)
            return 0;
        boolean[] isRed = new boolean[n + 2];
        int ans = 0;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 2; j < n; j++) {
                //如果此时两个数的最大公约数大于1，并且检查二者距离大于1（肯定成立），并且这两个数的左右都没有染红，就可以染红这两个，结果+2并设置isRed
                if(!isRed[i] && !isRed[i] && !isRed[j] && !isRed[j]){
                    int a = maxNum(nums[i], nums[j]);
                    if(a > 1){
                        ans += 2;
                        isRed[i + 1] = true;
                        isRed[j + 1] = true;
                    }
                }
            }
        }
        return ans;
    }

    private static int maxNum(int a, int b) {
        if(a == b)
            return a;
        //默认让b更大
        if(a > b)
            return maxNum(b, a);
        while (b % a != 0){
            a = b % a;
        }
        return a;
    }

思路分析：“打家劫舍变种”

直接找出满足所有条件的最佳组合很复杂。我们可以反过来想：既然所有选中的数必须有一个大于1的最大公约数（GCD），那么它们必然都是某个整数 d (d>1) 的倍数。

由于题目给的数字最大不超过100，这个公约数 d 也肯定在2到100之间。

因此，我们可以把复杂问题分解成近百个简单问题：

第一步：锁定公约数 d

我们假设最终选出的所有“红色”行为，它们的公约数就是 d。我们依次让 d 等于 2、3、4、…、100，分别计算每种情况下的最优解。

第二步：解决简化后的问题 当公约数 d 固定后，问题就变成了：

在原数组中，最多能选出多少个“不相邻”的、且是 d 的倍数的数？

第三步：动态规划（“打家劫舍”模型）

这个简化后的问题是一个非常经典的动态规划模型，可以类比为“打家劫舍”（不能偷相邻的屋子）。 我们从头到尾遍历数组，对每个位置 i 的数 a[i]，我们做决策：

• **不选 a[i]**：最大数量等于到位置 i-1 的最大数量。

• **选 a[i]**：因为不能和相邻的 a[i-1] 一起选，所以最大数量是 1 (代表 a[i] 自己) + 到位置 i-2 的最大数量。

• 我们在这两个选择中取一个更大的结果。

• 如果 a[i] 不是 d 的倍数：我们肯定不能选它，所以到位置 i 为止的最大数量，就等于到位置 i-1 的最大数量。

• 如果 a[i] 是 d 的倍数：我们有两个选择：

第四步：取全局最优解

我们对每一个 d（从2到100）都执行一次第三步的动态规划，会得到近百个结果。在所有这些结果中，取那个最大的数，就是题目的最终答案。

代码实现：

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
43
44
45

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        
        int maxResult = 0;
        
        // 枚举所有可能的公约数 d (从2到100)
        for (int d = 2; d <= 100; d++) {
            // 创建dp数组，dp[i]表示考虑前i个元素时的最大可选数量
            int[] dp = new int[n + 1];
            dp[0] = 0; // 前0个元素，可选数量为0
            
            for (int i = 1; i <= n; i++) {
                if (a[i - 1] % d != 0) {
                    // 当前元素不是d的倍数，不能选择
                    dp[i] = dp[i - 1];
                } else {
                    // 当前元素是d的倍数，可以选择
                    if (i == 1) {
                        // 第一个元素
                        dp[i] = 1;
                    } else {
                        // 选择当前元素：1 + 前i-2个元素的最大数量
                        // 不选择当前元素：前i-1个元素的最大数量
                        dp[i] = Math.max(dp[i - 1], dp[i - 2] + 1);
                    }
                }
            }
            
            // 更新全局最大值
            maxResult = Math.max(maxResult, dp[n]);
        }
        
        System.out.println(maxResult);
    }
}

总结：

这题其实看到题目中“不能相邻”，就联想到了打家劫舍，但这题没有做出来的原因有两个：

1. 题目没读懂，或者说想的太复杂了，我想着依次遍历每个元素，然后再往后找能符合条件的数字，其实就是找出最多的这样一组数字，其最大公约数>1并且两两都不相邻。这种把要求解的结果转化成简单易理解的形式很重要！
2. 对于降低复杂度，要抓住每个数字都1<= ai <=100，这个关键条件，也就是题目中的条件要仔细阅读，可能就是突破口

2、

题目：潜在同好

题目描述

在小红书平台的社交推荐项目中，产品团队希望基于用户的日常行为习惯分数，挖掘潜在的“同好”关系。系统简化如下，数据库中有 n 个用户的日常行为习惯分数，第 i 个用户的分数使用 ai表示。记第 i 个用户和第 j 个用户构成“同好”关系，当且仅当 ai 能被 aj 整除，或者 aj能被 ai整除。接下来将进行 m 次查询，每次给定一个额外的用户行为分数 x，请统计在数据库中，有多少不同的人能与这个人构成“同好”关系。

输入描述

第一行输入两个整数n,m （1<=n,m<=510^5），表示数据库中用户数量、查询次数。
第二行输入 n 个整数a1,a2,…,an （1<=ai<=510^5），表示数据库中的用户日常行为习惯分数。
接下来 m 行，每行输入一个整数 x（1<=x<=5*10^5），表示一个额外的用户行为习惯分数。

输出描述

对于每次查询，新起一行，输出一个整数，表示数据库中能与 x 构成“同好”关系的用户数量。

样例输入

1
2
3
4
5

5 3
1 2 2 5 6
4
2
1

样例输出

1
2
3

3
4
5

我做的：究极暴力O(n^2)

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

    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    sc.nextLine();
    String s = sc.nextLine();
    String[] s1 = s.split(" ");
    int[] nums = new int[n];
    for (int i = 0; i < n; i++) {
        nums[i] = Integer.parseInt(s1[i]);
    }
    for (int i = 0; i < m; i++) {
        String s2 = sc.nextLine();
        int cur = Integer.parseInt(s2);
        System.out.println(solution(cur, nums));
    }
}

    private static int solution(int cur, int[] nums) {
        int ans = 0;
        for (int num : nums) {
            if(num % cur == 0 || cur % num == 0)
                ans++;
        }
        return ans;
    }

思路分析：

2025-08-31-作业帮

选择题

1.count会统计’’和null吗？

• 对于count(*)：
  • 功能：统计表中的行数。
  • 是否统计 NULL？ ✅ 会
  • 是否统计 ‘’？ ✅ 会
• 对于count（列名）：
  • 功能：统计指定列中非 NULL 值的数量。
  • 是否统计 NULL？ ❌ 不会
  • 是否统计 ‘’？ ✅ 会
• 对于count（1）/count（任意常数）：
  • 功能：统计表中的行数。
  • 是否统计 NULL？ ✅ 会
  • 是否统计 ‘’？ ✅ 会

2.TCP三次连接发送的报文都是什么？

是SYN SYN+ACK ACK

而不是SYN SYN+ACK SYN+ACK

3.B-树和B+树都支持顺序访问还是随机访问？

B-树和B+树两者都支持，就是效率不同

4.长连接和短连接哪个占用服务器内存资源更少

长连接

5.影响散列表查找效率的都有什么？记录数n有影响吗？

• 哈希函数
• 负载因子=已存储记录数n/桶总数
• 冲突策略

记录数n没有影响，但会间接通过负载因子对查找效率有影响

6.SQL的concat函数会拼接null吗？

如果拼接的有null，结果直接为null，例如CONCAT(' xxx', NULL, ' yyy');结果就是NULL

编程题

第三题就是hot100原题，20分秒了

第二题做出来了但感觉思路很复杂

第一题不会

1、

题目：

1

长度为n的绳子，切成m段，1 < m,n ,且m <= n，问这m段长度乘积的最大值是多少

2、

题目：

1

一颗二叉树，树上每个节点权值不同，找出最小权值的叶子节点到最大权值叶子节点的路径

我做的：

1. 找到所有叶子节点并记录值，然后找出最小和最大权值
2. 分别找到这两个权值对应的节点
3. 找到这两个节点的最近公共祖先，然后计算路径长度

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

static List<Integer> values = new ArrayList<>();
    public static int getDis (TreeNode root) {
        // write code here
        //先找到最小和最大的叶子节点
        //1.先找到所以叶子节点的值，然后再遍历，碰到最大值或最小值就可以返回这两个节点了
        dfsFind(root);
        int minV = Integer.MAX_VALUE;
        int maxV = Integer.MIN_VALUE;
        for (Integer value : values) {
            minV = Math.min(minV, value);
            maxV = Math.max(maxV, value);
        }
        if(minV == maxV)
            return 0;   //说明最大值叶子节点和最小值叶子节点是同一个节点
        TreeNode minNode = dfsFindNode(minV, root);
        TreeNode maxNode = dfsFindNode(maxV, root);
        //再找到这两个节点的最近祖先节点，
        TreeNode node = findMinNode(minNode, maxNode, root);
        //从最近祖先节点，到这两个节点的距离之和，就是要返回的值
        int a = searchA(node, minV, 0);
        int b = searchA(node, maxV, 0);
        return a + b;
    }

    private static int searchA(TreeNode node, int value, int i) {
        if(node == null)
            return 0;
        if(node.val == value)
            return i;
        int l = searchA(node.left, value, i + 1);
        int r = searchA(node.right, value, i + 1);
        return l == 0 ? r : l;
    }

    private static TreeNode findMinNode(TreeNode a, TreeNode b, TreeNode root) {
        if(root == null || root == a || root == b)
            return root;
        TreeNode l = findMinNode(a, b, root.left);
        TreeNode r = findMinNode(a, b, root.right);
        if(l != null && r != null)
            return root;
        return l == null ? r : l;
    }

    private static TreeNode dfsFindNode(int value, TreeNode root) {
        if(root == null)
            return null;
        if(root.val == value)
            return root;
        TreeNode l = dfsFindNode(value, root.left);
        TreeNode r = dfsFindNode(value, root.right);
        return l == null ? r : l;
    }

    private static void dfsFind(TreeNode root) {
        if(root == null)
            return;
        if(root.left == root.right)
            values.add(root.val);
        dfsFind(root.left);
        dfsFind(root.right);
    }

思路分析：

2025-09-06-深信服

选择题

1.时间复杂度好坏

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) <O(n!)

2.散列表平均查找长度（成功/失败）的计算

ASL：平均查找长度

具体怎么算，要看是线性探测法还是拉链法

ASL成功：分母都是元素个数
ASL失败：分母都是数组长度

对于线性探测法：

成功的分子是：每个关键字查找时，需要比较的次数取决于它被插入时经过的探测次数。

失败的分子是：对于每个散列地址，从该地址开始直到遇到空位置所需的探测次数（包括空位置本身）的平均值。

比如n = 7，插入三个元素22,43,15，散列函数是key%7，这三个元素得到的结果都是1

则ASL成功 = （1 + 2 + 3） / 3 = 2

ASL失败 = （1 + 4 + 3 + 2 + 1 + 1 + 1） / 7 = 13 / 7 从0本身就是空，1次即可，1需要找四次（包括本身），以此类推

对于拉链法

成功的分子是每层链表节点个数 * 层数

失败的分子是所有链表长度之和

举例

• 散列表长度：m=7（即7个桶，索引0到6）
• 关键字集合：{12, 23, 45, 57, 20, 33, 78}
• 散列函数：h(key)=key%7

则ASL成功 = （1 * 5 + 2 * 2）/7 = 9/7 说明：第一层5个节点，查找长度是1；第二层两个节点，查找长度是2

ASL失败 = （2 + 1 + 1 + 2 + 1） / 7 = 1 说明 对于下标0，查找0次就可以失败，对于下标1， 查找2次才失败

2025-09-16-海康威视

选择题

1.基础类型转换

x是byte类型，y是double类型，问：x/y*2是什么类型？——double

当应用一个二元运算符时，如果两个操作数的类型不同，Java会自动将其中一个或两个操作数提升到一个更通用的类型。规则如下（按优先级顺序）：

1. 如果任一操作数是 double 类型，则另一个操作数转换为 double。
   • 例如：int + double → double + double → 结果类型为 double。
2. 否则，如果任一操作数是 float 类型，则另一个操作数转换为 float。
   • 例如：long + float → float + float → 结果类型为 float。
3. 否则，如果任一操作数是 long 类型，则另一个操作数转换为 long。
   • 例如：int + long → long + long → 结果类型为 long。
4. 否则（即两个操作数都是 byte、short 或 char），两个操作数都提升为 int，然后运算，结果类型为 int。
   • 例如：byte + short → int + int → 结果类型为 int。
   • 注意：即使两个操作数都是 byte，运算结果也是 int（除非使用强制类型转换）。

2.有关集合能不能存null

hashset和treeset默认都可以存入null ❌

核心规律总结

1. 基于哈希的集合（HashSet, HashMap, LinkedHashMap等）：
   • 通常允许一个null键（对于Set来说就是元素本身），因为HashMap支持。
   • 值（对于Map）可以存储多个null。
2. 基于排序/比较的集合（TreeSet, TreeMap, PriorityQueue）：
   • 参与排序的元素（Set的元素，Map的键）不允许为null，因为排序时需要调用比较方法，会抛出NullPointerException。
   • 不参与排序的部分（如TreeMap的值）可以存null。
3. 数组或链表结构的集合（ArrayList, LinkedList等List）：
   • 通常允许多个null，因为它们按索引存取，不依赖元素的equals或compareTo方法（除非你主动调用contains、sort等方法）。
4. 并发集合（ConcurrentHashMap, ConcurrentLinkedQueue, CopyOnWriteArrayList）：
   • 大多数不允许null。这是一个设计决策，旨在避免在并发场景下出现歧义。例如，map.get(key)返回null时，你无法区分是“键不存在”还是“键对应的值就是null”。禁止null可以消除这种歧义。
   • 例外：CopyOnWriteArrayList作为List，允许null。
5. 早期线程安全集合（Hashtable, Vector）：
   • Vector允许null。
   • Hashtable不允许null的键或值，其设计如此。
6. 队列（Queue）：
   • 情况比较复杂。ArrayDeque等明确禁止null，因为poll()方法用null来表示队列为空。而LinkedList虽然实现Queue接口且技术上允许null，但这样做极易引发逻辑错误，强烈不推荐。

3.反射能否调用类的私有构造函数？

可以

2025-09-25-昊一源

选择题

1.索引的添加方式

• 创建普通索引——Create … ON …()

  1 2	CREATE INDEX index_name ON table_name (column1 [ASC|DESC], column2 [ASC|DESC], ...);

• 修改表结构（添加索引）——Alter…ADD…()

  1 2	ALTER TABLE table_name ADD INDEX index_name (column1 [ASC|DESC], column2 [ASC|DESC], ...);

• 创建表的时候直接指定索引——Index … ()

  1 2 3 4 5 6

  CREATE TABLE table_name ( column1 data_type, column2 data_type, ..., INDEX index_name (column1 [ASC|DESC], column2 [ASC|DESC], ...) );