Array whose values are the product of every other integer

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.

• Thanks everyone for your feedback. I will take all this into account the next time I write any code. – footy Mar 27 '14 at 16:33
• here's a hint for the algorithm itself: the result on index i is product of all elements/inp[i] – ratchet freak Mar 27 '14 at 20:13
• Seems like the question was too easy, if they don't have time to interview everyone who did at least this good then better make something harder and get some meaty quality difference. – aaaaaaaaaaaa Mar 27 '14 at 21:15
• When you are asked Interview over the phone and you give them code, that isn't what they are looking for. they want you to explain what you would do, in English. – Malachi Mar 27 '14 at 21:21
• bad algorithm, the better way is to multiply all number in array, then divide the number in current index to calculate the result. This is a algorithm question, and I don't think the interviewer will really focus on your coding style. – zdd Mar 28 '14 at 1:36

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");


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) {
}
break;
case 1:
// with one zero, the all others will become zero too
for (int n : numbers) {
if (n == 0) {
}
else {
}
}
break;
default:
// two or more zeroes make everything zero
for (int i = 0; i < numbers.length; i++) {
}
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 :)

• I agree that the special treatment of zero is unnecessary and I like the general idea to compute the total product first and then factor out the current input, but your simplified solution yields zero for all elements if at least one zero in the input, e.g., [0,1,2,3] -> [0,0,0,0], but the correct result should be [6,0,0,0]. – Simon Lehmann Mar 27 '14 at 15:25
• Maybe I misunderstand the original problem, but after reading the OP solution, I think it contains the same error, which might very well be a reason why it was rejected. – Simon Lehmann Mar 27 '14 at 15:31
• @SimonLehmann You should maybe post that as an answer: because it may be the most important reason why the solution was rejected, i.e. "incorrect output". – ChrisW Mar 27 '14 at 15:41
• @ChrisW: The OP's code returns [6,0,0,0] for [0,1,2,3]. – palacsint Mar 27 '14 at 15:47
• Well, ok, I should have probably taken more time to read that code (and actually try it). The OP's programm does NOT have this error, as it uses a continue in the loop where the total product is calculated whenever it encounters a zero. Now I guess, the real reason why it was rejected might be that it is to complicated... – Simon Lehmann Mar 27 '14 at 15:48

What rolfl's answer called "the naive O(n2) 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.

• Agree with everything you say, except "It's correct in a wider range of conditions (less likely to overflow), which might be important" ... that implies that being wrong X times is bad, but X-1 times is OK... – rolfl Mar 27 '14 at 15:12
• +1 asking questions for the requirements is very important! It prove that you're trying to understand what you're doing and do not take details for granted. – Marc-Andre Mar 27 '14 at 15:34
• @ChrisW I did ask to the interviewer those questions. He said you can assume anything. He just wanted me to start writing code and not do any talking. – footy Mar 27 '14 at 16:20
• it is possible to build a O(n) solution that handles big numbers just as well as the O(n^2) solution, it's just the OP didn't do it. Calculate out[0] as product(in[1..n]), then out[n] = out[n-1] / in[n] * in[n-1]. This way you never hold the product of the entire array, which is the main performance concern in OP's solution. – Red Alert Mar 27 '14 at 21:15
• @RedAlert This won't work when there is exactly one zero in the input at any other position than the first, e.g. in = [1,0,2,3] -> out[0] = 0 * 2 * 3 = 0, out[1] = 0 / 0 * 1 = NaN, out[2] = NaN / 2 * 0 = NaN, out[3] = NaN / 3 * 2 = NaN. Even if you check for division by zero, you would incorrectly set out[1] = 0! And saying "you never hold the product of the entire array" when in fact you hold the product of the entire array but the first element is kind of a strange, especially as a "performance" argument. – Simon Lehmann Mar 28 '14 at 22:29

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!

Honestly..... that looks good.

it is pretty much what I would have done. It is O(n) which is smarter than the naive O(n2) 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.

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));
}
}

• can you explain the reasoning behind why you would do it like this, please? – Malachi Mar 27 '14 at 21:16
• The OP stated: I would like to get feedback on my answer and see what's wrong. This in no way addresses the OP's code and is just a code dump. Please review the OP's code (you can even explain how this would make for a better solution), otherwise this answer may be deleted. – Jamal Mar 27 '14 at 21:58