Coding

House robber

Asked at

Goldman Sachs

Google

Infosys

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

A robber is targeting to rob houses from a street. Each house has security measures that alert the police when two adjacent houses are robbed. The houses are arranged in a circular manner, thus the first and last houses are adjacent to each other.

Given an integer array money, where money[i] represents the amount of money that can be looted from the (i+1)th house. Return the maximum amount of money that the robber can loot without alerting the police.

Input: money = [2, 1, 4, 9] Output: 10 Explanation: [2, 1, 4, 9] The underlined houses would give the maximum loot. Note that we cannot loot the 1st and 4th houses together.

Input: money = [1, 5, 2, 1, 6] Output: 11 Explanation: [1, 5, 2, 1, 6] The underlined houses would give the maximum loot.

Input: money = [9, 4, 1, 8]

1 <= money.length <= 105
0 <= money[i] <= 1000

cpp

class Solution {
public:
    int houseRobber(vector<int>& money) {

    }
};

java

class Solution {
    public int houseRobber(int[] money) {

    }
}

python

class Solution:
    def houseRobber(self, money):

javascript

class Solution {
    houseRobber(money) {

    }
}

csharp

class Solution{
    public int HouseRobber(List<int> money) {
     
    }
}

func houseRobber(money []int) int {
    
}

Stuck? Show a way to structure it+

01Observe that a valid solution cannot rob both the first and last houses.
02Solve linear house robber once excluding the last house and once excluding the first.
03Return the larger result, handling the single-house case separately.
04Use the linear recurrence with two rolling states in each case.

Reference answer

Because the houses form a circle, the first and last houses cannot both be selected. Every valid solution therefore belongs to one of two exhaustive cases: rob from indices 0..n-2, or rob from indices 1..n-1. Solve each range with the linear house-robber recurrence. While scanning a range, maintain takeOrSkipCurrent = max(previousBest, value + bestTwoBack), then shift the two running states. Return the larger of the two range answers. If there is only one house, return its value directly because both ranges would otherwise be empty. Each linear pass is O(n) time and O(1) extra space, so the total remains O(n). Simply running the linear recurrence across the entire circular array can illegally select both endpoints.

Then expect these follow-ups

How would you return which houses were robbed?
Tests: reconstruction
Why do the two linear cases cover every valid circular solution?
Tests: case proof

Hiring now

Google has 52 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Small Business Field Sales Representative
Denver, Colorado
Senior Technical Program Manager, Special Projects
Denver, Colorado; Lakewood, Colorado, United States
OSP Engineering Lead, Technical Operations
Denver, Colorado

Or practice this question first

Next question