House Robber Interview Question | Skilled.dev
Interview Question

Steal Packages

Course launching October 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓

THIS NEEDS AN UPDATE. DESCRIBE THE DYNAMIC PROGRAMMING EVEN MORE. Check NOTES.md

In an alternate reality, you decided to use your powers for evil instead of good and started stealing packages. You know exactly how much each package is valued at, so you can walk down the street and pick up the best ones. The only issue is that with all the connected smart homes, if you rob two houses in a row, it will automatically call the police.

Write a function stealPackages that returns maximum amount you can earn without having the police called.

The houses are represented as an array where the items the value of a package at their house. You can't rob any two houses that are next to each other in the array because it will call the police.

const packageValues = [2, 3, 5, 1];
stealPackages(packageValues);
// 7
// You would steal packages at index 0 and 2

const packageValues = [1, 10, 3, 2, 5];
stealPackages(packageValues);
// 15
// You would steal packages at index 1 and 4

Validate My Answer

  1. You can reasonably assume a package values is > 0. It would never be negative because you wouldn't leave money, and zero is just a no-op.

  2. This may seem intimidating at first, but we can simplify it to subproblems. At any point, we only care about adjacent houses. We just need to know if there is a larger max profit by stealing the current house's packages or its adjacent packages.

  3. By using bottom-up dynamic programming, you can solve this in O(n) time and O(1) space.

  4. Make sure your solution handles an array with zero or one item.