Coding

House Robber

Asked at

Amazon

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

Stuck? Show a way to structure it+

01Define take and skip choices at each position
02Use dp[i] = max(dp[i - 1], value[i] + dp[i - 2]) for the linear version
03Initialize empty and one-element inputs explicitly
04Compress to previous two states
05For the circular version, solve the two cases excluding first or last and take the better answer

Reference answer

For the linear House Robber problem, the decision at a house is binary: skip it and keep the best answer through the previous house, or take it and add its value to the best answer two houses back. Therefore dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]). Keep only the last two states for O(1) extra space, and handle empty and one-house inputs before the recurrence. For House Robber II, the first and last houses are adjacent, so no valid solution can take both. Solve two linear ranges, excluding the first and excluding the last, then take the maximum. Do not use the linear recurrence over the whole circle. Test one and two houses, equal values, all zero values, and cases where the endpoints tempt an invalid choice. Time is O(n) and space is O(1) beyond the input.

Then expect these follow-ups

What constraint would change your chosen approach?
Tests: constraint adaptation
How would you test the edge cases before implementation?
Tests: implementation extension

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question