FastPrepFastPrep
Problem Brief

Get Minimum Servers

FULLTIMEOA
See Cisco online assessment and hiring insights

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 v from server u is greater than minActivity[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 Description

    Complete the function getMinServers in the editor.

    getMinServers has the following parameters:

    • int server_nodes: the number of servers
    • vector server_from: the server from which the signal is sent
    • vector server_to: the server to which the signal is sent
    • vector server_weight: the change in neural activity due to the signal passing through the server
    • vector 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

    1Example 1

    Input
    server_nodes = 5, server_from = [1, 1, 3, 3], server_to = [2, 3, 4, 5], server_weight = [-2, 5, -5, -3], minActivity = [0, -10, 5, -5, 5]
    Output
    2
    Explanation
    Example 1 illustration
    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.

    2Example 2

    Input
    server_nodes = 4, server_from = [1, 1, 2], server_to = [2, 3, 3], server_weight = [3, 4], minActivity = [1, 2, 3, 4]
    Output
    1
    Explanation
    In this case, you need to disconnect at least one server to ensure no server is vulunerable.

    Constraints

    Limits and guarantees your solution can rely on.

    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 
    public int getMinServers(int server_nodes, int[] server_from, int[] server_to, int[] server_weight, int[] minActivity) {
  // write your code here
}
    Input

    server_nodes

    5

    server_from

    [1, 1, 3, 3]

    server_to

    [2, 3, 4, 5]

    server_weight

    [-2, 5, -5, -3]

    minActivity

    [0, -10, 5, -5, 5]

    Output

    2

    Sign in to submit your solution.