Get Minimum Servers
Cisco● HardFULLTIMEOAProblem statement
In a neural network, there are nodes representing servers capturing neural signals in a cutting-edge machine learning application. Akin to the architecture of a neural network, there are server_nodes servers, where the ith server captures the signal of minimum neural activity represented by minActivity[i]. The servers are connected in a tree structure with server_nodes - 1 connections, where the ith connection connects the servers server_from[i] and server_to[i] and the change in neural activity of the signal traveling the ith connection is represented by server_weight[i].
The neural activity of a signal transmitted from server x and reaching server y is the sum of the neural activity change by traveling across the path from x to y.
Note:
- All the servers transmit the signals of activity 0.
- The tree is rooted at server 1.
- It is possible for a signal to have negative neural activity as well.
- The neural activity of a signal after passing through a connection improves or deteriorates, depending on whether the
server_weight[i]is positive or negative respectively.
A server u is said to be vulnerable if there exists a server v (!= u) in the subtree of u such that:
- The neural activity of the signal reaching server
vfrom serveruis greater thanminActivity[v].
Note: A subtree of a node x is a tree containing all the children of x and having x as the root.
The server can be disconnected in the following way:
- Choose a leaf node from the remaining tree and remove that server.
The task is to determine the minimum number of servers that need to be disconnected such that no server remains vulnerable.
Function
getMinServers(server_nodes: int, server_from: int[], server_to: int[], server_weight: int[], minActivity: int[]) → int
Complete the function getMinServers in the editor.
getMinServers has the following parameters:
int server_nodes: the number of serversvector server_from: the server from which the signal is sentvector server_to: the server to which the signal is sentvector server_weight: the change in neural activity due to the signal passing through the servervector minActivity: the minimum neural activity that a server can handle without being vulnerable
Returns
int: the minimum number of servers that need to be disconnected
Examples
Example 1
server_nodes = 5server_from = [1, 1, 3, 3]server_to = [2, 3, 4, 5]server_weight = [-2, 5, -5, -3]minActivity = [0, -10, 5, -5, 5]return = 2
Server 1 is vulnerable as the neural activity of signal reaching server 4 from 1 has an activity of 0(>-5). So server 4 is removed. Server 1 is vulnerable as the neural activity of signal reaching server 2 from 1 has an activity of -2(>-10). So server 2 is removed. Hence, the answer is 2.
Example 2
server_nodes = 4server_from = [1, 1, 2]server_to = [2, 3, 3]server_weight = [3, 4]minActivity = [1, 2, 3, 4]return = 1In this case, you need to disconnect at least one server to ensure no server is vulunerable.
Constraints
- 3 ≤ server_nodes ≤ 2 * 10^5 1 ≤ server_from[i], server_to[i] ≤ server_nodes -10^9 ≤ server_weight[i] ≤ 10^9 -10^9 ≤ minActivity[i] ≤ 10^9