Maximum K-Star Sum
Reported by candidates from Akuna Capital's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The Akuna Capital OA reported in July 2026 dresses up as a graph problem, but there's no traversal in it. Maximum K-Star Sum reduces to a per-node greedy pick. For each node as the center, you take its value plus the best k neighbor values, and you only add neighbors that help. You've got an invite and a clock, so here's the shape. If you blank on the live assessment, StealthCoder runs invisibly as a safety net and hands you the approach in real time.
The problem
You are given an undirected graph with g_nodes nodes and g_edges edges, together with an integer k. The nodes are numbered from 1 to g_nodes. Edge i connects g_from[i] and g_to[i]. A k-star is a non-empty subgraph that forms a star: one selected node is the center, and every other selected node is directly connected to that center. The star may have at most k arms. Node i has value values[i - 1]. The sum of a k-star is the sum of the values of all nodes in the subgraph. The illustration accompanying the example shows valid stars with 3 through 6 arms. The orange node is the center, every blue node is an arm, and every line is an edge. A k-star does not need to have exactly k arms; k is only the upper limit. Find the maximum possible sum of a k-star. Function getMaximumSumKStar(g_nodes: int, g_from: int[], g_to: int[], values: int[], k: int) → int Examples Example 1 g_nodes = 5 g_from = [3,3,3,3] g_to = [1,2,4,5] values = [10,20,30,40,50] k = 2 return = 120 The graph is a star centered on node 3. With k = 2, choose node 3 as the center and nodes 4 and 5 as its arms. Their values sum to 30 + 40 + 50 = 120, which is the maximum. Constraints 1 <= values.length = g_nodes. g_from.length = g_to.length = g_edges. Every edge joins two valid, distinct node numbers from 1 through g_nodes. The graph is undirected and has no duplicate edges. 0 <= k.
Reported by candidates. Source: FastPrep
Pattern and pitfall
Treat every node as a potential center. Build an adjacency list of neighbor values. For each center, sort the neighbor values descending, then add the top k, but stop at non-positive values. Values can be negative, so a star with zero arms is valid and k is only a cap. That's the main pitfall: blindly summing k neighbors tanks the answer. Also handle k = 0, where the answer is the best single node value, and isolated nodes. Track the max across all centers. Sorting each list costs O(deg log deg), so the total is O(E log E), fine for large inputs. A min-heap of size k works too, but sorting is simpler and less bug-prone. Watch for 1-indexed nodes versus the 0-indexed values array. If you freeze on the indexing or the negative-value case during the live OA, StealthCoder is the hedge that catches it.
Drill it cold or hedge it with StealthCoder. Either way, don't walk into the OA hoping you remember the trick.
You can drill Maximum K-Star Sum cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Made for the candidate who got the OA invite this morning and has 72 hours, not six months.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Akuna Capital's OA.
Akuna Capital reuses patterns across OAs. Made for the candidate who got the OA invite this morning and has 72 hours, not six months. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Maximum K-Star Sum FAQ
What's the trick in Maximum K-Star Sum?+
Every node is a candidate center. For each one, add its own value plus the largest neighbor values, up to k of them, skipping any that are negative or zero. Take the max over all centers. No DFS or BFS is needed, just adjacency lists and a sort.
How hard is this Akuna Capital OA question really?+
Easier than it looks. The graph wording and the star illustration scare people, but it's a greedy per-node computation. The traps are negative values, k = 0, and 1-indexed node numbers against a 0-indexed values array.
Do I have to use exactly k arms?+
No. The problem says k is only an upper limit. A star can have fewer arms, even zero, in which case the sum is just the center's value. Only add a neighbor when its value is positive, otherwise it lowers your total.
What's the time complexity I should aim for?+
O(N + E log E) works. Build adjacency lists of neighbor values in O(E), then sort each list descending and sum the top positive k. Total list length is 2E, so sorting everything stays within E log E. A size-k heap is an alternative.
How do I prepare for this in 48 hours?+
Write the solution once from scratch. Cover a tiny graph, an isolated node, k = 0, and all-negative values. Test the sample where node 3 is the center and the answer is 120. Practice converting 1-indexed edges to 0-indexed values cleanly, since that's where bugs hide.