Interview Question #1

I was going through some old bookmarks on my computer and found a site of programming teaser questions that were asked of candidates applying at Google.  Being a sucker for these sort of things I checked out the first question:

There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].

Solve it without division operator and in O(n).

I thought about this question for a while and I have to admit that it absolutely stumped me!  In attempt to learn something for this question, we’re going to look at the answer and then examine why this works.

For this example, let’s say we’re given the array [1, 2, 3, 4, 5]; The solution to this problem would then be [120, 60, 40, 30, 24].

The solution is as follows:

  1. Initialize a variable called product, to 1.
  2. Starting at the second element of the array, iterate through the array going forwards.  Multiply the current value of the given array with the product and store that value in the previous element of the results array.
  3. Re-initialize the product variable to 1.
  4. Starting at the last element, Iterate through the elements going backwards. Multiply the current value of the given array with the product and store it in the product variable.
  5. Multiply the current value of the product with the previous element of the results array.

Before we look at any code, let’s work this out.

The first step is trivial, so using the sample given above, let’s examine how we would get to the end result.  Let’s check out what the results array looks like during the second step.

  1. results = [1, 1, 1, 1, 1]   // results[1] = data[0] × product (1)
  2. results = [1, 1, 2, 1, 1]   // results[2] = data[1] × product (1)
  3. results = [1, 1, 2, 6, 1]   // results[3] = data[2] × product (2)
  4. results = [1, 1, 2, 6, 24] // results[4] = data[3] × product (6)

Now, let’s take a look at the value of the product and the results array during step 4.

  1. results = [1, 1, 2, 6, 24] product = 5 (product × 5)
  2. results = [1, 1, 2, 30, 24] product = 20 (product × 4)
  3. results = [1, 1, 40, 30, 24] product = 60 (product × 3)
  4. results = [1, 60, 40, 30, 24] product = 120 (product × 2)
  5. results = [120, 60, 40, 30, 24] product = 120 (product × 1)

Bam! We end up our answer!  Why does this work?  Well, let’s examine the factors of the answer:

results[0] = 5 × 4 × 3 × 2
results[1] = 5 × 4 × 3 × 1
results[2] = 5 × 4 × 2 × 1
results[3] = 5 × 3 × 2 × 1
results[4] = 4 × 3 × 2 × 1

Let’s see how we accumulate those factors in step 2

  1. results = [1, 1, 1, 1, 1]
  2. results = [1, 1, 2 × 1, 1, 1]
  3. results = [1, 1, 2 × 1, 3 × 2 × 1 , 1]
  4. results = [1, 1, 2 × 1, 3 × 2 × 1, 4 x 3 x 2 x 1]

Step 3

  1. results = [1, 1, 2 × 1, 3 × 2 × 1, 4 x 3 x 2 x 1] product = 5
  2. results = [1, 1, 2 × 1, 5 × 3 × 2 × 1, 4 x 3 x 2 x 1] product = 5 × 4
  3. results = [1, 1, 5 × 4 × 2 × 1, 5 × 3 × 2 × 1, 4 x 3 x 2 x 1] product = 5 × 4 × 3
  4. results = [1, 5 × 4 × 3 × 1, 5 × 4 × 2 × 1, 5 × 3 × 2 × 1, 4 x 3 x 2 x 1] product = 5 × 4 × 3 × 2
  5. results = [5 × 4 × 3 × 2 × 1, 5 × 4 × 3 × 1, 5 × 4 × 2 × 1, 5 × 3 × 2 × 1, 4 x 3 x 2 x 1] product = 5 × 4 × 3 × 2 × 1

In step 2, we’re first distributing the factors that appear before the given element in the array. In step 4, the product is distributing the factors that appear after each element as we go back.  Therefore, each element in the results array contains all factors that appear and before the same element in the given array.

Anyway, here’s the code for it:

int[] data = { 1, 2, 3, 4, 5 };
int n = data.length;
int[] results = new int[n];
for (int i = 0; < n; i++) results[i] = 1
// Step 2
for (int i = 0, product = 1; i < n - 1; i++) {
 product *= data[i];
 result[i + 1] = product;
}
// Step 4
for (int i = n - 1, product = 1; i > 0; i--) {
 product *= data[i];
 result[i - 1] *= product;
}

Leave a Reply

Your email address will not be published. Required fields are marked *