FastPrepFastPrep
Problem Brief

Thread Count (Also for Infra Automation Intern)

INTERNOA
See Snowflake online assessment and hiring insights

There are service_nodes of different micro-services in a system with bidirectional connections in the form of a tree, where the ith edge connects the micro-service service_from[j] and service_to[j]. Each micro-service is configured with a maximum number of live threads that can be present in its lifecycle, where the ith micro-service can have a maximum of threads[j] threads. The micro-services adjacent to each other must have maximum threads differing by exactly 1. Some configurations were lost, and only k of the micro-services are known. This information is given as a 2D array, currentValues, of size k x 2 denoting [micro-service index, maximum threads], or, [i, threads[i]].

Find the maximum number of live threads that each micro-service can have such that the total number of live threads in the system is the minimum possible. Return an array of length service_nodes where the ith element denotes the maximum number of live threads for the ith micro-service.

Note: It is guaranteed that the solution always exists.

1Example 1

Input
service_nodes = 5, service_from = [1, 2, 3], service_to = [2, 3, 4], k = 3, currentValues = [[1, 3], [2, 4], [3, 3]]
Output
[3, 4, 3, 3]
Explanation
Example 1 illustration
There are 4 micro-services, and 3 edges: {1, 2}, {2, 3}, and {2, 4}. There are 3 configurations left: 1, 2, and 3 with value 3, 4, and 3 respectively on them. The initial configuration is [3, 4, 3, 3], with the maixmum live threads on adjacent micro-services differing by exactly one.

Constraints

Limits and guarantees your solution can rely on.

  • 1 ≤ service_nodes ≤ 10^6
  • 1 ≤ service_from[i], service_to[i] ≤ service_nodes
  • 1 ≤ k ≤ service_nodes
  • 1 ≤ currentValues[i][0] ≤ service_nodes
  • 1 ≤ currentValues[i][1] ≤ 10^6
    • public int[] findMaximumNumberLiveThreads(int service_nodes, int[] service_from, int[] service_to, int k, int[][] currentValues) {
    // write your code here
}
    Input

    service_nodes

    5

    service_from

    [1, 2, 3]

    service_to

    [2, 3, 4]

    k

    3

    currentValues

    [[1, 3], [2, 4], [3, 3]]

    Output

    [3, 4, 3, 3]

    Sign in to submit your solution.