FastPrep
Problem · Graph

Assign Values

Learn this problem
● MediumMicrosoftFULLTIMEOA
See Microsoft hiring insights

Problem statement

You are given an undirected graph consisting of N vertices, numbered from 1 to N, and M edges. The graph is described by two arrays, A and B, both of length M. A pair (A[K], B[K]), for K from 0 to M-1, describes an edge between vertex A[K] and vertex B[K].

Your task is to assign all values from the range [1..N] to the vertices of the graph, giving one number to each of the vertices. Do it in such a way that the sum over all edges of the values at the edges' endpoints is maximal.

Notice that the value assigned to vertex 5 did not have any effect on the final result as it is not an endpoint of any edge.

Function

assignValues(N: int, A: int[], B: int[]) → int

Examples

Example 1

N = 5A = [2, 2, 1, 2]B = [1, 3, 4, 4]return = 31
In order to obtain the maximum sum of weights, you can assign the following values to the vertices: 3, 5, 2, 4, 1 (to vertices 1, 2, 3, 4, 5 respectively). This way we obtain the sum of values at all edges' endpoints equal to 7 + 8 + 7 + 9 = 31. edge (2, 3): 7 = 5 (vertex 2) + 2 (vertex 3) edge (2, 1): 8 = 5 (vertex 2) + 3 (vertex 1) edge (1, 4): 7 = 3 (vertex 1) + 4 (vertex 4) edge (2, 4): 9 = 5 (vertex 2) + 4 (vertex 4)

More Microsoft problems

drafts saved locally
public int assignValues(int N, int[] A, int[] B) {
  // write your code here
}
N5
A[2, 2, 1, 2]
B[1, 3, 4, 4]
expected31
checking account