4.5 of 5
www.facebook.com Menlo Park, CA 5000+ Employees

I interviewed in Palo Alto, CA and was asked:
"You are trying to rob houses on a street. Each house has some +ve amount of cash. Your goal is to rob houses such that you maximize the total robbed amount. The constraint is once you rob a house you cannot rob a house adjascent to that house."

Part of a Software Engineer Interview Review - one of 1,061 Facebook Interview Reviews

0
of 1
vote
Not that difficult to answer. You need to keep track of houses that are marked robbed. You can do some sort of recursion and at everys step evaluate sequence of 3 houses. At each step either you can add the middle house or the two adjascent houses to rob list (provided they are OK to rob.) The cumulative return would be the value of the immediate houses and the value returned by the function when called recursively on the remainder of the houses with the current houses marked robbed. I probably should just paste code here. Explaining it in word is twisted.

My complain is I was given all of 2 minutes to think about the question and all of 5-7 minutes to write code for it. I was asked this in 38th minute of a 45 minute interview.
- Interview Candidate on Oct 19, 2010 Flag Response
4
of 8
this is actually a typical dynamic programming question:

int getMaxValue(int[] values) {
if (values.length < 3)
return max(values[0], values[values.length - 1]);
int[] best = new int[values.length];
best[0] = values[0];
best[1] = values[1];
best[2] = values[0] + values[2];
for (int i = 3; i < values.length; i++) {
best[i] = max(best[i - 3], best[i - 2]) + values[i];
}
return max(best[best.length - 2], best[best.length - 1]);
}
- Anthony on Nov 4, 2010 Flag Response
1
of 6
It is a dp problem and it is typical, but your solution is incorrect.
- Endymion on Nov 16, 2010 Flag Response
2
of 3
public static int maxRob(int[] amount){

return maxAmount(amount, amount.length-1);
}

public static int maxAmount(int[] amount, int house){
if(house<=1){
return amount[house];
}

return Math.max(amount[house]+ maxAmount(amount, house-2), maxAmount(amount, house-1));

}
- Anonymous on Nov 22, 2010 Flag Response
0
of 2
Here is the working solution!!

static public int maxRob(int[] housePoints){
int length = housePoints.length;

switch(length){
case 0: return 0;
case 1: return housePoints[0];
case 2: return Math.max(housePoints[0],housePoints[1]);
}

Hashtable<Integer,ArrayList<Integer>> prev, best = new Hashtable<Integer,ArrayList<Integer>>(3);
ArrayList<Integer> scores = new ArrayList<Integer>(1);
best.put(0,scores);
scores = new ArrayList<Integer>(1);
best.put(1,scores);
scores = new ArrayList<Integer>(1);
best.put(2,scores);
for(int i=3;i<length;i++){
prev = best;
best = new Hashtable<Integer,ArrayList<Integer>>(3);
best.put(i-1,prev.get(i-1));
best.put(i-2,prev.get(i-2));
int tmp = housePoints[i];
scores = new ArrayList<Integer>();
best.put(i,scores);
prev = null;
}

int max = 0;
for(int sc : best.get(length-2)) if(sc>max) max = sc;
for(int sc : best.get(length-1)) if(sc>max) max = sc;
return max;
}
- Hee on Nov 29, 2010 Flag Response
1
of 3
public int maxRob(int[] W) {
int sz = W.length;
int[] V = new V[sz];
if(sz == 0) {
return 0;
} else if(sz == 1) {
return W[0];
} else if(sz == 2) {
return max(W[0], W[1]);
}
V[0] = W[0];
V[1] = max(V[0], W[1]);
for(int i = 2; i < sz; i++) {
V[i] = max(W[i] + V[i-2], V[i-1]);
}

return V[sz];
}
- Viet Nguyen on Dec 28, 2010 Flag Response
1
of 3
1. We need an int array same size as house values array to keep track of dp local results.
2. We need the local results to construct path, i.e., which houses we want to rob.
Here's Java code with unittest
/*
* MaxRob(n) = Max(MaxRob(n-2)+value(n), MaxRob(n-1))
*/
public class RobHouse {
public static void MaxRob(int[] values) {
if (values.length==0) {
return;
}
if (values.length==1) {
System.out.println("only 1 house to rob. Value: " + values[0]);
return;
}
if (values.length==2) {
System.out.println("only 1 house to rob. Value: " + Math.max(values[0],values[1]));
return;
}

int[] maxValues = new int[values.length];
maxValues[0] = values[0];
for (int i=1; i<values.length; i++) {
maxValues[i] = Math.max((i<2?0:maxValues[i-2]) + values[i], maxValues[i-1]);
}
//construct path
for (int i=values.length-1; i>0; i--) {
if (maxValues[i]!=maxValues[i-1]){
System.out.println("Rob house " + i + " value: " + values[i]);
}
}
if (maxValues[0]==maxValues[1]){
System.out.println("Rob house 0 value: " + values[0]);
}
System.out.println("Rob done.");
}

public static void main(String[] args) {
MaxRob(new int[] {5,2,4,1});//1010
MaxRob(new int[] {5,2,9,1});//1010
MaxRob(new int[] {1,2,1,1});//0101
}
}
- cindiana on Apr 23, 2011 Flag Response
1
of 2
If I were interviewer, I would give no hire for everyone above - Only Hee solution above is correct (but waaay overcomplicated).
When writing code consider: 1,3,1,3,100
- ZZ on Jun 4, 2011 Flag Response
0
of 3
- randm on Jul 10, 2011 Flag Response
1
of 1
vote
solve(0,0)

//previous indicate whether previous house was looted or not
solve(int house, bool previous)
{
if(house == N) return 0;
int &res = dp[house][previous];
if(res != -1) return res;

int res = solve(house+1, 0);

if(!previous)
res = max(res, cash[house]+ solve(house+1, 1));

return res;
}
- cmu on Sep 5, 2011 Flag Response
0
of 0
A set of data:
input:
4
4 3 5 9
output:
13

input:
10
4 3 5 9 2 6 8 1 10 7
output:
31

input:
100
46 62 74 1 88 77 69 92 67 16 83 79 25 22 56 34 14 91 58 64 65 66 89 75 5 17 51 78 8 47 52 41 81 96 95 28 33 35 4 85 70 9 63 7 27 36 71 48 43 94 80 60 26 13 50 90 10 20 39 55 15 49 23 82 29 57 73 68 59 31 18 97 40 93 100 54 38 44 2 84 37 45 99 98 21 86 24 53 3 61 42 6 19 12 30 72 87 76 11 32
output:
2895
- Tom on Mar 1, 2012 Flag Response
0
of 0
public class Solution {
public int findMax(int[] houses) {
if (houses == null || houses.length == 0) {
return 0;
} else if (houses.length == 1) {
return houses[0];
} else if (houses.length == 2) {
return Math.max(houses[0], houses[1]);
}

int[] res = new int[houses.length];
res[0] = houses[0];
res[1] = Math.max(houses[0], houses[1]);

int max = res[1];

for (int i = 2; i < houses.length; i++) {
res[i] = Math.max(res[i - 2] + houses[i], res[i - 1]);

if (res[i] > max) {
max = res[i];
}
}

return max;
}
}
- w1uo0 on May 20, 2012 Flag Response
0
of 0
public static int rob (int[] amounts) {
if (amounts == null) return 0;
int[] max = new int[amounts.length];
max[0] = amounts[0];
max[1] = Math.max(amounts[0], amounts[1]);
for (int i = 2; i < amounts.length; i++) {
max[i] = Math.max(max[i-2] + amounts[i], max[i-1]);
}
return max[max.length - 1];
}
- baibingz on Oct 30, 2012 Flag Response