IBM OA 案例分享,包含两道 HackerRank 编程题:筛选高负载时间点,以及通过重连现有链路使所有代码仓库连通。分别考察数组遍历和并查集。
IBM OA 题目解析:高负载统计与链路重连
分享 IBM HackerRank OA 高负载时间点统计与仓库链路重连两道题,包含题图、数组遍历和并查集思路、示例与复杂度分析。

IBM OA 两题解析
T1 先求负载总和,再筛选超过平均值两倍的时间点;T2 统计图的连通分量,在链路数量足够时求最少重连次数。
T1:高负载时间点
题目:给定长度为 n 的服务器负载数组 load,返回所有负载严格大于平均负载两倍的时间点下标。下标从 0 开始,按升序返回;没有符合条件的时间点则返回空列表。 思路:先遍历数组求总和 sum,再按下标顺序遍历。满足 load[i] > 2 × (sum / n) 时记录 i。可以等价判断 load[i] × n > 2 × sum,避免整数除法截断和浮点误差。 示例:load = [1, 2, 9],平均负载为 4,只有下标 2 的负载 9 大于 8,返回 [2]。 边界:恰好等于平均值两倍时不计入。计算总和与乘积时,Java、C++ 等语言应使用 64 位整数,防止溢出。 复杂度:时间 O(n),除返回结果外的额外空间 O(1)。

T2:连接所有代码仓库的最少重连次数
题目:给定 link_nodes 个代码仓库和现有的无向链路。直接或间接连接的仓库视为同步。每次可以移除一条现有链路,并将其连接到另一对仓库。求使所有仓库连通的最少重连次数;无法实现则返回 -1。 思路:记仓库数为 n、链路数为 m。连通 n 个节点至少需要 n - 1 条边,因此 m < n - 1 时直接返回 -1。否则使用并查集处理所有链路,统计连通分量数 c,返回 c - 1。 原理:连接 c 个连通分量至少需要 c - 1 次重连。当总边数足够时,各分量中可移除而不破坏连通性的冗余边足以完成这些连接。 示例:n = 4,链路为 (1, 2)、(1, 3)、(2, 3)。仓库 1、2、3 构成一个连通分量,仓库 4 单独构成另一个分量;将三角形中的一条冗余边改接仓库 4,返回 1。 边界:图已连通时返回 0;重连只能使用现有链路,不能凭空增加边。 复杂度:使用路径压缩和按秩或按大小合并,时间 O(n + m × α(n)),额外空间 O(n)。
