Array whose values are the product of every other integer

Question

I was asked the following interview question over the phone:

Given an array of integers, produce an array whose values are the product of every other integer excluding the current index.

Example:

[4, 3, 2, 8] -> [3*2*8, 4*2*8, 4*3*8, 4*3*2] -> [48, 64, 96, 24]

and I gave the following answer

import java.math.BigInteger;
import java.util.Arrays;

public class ProductOfAnArray {

    public static void main(String[] args) {

        try {
            System.out.println(Arrays.toString(ProductOfAnArray
                    .calcArray(new int[] { 4, 3, 2, 8 })));
            System.out.println(Arrays.toString(ProductOfAnArray
                    .calcArray(new int[] { 4, 0, 2, 8 })));
            System.out.println(Arrays.toString(ProductOfAnArray
                    .calcArray(new int[] { 4, 0, 2, 0 })));
            System.out.println(Arrays.toString(ProductOfAnArray
                    .calcArray(new int[] {})));
            System.out
                    .println(Arrays.toString(ProductOfAnArray
                            .calcArray(new int[] { 4, 3, 2, 8, 3, 2, 4, 6, 7,
                                    3, 2, 4 })));
            System.out
                    .println(Arrays.toString(ProductOfAnArray
                            .calcArray(new int[] { 4, 3, 2, 8, 3, 2, 4, 6, 7,
                                    3, 2, 4 })));
            System.out.println(Arrays.toString(ProductOfAnArray
                    .calcArray(new int[] { 4432432, 23423423, 34234, 23423428,
                            4324243, 24232, 2342344, 64234234, 4324247,
                            4234233, 234422, 234244 })));
        } catch (Exception e) {
            // debug exception here and log.
        }
    }

    /*
     * Problem: Given an array of integers, produce an array whose values are
     * the product of every other integer excluding the current index.
     * 
     * Assumptions. Input array cannot be modified. input is an integer array
     * "produce an array" - type not specified for output array
     * 
     * Logic explanation:
     * 
     * Assume we have array [a,b,c,d] Let multiple be multiple of each element
     * in array. Hence multiple = 0 if one of the element is 0; To produce the
     * output. Ans at i -> multiple divided by the value at i. if 2 numbers are
     * 0 then entire output will be 0 because atleast one 0 will be a multiple
     * if 1 number is 0 then every thing else will be 0 except that index whole
     * value is to be determined
     * 
     */
    public static BigInteger[] calcArray(final int[] inp) throws Exception {
        if (inp == null)
            throw new Exception("input is null");

        int cnt = 0;
        BigInteger multiple = new BigInteger("1");
        boolean foundZero = false;

        for (int i : inp) {
            if (i == 0) {
                cnt++;
                foundZero = true;
                if (cnt < 2)
                    continue;
                else
                    break;
            }
            multiple = multiple.multiply(BigInteger.valueOf(i));
        }

        BigInteger ans[] = new BigInteger[inp.length];

        for (int i = 0; i < inp.length; i++) {
            if (foundZero) {
                if (cnt < 2) {
                    ans[i] = (inp[i] == 0) ? multiple : new BigInteger("0");
                } else {
                    ans[i] = new BigInteger("0");
                }
            } else {
                ans[i] = multiple.divide(BigInteger.valueOf(inp[i]));
            }
        }
        return ans;
    }

}

But I was not selected. I would like to get feedback on my answer and see what's wrong.

Answer 1

1. It might not because of the code. Maybe you were unlucky and there was a better candidate or a candidate with more experience in their industry.

2. If it's not a bottleneck in an application (or a library function) don't do premature optimization. The naive solution is much easier to understand, faster to develop and easier to maintain since it's not so complex:

   public static BigInteger[] calcArray2(int[] input) throws Exception {
       if (input == null) {
           throw new NullPointerException("input is null");
       }
   
       BigInteger result[] = new BigInteger[input.length];
       for (int i = 0; i < input.length; i++) {
           result[i] = calculateProductExcept(input, i);
       }
       return result;
   }
   
   private static BigInteger calculateProductExcept(int[] input, int exceptIndex) {
       BigInteger result = BigInteger.ONE;
       for (int i = 0; i < input.length; i++) {
           if (i == exceptIndex) {
               continue;
           }
           result = result.multiply(BigInteger.valueOf(input[i]));
       }
       return result;
   }
   

   Anyway, is n division faster than n*n multiplications?

   More or less related: YAGNI, Simplicity -- the art of maximizing the amount of work not done -- is essential from the Agile Manifesto

3. You have a lot of copy pasted code here:

   System.out.println(Arrays.toString(ProductOfAnArray
           .calcArray(new int[] { 4, 3, 2, 8 })));
   System.out.println(Arrays.toString(ProductOfAnArray
           .calcArray(new int[] { 4, 0, 2, 8 })));
   

   You could extract out a method:

   private static void printProductOfArray(int... input) throws Exception {
       System.out.println(Arrays.toString(ProductOfAnArray.calcArray(input)));
   }
   

4. Swallowing exceptions is not a good practice, even in an exercise:

   } catch (Exception e) {
       // debug exception here and log.
   }
   

   If something throws an exception you'll miss it. You could modify the main method to throw exceptions and remove the try-catch block instead:

   public static void main(String[] args) throws Exception {
   

   (The Pragmatic Programmer: From Journeyman to Master by Andrew Hunt and David Thomas: Dead Programs Tell No Lies.)

5. You could throw a more specific exception here, like an IllegalArgumentException or a NullPointerException:

   if (inp == null)
       throw new Exception("input is null");
   

   Calling the method with null input array is rather a programming error, so unchecked exceptions are better here. (It would make the throw Exception on the main unnecessary.)

6. I guess result (as variable name) would be easier to understand here:

   BigInteger ans[] = new BigInteger[inp.length];
   

   I'd also avoid abbreviations. I've found that they undermine autocomplete. (When you type co and press Ctrl+Space in Eclipse it founds nothing but it could found count.) Furthermore, they require mental mapping (readers/maintainers have to decode them every time.

   See also: Clean Code by Robert C. Martin, Use Intention-Revealing Names, p18; Use Pronounceable Names, p21; Avoid Mental Mapping, p25

7. I'd rename this variable to fullProduct or something more descriptive to express its purpose:

   BigInteger multiple = new BigInteger("1");
   

Answer 2

For starters, you have very weird line breaks:

System.out
        .println(Arrays.toString(ProductOfAnArray
                .calcArray(new int[] { 4, 3, 2, 8, 3, 2, 4, 6, 7,
                        3, 2, 4 })));

That's not layout, that's obfuscation! When dealing with long method chains, it may be preferable to break before each method invocation:

someObject
  .thisIs()
  .aFluid()
  .interface();

but that's not the case here, and this layout does not increase readability. Instead, break after the opening paren of the argument list:

System.out.println(
    Arrays.toString(ProductOfAnArray.calcArray(new int[] {
        4, 3, 2, 8, 3, 2, 4, 6, 7, 3, 2, 4
    }))
);

or something like that. Note that you could have written this as

System.out.println(
    Arrays.toString(ProductOfAnArray.calcArray(
        4, 3, 2, 8, 3, 2, 4, 6, 7, 3, 2, 4
    ))
);

(i.e. without the explicit array) when declaring your function with varargs: calcArray(int... inp).

The next question is why you are returning an array – a List<BigInteger> would be more flexible – arrays have little use in modern Java (the usage of varargs implies arrays, and high-performance code may need them. But in all other cases, they are too inflexible – e.g. arrays and generics don't work together).

But why BigInteger? Yes, you don't want to overflow, but we can assume that your interviewers would be content with an int. If you want to allow larger numbers, the first step would be long. Big Integers are truly awkward to use and necessarily less performant that native types, so I would avoid them wherever possible.

Your code inside calcArray is unnecessarily clever. Let's look at this loop:

for (int i : inp) {
    if (i == 0) {
        cnt++;
        foundZero = true;
        if (cnt < 2)
            continue;
        else
            break;
    }
    multiple = multiple.multiply(BigInteger.valueOf(i));
}

Notice that foundZero is equivalent to cnt > 0, and that you aren't using braces around the bodies of the inner if/else. Your continue is rather confusing, and the following expresses the control flow much better:

for (int i : inp) {
    if (i != 0) {
        multiple = multiple.multiply(BigInteger.valueOf(i));
    }
    else {
        cnt++;
        if (cnt >= 2) {
            break;
        }
    }
}

This conditional in the next loop is also too complex, and could be simplified to

if (cnt < 2 && inp[i] == 0) {
    ans[i] = multiple;
} else {
    ans[i] = new BigInteger("0");
}

When applying these criticisms, the Simplest Thing That Could Work might be this:

public static List<Long> specialProduct(int... numbers) {
    long product = 1;
    int zeroesCount = 0;
    for (int n : numbers) {
        if (n != 0) {
            product *= n;
        }
        else {
            zeroesCount++;
        }
    }

    List<Long> output = new ArrayList<>(numbers.length);

    switch (zeroesCount) {
    case 0:
        // with no zeroes, we don't have to perform any checks
        for (int n : numbers) {
            output.add(product / n);
        }
        break;
    case 1:
        // with one zero, the all others will become zero too
        for (int n : numbers) {
            if (n == 0) {
                output.add(product);
            }
            else {
                output.add(0L);
            }
        }
        break;
    default:
        // two or more zeroes make everything zero
        for (int i = 0; i < numbers.length; i++) {
            output.add(0L);
        }
        break;
    }

    return output;
}

Oh, and naming! Have vocals become so precious that we must write cnt instead of count? Must we write ans instead of answer if you can actually write a long word like multiple? And what the heck is inp?

Your code is not bad, but it isn't good, and could certainly have been written better. The next time, maybe :)

Answer 3

What rolfl's answer called "the naive O(n²) solution of nested loops" might be better:

• It's slower, but that doesn't matter for small/infrequent arrays
• If your solution had used int instead of BigInteger then the naive solution would have handled slightly more/bigger input numbers, which is a slight bonus (and, deciding to use BigInteger because you haven't clarified how big the input might be will have performance consequences of its own)
• It's more obvious (mapping from problem to solution) and easier to read (because it's more obvious), which might be more important than being optimized for speed

During the phone interview, did you ask questions like:

• Are the arrays very long?
• Should I optimize for maximum speed, or for minimum memory, or for maximum readability?

Asking questions may be part of an interview process: "Does the candidate ask questions to clarify ambiguous requirements before coding?"

I didn't find it easy to verify by inspection whether your calcArray is correct. Maybe I'm not as clever as you.

---

The code in your main has a lot of repeated System.out.println(Arrays.toString(ProductOfAnArray.calcArray statements.

Instead it might be better to have a collection of input arrays, which you iterate (passing each in turn to calcArray).

Even better if the test data is a collection of input arrays and expected output so that the code can assert whether actual output matches expected output.

Answer 4

As @rolfl said your code look good to me too. I just wanted to add some very very minor notes about your code.

Style

if (inp == null)
    throw new Exception("input is null");

This particular way of formatting if could be seen as a problem. Not using brackets for an single line can sometimes be seen as something bad. It's really a minor point that should not influence the outcome for a job interview, but if they are very very fanatic, it could have an influence.

Tests

Your main looks like a bunch of tests to me. I don't know the time you had to produce the code, but do know that test are important for a lot of companies. You could transform those homemade "tests" into a full suite of JUnit tests. I think that could give you an edge over other candidates. It would help show what you understand of the requirements and predict how your code should behave. It can help understand why are you doing certain things the way you did.

Constant

Other minor point, you should use constant when they are available.

BigInteger multiple = new BigInteger("1");
new BigInteger("0");

should be

BigInteger multiple = BigInteger.ONE;
BigInteger.ZERO;

There will be less new in your code, so it could help if the function is called a lot!

Answer 5

Honestly..... that looks good.

it is pretty much what I would have done. It is O(n) which is smarter than the naive O(n²) solution of nested loops, it manages overflow well with the BigInteger... it is good.

The only concern is that the interviewer may have expected an int[] return type, and the assumption that overflow won't happen.

If it were me, I would have probably done an int[] solution and qualified the result with:

you know this is at risk of overflow, and depending on the real-world requirements I would code it with BigInteger if needed.

Still, I imagine there is some other reason you didn't get the job.... not this code.... and, if it was the code, then you may not want to work there anyway ;-)

All the best.

Answer 6

What about something like this ?

import java.util.Arrays;

public class ArrayCalc {

    public static void main(String[] args){

        Integer[] exparray = {2,3,4};

        Integer[] resultarray = new Integer[exparray.length]; 

        for (int i = 0; i< exparray.length; i++){

            if(!exparray[i].equals(0)){
                Integer result = 1;
                for (int j = 0; j<exparray.length; j++)
                    result = result * exparray[j];
                result = result/exparray[i];
                resultarray[i] = result;
            }
        }
        System.out.println(Arrays.toString(resultarray));
    }
}