华为笔试,难度变大了(0522实习笔试真题解析)
关注我们,每天更新大厂最新笔试题解析
前言
本次笔试难度较高,特别是第三题比较麻烦。第一题打卡题,数据很小,怎么做都行。第二题迷宫最短路,不算很难,转过弯来就行。第三题树形dp,但是这个dp比较麻烦,并且每个子状态的求解类似一个分组背包。
(第三题没有提交过,大家参考一下就可以了,有不同的想法也可以在评论区留言)
春招和暑期实习的笔试也陆陆续续开始啦,有参加笔试的同学欢迎投稿哦,投稿一场完整笔试的,有请你喝一周的奶茶的现金奖励!(投稿加文末微信,备注投稿)
文末也有我们的面向校招的一对一进阶提高的活动介绍,有兴趣的同学也可以了解一下!
获取公共链表片段
给定两个链表,获取两者中相同节点值的最大连续片段。如果没有公共片段,返回-1。
解答要求
时间限制: C/C++ 1000ms,其他语言: 2000ms内存限制: C/C++ 256MB, 其他语言: 512MB
输入
第一行表示链表1,第二行表示链表2,每条链表长度不超过20个元素,链表不会为空。
输出
公共链表片段
样例1
输入
1 2 2 3 9 1 5
9 2 2 3 6 8
输出
2 2 3
思路与代码
数据非常小,所以直接模拟即可。
找到第一个数组的所有子数组,放入哈希表。
遍历第二个数组的所有子数组,判断是否存在于哈希表即可。
nums1 = input()
nums2 = input()
# 找到最长公共子数组
s = set()
n,m = len(nums1),len(nums2)
for i in range(n):
for j in range(i+1,n+1):
s.add(nums1[i:j+1])
res = ""
for i in range(m):
for j in range(i+1,m+1):
if nums2[i:j+1] in s and j+1-i > len(res):
res = nums2[i:j+1]
if res:
print(res.strip())
else:
print(-1)
矿车运输成本
露天矿采矿作业的特点是规模大,矿石和废料的移动量达到百万吨,运输成本开销较大,需要寻求一种最优的运输路径节省成本。
已知矿场可以划分成N*M的网格图,每个网格存在地形的差异,因此通过不同网格时,成本开销存在差异。
网格有以下5种类型:
1、标志为'S’的网格为运输起点;
2、标志为'E”的网格时运输终点;
3、标志为'B’的网格为阻塞点,不允许通行;
4、标志为'C'的网格为检查点,矿车在运输路径中,至少需要进入一次检查点。
5、标志为‘数字”的网格,其数字表示经过该网格的成本开销。
运输矿车只能上下左右4个方向运行,不允许斜对角进入其他网格。必要时可重复进入网格。
请根据输入的网格图,寻求一条从S网格到E网格,并且至少经过一次检查点的最低成本运输路径,并输出其成本开销。
解答要求
时间限制: C/C++ 1000ms,其他语言: 2000ms内存限制: C/C++ 256MB, 其他语言: 512MB
输入
第一行:网格图的行数N[3,200]和网格图的列数M[3,200],使用空格隔开。
第二行至第N+1行:网格图每一行的元素,可以为'S’,E’,'B',‘C'或者数字[0,100],并且有且仅有一个'S’和一个'E’,同时存在一个或者多个‘C',并依次使用空格隔开。
输出:
第一行:输出运输最低成本开销。如果不存在可达通路,请输出-1
示例 1:
输入:
3 3
S 4 5
7 B 3
C 9 E
输出:
16
思路与代码
逆向思维+迪杰斯特拉。
枚举所有的C点,从C点出发跑一次迪杰斯特拉,找到C->S和C->E的最短距离即可。
import heapq
from math import inf
n,m = map(int, input().split())
matrix = []
for _ in range(n):matrix.append(input().split())
def solve(st_i: int, st_j:int):
distance = [[inf]*m for _ in range(n)]
visited = [[False]*m for _ in range(n)]
distance[st_i][st_j] = 0
h = []
heapq.heappush(h, [0, st_i,st_j])
while h:
d,i,j = heapq.heappop(h)
if visited[i][j]: continue
visited[i][j] = True
for ni,nj in ((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
if ni<0 or nj<0 or ni>=n or nj>=m or visited[ni][nj] or matrix[ni][nj] == 'B':continue
w = 0
if matrix[ni][nj] == 'C' or matrix[ni][nj] == 'E' or matrix[ni][nj] == 'S':
w = 0
else:
w = int(matrix[ni][nj])
if distance[ni][nj] > distance[i][j] + w:
distance[ni][nj] = distance[i][j] + w
heapq.heappush(h, [distance[ni][nj], ni, nj])
return distance
C = []
for i in range(n):
for j in range(m):
if matrix[i][j]== 'C':
C.append([i, j])
res = inf
si, sj, ei, ej = 0, 0, 0, 0
for i in range(n):
for j in range(m):
if matrix[i][j] == 'S':
si, sj = i, j
elif matrix[i][j] == 'E':
ei, ej = i, j
for ci,cj in C:
dis = solve(ci,cj)
if dis[si][sj] == inf or dis[ei][ej] == inf:
continue
else:
res = min(res, dis[si][sj] + dis[ei][ej])
if res == inf:
print(-1)
else:
print(res)
最优索引选择
某项目组打算使用建立索引方法提升数据库系统的性能。
已知当前数据库系统存在N个表,并且已经通过实际业务workload测试,得到了各个表进行索引的实用值(收益),以及索引的空间开销。
我们把索引分成若干个索引组,所有索引组构成一个树型结构,每个索引组作为树的一个节点。并且挑选索引时有以下两个约束:
1、父子依赖:当从某个索引组节点中挑选索引,则需要保证其父节点至少存在一个索引已经被挑选。题目保证树的正确性,并且保证父节点的组编号,小于子节点的组编号。
2、路径互斥:不同路径上的索引组存在互斥。当挑选了某个路径上的索引,则不能挑选其他不在该路径上的索引。
如下图,根据父子依赖约束,假设挑选组路径为[0,1,3],当挑选组3里面的索引,需要保证组1里至少有一个索引已被挑选,同样需要保证组0里至少有一个索引已经被挑选。然后根据路径互斥约束,组3和组2不在同一个路径里,挑选了组3里面的索引,则不能再挑选组2里面的索引。
请根据每个表的索引的实用值、空间开销、组的依赖关系和组的互斥关系,选择若干个索引,保证所选的索引总空间开销不超过给定的空间闽值 B 的前提下,使得总实用值最大,并输出这个最大值。
解答要求
时间限制: C/C++ 2000ms,其他语言: 4000ms内存限制: C/C++ 256MB, 其他语言: 512MB
输入:
第一行3个整数(单空格间隔),依次表示:空间阈值B [1,5000]、表索引的数量N [1,10000],和分组数量M[1,100](组编号从0开始依次递增)。
第二行至第N+1行每行3个整数(单空格间隔),依次表示每个表索引的组编号、实用值和空间开销。
第N+2行M个整数(单空格间隔),从组0开始依次为每个组的父组编号;若值为-1,表示无父(该组即为根节点)。
输出
第一行:输出最大的总实用值
示例 1:
输入:
40 4 2
0 10 10
1 30 10
0 5 20
1 60 40
-1 0
输出:
45
思路与代码
树形dp+01背包。
从根出发,对于每个树上的节点,我们可以选择节点上的若干个索引,我们直接跑一次01背包,f[j]的含义就是,空间阈值为j的时候,获取的最大价值。
接着我们枚举当前节点消耗的阈值的所有情况,每种情况都向下依赖特定的子节点的状态,取最大值。
dp[i][j]表示考虑节点i,空间阈值为j的时候可以获取的最大价值。
状态转移如下:
dp[i][j] = MAX(dp[i][j], dp[nx][j-k] + f[k])
其中,f[k]表示当前节点可用的空间阈值为k的时候可以获取的最大价值,使用01背包求解。
B,N,M = map(int, input().split())
indexs = [[0,0] for _ in range(N)]
nodes = [[] for _ in range(M)]
for i in range(N):
idx,val,cst = map(int, input().split())
indexs[i] = [val, cst]
nodes[idx].append(indexs[i])
fa = [int(x) for x in input().split()]
graph = [[] for _ in range(M)]
root = -1
for i in range(len(fa)):
if fa[i] == -1:
root = i
continue
graph[fa[i]].append(i)
dp = [[0]*(B+1) for _ in range(M)]
#i是节点 j是剩余的阈值
def dfs(node,cst):
# 当前这一组至少选择一个,
# 每一组选取哪些元素可以获取最大收益?
f = [0] * (cst + 1)
curIndexs = nodes[node]
n = len(curIndexs)
for i in range(1, n + 1):
for j in range(cst, curIndexs[i-1][1]-1, -1):
f[j] = max(f[j], f[j - curIndexs[i-1][1]] + curIndexs[i-1][0])
dp[node][cst] = f[-1] #到这里就截止
for nx in graph[node]:
cur = 0
for j in range(cst):
dfs(nx, cst-j)
if f[j]!=0:
cur = max(cur, f[j] + dp[nx][cst-j])
dp[node][cst] = max(dp[node][cst], cur)
dfs(root,B)
print(dp[root][B])
最后插一下我们的进阶一对一辅导啦
我们是一个针对技术岗(前后端开发、测试、测开、大数据开发)校招一对一进阶提高的工作室。我们从2020年2月份开始,迄今整整三年的时间,带领300+学员斩获1500+大厂offer,参加活动的同学人均5个中大厂offer以上,以下是我们活动内容的介绍! 万诺coding
我们主要是针对有一定基础的同学提供一对一面试辅导,针对每个同学不同的情况定制内容,包括但不限于“数据结构与算法”/“计算机基础知识”/“项目梳理”/“面试技巧”/“面试复盘”等内容。
摸底测试:如果有兴趣深入了解我们的活动,需要先参加我们的“摸底测试”(类似面试),方便我们了解你的具体情况(主要是code能力和计算机素养),定制出相应的辅导计划。同时这也是一个双向筛选的过程,如果基础过差的同学,抱歉我们可能无法辅导(基础过差的同学一对一辅导成本过高,对双方都不适合);摸底测试通过的同学,我们会定制化一个针对性的提高计划。然后你再考虑是否参加我们的活动。
承诺保offer:通过摸底测试后,我们会针对每个同学的情况给定一个“保offer”计划。然后同学可以根据自己的实际情况考虑参不参加我们的活动。
有兴趣的同学可以扫码添加我们的微信(whynotlab)