FastPrep
Problem · Tree

Get Minimum Servers

Learn this problem
● HardCiscoFULLTIMEOA
See Cisco hiring insights

Problem 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 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

    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 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

    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
    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.

    Example 2

    server_nodes = 4server_from = [1, 1, 2]server_to = [2, 3, 3]server_weight = [3, 4]minActivity = [1, 2, 3, 4]return = 1
    In 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

    More Cisco problems

    drafts saved locally
    public int getMinServers(int server_nodes, int[] server_from, int[] server_to, int[] server_weight, int[] minActivity) {
  // write your code here
}
    server_nodes5
    server_from[1, 1, 3, 3]
    server_to[2, 3, 4, 5]
    server_weight[-2, 5, -5, -3]
    minActivity[0, -10, 5, -5, 5]
    expected2
    checking account