Eclipse's Blog
0%

阿里云20250511笔试

发表于 分类于

单选9题27分，多选6题18分，编程题3题55分
笔试前就发面试预约了

单选

  1. 一棵平衡二叉树，平衡因子为1，节点总数64，树的最低高度是
  2. 哈希索引在什么情况下性能优于B+索引
    哈希索引特别适用于等值查询（例如 WHERE column = value）
  3. kruskal算法最小生成树，优先选择怎样的边
    权值最小的
  4. 生产者-消费者，缓冲区容量为10，生产者和消费者信号量的初始值为多少
  5. 斐波那契数列递归，时间复杂度多少 递归是O(2^n)
  6. 排序，三次排序结果判断是哪个排序
  7. SQL语句
  8. Http/1.1长连接作用
  9. 二级页表，一级8位，二级8为，页内偏移12位，最大容量是2^28

多选

  1. 索引
  2. 二分，查某个数要比较哪些数
  3. 用户线程和内核线程
    用户线程是指在用户空间中实现的线程管理机制，所有的线程创建、调度和同步操作都在用户空间完成，不需要内核直接参与。
    内核线程是由操作系统内核管理和调度的线程。每个内核线程都对应着一个内核级别的任务控制块(TCB)，内核直接负责这些线程的创建、调度和同步。
  4. HTTP请求方式哪些安全
    GET 和 HEAD（只返回响应头） 是安全的
    POST 和 PUT 是不安全的，但不一定会改变资源状态
    OPTIONS 和 TRACE 是安全的（OPTIONS：用于获取服务器支持的通信选项
    TRACE：用于回显客户端请求（用于调试），不应修改资源状态。）
    安全一定幂等，幂等不一定安全（PUT、DELETE是幂等的，但不安全）
  5. 单例模式
    饿汉模式创建单例是线程安全的，在类加载时就初始化单例，类加载是线程安全的
    懒汉模式普通不是线程安全的，用双重检查保证线程安全
    静态内部类实现单例是线程安全，因为静态内部类类加载是线程安全的
  6. 高效插入删除的数据结构有哪些

编程

  1. 字符串和声（15分）
    字符串模拟
  2. Tk网格的最大转换（15分）
    找规律
  3. 好路径计数（25分）
    输入一棵树，好路径为起点和终点都为M，路径上的所有点权值<=M，求这棵树上有多少好路径

​ DFS

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
class Solution {
public:
    int goodPathsCount = 0;

    // 深度优先搜索函数
    void dfs(int node, int parent, int maxValue, const vector<vector<int>>& adj, const vector<int>& values, int M) {
        // 如果当前节点权值为 M，并且路径上最大值不超过 M，则找到一条好路径
        if (values[node] == M && maxValue <= M) {
            goodPathCount++;
        }

        for (int neighbor : adj[node]) {
            if (neighbor == parent) continue; // 避免回溯到父节点

            int nextMax = max(maxValue, values[neighbor]);
            if (nextMax > M) continue; // 剪枝：如果路径最大值已经超过 M，不再继续

            dfs(neighbor, node, nextMax, adj, values, M);
        }
    }

    int numberOfGoodPaths(vector<vector<int>>& edges, vector<int>& values) {
        int n = values.size();
        vector<vector<int>> adj(n);

        // 构建邻接表
        for (auto& edge : edges) {
            int u = edge[0];
            int v = edge[1];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        // 统计每个权值对应的节点列表
        unordered_map<int, vector<int>> valueToNodes;
        for (int i = 0; i < n; ++i) {
            valueToNodes[values[i]].push_back(i);
        }

        // 对于每个不同的权值 M，作为起点开始 DFS
        for (const auto& [value, nodes] : valueToNodes) {
            for (int node : nodes) {
                dfs(node, -1, values[node], adj, values, value);
            }
        }

        // 每条路径被计算了两次，所以最终结果要除以 2
        return goodPathCount / 2;
    }
};