How should I practice Maximum Sum of a K-Star?

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

Is Maximum Sum of a K-Star associated with Microsoft?

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

Maximum Sum of a K-Star

Microsoft● MediumINTERNOA

Problem statement

An undirected graph has nodes numbered1 through gNodes. Edge i connects gFrom[i] and gTo[i]. Node v has value values[v - 1].

A k-star contains one center and up to k distinct neighbors of that center. The center alone is allowed. Extra edges between selected neighbors do not matter; the chosen star need not be an induced subgraph.

Return the maximum sum of the selected node values. The star must be nonempty. Use a 64-bit result.

Function

bestSumKStar(gNodes: int, gFrom: int[], gTo: int[], values: int[], k: int) → long

Examples

Example 1

gNodes = 5gFrom = [3,3,3,3]gTo = [1,2,4,5]values = [10,20,30,40,50]k = 2return = 120

Choose node3 as the center and nodes4 and5 as its two arms. Their sum is30 + 40 + 50 = 120. Every other center has only node3 as a neighbor, so none gives a larger total.

Constraints

1 <= gNodes <= 200000.
0 <= gFrom.length <= 200000.
gFrom.length equals gTo.length.
values.length equals gNodes.
-10^6 <= values[i] <= 10^6.
0 <= k < gNodes.
Every endpoint integer in gFrom and gTo is between1 and200000.
Edges form a simple undirected graph on IDs1 through gNodes: no self-loops or repeated unordered edges.