โ† Deutsche Bank questions
CodingReported in a candidate post, Oct 2024

House robber: maximize loot without hitting adjacent houses

Filed under Deutsche Bank

Check for an empty list, zero values, and whether the houses form a line (not a circle).

The question

Houses stand in a line, each holding some money. A thief cannot rob two adjacent houses. Given the amounts, return the maximum total he can rob.

Constraints

  • 0 <= n <= 10^5
  • Amounts are non-negative integers
  • Adjacent houses cannot both be robbed

Examples

Input
[2, 7, 9, 3, 1]
Output
12
Why
Rob houses 1, 3 and 5: 2 + 9 + 1 = 12.
Input
[1, 2, 3, 1]
Output
4
Why
Rob houses 1 and 3: 1 + 3 = 4.

Approach

  1. Check for an empty list, zero values, and whether the houses form a line (not a circle).

Solution

O(n) time, O(1) space

Python
def rob(nums):
    prev, cur = 0, 0  # best loot up to two houses ago / one house ago
    for x in nums:
        prev, cur = cur, max(cur, prev + x)  # skip house, or rob it
    return cur

Tips

  • What they are testing: Turning a choice at each step (rob or skip) into a clean recurrence and then compressing to two variables.
  • Common mistake: Greedily taking the larger of each adjacent pair or alternating houses, which fails on inputs like [2, 1, 1, 2].

Related Deutsche Bank questions

Collected from public candidate posts and coding forums. Updated Nov 2026.