Palantir interview question: phone interview.

http://www.palantir.com/

given int[] in, generate int[] out, out[i]= product of every element of in except
in[i]，canot use divede mark (/), O(n) time required

/**
* c[i] = A[0]*A[1]*..*A[i]
* d[i] = A[n]*A[n-1]*..*A[i]
*
* and c[0] = a[0], d[n]=a[n];
*
* then B[i] = c[i-1] * d[i+1]
*
* @return b
*/
public static final int[] multiply(int[] a) {
if (a.length==1)
return a;

int n = a.length-1;
int[] b = new int[n+1];
int[] c = new int[n+1];
int[] d = new int[n+1];

c[0] = a[0];
d[n] = a[n];

for (int i=1;i<=n;i++) {

c[i] = c[i-1] * a[i];
d[n-i] = d[n-i+1] * a[n-i];
}

b[0] = d[1];
b[n] = c[n-1];
for (int i=1; i<=n-1; i++) {
b[i] = c[i-1] * d[i+1];
}
return b;
}