2023 华为笔试题 0426

笔试时间：2023年4月26日春招暑期实习

第一题

题目：批量初始化次数

某部门在开发一个代码分析工具，需要分析模块之间的依赖关系，用来确定模块的初始化顺序、是否有循环依期等问题。"批量初始化”是指一次可以初始化一个或多个模块。例如模块1依赖模块2，模块3也依赖模块2，但模块1和3没有依赖关系，则必须先"批量初始化”模块2，再"批量初始化"模块1和3。现给定一组模块间的依赖关系，请计算需要“批量初始化"的次数。

解答要求

时间限制: C/C++ 1000ms.其他语言: 2000ms

内存限制: C/C++ 256MB,其他语言: 512MB

输入描述

(1)第1行只有一个数字.表示模块总数N。

(2)随后的N行依次表示模块1到N的依赖数据。每行的第1个数表示依赖的模块数量(不会超过N)，之后的数字表示当前模块依赖的ID序列。该序列不会重复出现相同的数字，模块ID的取值定在[1,N]之内。

(3)模块总数N取值范围 1<=N<=1000.

(4)每一行里面的数字按1个空格分隔。

输出描述

输出"批量初始化次数”.若有循环依赖无法完成初始化，则输出-1。

示例输入1

输入: 5

3 2 3 4

1 5

1 5

0

输出: 3

解释:共5个模块。

模块1依赖模块2、3、4；

模块2依赖模块5

模块3依赖模块5

模块4依赖模块5

模块5没有依赖任何模块

批量初始化顺序为{5}->{2，3，4}->{1},共需”批量初始化”3次

示例输入2

输入: 3

1 2

1 3

1 1

输出: -1

解释:存在循环依赖，无法完成初始化，返回-1

参考题解

拓扑排序模拟即可。

Python：

from collections import deque
N = int(input())

indegre = [0 for _ in range(N + 1)]
nxs = {i:[] for i in range(N+1)}

for i in range(1,N +1):
    lines = [int(c) for c in input().split(" ")]
    if lines[0] == 0: continue
    for j in range(1, len(lines)):
        nxs[lines[j]].append(i)
        indegre[i] += 1

q = deque()
for i in range(1,N+1):
    if indegre[i] == 0:
        q.append(i)

cnt1 = 0
cnt2 = 0
while len(q):
    size = len(q)
    cnt1 += 1
    for i in range(size):
        node = q.popleft()
        cnt2 += 1
        for nx in nxs[node]:
            indegre[nx]-=1
            if indegre[nx] == 0: q.append(nx)

if cnt2 == N:
    print(cnt1)
else:
    print(-1)

第二题

题目：分配资源ID

给定一个管理ID的资源池，可以从资源池中分配资源ID和释放资源ID，分配方式有动态分配和指定分配，动态分配是从资源池的开始分配一个资源ID，指定分配是指定一个资源ID进行分配，无论哪种分配方式释放资源ID时都需要放到资源池的尾部。执行一系列操作后，请问资源池的第一个空闲资源ID应该是多少?

注意:

资源池的初始顺序是从小到大。

资源池中空闲资源ID不足时，动态分配失败，对资源池不进行任何操作.

指定分配资源ID已经被占用或者不在资源池范围内时，对资源池不进行任何操作。

释放资源ID不在资源池范围内时或者已经是空闲资源ID时，对资源池不进行任何操作。

保证每个用例最后都有空闲资源ID。

解答要求

时间限制: C/C++ 100ms,其他语言: 200ms

内存限制: C/C++ 32MB.其他语言: 64MB

解答要求

时间限制: C/C++ 1000ms,其他语言: 2000ms

内存限制: C/C++ 256MB,其他语言: 512MB

输入描述

第一行是资源池的范围:

第二行是操作个数。

第三行开始，第一个数字代表操作类型，1表示动态分配，2表示指定分配，3表示释放；

如果第一个数字是1，第二个表示分配的个数;

如果第一个数字是2，第二个表示分配的资源ID;

如果第一个数字是3，第二个表示释放的资源ID。

输出描述

资源池的第一个空闲资源ID

示例输入1

输入: 1 3

2

2 2

3 1

输出: 2

解释:第一行资源池范围是[1.3]，资源池的初始顺序是1->2->3。

第二行操作个数有2个。

第三行动态分配1个资源ID，资源池中剩余的资源ID顺序是2->3.

第四行释放1个资源ID，资源ID是1，资源池中剩余的资源ID顺序是2->3->1.

执行以上操作后，资源池的第一个空闲资源ID是2。