华为笔试真题解析，拿下！！！

大家好，我是吴师兄。

提前批开始啦！ 早点练习，准备好秋招吧。

今天分享的是 华为 笔试真题，拿下它！！！

第一题

题目描述

请设计一个文件缓存系统，该文件缓存系统可以指定缓存的最大值(单位为字节)。文件缓存系统有两种操作：存储文件（ put ）和读取文件（ get ）

操作命令为 put fileName fileSize 或者 get fileName

存储文件是把文件放入文件缓存系统中；读取文件是从文件缓存系统中访问已存在的文件，如果文件不存在，则不作任何操作。

当缓存空间不足以存放新的文件时，根据规则删除文件，直到剩余空间满足新的文件大小为止，再存放新文件。

具体的删除规则为：文件访问过后，会更新文件的最近访问时间和总的访问次数，当缓存不够时，按照第一优先顺序为访问次数从少到多，第二顺序为时间从老到新的方式来删除文件。

输入描述

第一行为缓存最大值 m (整数，取值范围为 0 < m <= 52428800 )

第二行为文件操作序列个数 n ( 0 <= n <= 300000 ）

从第三行起为文件操作序列，每个序列单独一行

文件操作定义为 "op fileName fileSize"

fileName 是文件名， fileSize 是文件大小

输出描述

输出当前文件缓存中的文件名列表，文件名用英文逗号分隔，按字典顺序排序

如： a,c

如果文件缓存中没有文件，则输出 NONE

补充说明

1. 如果新文件的文件名和文件缓存中已有的文件名相同，则不会放在缓存中
2. 新的文件第一次存入到文件缓存中时，文件的总访问次数不会变化，文件的最近访问时间会更新到最新时间
3. 每次文件访问后，总访问次数加 1 ，最近访问时间更新到最新时间
4. 任何两个文件的最近访问时间不会重复
5. 文件名不会为空，均为小写字母，最大长度为 10
6. 缓存空间不足时，不能存放新文件
7. 每个文件大小都是大于 0 的整数

解题思路

系统设计的大模拟题，关键还是在于读懂题意。用人话捋一遍题目。

文件缓存系统可以认为是一个池子。

对这个文件池子我们可以做两件事情：

1. 往池子里扔文件，对应操作 put fileName fileSize ，其中 fileName 是文件名字， fileSize 是文件大小
2. 查看池子里已有的文件，对应操作 get fileName ，其中 fileName 是文件名字。

池子具有一个容量上限值，当放入一个新文件的空间不足时，需要删除掉若干之前放入的文件，来腾出空间方这个最新的文件。

删除文件具有优先级：

1. 优先删除之前访问次数最少的文件，也就是 get fileName 调用次数最少的那个
2. 如果访问次数相同，则删除最近一次访问时间，最早的那个文件。

不断删除文件，直到最后有足够空间放入新文件。

题目问的是，经过若干次操作之后，池子里还剩下哪些文件。

数据结构设计

每次插入或访问文件 fileName 的时候，我们都要修改这个文件的访问次数以及访问时间。

所以我们需要通过 fileName 的信息，来获取先前信息。

很容易想到这种快速查找以及修改， 需要用到哈希表来实现 。

可以以文件名字 fileName 作为 key ，访问次数、最近访问时间、文件大小所构成的三元组 [getCount, lastGetTime, fileSize] 作为 value ，构建哈希表。

譬如，在执行了以下语句

put a 10
put b 20
get a
get a
get b

之后，表示系统缓存的哈希表形如

dic = {
"a": [2, 3, 10],
"b": [1, 4, 20]
}

那么对每一次 插入和访问文件操作 ，都可以操作哈希表来表示文件缓存系统的变化了。

每行输入均为带空格的一个字符串。我们对其根据空格进行切割，再做后续判断和对应操作，即

for time in range(N):
    ops = input().split()
    # 插入操作
    if ops[0] == "put":
        pass 
    # 访问操作
    elif ops[0] == "get":
        pass

插入操作

当 ops[0] == "put" 时，对应插入操作。 ops 是一个三元组，插入的文件名和文件大小可以通过 ops 得到

fileName, fileSize = ops[1], int(ops[2])

当以下两种情况出现时， 可以直接跳过该插入操作

1. 文件名 fileName 已经存在于哈希表 dic 中，即之前已经插入过同名文件
2. 文件大小 fileSize 超过了缓存最大值，即就算把整个缓存系统都清空，都无法插入该文件

if fileName in dic:
    continue
if fileSize > maxSize:
    continue

在将文件加入缓存系统之前，我们还需要 判断缓存系统是否包含足够的空间来存储该文件 。

如果空间不足，则需要删除若干文件，直至空间足够。

因为不知道需要删除多少文件，所以需要在一个 while 循环中持续地进行删除操作，循环不变量为 maxSize - curSize < fileSize 。

maxSize - curSize 表示剩余空间，如果剩余空间小于文件大小，则需要不断删除。

对应的代码为

while maxSize - curSize     delFileName = min(dic.keys(), key=lambda k: (dic[k][0], dic[k][1]))
    delFileSize = dic[delFileName][2]
    del dic[delFileName]
    curSize -= delFileSize

删除完毕后，可以进行插入操作，同时需要更新当前缓存系统的空间 curSize ，即

dic[fileName] = [0, time, fileSize]
curSize += fileSize

综上，插入操作对应的代码为

if ops[0] == "put":
    fileName, fileSize = ops[1], int(ops[2])
    if fileName in dic:
        continue
    if fileSize > maxSize:
        continue
    while maxSize - curSize         delFileName = min(dic.keys(), key=lambda k: (dic[k][0], dic[k][1]))
        delFileSize = dic[delFileName][2]
        del dic[delFileName]
        curSize -= delFileSize

    dic[fileName] = [0, time, fileSize]
    curSize += fileSize

访问操作

当 ops[0] == "get" 时，对应访问操作。 ops 是一个二元组，访问的文件名可以通过 ops 得到

fileName = ops[1]

然后需要判断访问的文件名 fileName 是否在之前已经存在于缓存系统中，即是否位于哈希表 dic 中。若

• 不存在，则直接跳过
• 存在，则 fileName 的访问次数 +1 ，且更新访问时间

综上，访问操作对应的代码为

if ops[0] == "get":
    fileName = ops[1]
    if fileName not in dic:
        continue
    dic[fileName][0] += 1
    dic[fileName][1] = time

参考代码

# 公众号：吴师兄学算法
# 输入文件缓存系统的容量
maxSize = int(input())
# 输入操作个数
N = int(input())
# 构建表示文件缓存系统的哈希表
# 其中key为
dic = dict()
# 当前系统的大小
curSize = 0

# 遍历N次，其中每一次操作都对应时间time
for time in range(N):
    ops = input().split()
    # 插入操作
    if ops[0] == "put":
        fileName, fileSize = ops[1], int(ops[2])
        # 如果文件名已经存在，则直接跳过
        if fileName in dic:
            continue
        # 如果文件本身的大小已经超过了最大容量，则直接跳过
        if fileSize > maxSize:
            continue
        # 如果剩余空间不足，则持续删除文件
        while maxSize - curSize             # 优先删除访问次数最少的，其次删除最近一次访问的时间最早的
            delFileName = min(dic.keys(), key=lambda k: (dic[k][0], dic[k][1]))
            delFileSize = dic[delFileName][2]
            del dic[delFileName]
            curSize -= delFileSize

        # 将新文件加入哈希表中，key为文件名，value为[访问次数，最近访问时间，文件大小]所构成的三元组
        dic[fileName] = [0, time, fileSize]
        curSize += fileSize

    # 访问操作
    elif ops[0] == "get":
        fileName = ops[1]
        # 如果文件不位于哈希表中，不做任何操作
        if fileName not in dic:
            continue
        # 该文件的访问次数+1
        dic[fileName][0] += 1
        # 该文件的访问时间更新
        dic[fileName][1] = time


# 操作了N次之后，查看哈希表中剩余哪些文件，排序后输出
ans = sorted(dic.keys())
print(",".join(ans)) if ans else print("NONE")

第二题

题目描述

一个应用启动时，会有多个初始化任务需要执行，并且任务之间有依赖关系，例如 A 任务依赖 B 任务，那么必须在 B 任务执行完成之后，才能开始执行 A 任务。

现在给出多条任务依赖关系的规则，请输入任务的顺序执行序列，规则采用贪婪策略， 即一个任务如果没有依赖的任务，则立刻开始执行，如果同时有多个任务要执行，则根据任务名称字母顺序排序。

例如： B 任务依赖 A 任务， C 任务依赖 A 任务， D 任务依赖 B 任务和 C 任务，同时， D 任务还依赖 E 任务。那么执行任务的顺序由先到后是： A 任务， E 任务， B 任务， C 任务， D 任务。这里 A 和 E 任务都是没有依赖的，立即执行

输入描述

输入参数每个元素都表示任意两个任务之间的依赖关系，输入参数中符号 -> 表示依赖方向，例 A->B 表示 A 依赖 B ，多个依赖之间用单个空格分割

输出描述

输出为排序后的启动任务列表，多个任务之间用单个空格分割

示例一

输入

A->B C->B

输出

B A C

说明

任务 A 和 C 都依赖于任务 B 。任务 B 执行后， A 和 C 立即执行， A 和 C 的执行顺序按照字典序排列。

示例二

输入

    
B->A C->A D->B D->C D->E

输出

A E B C D

解题思路

看到存在依赖关系，立马想到拓扑排序。

本题一个小难点在于如何对同级节点进行排序。

在BFS每一层搜索之前，可以构建一个空数组 nodes_new ，来储存搜索过程中新出现的入度为 0 的节点。这些新出现的这些节点属于拓扑排序中的同级节点，需要在 for 循环结束后进行排序，然后加入到 ans 中。

代码如下

while q:
    nodes_new = list()
    qSize = len(q)
    for _ in range(qSize):
        cur_node = q.popleft()
        for nxt_node in neighbor_dic[cur_node]:
            indegree_dic[nxt_node] -= 1
            if indegree_dic[nxt_node] == 0:
                nodes_new.append(nxt_node)
                q.append(nxt_node)
    nodes_new.sort()
    ans += nodes_new

参考代码

# 公众号：吴师兄学算法
from collections import deque, defaultdict

# 对输入进行分割，得到若干个字符串，每一个字符串包含依赖关系
lst = input().split()
# 构建邻接表
neighbor_dic = defaultdict(list)

# 构建入度哈希表（因为节点名字是字符串而不是数字，因此用哈希表而不是数组）
indegree_dic = defaultdict(int)

# 遍历lst中的每一对依赖关系
for pairs in lst:
    # 根据"->"进行分割，得到节点a和b
    # "a->b"表示节点a依赖于节点b
    # 必须执行节点b之后，才能执行节点a
    a, b = pairs.split("->")
    # a为b的邻居，延长b的邻接节点
    neighbor_dic[b].append(a)
    # 节点a的入度增加
    indegree_dic[a] += 1

# 初始化答案数组，其中入度为0的节点为初始节点，同时根据字典序进行排序
ans = sorted(k for k in neighbor_dic.keys() if indegree_dic[k] == 0)
# 初始化队列，其中队中元素为ans中的元素
q = deque(ans)

# BFS
while q:
    # 初始化一个列表，储存新出现的入度为0的节点
    # 新出现的这些节点，需要在for循环结束后立即执行，加入到ans中
    nodes_new = list()
    # 获得当前层的节点数
    qSize = len(q)
    # 循环qSize次，弹出队列中所有节点
    for _ in range(qSize):
        # 弹出当前队头节点cur_node
        cur_node = q.popleft()
        # 考虑cur_node的所有近邻节点nxt_node
        for nxt_node in neighbor_dic[cur_node]:
            # 近邻nxt_node的入度-1
            indegree_dic[nxt_node] -= 1
            # 如果该近邻节点的入度降为0
            if indegree_dic[nxt_node] == 0:
                # 将其加入nodes_new数组中
                nodes_new.append(nxt_node)
                # 将其加入q中
                q.append(nxt_node)
    # 对nodes_new根据字典序进行排序，然后加在ans后面
    # 表示需要立即执行nodes_new中的节点
    nodes_new.sort()
    ans += nodes_new

print(*ans)

第三题

题目描述

Wonderland是小王居住地一家很受欢迎的游乐园。Wonderland目前有4种售票方式，分别为一日票（1天）、三日票（3天）、周票（7天）和月票（30天）。

times = [1,3,7,30]

每种售票方式的价格将由一个数组给出，每种票据在票面时限内可以无限制的进行游玩。例如，小王在第 10 日买了一张三日票，小王可以在第 10 日、第 11 日和第 12 日进行无限制的游玩。

小王计划在接下来一年内多次游玩该游乐园。小王计划的游玩日期将由一个数组给出。现在，请您根据给出的售票价格数组和小王计划游玩日期数组，返回完成游玩计划所需要的最低消费。

输入描述

输入为 2 个数组：

售票价格数组为 costs ， costs.length = 4 ，默认顺序为一日票、三日票、周票和月票。小王计划游玩日期数组为 days ， 1 ≤ days.length ≤ 365 ， 1 ≤ days[i] ≤ 365 ，默认顺序为升序。