Maximum Star Sum of a Graph

Maximum Star Sum of a Graph

1. What is this problem about?

The Maximum Star Sum of a Graph coding problem asks you to find the maximum possible "star sum" of a node in a graph. A star graph consists of a center node and at most k of its neighbors. The "star sum" is the sum of the value of the center node plus the values of its chosen neighbors. You want to pick the neighbors that have the highest positive values to maximize the sum.

2. Why is this asked in interviews?

Amazon and Google ask this to test a candidate's understanding of graph representation (adjacency lists) and greedy selection. It requires you to iterate through each node, treat it as a potential center, and quickly find its best neighbors. It evaluates your ability to handle basic graph data structures and sorting or priority queues efficiently.

3. Algorithmic pattern used

This problem follows the Graph, Sorting, and Greedy interview pattern. First, build an adjacency list where each node stores the values of its neighbors. Then, for each node:

1. Sort its neighbors' values in descending order.
2. Take at most k neighbors, but only if their values are positive (adding a negative value would decrease the star sum).
3. The sum of the node's value and these top neighbors is the star sum for this node. Keep track of the global maximum star sum found.

4. Example explanation

Node 1 (val 10) connected to: Node 2 (val 5), Node 3 (val -2), Node 4 (val 8). k = 2.

1. Neighbor values for Node 1: [5, -2, 8].
2. Sort descending: [8, 5, -2].
3. Pick at most k=2 neighbors that are > 0: [8, 5].
4. Star sum for Node 1: 10 + 8 + 5 = 23. Star sum for other nodes would be calculated similarly.

5. Common mistakes candidates make

A common error is including neighbors with negative values, which reduces the total sum. Another mistake is forgetting that the "center" node's value can be negative, and the star sum might just be the value of a single node if all neighbors are negative or k=0. Candidates also sometimes fail to efficiently sort neighbors, which is fine if k is small but can be optimized with a Max-Heap if needed.

6. Interview preparation tip

In "Graph, Greedy interview pattern" problems, the choice for one node often doesn't affect another. This allows you to solve for each node independently. Always clarify if the neighbors' values are stored on the nodes or the edges, as this changes the adjacency list implementation.