Tag: pattern

CodeFights Solves It: houseRobber

CodeFights Solves It: houseRobber

This week’s Interview Practice Task of the Week is houseRobber, a technical interview question that’s been asked at LinkedIn. In this challenge, we’re asked to assist a robber in stealing from houses. Not something that we recommend you do in real life, of course! We will be looking at an (inefficient) recursive solution and then seeing how we can speed it up using memoization (not a typo!) or dynamic programming.

In this task, we are given an array loot, where loot[i] represents the total value of goods we can take from house i. Each house is connected to its neighbors, so the robber isn’t willing to rob two neighboring houses. This means if we take the loot from house i, houses i-1 and i+1 are off limits! Our task is to write a function houseRobber(loot) that returns the maximum amount of loot the robber can steal given loot.

For example, if loot = [5,10,12,2] then the maximum amount of loot that the robber can take is 17 (stealing 5 from house 0 and 12 from house 2). If we had the same values in a different order such as loot = [5,10,2,12], then the maximum amount the robber can take jumps up to 24 (stealing 10 from house 1 and 12 from house 2).

These examples are a little misleading, however. They suggest that we look at stealing from the even numbered houses, and compare that to what we would get stealing from the odd numbered houses. While stealing from evens or odds will ensure we visit the maximum number of houses, it doesn’t guarantee maximum value. For example:

LinkedIn technical interview question solution
Can’t just look at the even and odd houses!

In the problem we are guaranteed that each house has a non-negative amount of money.

Recursive solution

Let’s start by looking at a few cases. First, we’ll look at a few trivial cases:

  1. If there are no houses (i.e. loot = []) then the robber is out of luck and gets nothing. We return 0.
  2. If there is only one house, then the solution is obvious: take whatever is inside, so we return loot[0].
  3. If there are two houses, then the robber should steal from the house that has the most money, so we should return max(loot[0], loot[1]).

These are called our base cases.

Here comes the magic part: what if we have N houses, where N > 2? Let’s start at the first house: we have to decide whether the robber should rob this house or not. Our two choices are:

  1. Steal from the first house. Then we cannot steal from the second house. The best we will be able to get is the value from this house (loot[0]) plus whatever we can get from house 3 onward (because the second house is off-limits). So our payoff is loot[0] + houseRobber(loot[2:]).
  2. Don’t steal from the first house. Then this problem is identical to ignoring the first house altogether, and evaluating houseRobber(loot[1:]) (ignoring the first house, and solving the same problem from second house).

We should evaluate both choices, and return the larger of the two. Notice that regardless of which step we make, the problem gets smaller on each step. Eventually we’ll end up with 0, 1, or 2 houses in our list, and the base cases will actually evaluate our solution.

Here’s the recursive solution in code:

Running this code passes the first 24 tests, but then times out on test 25.

The problem is for all cases except the base cases, houseRobber calls itself 2 more times. This tells us that we can expect houseRobber to be O(2^N), where N is the number of houses. To see the calls, and to find a possible remedy, let’s walk through what our code is doing for the input loot = [4, 1, 2, 7, 5, 3, 1]. Each node here represents a call to houseRobber with the input in the box. The boxes have been color-coded, so each different input is represented with a different color.

LinkedIn technical interview question solution

One of the things that should jump out at you is that we are evaluating the same function many times. For example, houseRobber([5,3,1]) shown in red is called 5 times! Each time it returns the same value 6 (as robbing the first and the last house gets the most loot from houses with values [5, 3, 1]).

Improving with memoization

To reduce the amount of redundant work we have to do, one technique is to memorize the answer of each calculation as we do it. This is called memoization, as in “to write down the answer on a memo so we can get it later”. (Actually, memoization comes from the Latin “to be remembered”, but that makes it sound like we should be using the term “memorization” instead!) Basically, the first time we encounter a particular input we will store it in a hash table.

We will not call a helper function for two reasons: not to pollute the global namespace with our previously memoized answers, and because we need to convert loot to a tuple (we cannot use lists as keys to a hash table).

When we run this version, it passes all the tests. We can show the tree of calls to _houseRobberRecursive for this new variation. Note there are many fewer calls, as we are able to reuse anything we have already calculated. (It is important to note the left branch of each note is executed first, because of the order we evaluated valueSteal and valueLeave in _houseRobberRecursive).

LinkedIn technical interview question solution
Calls to “_houseRobberRecursive” when using memoization

Dynamic programming solution

We already have a solution, but it’s a little messy. We created a helper function to keep our hash table memo_ans outside of the global namespace, because it would be bad if someone else had also written a function that used memo_ans to store their results.

Notice that memoization started with the full list [4, 1,2, 7, 5, 3, 1] and broke it down to smaller and smaller cases. This is called a top-down approach. Our next approach will be a bottom-up approach, where we start from the small cases and work up to the final solution.

We will introduce an array steal[i], where steal[i] is the best we can do if we are only allowed to steal from the last i+1 houses. If loot = [4, 1, 2, 7, 3, 1] then

  • steal[0] = 1 (if we can only steal from the last house, then the best we can do is taking the last house’s loot)
  • steal[1] = 3 (we can either steal 3 or 1; 3 is clearly better)
  • steal[2] = 8 (given [7,3,1] stealing 7 and 1 is clearly more than just stealing 3).
  • steal[3] = 8 (best we can do from [2,7,3,1])
  • etc.

The answer we actually want is the last element of the steal array.

Remember our magic step for this problem? It was when deciding whether to steal from house i, all we had to do was compare loot[i] + (most you could steal from house i+2 on) and (most your could steal from house i+1 on). But note that steal[i] tells us the best we can do from the last i houses. This suggests we can find steal[i] using the following technique:

This won’t give us steal[0] or steal[1], but these are our base cases. Note how much simpler our code becomes:

This is much tidier, but we can reduce this code even more. Notice that steal[i] depends only on the current value of the loot and the last two values of steal. This means we don’t need to keep an array steal. Instead, we just need to keep track of the last two entries.

Warning: At the moment, we are still going to accomplish our goal of finding the maximum value that our robber could take. If you wanted to be able to produce a list of houses for the robber to pilfer to achieve the maximum, the steal array is incredibly useful. There is a “backtracking” algorithm to reconstruct which houses the robber should steal from. The optimized version below reduces the space complexity of our solution from O(N) to O(1), but at the cost of being able to efficiently reconstruct the list of houses that have been hit.

Our new code is:

So far we have implemented the bottom-up technique literally. We have made our way from the “end of the street” and worked backward. However, all that matters in this problem are which houses are next to each other. There isn’t a reason to reverse the houses. We could consider steal[i] as being the most we could steal from the first i houses (instead of the last i houses). The only reason we did it that way is it’s a little easier to conceptualize “running out of houses” at the end of the list.

We can make our problem look a little more like a standard problem with the following observation: if we initialize oldBest and newBest to zero, and go through every house, then the first pass through the loop sets oldBest and newBest to the correct value. This simplifies our base cases and makes the problem more familiar:

Similar problems

This problem is a recursively defined series in disguise. This is a series where you calculate the next value using the previous values. One of the most famous examples is the Fibonacci numbers:

where the first two numbers are 0 and 1. After the first two numbers, we get the next number by summing the previous two numbers in the sequence. For example, the seventh number in the sequence is 8 because 5 + 3 = 8. The mathematical expression for the Fibonacci numbers F[n] is given by

and where F[0] = 0 and F[1] = 1. This definition leads to a recursive function call:

Because we see each call to fib(n) (except the base cases n=0 and n=1) call fib two more times, we are not surprised to find an O(2^n) running time. We can memoize this function (and this is good practice!), but we can also write an iterative or dynamic programming solution:

Note how similar the program is to houseRobber. Many problems that involve making a choice to explore two different paths, such as rob house i or not, will given rise to these recursive sequences. This is a good pattern to know!

The overall approach:

  1. Usually we are iterating through our problem, and have to decide whether or not to include the current element. In this case our decision was whether or not to rob a house, but in other instances it might be whether or not to pack a certain item, or whether we use a road to get to our destination.
  2. Start by relating this problem to “smaller” instances of the problem. If it helps, write a recursive solution first (although usually these will have bad run times). Usually these smaller instances are related to the different possible choices you could have made. In this case, the smaller instances were “making the best value from the remaining houses”.
  3. Look at how many of the “smaller” instances you have to use to solve the next instance. In this case, we only used the last two instances. This can help you write the solution as an iterative solution.

Tell us…

Have you ever gotten a question like this in a technical interview? What strategy did you take to solve it? Let us know on the CodeFights forum!

CodeFights Explainer: Prefix Sums

CodeFights Explainer: Prefix Sums

Prefix sums, or cumulative sums, allow us to quickly find the sum of any contiguous slice of an array.

As a quick example, suppose you copy down some driving directions. They tell you to drive down Penny Lane for 3 miles, then make a left onto Abbey Road, which we travel down for 5 miles before continuing on Lake Shore Drive for 4 miles, and so on. We convert these directions into the number of miles driven on each road.

The prefix sum for the distances is:

This tells us that it took 3 miles to get to the end of the first direction (Penny Lane), and 8 miles in total to get to the end of the second direction (Abby Road). If we want to know how long it took to get from the end of Abbey Road (mile 8 of our trip) to the end of Sunset Blvd (mile 18), we do one subtraction on prefix_distances rather than two additions on distances:

A useful example of prefix sums would be calculating a moving average of an array, which is designed to remove periodic fluctuations in data. For example, if we knew the amount of money brought in by sales of cookies at the CodeFights Cafe per day, we might get something like:

We might guess there is fluctuation based on the day of the week. (Maybe it’s in an area that slows down over the weekend.) The seven day moving average would contain the average of the first seven values (4,5,8,10,12,0,0), while the next value would be the overlapping average of the next seven values (5,8,10,12,0,0,5). The moving average is:

In order to calculate the moving_ave we can start with the prefix sums:

To get the cookies sold for the first seven days, we can look at prefix_cookies[6]. To get the total number of cookies sold from day 2 to day 8 we can calculate prefix_cookies[7]-prefix_cookies[1]. Once we have the prefix sums, calculating the total number of cookies sold in any seven day period becomes trivial. Once we know the number of cookies sold in a week, we can divide by seven to find the average.

The nice thing about the prefix sums approach to moving averages is that the method is agnostic about the period used to average over. If CodeFights Cafe found that there was a monthly cycle to their cookie sales, it would be easy to use the same array prefix_cookies to average over 30 days instead.

Other applications of prefix sums are:

  • Calculating the average value of blocks of pixels (useful in noise removal).

  • Calculating whether one point is visible from another, given an array of heights (called the line of sight problem).

  • Finding cumulative distributions (for example, working out what percentage of income the top 1% of earners make from an array of incomes).

Maybe more impressive is the fact that prefix sums can be performed in parallel. This leads to some really useful algorithmic tricks.

Parallelizing prefix sums

If we are trying to calculate the prefix sum of an array L , we can give a linear time algorithm. To calculate the prefix[n], simply take:

This algorithm seems simple and fast, but it is also clear that because prefix[n] depends on prefix[n-1] the problem seems embarrassingly serial. That is, it doesn’t seem like we can take a huge array and split it in two, and have each computer calculate half the prefix sum, and then easily join the results together in a way that saves time.

The amazing thing is that there is a parallel algorithm for prefix sum! The method involves passing through the array twice:

  1. Bottom-up
    Takes the array and builds a binary tree from the array, making pairwise sums along the way.
  2. Top-down
    Takes the array of sums, and determines the prefix sums.

Let’s look at how this works with our array of distances, [3,5,4,6,2].

First we build a tree, where each element is a leaf at the bottom. Each node keeps track of the index range it comes from (to help us put results from different processes together), the sum of all the elements in index range, and one other element that we’ll ignore for right now.

Prefix Sums Figure 1
Notice that the sum stored in each node can be obtained by adding the sum of its two children. This means that we can split the job off to different machines, and then combine them at the end. What we end up with at the top node (or root node) is the sum of all the elements in the array.

To get the prefix sums, we will define left for a node with an index range [a,b) to be the sum of all the elements of the array with an index of less than a. In other words, this is the sum of all the elements that appear to the left of the first element included in this node. We start at the root node and make our way down the tree.

Prefix Sums Figure 2
To convince ourselves that we can really construct the left attribute this way, we will concentrate on the red boxed square. Moving from the parent (index = [0,4)) to the left child is easy: Since the left child has the same lower limit, it just copies the left value (0 in this case, because these are the elements that start at the beginning of the array). Moving to the right child (index = [2,4)) takes a little more thought. The right child knows that indices from [2,4) add up to 10 by looking at its own sum attribute. By knowing the sum in the parent element is 18, we can deduce that the sum of all elements with indices less than 2 must be 18 - 10 = 8.

To get the prefix sum requires taking the left element of all the leaves (except the first one, which is trivially zero) and the sum of the entire array.

Prefix Sums Figure 3
so our prefix_distances are found to be:

Key points

  • Prefix sums are interesting in their own right, in terms of just precomputing results and then allowing you to rapidly calculate any contiguous slice of an array.

  • Demonstrates a pattern in computer science of breaking a seemingly serial task into one that can be parallelized. Can be generalized: build up a binary tree, then move down the tree from the top to separate off the contribution from the “left hand side” of the tree.

Tell us…

Have you ever encountered a problem in an interview that you solved using prefix sums? Or better yet, encountered one in real life? Let us know over on the CodeFights forum!

CodeFights Solves It, Interview Practice Edition: productExceptSelf

CodeFights Solves It, Interview Practice Edition: productExceptSelf

If it’s been asked as an interview question at Amazon, LinkedIn, Facebook, Microsoft, AND Apple, you know it’s got to be a good one! Have you solved the challenge productExceptSelf in Interview Practice yet? If not, go give it a shot. Once you’re done, head back here. I’ll walk you through a naive solution, a better solution, and even a few ways to optimize.

…Done? Okay, let’s get into it!

The object of this problem is to calculate the value of a somewhat contrived function. The function productExceptSelf is given two inputs, an array of numbers nums and a modulus m. It should return the sum of all N terms f(nums, i) modulo m, where:

f(nums,i) = nums[0] * nums[1] * .... * nums[i-1] * nums[i+1] * ... * nums[N-1]


We can see this most easily with an example. To calculate productExceptSelf([1,2,3,4],12) we would calculate:

  • f([1,2,3,4], 0 ) = 2*3*4 = 24
  • f([1,2,3,4], 1 ) = 1*3*4 = 12
  • f([1,2,3,4], 2 ) = 1*2*4 = 8
  • f([1,2,3,4], 3 ) = 1*2*3 = 6

The sum of all these numbers is 50, so we should return 50 % 12 = 2.

A naive solution

The explanation of the code suggests an implementation:

This is technically correct, but the execution time is bad. Each call to the function f(nums, i) has to do a scan (and multiplication) in the array, so we know the function is O(N). We call f(nums,i) a total of N times, so this function is O(N2)!

Sure enough, this function passes all the test cases. But it gives us a time length execution error on test case #16, so we have to find a more efficient solution.

Division is a better solution (but still not good enough)

A different way of approaching this problem is to find the product of all the numbers, and then divide by the one you are leaving out. We would have to scan to see if any of the numbers were zero first, as we can run into trouble dividing by zero. Essentially, we’d have to deal with that case separately, but it turns out that any array nums with a zero in it is easy to calculate. (This would be a good extension exercise!)

If we look under the constraints of the code, we are told that 1 <= nums[i], so we don’t have to worry about this case. We can simplify our problem to:

Again, we get a time execution error! Note that the running time is much better. We make a pass through the array once to get productAll, then a pass through the array again to get the f_i, and one more pass through the array to do the sum. That makes this is a O(N) solution!

Why is the interviewer asking this question?

In other words, what is this question testing? As I mentioned in the introduction, the function we’re calculating is a little contrived. Because it doesn’t seem to have any immediate applicability, the companies asking us this question in interviews are probably looking to see if we know a particular technique or trick.

One of the assumptions that I made when calling the algorithms O(N) or O(N2) was that multiplication was a constant time operation. This is a reasonable assumption for small numbers, but even for a computer there is a significant difference between calculating

456 x 434


324834750321321355120958 x 934274724556120

There are a couple of math properties of residues (the technical name for the “remainders” the moduli give us) that we can use. One is:

(a + b + c ) % m is the same as (a % m + b % m + c % m) % m

This is nice because a%m, b%m, and c%m are all small numbers, so adding them is fast.

The other property is:

(a * b) % m is the same as ((a % m) * (b % m)) % m

That is, I can multiply the remainders of a and b after division by m, and the result I get will have the correct remainder.

At first glance, this doesn’t seem to be saving us much time because we’re doing a lot more operations. We are taking the modulus three times per multiplication, instead of just once! But it turns out that the modulus operation is fast. We more than make up for it by only multiplying small numbers.

So we can change our calculation of f_i to

This still isn’t good enough to pass the test, but we’re getting there. The problems we still have are:

  1. The number productAll is still very large
  2. Integer division is (relatively) slow

Our next approach will eliminate both of these problems.

Note: NOT a property

The big number is productAll, so you might hope that we can find productAll % m, and _then_ do the division. This doesn’t work.

The mathematical problem is that non-zero numbers can be multiplied to give 0, so division is problematic. Looking at division, and then taking a modulus:

48 / 6 = 8_ so _(48 / 6) % 12 = 8

but reversing the order (taking the modulus, then doing the division) yields:

(48 % 12) / 6 = 0 / 6 = 0

So we can’t take the modulus of productAll and avoid big numbers altogether.

Prefix products (aka cumulative products)

We can speed up the execution by building by an array, prefixProduct, so that prefixProduct[i] contains the product of the first i-1 numbers in nums. We will leave prefixProduct[0] = 1.

The neat thing about this array is that prefixProduct[i] contains the product of all elements of the array up to i, not including i. If we also made a suffixProduct such that suffixProduct[i] was equal to all the product of all numbers in nums past index position i, then the productExceptSelf for number i would just be the product of all numbers except the ith one = prefixProduct[i] * suffixProduct[i]

We have eliminated one of the costly operations: division! We can also avoid seeing large numbers in the multiplication as well, by changing the step inside the loop to contain a modulus.

Our new solution is:

This finally works! We’ve eliminated all multiplication by big numbers (but still have multiplications by small numbers), and no divisions at all. But we can still do better…

For the technical interview, an even better solution

It turns out that we don’t need to have a suffixProduct. We can build it as we go! This is the accumulator pattern:


The main things you’re being asked to think about in this task are:

  • Arithmetic operations aren’t always constant time. Multiplying big numbers is much slower than multiplying small numbers.
  • Operations are not all the same speed. Integer modulus is very fast, addition and multiplication are fast, while division is (relatively) slow.
  • Some number theory: You can multiply the residues of numbers, instead of the numbers themselves. But you cannot divide by residues, or divide the residues unless you have certain guarantees about divisibility.
  • The idea of precomputing certain operations, which is where the prefixProduct comes in.

Other problems that use the cumulative or prefix techniques are finding the lower and upper quartiles of an array, or finding the equilibrium point of an array. (I cover prefix sums in a lot more detail in this article.)

Footnote: Horner’s Method

One of the solutions presented used a method of calculation known as Horner’s method. Take the cubic

f(x) = 2 x^3 + 3 x^2 + 2 x + 6

To evaluate f(3) naively would require 8 multiplications (every power x^n is n copies of x multiplied together, and then they are multiplied by a coefficient), and three additions. There is a lot of wasted calculation here, because when we calculate x^3 we calculate x^2 in the process! We could store the powers of x separately to reduce the number of multiplications.

Horner’s method is a way of doing this without using additional storage. The idea is, for example, that we can use operator precedence to store numbers for us:

3 x^2 + 2 x + 6 = (3 * x + 2) * x + 6

The left side has a (naive) count of 4 multiplications and 2 additions, while the right side has 2 multiplications and 2 additions. Moving to the cubic is even more dramatic:

f(x) = 2 x^3 + 3x^2 + 2 x + 6 = ( (2 * x + 3) * x + 2 ) * x + 6

This takes our 8 multiplications and 3 additions to only 3 multiplications and 3 additions!

The shortest solution so far, submitted by CodeFighter k_lee, uses Horner’s method, along with taking moduli at the different steps. See if you can decipher it.

Tell us…

Did your solution for this Interview Practice challenge look different than mine? How did you approach the problem? Let us know over on the CodeFights forum!