华为一场让人捉摸不透的笔试(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()