大厂真题 / 华为

华为 4.29 笔试真题 - 研发岗

本场考试概述

考试时间：2026年4月29日 考试岗位：研发岗（国内） 难度评级：中等偏难

考点分析：

第一题：哈希计数 + 后缀和（难度中等）
第二题：二叉树层序遍历 + 自底向上累加（难度简单）
第三题：分治最近点对（难度困难）

建议策略：

第一题和第二题相对基础，确保拿满分
第三题分治最近点对是竞赛经典算法，建议提前掌握模板，考场上能快速默写
注意第一题的去重处理和第三题的精度截断（向下取整，不是四舍五入）

第一题：电商购物记录商品关联分析

题目描述

某电商平台希望分析用户的购买行为，找出经常一起购买的商品对。商品对指两个不同商品 ID 在同一用户的购物记录中同时出现。

给定 $n$ 个用户的购物记录和 $q$ 个查询，每个查询给出阈值 $t$，要求输出共现频率 $\geq t$ 的商品对数量。

输入描述：

第一行包含整数 $n, q$，表示用户数量和查询数量。接下来 $n$ 行，每行第一个整数 $k$ 表示该用户购买的商品数量，接下来 $k$ 个整数表示商品 ID。同一用户的商品 ID 可能重复，需去重处理。接下来 $q$ 行，每行一个整数 $t$，查询共现频率 $\geq t$ 的商品对数量。

输出描述：

共 $q$ 行，每行输出一个整数，表示满足条件的商品对数量。

样例

输入

输出

4
1

样例解释：对每个用户的购物记录去重后生成商品对，统计各商品对出现次数：$(1,2)$ 出现 1 次，$(1,3)$ 出现 2 次（用户 1 和用户 5），$(2,3)$ 出现 1 次，$(2,4)$ 出现 1 次。查询 $t=1$ 时共 4 对满足，查询 $t=2$ 时仅 $(1,3)$ 满足。

思路分析

第一步：理解商品对的共现

每个用户有一组商品（去重后），从中选出所有二元组合就构成了该用户产生的商品对。一个商品对的”共现频率”就是有多少个用户同时买了这两件商品。

第二步：暴力枚举商品对

关键观察：题目没有给出明确的数据范围约束，但从实际场景推断，单个用户的去重商品数有限。假设每个用户最多有 $k$ 种不同商品，则每个用户产生 $\binom{k}{2}$ 个商品对。对所有用户的商品对用哈希表累加频次即可。

为了保证商品对的唯一表示，对每个用户的商品去重后排序，然后双重循环枚举所有 $(a, b)$ 对（$a < b$），以 $(a, b)$ 为 key 在哈希表中 +1。

第三步：后缀和加速多次查询

统计完所有商品对的频次后，建立计数数组 $\text{cnt}[f]$ = 频次恰好等于 $f$ 的商品对数量。从后往前做后缀和：$\text{cnt}[f] += \text{cnt}[f+1]$，这样 $\text{cnt}[t]$ 就表示频次 $\geq t$ 的商品对数量，每个查询 $O(1)$ 回答。

题解代码

import sys
from collections import defaultdict

input = sys.stdin.readline

def solve():
    n, q = map(int, input().split())

    freq = defaultdict(int)

    for _ in range(n):
        line = list(map(int, input().split()))
        k = line[0]
        items = sorted(set(line[1:k + 1]))
        for i in range(len(items)):
            for j in range(i + 1, len(items)):
                freq[(items[i], items[j])] += 1

    # cnt[f] = 频次恰好等于 f 的商品对数量
    cnt = [0] * (n + 2)
    for c in freq.values():
        cnt[c] += 1

    # 后缀和：cnt[f] 变为频次 >= f 的商品对数量
    for i in range(n, 0, -1):
        cnt[i - 1] += cnt[i]

    out = []
    for _ in range(q):
        t = int(input())
        out.append(str(cnt[t] if t <= n else 0))
    print('\n'.join(out))

solve()

复杂度分析

时间复杂度：$O(\sum k_i^2 + n + q)$，枚举阶段每个用户 $O(k_i^2)$，后缀和 $O(n)$，查询 $O(q)$

空间复杂度：$O(P + n)$，$P$ 为不同商品对数量

第二题：文件目录的分层压缩

题目描述

有一个 $n$ 层目录的文件系统，每个目录有至多两个子目录（完全二叉树结构）。需要统计每个目录（含子目录）的总大小。

一个目录的总大小等于自身文件大小加上所有子目录的总大小。

输入描述：

第一行包含整数 $n$，表示目录的层数。第二行为按二叉树层序遍历给出的第 1 到第 $n$ 层各目录文件的大小，$-1$ 表示该节点为空，$0$ 表示该节点无文件但可能有子目录。

输出描述：

按二叉树层序遍历输出统计后的每个目录总大小，空节点用 $-1$ 表示。最后一层末尾连续的 $-1$ 应省略不输出。

样例

输入

3
1 2 -1 5 3

输出

11 10 -1 5 3

样例解释：节点 5 和 3 无子节点。节点 2 有两个子节点 5 和 3，总大小为 $2+5+3=10$。根节点只有左子节点（总大小 10），总大小为 $1+10=11$。

思路分析

第一步：理解数据结构

输入是一棵二叉树按层序铺成的一维数组，下标从 0 开始。$n$ 层二叉树最多 $2^n - 1$ 个节点。这和堆的数组表示完全一致：下标 $i$ 的左孩子在 $2i+1$，右孩子在 $2i+2$。

第二步：自底向上累加

要计算每个节点的子树总和，只需从数组末尾向前遍历：处理父节点时，子节点的值已经是各自子树的累加结果。

具体做法：从 $\lfloor \text{len}/2 \rfloor - 1$ 开始倒序到 0（这是最后一个非叶子节点的下标）。对每个非空节点，加上其非空孩子的值。

以样例 1 2 -1 5 3 为例：

数组下标：0→1, 1→2, 2→-1, 3→5, 4→3
从下标 1 开始（最后一个非叶子节点）：$\text{tree}[1] = 2 + 5 + 3 = 10$
下标 0：左孩子 $\text{tree}[1]=10$，右孩子 $\text{tree}[2]=-1$ 跳过，$\text{tree}[0] = 1 + 10 = 11$
结果：11 10 -1 5 3

第三步：输出裁剪

末尾连续的 $-1$ 省略不输出。

题解代码

import sys

input = sys.stdin.readline

def solve():
    n = int(input())
    max_nodes = (1 << n) - 1
    tree = [-1] * max_nodes

    vals = list(map(int, input().split()))
    for i in range(len(vals)):
        tree[i] = vals[i]

    # 从最后一个非叶子节点开始，倒序累加子节点
    for i in range(max_nodes // 2 - 1, -1, -1):
        if tree[i] == -1:
            continue
        left = 2 * i + 1
        right = 2 * i + 2
        if left < max_nodes and tree[left] != -1:
            tree[i] += tree[left]
        if right < max_nodes and tree[right] != -1:
            tree[i] += tree[right]

    # 去掉末尾连续的 -1
    last = len(vals) - 1
    while last >= 0 and tree[last] == -1:
        last -= 1

    print(' '.join(str(tree[i]) for i in range(last + 1)))

solve()

复杂度分析

时间复杂度：$O(2^n)$，遍历所有节点一次

空间复杂度：$O(2^n)$，存储层序数组

第三题：无人机的安全距离检测

题目描述

某活动现场有 $n$ 架无人机，每架无人机有固定坐标 $(x, y)$。计算所有无人机之间的最小欧式距离，仅保留整数部分（向下截断，不四舍五入）。如果只有 1 架无人机，输出 $-1$。

样例

输入

输出

样例解释：坐标 $(10,18)$ 和 $(22,25)$ 两点的欧式距离最小，约为 $13.89$，直接截断小数部分输出 $13$。

思路分析

第一步：分析暴力法的瓶颈

最直接的方法是两两枚举 $n$ 个点，计算距离取最小值，时间复杂度 $O(n^2)$。当 $n$ 较大时（如 $10^5$），暴力法会超时。

第二步：分治最近点对算法

这是计算几何中的经典问题，分治算法可以将复杂度降到 $O(n \log^2 n)$。核心思想：

排序 + 分割：先将所有点按 $x$ 坐标排序，从中间位置一分为二
递归求解：递归求左半部分最近距离 $d_L$ 和右半部分最近距离 $d_R$，取较小值 $d = \min(d_L, d_R)$
跨区域检查：全局最近点对可能一个在左半、一个在右半。但这种跨区域点对的两个点到分割线的 $x$ 距离一定都小于 $d$——否则光 $x$ 方向的差值就已经 $\geq d$ 了，不可能比 $d$ 更近。所以只需要检查分割线附近宽度为 $2d$ 的竖直条带内的点
条带扫描：条带内的点按 $y$ 坐标排序，对每个点只需向上检查 $y$ 差小于 $d$ 的点。可以证明每个点最多检查常数个邻居（约 6-8 个），所以条带内检查是 $O(n)$ 的

第三步：实现要点

用距离的平方来比较，避免浮点运算误差，最后才开方
点数 $\leq 3$ 时直接暴力
最终输出要用 int(math.sqrt(d2)) 向下截断

题解代码

import sys
import math

input = sys.stdin.readline

def dist2(a, b):
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2

def closest_pair(pts, l, r):
    # 点数 <= 3 时暴力
    if r - l <= 3:
        min_d = float('inf')
        for i in range(l, r):
            for j in range(i + 1, r):
                min_d = min(min_d, dist2(pts[i], pts[j]))
        return min_d

    mid = (l + r) // 2
    mid_x = pts[mid][0]
    d = min(closest_pair(pts, l, mid), closest_pair(pts, mid, r))

    # 筛选 x 距分割线不超过 sqrt(d) 的点
    strip = []
    for i in range(l, r):
        dx = pts[i][0] - mid_x
        if dx * dx < d:
            strip.append(pts[i])

    # 按 y 排序后只检查 y 相邻的点
    strip.sort(key=lambda p: p[1])

    for i in range(len(strip)):
        for j in range(i + 1, len(strip)):
            dy = strip[j][1] - strip[i][1]
            if dy * dy >= d:
                break
            d = min(d, dist2(strip[i], strip[j]))

    return d

def solve():
    n = int(input())
    if n == 1:
        input()
        print(-1)
        return

    pts = []
    for _ in range(n):
        x, y = map(int, input().split())
        pts.append((x, y))

    pts.sort()
    d2 = closest_pair(pts, 0, n)
    print(int(math.sqrt(d2)))

solve()

复杂度分析

时间复杂度：$O(n \log^2 n)$，分治共 $\log n$ 层，每层对条带内点按 $y$ 排序耗费 $O(n \log n)$

空间复杂度：$O(n)$，存储点坐标和临时数组

小结

第一题考查哈希计数 + 后缀和，核心在于对每个用户的商品去重排序后枚举所有二元组合，再用后缀和将多次查询优化到 $O(1)$
第二题是基础的二叉树层序数组操作，利用父子下标关系自底向上累加即可，属于送分题
第三题是经典的分治最近点对，属于竞赛级难题，需要提前掌握分治框架和条带扫描技巧，注意最终结果向下截断

这篇文章有帮助吗？

| GitHub 留言