Gone are the days in interviews where programmers are interviewed with questions like “what is an array?” because in most of the interviews now, you can expect questions like “explain minimum subset sum difference” and such complicated problems.
For the tech geniuses out there, we bring this article forth with a tricky interview question: “How to solve the House Robber problem.”
With this detailed guide, you can answer this complex question with not just one but four different solutions. Want to find out those approaches? Then, let’s get straight ahead!
What is a House Robber Problem?
To understand this difficult yet fun problem, here’s a scenario.
Imagine there are 6 houses in the street, all placed next to each other, and there is a robber trying to rob the houses. Now the robber might pick the first house and steal the goods. But will he move to the next house immediately? Mostly not, because it isn’t safe to rob the next house for alarm purposes.
Hence he might skip two houses for a good gap. Why didn’t he pick the third house, though? Simply because he might not be able to get the rich goods in house 4. This is the house robber problem!
Here’s a numerical explanation:
There are 5 houses A, B, C, D, E, and the worth of each house’s goods are
A: 100
B: 20
C: 30
D: 70
E: 40
Now the input of the problem would be
Input: [100,20,30,70,40]
The robber has to steal from the houses with at least two houses skipped, so the output would be
Output: 170
How so? If you add the worth of A and D ( because the robber skips houses B and C), it will be 100 + 70 = 170.
Note: In most of the interviews, when you’re asked this question, you might prefer a dynamic programming method, but the recruiters will want to see you explore other methods too! So choose wisely.
House Robber Problem Solutions
Now that you have got a basic understanding of what this problem is about, how will you solve it? Usually, in interviews, you will be given an array of numbers and asked to find which numbers the robber will rob.
To solve this, here are the solution methods:
Naive Approach
The first method is the basic naive approach which uses the recursion function. Firstly, you should prepare the input array with the digits corresponding to the money in each house.
Then you should calculate the array’s total size. After that, keep base case n < 0 and call a recursive function. If the previous element isn’t chosen, use the current element and run the function. Supposedly, if the previous element is chosen, move past the current element.
Here the time and space complexity would respectively be O(2N) and O(1) since the recursive function takes memory.
Dynamic Programming
Top-Down
In this method, we specifically use the Top-Down technique. While the recursion method helps you out, dynamic programming will execute the answer within a less time.
For this method, first, you should create a dynamic programming vector. That vector should have a size of n+1 and value of – 1. Moreover, you should include pick and pick not variables.
After this, you have to create a recursive call. Once you do the call, there are two possibilities such as:
- If N is less than 0, then the stolen value might be 0.
- If N is greater than 0, then the stolen value is hval [0]
- If the DP of N is DP [n] != – 1, then the value would ultimately be DP [n].
After this, you should allocate the pick variable as pick = hval[n] + maxLoot(hval, n-2, DP)
Moving, you should similarly allocate not pick variable as notPick = maxLoot(hval, n-1, DP)
Finally, arrange DP [n] as max(pick, notPick) and then return the entire DP [n].
Your desired answer would be out and both the time and space complexity would be O (2n).
Bottom-Up
Another method under Dynamic programming would be bottom-up. For this method, the first step is to create an extra array. In it, you will store the sub-problems. This array will be called the DP array.
Next, you should avoid these three cases:
- If the array’s length comes down to 0, you should print the value 0.
- If the length comes to 1, print the element which is first.
- Similarly, if the length is 2, then you print only two elements and not more than that.
Now, change dp [0] to array [0]. Notably, you should change dp [1] to array [0]’s maximum and array [1]. Now traverse the array (from 2nd element) to the array’s end.
For each index, keep upgrading the dp [i] as dp [i-2] + array [i] and dp [i-1]. This is done so that the chosen element alone is selected. Also, if no element is selected, it helps in selecting the previous element. Finally, print the value of dp [n-1]
Your result will come and the time and space taken would be O (n)
Note: In dynamic programming, the space and time complexity will be super high that is why in interviews it is always best to choose another method.
Constant Space Method
In this method, the space and time complexity would be O (n) and O (1), like the naive approach. To practice this method, you should first avoid these three cases similar to the bottom-down approach.
Then, make two variables such as value 1 and value 2. Then, keep:
Value 1 = array [0]
Value 2 = Maximum of array [0] and array [1]
After this, just like the bottom-down method, traverse the array. Once you’re done with it. You should do the following,
For each index, change max_val to the max of value 1 plus array [i] and value 2.
This helps to avoid the previous element if a current element is present. Also, a previous element will be picked if no element is chosen.
Then, for each index, change Value 1 to Value 2 and Value 2 to max_val.
Finally, print the estimate (value) of max_val.
Conclusion
House robber is a problematic question, but with the right method, you can ace it. We hope our guide has helped you to figure out the problem.
If you have any other doubts on questions like merge k-sorted arrays, rod-cutting problems, minimum subset sum difference and such, visit our website and enrich your knowledge.