How should I practice Assign Values?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft online assessment problems in FastPrep.

Is Assign Values associated with Microsoft?

FastPrep tags this as a Microsoft coding interview or online assessment practice problem when the problem catalog has that company context.

FastPrep

Problem · Graph

Assign Values

● MediumMicrosoftFULLTIMEOA

See Microsoft hiring insights

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.

Examples

01 · Example 1

N = 5
A = [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)