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.
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.