大厂真题 / 华为

华为AI岗 2026-09-11

本场考试概述

考试时间：2026-09-11

考试岗位：AI岗

考点分析：两道可见编程题，分别涉及滑动窗口与单调队列、核心点连通分量与集合求交。难度评估为中等（编辑判断）。

本页整理两道编程题，包含完整题意、数据范围、样例与 Python 解法。下文统一使用 n、M、a、b 等记号。

建议策略：先解决普通连续区间，再证明折损条件的单调性；密度聚类题先区分核心点、边界点、噪声点，不要把所有邻近点直接合并。

第 1 题：端侧大模型动态权重剪枝管理器

题目描述

有 n 个按顺序排列的参数块，第 i 块的重要度为正整数 a[i]，内存占用为正整数 b[i]。只能保留一个连续区间，内存预算为 M。

计算两个最大重要度之和：

不修改任何参数块，区间总内存不超过 M。
允许将所选区间中重要度最小的一块深度量化：该块内存变为原来的一半并向下取整，重要度变为 0；也允许不使用量化。

最小重要度并列时，为获得最多的内存节省，选择其中内存最大的块即可。无法保留有正收益的区间时答案为 0。

输入描述

第一行 n、M；第二行 n 个重要度；第三行 n 个内存占用。数据范围：$1\le n\le 10^5$，$1\le M\le 10^9$，$1\le a[i],b[i]\le 10^4$。

输出描述

一行两个整数，依次表示普通模式和允许量化模式的最大重要度之和。

样例

输入

11
10 100 10
2 5 2

输出

120 200

普通模式保留后三块；量化模式保留前三块并折损中间块，内存为 11，重要度为 200。

补充自测

输入

6
1 4
4 3

输出

5 5

不量化时只能保留单块；量化中间块后，前两块内存为 5、得分为 5，而三块内存仍为 8，不能保留。

思路分析

第一步：普通模式。 因为所有内存与重要度都为正数，固定右端点时，满足预算的最靠左窗口就是得分最大的窗口。右端依次扩展，内存超限就移动左端，总共只需线性扫描。

第二步：写出量化后的预算。 若区间内存和为 B，折损块为 p，节省量为 (b[p] + 1) // 2，合法条件为 B - (b[p] + 1) // 2 <= M。得分为重要度和减去 a[p]。注意节省量是向上取整的一半，而剩余内存才是向下取整的一半。

第三步：证明窗口仍可单调收缩。 删除的不是折损块时，折损候选不变，内存只会减少。删除折损块时，删除的完整内存不小于原先节省量，还可对剩余块重新量化，所以有效内存也不会增加。因此一个已经超限的区间，向右添加元素不会重新合法，被丢弃的左端不需要回退。

第四步：维护最合适的折损块。 单调队列按 (重要度, -内存) 递增存储下标。新块比队尾更优或相同时，旧队尾更早过期且不会更优，可以弹出。队头就是最小重要度中内存最大的块。固定右端时，扩大区间会使“重要度总和减最小重要度”不减，所以只检查最靠左合法窗口即可。

正确性说明

普通窗口由正数性质保证最优。量化窗口的有效内存对子区间不增，得分对超区间不减，故双指针对每个右端找到的最靠左合法区间涵盖该右端的最优得分。队列比较顺序恰好实现折损规则。最后与不量化的最优值取最大，覆盖允许但不强制操作的情况。

题解代码

import sys
from collections import deque


def maximize(a, b, budget):
    left = memory = score = ordinary = 0
    for right in range(len(a)):
        memory += b[right]
        score += a[right]
        while left <= right and memory > budget:
            memory -= b[left]
            score -= a[left]
            left += 1
        ordinary = max(ordinary, score)

    left = memory = score = 0
    compressed = ordinary
    queue = deque()
    for right in range(len(a)):
        memory += b[right]
        score += a[right]
        key = (a[right], -b[right])
        while queue and (a[queue[-1]], -b[queue[-1]]) >= key:
            queue.pop()
        queue.append(right)
        while queue and memory - (b[queue[0]] + 1) // 2 > budget:
            if queue[0] == left:
                queue.popleft()
            memory -= b[left]
            score -= a[left]
            left += 1
        if queue:
            compressed = max(compressed, score - a[queue[0]])
    return ordinary, compressed


def solve():
    input = sys.stdin.readline
    n, budget = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    print(*maximize(a, b, budget))


if __name__ == '__main__':
    solve()

复杂度分析

时间复杂度：O(n)。每个下标进出窗口和队列至多各一次。

空间复杂度：O(n)，包含输入数组和单调队列。

易错点

并列最小值不能随意选，本文采用内存最大的块。
第二问必须保留不操作的选项，单块量化的重要度为 0。
内存和及重要度和应用足够宽的整数；Python 整数不会固定宽度溢出。

第 2 题：文档片段相关性判定

题目描述

将每个文档片段表示为二维点，给定邻域半径 eps 和最小点数 min_pts。一个点的邻域包含距离不超过 eps 的所有点，包括自身；邻域点数至少为 min_pts 时，它是核心点。

每一步只能从核心点走到其邻域中的点。若存在某个核心点，可以分别沿这样的路径到达两个查询点，则这两个点密度相连。非核心点只能作为路径终点，不能用于连接两个核心点簇。处于核心点邻域但不是核心点的点为边界点，其他点为噪声点；噪声点与任何点（包括自身）都不密度相连。

输入描述

第一行依次为 n、m、eps、min_pts。接着 n 行，每行两个浮点坐标；随后 m 行，每行两个查询点编号。编号从 0 开始。

数据范围：$1\le n,m\le 1000$，$0<eps\le 1000$，$2\le min_pts\le n$，坐标均在 $[-10000,10000]$ 内。距离采用欧氏距离。

输出描述

每个查询输出一行，密度相连为 1，否则为 0。

样例

输入

输出

前五个点为同一个核心簇；最后两个点都是噪声点。

补充自测

输入

输出

前三点属于同一核心连通分量；最后一点为噪声点。

思路分析

第一步：建立邻域并标核心点。 两两检查距离的平方即可。为避免固定浮点容差把略大于半径的距离误判为相等，代码把输入有限十进制坐标和半径统一放大为整数，以整数平方精确比较。

第二步：只连接核心点。 两个相邻核心点可以互相到达，核心点组成的无向图可用并查集求连通分量。非核心点没有继续走出的资格，绝对不能参与合并。

第三步：给每个点维护簇集合。 核心点的集合只有自身所在分量；边界点收集邻域内全部核心点的分量，可能有多个；噪声点集合为空。

第四步：查询集合交集。 两个点密度相连，当且仅当它们的簇集合存在共同分量。遍历较小集合并在另一集合中检查成员，找到一个就可以返回。

正确性说明

合法路径的非终点都是核心点，因而某个核心点能到达的核心点恰好是其核心连通分量。它能到达的非核心点恰好邻接这一分量。两个查询点可由同一个核心点到达，等价于二者都属于该核心分量的可达点集合，即簇集合有交集。

题解代码

import sys
from decimal import Decimal


def scaled(values):
    numbers = [Decimal(value) for value in values]
    places = max(0, max(-value.as_tuple().exponent for value in numbers))
    result = []
    for value in numbers:
        sign, digits, exponent = value.as_tuple()
        coefficient = 0
        for digit in digits:
            coefficient = coefficient * 10 + digit
        result.append((-1 if sign else 1) * coefficient * 10 ** (exponent + places))
    return result


def cluster_memberships(points, radius, min_pts):
    n = len(points)
    neighbors = [[] for _ in range(n)]
    for i, (x, y) in enumerate(points):
        for j, (u, v) in enumerate(points):
            if (x - u) ** 2 + (y - v) ** 2 <= radius ** 2:
                neighbors[i].append(j)
    core = [len(row) >= min_pts for row in neighbors]
    parent = list(range(n))
    size = [1] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for i in range(n):
        if not core[i]:
            continue
        for j in neighbors[i]:
            if core[j]:
                a, b = find(i), find(j)
                if a != b:
                    if size[a] < size[b]:
                        a, b = b, a
                    parent[b] = a
                    size[a] += size[b]
    return [{find(j) for j in row if core[j]} for row in neighbors]


def solve():
    input = sys.stdin.readline
    n, m, eps, min_pts = input().split()
    n, m, min_pts = int(n), int(m), int(min_pts)
    tokens = [eps]
    for _ in range(n):
        tokens.extend(input().split())
    values = scaled(tokens)
    points = list(zip(values[1::2], values[2::2]))
    memberships = cluster_memberships(points, values[0], min_pts)
    for _ in range(m):
        a, b = map(int, input().split())
        first, second = memberships[a], memberships[b]
        if len(first) > len(second):
            first, second = second, first
        print(int(any(root in second for root in first)))


if __name__ == '__main__':
    solve()

复杂度分析

时间复杂度：在定长数值运算及哈希查找均摊 O(1) 的模型下，预处理 O(n² α(n))，单次查询 O(min(s[a], s[b]))，其中 s[i] 是点 i 的簇集合大小，总计至多 O(n² α(n) + mn)。α 为反阿克曼函数。十进制缩放另需与输入数字长度相关的解析和大整数运算；任意高精度输入不能视为定长运算。

空间复杂度：O(n²)，邻域列表和各点簇集合；查询逐行处理，不存储全部查询。

易错点

边界点可以同时邻接两个不同核心簇，却不能把它们合并。
查询同一个噪声点仍输出 0。
半径边界使用“不超过”，重复坐标的不同点也要分别计数。

小结

连续区间题的关键是证明附加操作不会破坏窗口单调性；密度相连不是把全部邻近关系做普通连通分量。两题均可通过代码块下方的 ACM IDE 入口运行样例与补充自测。

这篇文章有帮助吗？

| GitHub 留言