【秋招笔试】09.11华子(海外留学生版)秋招-三语言题解
🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试
💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历
✨ 本系列打算持续跟新
春秋招笔试题
👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸
✨ 笔试合集传送们 -> 🧷春秋招笔试合集
🍒 本专栏已收集
100+
套笔试题,笔试真题
会在第一时间跟新🍄 题面描述等均已改编,如果和你笔试题看到的题面描述不一样请理解,做法和题目本质基本不变。
🍹 感谢各位朋友们的订阅,你们的支持是我们创作的最大动力 💞
🌈 华为秋招(海外留学生版)笔试,来啦!!!
🍥 留学生的题目难度相对于国内来说总体来看会简单一丢丢,但整体题目风格,难度,几乎都是一样的哦~
tips
国内的有些题会复用留学生考过的题目哦,国内机考的朋友可以把留学生的题目也刷一刷1️⃣ 推公式/枚举/二分,这题的做法很多,由于数据比较小,大家怎么做都可以哈
2️⃣ 模拟题,华子最喜欢的阅读理解+模拟,建议大家多练!!!
3️⃣ 力扣原题改编,今年秋招华为出了很多这种力扣的改编题,基本二三两题都是有出处的,大家平时没事可以多刷刷扣子,打打牛客/力扣的周赛。
📊 01.数据中心负载均衡 评测链接🔗
问题描述
LYA 公司运营着一个大型数据中心,该中心包含 个计算节点。每个节点都有特定数量的 CPU 核心和当前负载。不幸的是,一个节点突然宕机,现在需要将其负载均衡地分配到其他节点上。
每个节点的 CPU 核心数为 ,当前负载数为 。一个 CPU 核心的最大负载数为 200,因此节点的总负载容量为 。节点的 CPU 负载率定义为:当前负载数 / 总负载容量。
宕机节点的负载数为 。您的任务是设计一种算法,将这些负载均衡地分配到其他节点上,使得分配后所有节点的 CPU 负载率保持一致。
请注意以下两点:
- 如果宕机节点的负载数超过了所有其他节点的剩余容量总和,则不进行重新分配,每个节点新增的负载数为 0。
- 如果可以进行分配,输入保证最终可以实现完全均衡,即分配后各个计算节点的 CPU 负载率相等,精度不低于 0.001。
输入格式
第一行包含一个整数 ,表示宕机节点的负载数。
第二行包含一个整数 ,表示计算节点的数量。
第三行包含 个整数,表示每个节点的 CPU 核心数 。
第四行包含 个整数,表示每个节点当前的负载数 。
输出格式
输出一行,包含 个整数,表示每个节点应该新增的负载数。
样例输入1
1180
3
45 28 45
6750 4200 6750
样例输出1
450 280 450
样例输入2
500
3
2 2 2
200 300 400
样例输出2
0 0 0
样例解释
样例1 | 宕机节点有 1180 个负载需要迁移。有 3 个计算节点,CPU 核心数分别为 45、28、45,当前负载分别为 6750、4200、6750。分配 450、280、450 个负载后,三个节点的 CPU 负载率均为 0.8。 |
样例2 | 宕机节点有 500 个负载需要迁移。有 3 个计算节点,每个有 2 个核心,当前负载分别为 200、300、400。所有节点总共只能增加 300 个负载,小于 500,因此不进行重新分配。 |
数据范围
题解
二分/推公式/枚举
本题可以二分计算,直接推公式计算,数据范围也比较小,也可以直接枚举计算。
我们这里采用二分来实现
二分步骤:
-
首先,需要判断是否有足够的容量来容纳宕机节点的负载。如果没有,我们就直接返回全 0 的结果。
-
如果有足够的容量,我们就需要找到一个合适的负载率,使得所有节点达到这个负载率后,刚好分配完宕机节点的所有负载。
-
关键点在于如何找到这个合适的负载率。我们可以使用二分查找来解决这个问题。
-
二分查找的下界是当前所有节点的最大负载率,上界是 1(因为负载率不可能超过 1)。
-
对于每个猜测的负载率,我们计算需要分配给每个节点的负载数,然后求和看是否等于宕机节点的负载数。
-
如果和小于宕机节点的负载数,说明猜测的负载率太小;如果和大于宕机节点的负载数,说明猜测的负载率太大。
-
通过不断调整猜测的负载率,我们最终可以找到一个精确到 0.001 的解。
时间复杂度分析:
- 二分查找的次数是 ,也就是 ,是一个常数。
- 每次二分查找中,我们需要遍历所有节点,复杂度为 。
- 因此,总的时间复杂度是 ,对于给定的 ,这个复杂度是完全可以接受的。
参考代码
- Python
def distribute_load(N, K, C, T):
# 检查是否有足够的容量
total_capacity = sum(200 * c - t for c, t in zip(C, T))
if total_capacity < N:
return [0] * K
# 二分查找合适的负载率
left, right = max(t / (200 * c) for c, t in zip(C, T)), 1.0
while right - left > 1e-6:
mid = (left + right) / 2
allocated = sum(max(0, int(200 * c * mid) - t) for c, t in zip(C, T))
if allocated < N:
left = mid
else:
right = mid
# 计算每个节点应该新增的负载数
result = [max(0, int(200 * c * right) - t) for c, t in zip(C, T)]
# 处理可能的舍入误差
diff = N - sum(result)
for i in range(K):
if diff > 0 and result[i] < 200 * C[i] - T[i]:
result[i] += 1
diff -= 1
if diff == 0:
break
return result
# 读取输入
N = int(input())
K = int(input())
C = list(map(int, input().split()))
T = list(map(int, input().split()))
# 计算并输出结果
result = distribute_load(N, K, C, T)
print(*result)
- Java
import java.util.*;
public class Main {
public static int[] distributeLoad(int N, int K, int[] C, int[] T) {
// 检查是否有足够的容量
long totalCapacity = 0;
for (int i = 0; i < K; i++) {
totalCapacity += 200L * C[i] - T[i];
}
if (totalCapacity < N) {
return new int[K];
}
// 二分查找合适的负载率
double left = 0, right = 1.0;
for (int i = 0; i < K; i++) {
left = Math.max(left, (double) T[i] / (200 * C[i]));
}
while (right - left > 1e-6) {
double mid = (left + right) / 2;
long allocated = 0;
for (int i = 0; i < K; i++) {
allocated += Math.max(0, (int)(200 * C[i] * mid) - T[i]);
}
if (allocated < N) {
left = mid;
} else {
right = mid;
}
}
// 计算每个节点应该新增的负载数
int[] result = new int[K];
int sum = 0;
for (int i = 0; i < K; i++) {
result[i] = Math.max(0, (int)(200 * C[i] * right) - T[i]);
sum += result[i];
}
// 处理可能的舍入误差
int diff = N - sum;
for (int i = 0; i < K && diff > 0; i++) {
if (result[i] < 200 * C[i] - T[i]) {
result[i]++;
diff--;
}
}
return result;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int K = scanner.nextInt();
int[] C = new int[K];
int[] T = new int[K];
for (int i = 0; i < K; i++) {
C[i] = scanner.nextInt();
}
for (int i = 0; i < K; i++) {
T[i] = scanner.nextInt();
}
int[] result = distributeLoad(N, K, C, T);
for (int i = 0; i < K; i++) {
System.out.print(result[i] + (i == K - 1 ? "\n" : " "));
}
}
}
- Cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
vector<int> distributeLoad(int N, int K, const vector<int>& C, const vector<int>& T) {
// 检查是否有足够的容量
long long totalCapacity = 0;
for (int i = 0; i < K; ++i) {
totalCapacity += 200LL * C[i] - T[i];
}
if (totalCapacity < N) {
return vector<int>(K, 0);
}
// 二分查找合适的负载率
double left = 0, right = 1.0;
for (int i = 0; i < K; ++i) {
left = max(left, static_cast<double>(T[i]) / (200 * C[i]));
}
while (right - left > 1e-6) {
double mid = (left + right) / 2;
long long allocated = 0;
for (int i = 0; i < K; ++i) {
allocated += max(0, static_cast<int>(200 * C[i] * mid) - T[i]);
}
if (allocated < N) {
left = mid;
} else {
right = mid;
}
}
// 计算每个节点应该新增的负载数
vector<int> result(K);
int sum = 0;
for (int i = 0; i < K; ++i) {
result[i] = max(0, static_cast<int>(200 * C[i] * right) - T[i]);
sum += result[i];
}
// 处理可能的舍入误差
int diff = N - sum;
for (int i = 0; i < K && diff > 0; ++i) {
if (result[i] < 200 * C[i] - T[i]) {
result[i]++;
diff--;
}
}
return result;
}
int main() {
int N, K;
cin >> N >> K;
vector<int> C(K), T(K);
for (int i = 0; i < K; ++i) {
cin >> C[i];
}
for (int i = 0; i < K; ++i) {
cin >> T[i];
}
vector<int> result = distributeLoad(N, K, C, T);
for (int i = 0; i < K; ++i) {
cout << result[i] << (i == K - 1 ? "\n" : " ");
}
return 0;
}
�
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
这里收集了超全的互联网春秋招笔试题,欢迎大家的订阅,会持续跟新的