跳到内容
当前位置:首页>笔试招聘真题>华为一场让人捉摸不透的笔试(0422春招实习笔试真题解析)

华为一场让人捉摸不透的笔试(0422春招实习笔试真题解析)

  • 2026-11-14 23:37:12
华为一场让人捉摸不透的笔试(0422春招实习笔试真题解析)

关注我们,每天更新大厂最新笔试题解析

前言

本次ai岗机考全是传统算法题,华为是你永远猜不透的女人,所以算法的准备上还是要全面,尤其对于华为这种笔试有硬性分数要求,且面试手撕要求bugfree的公司。

在线做题链接:https://niumacode.com/

  • 第 1 题(统计二叉树中"平衡路径"的数量,150 分,中等难度,DFS)
    用前缀和加回溯,在 DFS 过程中用哈希表记录根到当前节点的所有路径和出现次数,通 过判断当前前缀和是否之前出现过就能快速找出和为 0  的向下路径,最后减去节点自身值为 0 导致的单点路径即可。
  • 第 2 题(网络异常流量传播链路溯源,300 分,困难难度,动态规划)
    先用建图 + DFS/BFS找出总负载达标的关键节点连通块,再按时间顺序在关键节点构成的 DAG 上做最长路
    DP,求一条传播链能覆盖的最大用户数。

第 1 题 — 统计二叉树中"平衡路径"的数量(150 分)

在线做题链接:https://niumacode.com/

题目内容

定义二叉树的平衡路径需同时满足以下 3 个条件:

  1. 路径从任意节点出发,仅能向下延伸(只能向左/右子节点,不可向上回溯)。
  2. 路径上所有节点的和相加为 0。
  3. 路径长度(包含的节点个数)至少为 2。

请实现一个 Python 函数,输入二叉树的根节点(按层序遍历规则构建),返回该树中所有"平衡路径"的总数。

注意:

  • 建树规则:层序遍历列表按「从上到下、从左到右」的顺序构建二叉树,None 表示对应位置无节点。
  • 路径延伸:从起点出发,仅沿左子节点 OR 右子节点单向向下(单链,不可分叉)。
  • 统计方式:每个符合条件的单链路径独立计数(即使路径有重叠)。

输入描述

二叉树的层序遍历列表(元素为整数或 None,None 表示空节点)。

输出描述

整数,表示平衡路径的总数。

样例

样例 1

输入:[10, -5, -5, 2, -2, 3, -3]
输出:0

样例 2

输入:[0, 0, None]
输出:1

样例 3

输入:[1, -1, 2, -2, None, 3, -3]
输出:2

思路与代码

这道题的核心是在二叉树中寻找从上到下、和为 0 且节点数  的单链路径。解题思路:树的构建:通过按层遍历(广度优先搜索思路)解析输入的列表,将节点还原成树状结构。前缀和+DFS:寻找和为 0 的路径,可以转换为寻找两个节点 A 和 B(A 是 B 的祖先),使得它们到根节点的前缀和相等。通过深度优先搜索(DFS)自顶向下遍历,用哈希表记录当前路径上出现过的前缀和及其次数,可以在  的时间复杂度内完成统计。长度限制:题目要求节点数至少为 2。如果当前节点到某个祖先的前缀和为 0,且长度为 1(即只有当前节点自己),意味着当前节点的值为 0。因此,当当前节点的值为 0 时,我们要将匹配到的路径总数减 1,以排除掉单节点路径。

import sys
import json


classTreeNode:
def__init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None


defsolve():
# 读取一行并去除首尾空白
    line = sys.stdin.readline().strip()
ifnot line:
return

    line = line.replace("None", "null")
    line = line.replace("'", '"')

    arr = json.loads(line)

# 层序遍历构建二叉树
    root = TreeNode(arr[0])
    queue = [root]
    i = 1
    n = len(arr)

while queue and i < n:
        curr = queue.pop(0)
# 构建左子节点
if i < n and arr[i] isnotNone:
            curr.left = TreeNode(arr[i])
            queue.append(curr.left)
        i += 1
# 构建右子节点
if i < n and arr[i] isnotNone:
            curr.right = TreeNode(arr[i])
            queue.append(curr.right)
        i += 1

    ans = 0
# 前缀和字典,初始化 0 出现 1 次,代表“从根节点直接出发”的情况
    prefix_sums = {0: 1}

defdfs(node, curr_sum):
nonlocal ans
ifnot node:
return

        curr_sum += node.val

# 查找是否存在祖先节点的前缀和与当前前缀和相同
# 如果相同,说明祖先(不含)到当前节点(含)的路径和为 0
        ans += prefix_sums.get(curr_sum, 0)

# 排除长度为 1 的路径:如果 node.val == 0,则它的父节点的前缀和必然也是 curr_sum
# 这会导致计入一条单节点路径,所以需要减去 1
if node.val == 0:
            ans -= 1

# 记录当前前缀和
        prefix_sums[curr_sum] = prefix_sums.get(curr_sum, 0) + 1

# 向下延伸遍历
        dfs(node.left, curr_sum)
        dfs(node.right, curr_sum)

# 回溯:撤销当前节点的前缀和记录
        prefix_sums[curr_sum] -= 1

    dfs(root, 0)
    print(ans)


if __name__ == '__main__':
    solve()

第 2 题 — 网络异常流量传播链路溯源(300 分)

在线做题链接:https://niumacode.com/

题目背景

在网络监控中,异常流量的流动通常具有局部聚集性。监控系统需要识别出高负载的基站(关键节点),并判断流量在这些节点之间定向的传播链的最长路径。

题目描述

网络监控规则

  • 直接关联:对于基站  和 ,若其曼哈顿距离 ,则判定两者具有直接关联。
  • 关键节点判定:计算一个基站及其所有具有"直接关联"属性的基站(含自身)的流量负载  之和。若该总和 ,则该基站被判定为关键节点。

流量传播链路

流量只能在关键节点之间定向流动,规则如下:

  • 链路条件:若两个关键节点具有"直接关联"关系,且发生时间戳  不同,则流量从时间较早的基站流向时间较晚的基站。
  • 注意:若两个关联的关键节点发生时间完全相同,则它们之间无法建立有效的传播链路。

传播链条

传播链条是由一系列关键节点通过有向链路首尾相连构成的路径。

  • 衡量指标:链条的规模为该路径上所有节点服务的用户数  之和。
  • 任务:计算全网中可能形成的所有传播链条中,能够覆盖的最大用户总数。

处理流程指引

  1. 节点识别:基于空间距离和流量负载阈值,从所有基站中筛选出满足要求的关键节点。
  2. 构建拓扑:在关键节点间,基于空间关联和时间先后顺序(时间早 → 时间晚)建立定向传播关系。
  3. 路径计算:在构成的有向传播网络中,寻找一条或多条连续路径,使得累计服务的用户数  达到最大。

输入描述

  • 第一行:三个整数 (基站总数,)、(直接关联的曼哈顿距离阈值)和 (负载阈值)。
  • 接下来的  行,每行包含  个整数:。
  • 所有坐标、时间戳、负载和用户数的取值范围均为 。

输出描述

输出一个整数,代表最大用户数。若全网无法形成任何链路或关键节点,输出 。

样例

样例 1

输入:
3 1 500
0 0 10 100 50
1 0 20 100 50
0 1 30 100 50

输出:
0

说明:

  • 节点识别:三个基站虽然互为邻居,但每个基站能查到的邻域最大负载和仅为 。判定门槛 ,因 ,图中没有任何基站能成为关键节点。
  • 结论:由于传播链路只能在关键节点间建立,无关键节点即无法形成链条,输出 。

样例 2

输入:
4 1 150
0 0 10 100 10
1 0 20 100 10
5 5 10 200 100
5 6 30 200 100

输出:
200

说明:

  • 节点识别:基站  和 :曼哈顿距离为 ,互为邻居。所在连通块负载之和 ,均为关键节点。基站  和 :曼哈顿距离为 ,互为邻居,连通块负载 ,也均为关键节点。
  • 链路构建:基站 ()→ 基站 (),可建立传播链路,用户数之和 。基站  的用户数之和仅为 。
  • 结论:最大覆盖用户数为 。

思路与代码

这道题是一个典型的图论与动态规划结合的题目。难点在于如何在节点数量可能较多的情况下,高效地找出“关键节点”并构建出流量传播网。 解题思路:空间网格降维(Spatial Grid Optimization):由于直接两两计算曼哈顿距离的复杂度是 ,当节点数巨大时会超时。我们将地图划分为边长为 E 的网格,对于任何一个基站,它的潜在关联邻居一定在它所在网格及其周围 8 个网格内。这使得寻找相邻基站的耗时从全局遍历降至常数级(平均)。筛选关键节点:利用上述优化,求出每台基站的“局部负载和”,将负载和  的过滤为关键节点。构建 DAG(有向无环图):遍历关键节点,如果两者是“邻居”且时间戳不同,建立一条从早到晚的有向边。因为时间单调递增,形成的必然是没有环路的 DAG。记忆化搜索(DFS+Memoization):在 DAG 上使用动态规划求出一条路径,使其权值(用户数 U 之和)最大化。

import sys

# 扩展递归深度,防止在极端情况下因链路过长而导致栈溢出
sys.setrecursionlimit(200000)


defsolve():
# 解析 N, E, T
    parts = sys.stdin.readline().split()
    N, E, T = map(int, parts[:3])

    x = [0] * N
    y = [0] * N
    t = [0] * N
    W = [0] * N
    U = [0] * N

# 建立空间网格划分,网格边长至少为1
    S = max(1, E)
    grid = {}

# 循环读取接下来的 N 行数据
for i in range(N):
        line = sys.stdin.readline()
ifnot line:
break

        row_data = line.split()
        x[i] = int(row_data[0])
        y[i] = int(row_data[1])
        t[i] = int(row_data[2])
        W[i] = int(row_data[3])
        U[i] = int(row_data[4])

        cell_x = x[i] // S
        cell_y = y[i] // S
        cell = (cell_x, cell_y)
if cell notin grid:
            grid[cell] = []
        grid[cell].append(i)

# 1. 查找并统计每个节点的邻域负载
    adj_sum = [0] * N
for i in range(N):
        cx, cy = x[i] // S, y[i] // S
        curr_sum = 0
# 只搜寻相邻的 9 个格子
for dx in (-1, 0, 1):
for dy in (-1, 0, 1):
                cell = (cx + dx, cy + dy)
if cell in grid:
for j in grid[cell]:
if abs(x[i] - x[j]) + abs(y[i] - y[j]) <= E:
                            curr_sum += W[j]
        adj_sum[i] = curr_sum

# 2. 筛选出关键节点
    critical_nodes = set(i for i in range(N) if adj_sum[i] >= T)

ifnot critical_nodes:
        print(0)
return

# 3. 建立有向传播关系(拓扑关系)
    graph = {i: [] for i in critical_nodes}
for i in critical_nodes:
        cx, cy = x[i] // S, y[i] // S
for dx in (-1, 0, 1):
for dy in (-1, 0, 1):
                cell = (cx + dx, cy + dy)
if cell in grid:
for j in grid[cell]:
# 确保邻居也是关键节点,且不是自己
if j in critical_nodes and i != j:
if abs(x[i] - x[j]) + abs(y[i] - y[j]) <= E:
# 时间戳早的指向时间戳晚的
if t[i] < t[j]:
                                    graph[i].append(j)

# 4. 动态规划寻找最大权值路径 (记忆化深度优先搜索)
    dp = {}

defdfs(node):
if node in dp:
return dp[node]

        max_next = 0
for nxt in graph[node]:
            max_next = max(max_next, dfs(nxt))

# 当前节点的最大覆盖量 = 下游最大覆盖量 + 当前自身的用户量
        dp[node] = max_next + U[node]
return dp[node]

    max_users = 0
# 在所有关键节点上尝试起步,找出全网最大链路覆盖量
for c in critical_nodes:
        max_users = max(max_users, dfs(c))

    print(max_users)


if __name__ == '__main__':
    solve()
微信咨询 微信客服二维码微信扫一扫 · 添加人工客服 QQ QQ咨询 QQ咨询二维码QQ扫一扫 · 添加人工客服 帮助手册