机试题目

王晨曦2022年1月5日大约 10 分钟

机试题目

API集群负载统计

某个产品的RESTfulAPI集合部署在服务器集群的多个节点上，
近期对客户端访问日志进行了采集，需要统计各个API的访问频次根据热点信息在服务器节点之间做负载均衡，
现在需要实现热点信息统计查询功能。
RESTfulAPI的由多个层级构成，
层级之间使用/连接，如/A/B/C/D这个地址，A属于第一级，B属于第二级，C属于第三级，D属于第四级。
现在负载均衡模块需要知道给定层级的上某个各字出现的频次，未出现过用0次表示，实现这个功能。
输入描述第一行为N，表示访问历史日志的条数，0<N≤100。
接下来N行，每一行为一个RESTfulAPI的URL地址，约束地址中仅包含英文字母和连接符，最大层级为10，每层级字符串最大长度为10。
最后一行是层级L和要查询的关键词。
输出描述输出给定层级上，关键字出现的频次，使用完全匹配方式(大小写敏感)。

anwser

import sys

input_strs = list()

for line in sys.stdin:
    input_str = line.strip()
    if input_str:
        input_strs.append(input_str)

n = int(input_strs[0])
urls = input_strs[1: 1+n]
level_key: str = input_strs[1+n]
level, key = level_key.split()
level = int(level)

source = dict()
for url in urls:
    names = url.split('/')
    for index in range(len(names)):
        name = names[index]
        if name:
            if index in source:
                if name in source[index]:
                    source[index][name] += 1
                else:
                    source[index][name] = 1
            else:
                source[index] = dict()
                source[index][name] = 1

if level not in source:
    print(0)
elif key not in source[level]:
    print(0)
else:
    print(source[level][key])

=======================================================

CPU算力分配

两个算力集群调整

anwser

import sys

def main():
    input_strs = list()

    for line in sys.stdin:
        input_str = line.strip()
        if input_str:
            input_strs.append(input_str)

    A_cpu_cnt, B_cpu_cnt = [int(i) for i in input_strs[0].split()]
    A_cpu_list = [int(i) for i in input_strs[1].split()]
    B_cpu_list = [int(i) for i in input_strs[2].split()]
    A_cpu_list.sort()
    B_cpu_list.sort()

    A_sum = sum(A_cpu_list)
    B_sum = sum(B_cpu_list)

    for a in A_cpu_list:
        for b in B_cpu_list:
            if A_sum + b -a == B_sum + a - b:
                print(a, b)
                return

main()

=======================================================

5G网络建设

现需要在某城市建设5G网络建设，已经选取N个地点设置5G基站，编号固定为1到N，接下来需要哥哥基站之间使用光纤进行连接，
以确保基站能互联互通，不同基站之间架设光纤的成本各不相同，且有些节点之间已经存在光纤连接。
请你设计算法，计算出能联通这些基站的最小成本是多少。
注意：基站的联通具有传递性，入基站A与基站B架设了光纤，基站B与基站C也架设了光纤，
则基站A与基站C视为可以互相联通。
输入描述：
第一行输入标识基站的个数，其中0 < N <= 20
第二行输入表示具备光纤直连条件的基站对的数目M，其中 0 < M < N*(N - 1) / 2  
从第三行开始连续输入M行数据，格式为 X Y Z P，
其中X Y 表示基站的编号， 0 < X <= N, 0 < Y <= N , X != Y ,
Z 表示 X Y之间架设光纤的成本， 其中 0 < Z <= 100, 
P 表示是否已经存在光纤连接， 0表示未连接，1表示已连接

输出描述：
如果给定条件，可以建设成功互联互通的5G网络, 则输出最小的建设成本
如果给定条件，无法建设成功互联互通的5G网络，则输出-1

anwser

class Edge:
    # 定义边的类
    def __init__(self, u, v, cost, pre):
        self.u = u  # 基站u
        self.v = v  # 基站v
        self.cost = cost  # 架设光纤的成本
        self.pre = pre  # 是否已存在光纤连接

def find(x):
    # 并查集查找函数，用于查找x所在的集合
    if parent[x] != x:
        # 如果x不是自己的父节点，那么就让x的父节点为x的父节点的父节点（路径压缩）
        parent[x] = find(parent[x])
    return parent[x]  # 返回x的父节点

def union(x, y):
    # 并查集合并函数，用于合并x和y所在的集合
    rootX = find(x)  # 找到x的根节点
    rootY = find(y)  # 找到y的根节点
    if rootX != rootY:
        # 如果x和y的根节点不同，那么就将x的根节点的父节点设为y的根节点
        parent[rootX] = rootY

def main(): 
    input_strs = list()

    for line in sys.stdin:
        input_str = line.strip()
        if input_str:
            input_strs.append(input_str)
    
    N = int(input_strs[0])
    M = int(input_strs[1])
    parent = list(range(N + 1 ))
    edges = list()

    M_ones = input_strs[2:2+M]

    for one in M_ones: 
        X, Y, Z, P = map(int, one.split())  # 输入基站X, Y, 架设光纤的成本Z, 是否已存在光纤连接P
        edges.append(Edge(X, Y, Z, P))  # 添加边
        if P == 1:  # 如果已存在光纤连接，那么就将X和Y合并
            union(X, Y)
                # 将所有的边按照成本从小到大排序

    edges.sort(key=lambda edge: edge.cost)
    cost = 0  # 总的成本
    
    for edge in edges:
        # 如果边的两个端点不在同一个集合中，那么就将这条边添加到最小生成树中
        if find(edge.u) != find(edge.v):
            cost += edge.cost  # 累加成本
            union(edge.u, edge.v)  # 合并边的两个端点所在的集合
    
    for i in range(2, N + 1):
        # 检查所有的基站是否都在同一个集合中
        if find(i) != find(1):
            # 如果有基站不在同一个集合中，那么就输出-1并结束程序
            print(-1)
            break
    else:
        # 输出总的成本
        print(cost)


if __name__ == "__main__":
    N = int(input())  # 输入基站的个数
    M = int(input())  # 输入具备光纤直连条件的基站对的数目
    parent = [i for i in range(N + 1)]  # 初始化并查集数组，初始时每个节点的父节点就是自己
    edges = []  # 存储所有的边
    
    for _ in range(M):
        X, Y, Z, P = map(int, input().split())  # 输入基站X, Y, 架设光纤的成本Z, 是否已存在光纤连接P
        edges.append(Edge(X, Y, Z, P))  # 添加边
        if P == 1:  # 如果已存在光纤连接，那么就将X和Y合并
            union(X, Y)
    
    # 将所有的边按照成本从小到大排序
    edges.sort(key=lambda edge: edge.cost)
    cost = 0  # 总的成本
    
    for edge in edges:
        # 如果边的两个端点不在同一个集合中，那么就将这条边添加到最小生成树中
        if find(edge.u) != find(edge.v):
            cost += edge.cost  # 累加成本
            union(edge.u, edge.v)  # 合并边的两个端点所在的集合
    
    for i in range(2, N + 1):
        # 检查所有的基站是否都在同一个集合中
        if find(i) != find(1):
            # 如果有基站不在同一个集合中，那么就输出-1并结束程序
            print(-1)
            break
    else:
        # 输出总的成本
        print(cost)

class Edge:
    # 定义边的类
    def __init__(self, u, v, cost, pre):
        self.u = u  # 基站u
        self.v = v  # 基站v
        self.cost = cost  # 架设光纤的成本
        self.pre = pre  # 是否已存在光纤连接

def find(x):
    # 并查集查找函数，用于查找x所在的集合
    if parent[x] != x:
        # 如果x不是自己的父节点，那么就让x的父节点为x的父节点的父节点（路径压缩）
        parent[x] = find(parent[x])
    return parent[x]  # 返回x的父节点

def union(x, y):
    # 并查集合并函数，用于合并x和y所在的集合
    rootX = find(x)  # 找到x的根节点
    rootY = find(y)  # 找到y的根节点
    if rootX != rootY:
        # 如果x和y的根节点不同，那么就将x的根节点的父节点设为y的根节点
        parent[rootX] = rootY

def main(): 
    input_strs = list()

    for line in sys.stdin:
        input_str = line.strip()
        if input_str:
            input_strs.append(input_str)
    
    N = int(input_strs[0])
    M = int(input_strs[1])
    parent = list(range(N + 1 ))
    edges = list()

    M_ones = input_strs[2:2+M]

    for one in M_ones: 
        X, Y, Z, P = map(int, one.split())
        edges.append(Edge(X, Y, Z, P))  
        if P == 1: 
            union(X, Y)
                
    edges.sort(key=lambda edge: edge.cost)
    cost = 0 
    
    for edge in edges:
        if find(edge.u) != find(edge.v):
            cost += edge.cost
            union(edge.u, edge.v) 
    
    for i in range(2, N + 1):
        if find(i) != find(1):
            print(-1)
            return
    
    print(cost)
    return


if __name__ == "__main__":
    main()

=======================================================

wonderland游乐场

题目描述

Wonderland是小王居住地一家很受欢迎的游乐园。

Wonderland目前有4种售票方式，分别为

·一日票(1天)、

·三日票(3天)、

·周票(7天)

·月票(30天)。

每种售票方式的价格由一个数组给出，每种票据在票面时限内可以无限制地进行游玩。例如:

小王在第10日买了一张三日票，小王可以在第10日、第11日和第12日进行无限制地游玩。

小王计划在接下来一年多次游玩该游乐园。小王计划地游玩日期将由一个数组给出。

现在，请您根据给出地售票价格数组和小王计划游玩日期数组，返回游玩计划所需要地最低消费。

输入描述

输入为2个数组:

·售票价格数组为costs，costs.length = 4，默认顺序为一日票、三日票、周票和月票。

·小王计划游玩日期数组为days，1≤days.length≤365，1≤days[i]≤365，默认顺序为升序。

输出描述

完成游玩计划的最低消费。

anwser

def mincostTickets(costs, days):
    # 找到days数组中的最大值，确定旅游的最后一天
    maxDay = max(days)
    # 创建一个长度为maxDay+1的布尔数组，用于标记每一天是否需要游玩
    travelDays = [False] * (maxDay + 1)
    for day in days:
        travelDays[day] = True

    # 创建一个长度为maxDay+1的整数数组，用于保存每一天的最低消费
    dp = [0] * (maxDay + 1)
    for i in range(1, maxDay + 1):
        # 如果这一天不需要游玩，那么这一天的最低消费就和前一天的最低消费相同
        if not travelDays[i]:
            dp[i] = dp[i - 1]
            continue

        # 计算购买各种票后的消费
        cost1 = dp[max(0, i - 1)] + costs[0]  # 购买1天的票
        cost3 = dp[max(0, i - 3)] + costs[1]  # 购买3天的票
        cost7 = dp[max(0, i - 7)] + costs[2]  # 购买7天的票
        cost30 = dp[max(0, i - 30)] + costs[3]  # 购买30天的票

        # 这一天的最低消费就是购买各种票后消费的最小值
        dp[i] = min(cost1, cost3, cost7, cost30)

    # 返回最后一天的最低消费，即为完成整个游玩计划的最低消费
    return dp[maxDay]


costs = list(map(int, input().split()))
days = list(map(int, input().split()))

print(mincostTickets(costs, days))

=======================================================

查找接口成功率，最优时间段


题目描述

服务之间交换的接口成功率作为服务调用关键质量特性，
某个时间段内的接口失败率使用一个数组表示，数组中每个元素都是单位时间内失败率数值，
数组中的数值为0~100的整数 给定一个数值(minAverageLost)表示个时间段内平均失败率容忍值，
即平均失败率小于等于minAverageLost找出数组中最长时间段，如果未找到则直接返回NULL。 
输入描述 
输入有两行内容，
第一行为{minAverageLost},
第二行为{数组}，数组元素通过空格(" “)分隔，minAverageLost及数组中元素取值范围为0~100的整数，
数组元素的个数不会超过100个。 

输出描述 
找出平均值小于等于minAverageLost的最长时间段，输出数组下标对，
格式{beginIndex}-{endIndex}(下标从0开始)，如果同时存在多个最长时间段，
则输出多个下标对且下标对之间使用空格(” ")拼接，多个下标对接下标从小到大排序。

anwser


# 双下标 双循环嵌套 ? 应该既可以?

# 容忍的平均失败率
toleratedAverageLoss = int(input())

# 读取失败率数组
failureRates = list(map(int, input().split()))

arrayLength = len(failureRates)

# 创建一个累积和数组，用于快速计算任意时间段的失败率总和
cumulativeSum = [0] * arrayLength
cumulativeSum[0] = failureRates[0] 
for i in range(1, arrayLength):
    cumulativeSum[i] = cumulativeSum[i - 1] + failureRates[i]

# 存储满足条件的时间段的开始和结束索引
validPeriods = []
maxLength = 0
for start in range(arrayLength):
    for end in range(start, arrayLength):
        sum = cumulativeSum[end] if start == 0 else cumulativeSum[end] - cumulativeSum[start - 1]
        length = end - start + 1
        toleratedLoss = length * toleratedAverageLoss

        # 如果这个时间段的平均失败率小于等于容忍的平均失败率
        if sum <= toleratedLoss:
            # 如果这个时间段比之前找到的时间段更长，清空结果列表并添加这个时间段
            if length > maxLength:
                validPeriods = []
                validPeriods.append((start, end))
                maxLength = length
            # 如果这个时间段和之前找到的最长时间段一样长，添加这个时间段
            elif length == maxLength:
                validPeriods.append((start, end))

# 如果没有找到满足条件的时间段，输出"NULL"
if len(validPeriods) == 0:
    print("NULL")
# 否则，输出所有满足条件的时间段
else:
    validPeriods.sort()

    print(' '.join(f'{start}-{end}' for start, end in validPeriods))