IBM OA

Round 1

Questions: You are given a network of g_nodes data centers connected by g_edges bidirectional connections. The i-th connection connects data centers g_from[i] and g_to[i] with a latency of g_weight[i]. The goal is to divide this network into k or fewer subnetworks by removing some connections such that the maximum latency of the connections in each subnetwork is minimized.

Example: Consider an example with:

g_nodes = 3
g_edges = 3
g_from = [1, 2, 3]
g_to = [2, 3, 1]
g_weight = [4, 5, 3]
k = 2

In this scenario, the optimal solution is to remove 1 - 2 and 2 - 3 to achieve the desired split, resulting in two separate networks with the minimized maximum latency of 3.

Function Description: Parameters:

• g_nodes: An integer representing the number of data centers (nodes).
• g_from: An array of integers representing the starting points of the connections.
• g_to: An array of integers representing the endpoints of the connections.
• g_weight: An array of integers representing the latencies of the respective connections.
• k: An integer representing the maximum number of subnetworks to form.

Returns: The function should return an integer representing the minimum possible value of the maximum latency of the networks formed.

Constraints:

• 2 ≤ g_nodes ≤ 10^4
• 1 ≤ g_edges ≤ 10^5
• 1 ≤ g_from[i], g_to[i] ≤ g_nodes
• 1 ≤ g_weight[i] ≤ 10^9 It is guaranteed that the graph is initially connected.