House Robber with Selected Indices
Reported by candidates from Google's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The mistake that sinks a first attempt on this Google OA, reported February 2026, is returning the right sum with the wrong indices. It's House Robber with a twist: you also have to rebuild which indices you picked, and the tie rule is strict. Skip on equality. That one rule decides whether your output matches the expected arrays on the zero-heavy cases. The pattern is dynamic programming over a prefix, then a walk backward. If you blank on the reconstruction logic during the live assessment, StealthCoder runs invisibly as a safety net and gives you the working structure in real time.
The problem
Each element of points is the number of points available at one index. Choose any set of indices such that no two chosen indices are adjacent and the sum of their values is as large as possible. Return a ragged long[][] with two rows. Row 0 contains only the maximum sum. Row 1 contains the chosen zero-based indices in increasing order. Use this deterministic tie rule: while reconstructing from right to left using optimal prefix sums, choose index i only when taking it gives a strictly larger sum than skipping it; on equality, skip i. Choosing no index is allowed. Function robWithIndices(points: int[]) → long[][] Examples Example 1 points = [2,7,9,3,1] return = [[12],[0,2,4]] Indices 0, 2, and 4 are non-adjacent and contribute 2 + 9 + 1 = 12. Example 2 points = [2,2] return = [[2],[0]] Either index gives sum 2. At index 1 taking and skipping tie, so the rule skips it and keeps index 0. Example 3 points = [0,0,0] return = [[0],[]] Every take decision ties with skipping, so the deterministic strategy returns the empty selection with maximum sum zero. Constraints 0 <= points.length <= 200000 0 <= points[i] <= 1000000000 The maximum sum must be computed with signed 64-bit arithmetic.
Reported by candidates. Source: FastPrep
Pattern and pitfall
Build dp where dp[i] is the best sum using the first i elements. dp[0] = 0, dp[1] = points[0], and dp[i] = max(dp[i-1], dp[i-2] + points[i-1]). Use long, since 200000 values up to a billion overflow int. Then reconstruct from the right. At index i, take it only if dp[i-2] + points[i] is strictly greater than dp[i-1]. If you take it, jump back two. Otherwise move back one. Reverse the list at the end so the indices are increasing. The common pitfall is using greater-or-equal, which flips Example 2 to [1] instead of [0]. Another is forgetting the empty array, where length is 0 and you return [[0],[]]. Also don't use recursion at 200000 depth. Iterate. StealthCoder is your hedge in the live OA if the backward walk's off-by-one indexing trips you up.
The honest play: practice the pattern, and have StealthCoder ready for the one you didn't see coming.
You can drill House Robber with Selected Indices 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. Built for the candidate who saw this exact problem leak two days before his OA and wondered if anyone had a play.
Get StealthCoderRelated leaked OAs
This OA pattern shows up on LeetCode as house robber. If you have time before the OA, drill that.
You've seen the question.
Make sure you actually pass Google's OA.
Google reuses patterns across OAs. Built for the candidate who saw this exact problem leak two days before his OA and wondered if anyone had a play. Works on HackerRank, CodeSignal, CoderPad, and Karat.
House Robber with Selected Indices FAQ
What's the trick in this House Robber with indices problem?+
Standard prefix DP for the max sum, then a backward walk to recover indices. The trick is the tie rule. Take index i only when dp[i-2] + points[i] is strictly greater than dp[i-1]. On equality, skip. That decides every ambiguous case.
Why does Example 2 return index 0 and not index 1?+
Both indices give sum 2. Reconstructing from the right, taking index 1 ties with skipping it, so the rule skips it. You then land on index 0, where taking it beats an empty prefix. Result is [[2],[0]].
Do I need long for this problem?+
Yes. With up to 200000 elements at up to 1000000000 each, the sum can far exceed the int range. The statement requires signed 64-bit arithmetic. Use long for the dp array and the returned row 0.
How do I handle empty input or all zeros?+
An empty array returns [[0],[]]. All zeros also returns [[0],[]], because every take ties with skip and the rule skips. Make sure your reconstruction doesn't push indices on ties, and that the second row can be empty.
How do I prep for this in 48 hours?+
Write House Robber twice from scratch, then add reconstruction with the strict-greater rule. Test on [2,2], [0,0,0], and an empty array. Use an iterative loop, not recursion, since length can reach 200000. Skip broader topics.