FastPrep
Problem · Tree

Thread Count (Also for Infra Automation Intern)

Learn this problem
● HardSnowflakeINTERNOA
See Snowflake hiring insights

Problem statement

There are service_nodes microservices connected by bidirectional edges that form a tree. Edge j connects service_from[j] and service_to[j].

Each microservice has a maximum live-thread value. The values of any two adjacent microservices must differ by exactly 1. Some values were lost, and only k values remain known. Each row [i, value] in currentValues fixes the value of microservice i.

Find the live-thread value for every microservice such that all fixed values and adjacency requirements hold and the total sum of values is as small as possible. A valid solution is guaranteed to exist.

Returns: int[] of length service_nodes, where element i is the live-thread value of microservice i + 1.

Function

findMaximumNumberLiveThreads(service_nodes: int, service_from: int[], service_to: int[], k: int, currentValues: int[][]) → int[]

Examples

Example 1

service_nodes = 4service_from = [1, 2, 2]service_to = [2, 3, 4]k = 3currentValues = [[1, 3], [2, 4], [3, 3]]return = [3, 4, 3, 3]

There are four microservices and three edges: (1, 2), (2, 3), and (2, 4).

The known values fix nodes 1, 2, and 3 to 3, 4, and 3. Assigning node 4 the value 3 satisfies the required difference of exactly 1 across every edge and minimizes the total. The result is [3, 4, 3, 3].

Constraints

  • 1 ≤ service_nodes ≤ 10^5
  • 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

More Snowflake problems

drafts saved locally
public int[] findMaximumNumberLiveThreads(int service_nodes, int[] service_from, int[] service_to, int k, int[][] currentValues) {
    // write your code here
}
service_nodes4
service_from[1, 2, 2]
service_to[2, 3, 4]
k3
currentValues[[1, 3], [2, 4], [3, 3]]
expected[3, 4, 3, 3]
checking account