大厂真题 / 华为
华为 4.15 笔试真题 - 研发岗
本场考试概述
考试时间：2026年4月15日 考试岗位：研发岗（国内） 难度评级：中等偏难
考点分析：
- 第一题：双端队列 + 栈模拟（难度简单）
- 第二题：树上贪心 + BFS（难度困难）
- 第三题：面向对象设计 + 矩形遮挡判断（难度困难）
建议策略：
- 第一题是经典浏览器前进后退模型，用 deque + stack 按规则模拟即可快速拿分
- 第二题需要理解”翻转只影响同奇偶深度后代”这个关键性质，从根到叶贪心
- 第三题工程量大，核心难点在窗口遮挡判断和排序规则，数据量小可暴力枚举像素
第一题：浏览器地址栏
题目描述
实现浏览器地址栏的前进/后退功能，支持四种操作：
visit url：访问新页面，加入历史记录；若历史记录数超过上限 M，删除最早记录；清空前进记录back：若历史记录至少有两个页面，退回上一页，当前页面压入前进记录forward：若前进记录不为空，取出最近一个前进页面，加入历史记录print：输出当前页面地址
初始状态：当前页面为 Blank，历史记录仅有一个 Blank 页面。
样例
输入
7
10
visit a.com
visit b.com
back
visit c.com
print
forward
print
输出
c.com
c.com
思路分析
第一步：识别数据结构
历史记录需要从尾部追加（visit）、从尾部弹出（back），还要在超出容量时从头部淘汰——这恰好是双端队列（deque）的典型应用。前进记录只需要后进先出的压入和弹出，用栈即可。
第二步：理清操作语义
visit：追加到队尾，若超容量从队首淘汰，同时清空前进栈（浏览了新页面后不可能再前进到旧页面）back：队尾弹出压入前进栈，相当于暂存当前页。队列中至少保留一个页面才能回退forward：前进栈顶弹出追加到队尾，恢复之前离开的页面print：直接读取队尾元素
第三步：实现要点
数据规模很小，直接按规则逐条模拟。初始时将 Blank 放入 deque 作为起始页。
题解代码
import sys
from collections import deque
input = sys.stdin.readline
def solve():
n = int(input())
max_history = int(input())
history = deque(["Blank"])
forward_stack = []
result = []
for _ in range(n):
line = input().strip()
if line.startswith("visit "):
url = line[6:]
history.append(url)
if len(history) > max_history:
history.popleft()
forward_stack.clear()
elif line == "back":
if len(history) >= 2:
forward_stack.append(history.pop())
elif line == "forward":
if forward_stack:
history.append(forward_stack.pop())
elif line == "print":
result.append(history[-1])
print("\n".join(result))
solve()
复杂度分析
时间复杂度：O(n)，每次操作均为 O(1)。 空间复杂度：O(M)，历史记录最多存储 M 个页面。
第二题：异或树
题目描述
一棵 n 个节点的有根树（根为节点 1），每个节点有初始值 0 或 1。选择某个节点 u 操作时：u 本身的值翻转，且距离 u 为偶数的所有后代节点也翻转（距离为奇数的不变）。目标是使每个节点达到给定的目标值，求最少操作次数。
样例
输入
5
1 2
2 3
4 5
3 4
0 0 0 0 0
1 1 1 1 1
输出
2
思路分析
第一步：理解翻转的影响范围
翻转节点 u（深度为 d）时，u 本身被翻转，u 的距离为偶数的后代也被翻转。距离为偶数意味着这些后代节点与 u 的深度奇偶性相同。因此，翻转 u 只会影响子树中与 u 深度奇偶相同的节点。
第二步：贪心策略——为什么从根到叶逐层处理是最优的？
对于任意节点 v，能影响它的操作只来自路径上与它同奇偶深度的祖先。更深的节点翻转不会影响更浅的节点。因此，从根到叶按 BFS 序处理时，每到达一个节点，只需检查当前值是否等于目标值——如果不等，必须在此刻翻转，因为之后不会有更浅的节点来修正它。贪心不可回头。
第三步：用两个计数器传递翻转状态
沿路径维护两个计数器：even_flips（偶数深度祖先的翻转次数）和 odd_flips（奇数深度祖先的翻转次数）。对于深度为 d 的节点，取与 d 同奇偶的计数器，当前实际值 = 初始值 XOR（翻转次数的奇偶性）。若当前值不等于目标值，执行翻转并更新计数器。
题解代码
import sys
from collections import deque
input = sys.stdin.readline
def solve():
n = int(input())
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)
init_val = [0] + list(map(int, input().split()))
goal_val = [0] + list(map(int, input().split()))
if n == 1:
print(0 if init_val[1] == goal_val[1] else 1)
return
# BFS 建树，记录深度和 BFS 序
depth = [0] * (n + 1)
children = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
order = []
q = deque([1])
visited[1] = True
while q:
u = q.popleft()
order.append(u)
for v in adj[u]:
if not visited[v]:
visited[v] = True
depth[v] = depth[u] + 1
children[u].append(v)
q.append(v)
# 贪心：沿 BFS 序从根到叶处理
even_flips = [0] * (n + 1) # 路径上偶数深度祖先翻转次数
odd_flips = [0] * (n + 1) # 路径上奇数深度祖先翻转次数
flipped = [False] * (n + 1)
ans = 0
for u in order:
d = depth[u]
# 同奇偶深度的祖先翻转才影响当前节点
parity_flips = even_flips[u] if d % 2 == 0 else odd_flips[u]
cur = init_val[u] ^ (parity_flips & 1)
if cur != goal_val[u]:
flipped[u] = True
ans += 1
# 将翻转计数传递给子节点
for v in children[u]:
even_flips[v] = even_flips[u]
odd_flips[v] = odd_flips[u]
if flipped[u]:
if d % 2 == 0:
even_flips[v] += 1
else:
odd_flips[v] += 1
print(ans)
solve()
复杂度分析
时间复杂度：O(n)，BFS 建树和贪心遍历各一轮，每个节点常数时间。 空间复杂度：O(n)，存储树结构、深度数组和翻转计数。
第三题：实现一个窗口系统
题目描述
实现一个简单的窗口系统，坐标原点在屏幕左上角。每个窗口有名称、左上角坐标、宽高和层级属性。
遮挡规则：层级大的覆盖层级小的；同层级后创建的覆盖先创建的；resize 和 move 不改变创建顺序。窗口只要没被完全覆盖就算可见；完全在屏幕外的不可见。
支持操作：
init W H：初始化屏幕createWindow name x y w h level：创建窗口removeWindow name：删除窗口resize name w h：调整大小move name x y：移动窗口queryVisibility name：查询是否可见queryAllVisibleWindows x y w h：查询区域内所有可见窗口，按层级降序 + 同层字典序升序返回
样例
输入
init 200 300
createWindow window1 10 10 100 100 1
createWindow window2 20 20 40 30 2
createWindow window3 70 90 50 3
removeWindow window2
removeWindow window4
queryVisibility window1
queryAllVisibleWindows 10 10 100 100
输出
true
true
true
true
false
true
false
true
window3;window1
思路分析
第一步：识别题型——面向对象模拟
这是一道工程量较大的模拟题，操作数不超过 200，窗口数量极少。核心不在算法效率，而在正确处理遮挡关系和可见性判断。
第二步：窗口数据建模
每个窗口需要记录：名称、左上角 (x, y)、宽高 (w, h)、层级 level 和创建序号 order（用于同层级的覆盖优先级判断）。用字典维护名称到窗口数据的映射。
第三步：可见性判断——暴力枚举像素
窗口可见当且仅当：（1）与屏幕有交集；（2）交集区域中存在至少一个像素点没有被更高优先级的窗口覆盖。”更高优先级”指层级更大、或层级相同但创建更晚。
由于窗口数和坐标范围都很小（操作数 ≤ 200），可以直接枚举交集区域的每个像素点，检查是否有至少一个未被覆盖的点。
第四步：queryAllVisibleWindows 的排序
找出查询矩形内所有与之有交集且可见的窗口，按层级降序排列，同层级按名称字典序升序排列，用 ; 连接输出。
题解代码
import sys
input = sys.stdin.readline
screen_w = screen_h = 0
windows = {} # name -> [x, y, w, h, level, order]
create_counter = 0
def rects_intersect(x1, y1, w1, h1, x2, y2, w2, h2):
return x1 < x2 + w2 and x1 + w1 > x2 and y1 < y2 + h2 and y1 + h1 > y2
def is_visible(name):
win = windows[name]
x, y, w, h, level, order = win
# 窗口与屏幕的交集
wx1 = max(x, 0)
wy1 = max(y, 0)
wx2 = min(x + w, screen_w)
wy2 = min(y + h, screen_h)
if wx1 >= wx2 or wy1 >= wy2:
return False
# 收集优先级更高的窗口
covers = []
for other_name, other in windows.items():
if other_name == name:
continue
if other[4] > level or (other[4] == level and other[5] > order):
covers.append(other)
# 枚举像素点，找到至少一个未被覆盖的即可见
for px in range(wx1, wx2):
for py in range(wy1, wy2):
covered = False
for c in covers:
if c[0] <= px < c[0] + c[2] and c[1] <= py < c[1] + c[3]:
covered = True
break
if not covered:
return True
return False
result = []
try:
while True:
line = input().strip()
if not line:
continue
parts = line.split()
cmd = parts[0]
if cmd == "init":
w, h = int(parts[1]), int(parts[2])
if w > 0 and h > 0:
screen_w, screen_h = w, h
windows.clear()
create_counter = 0
result.append("true")
else:
result.append("false")
elif cmd == "createWindow":
name = parts[1]
x, y, w, h, level = int(parts[2]), int(parts[3]), int(parts[4]), int(parts[5]), int(parts[6])
if w > 0 and h > 0 and name not in windows:
windows[name] = [x, y, w, h, level, create_counter]
create_counter += 1
result.append("true")
else:
result.append("false")
elif cmd == "removeWindow":
name = parts[1]
if name in windows:
del windows[name]
result.append("true")
else:
result.append("false")
elif cmd == "resize":
name = parts[1]
nw, nh = int(parts[2]), int(parts[3])
if name in windows and nw > 0 and nh > 0:
windows[name][2] = nw
windows[name][3] = nh
result.append("true")
else:
result.append("false")
elif cmd == "move":
name = parts[1]
nx, ny = int(parts[2]), int(parts[3])
if name in windows:
windows[name][0] = nx
windows[name][1] = ny
result.append("true")
else:
result.append("false")
elif cmd == "queryVisibility":
name = parts[1]
if name not in windows:
result.append("false")
else:
result.append("true" if is_visible(name) else "false")
elif cmd == "queryAllVisibleWindows":
qx, qy, qw, qh = int(parts[1]), int(parts[2]), int(parts[3]), int(parts[4])
visible = []
for wname, win in windows.items():
if rects_intersect(win[0], win[1], win[2], win[3], qx, qy, qw, qh) and is_visible(wname):
visible.append(wname)
if not visible:
result.append("NoVisibleWindow")
else:
# 层级降序，同层字典序升序
visible.sort(key=lambda n: (-windows[n][4], n))
result.append(";".join(visible))
except EOFError:
pass
print("\n".join(result))
复杂度分析
时间复杂度：O(Q * W * S)，Q 为操作数，W 为窗口数，S 为屏幕面积；所有数量级均很小，暴力可行。 空间复杂度：O(W)，存储窗口列表。
小结
- 第一题是经典的浏览器前进后退模型，用双端队列维护有容量上限的历史记录、用栈维护前进记录，逐条模拟即可。关键是
visit清空前进栈、back要保证至少两个页面才能回退。 - 第二题核心在于发现”翻转节点 u 只影响子树中与 u 同奇偶深度的后代”这一性质。有了这个观察，沿 BFS 序从根到叶贪心，用两个计数器传递偶/奇深度祖先的翻转次数，即可 O(n) 解决。
- 第三题是工程模拟题，难度在于正确实现窗口遮挡的优先级判断（层级 > 创建顺序）和可见性检测。数据规模极小，暴力枚举像素点即可通过。