Zillow Interview Question
Software Engineer / DevelopersConstruct two arrays:
C1, C1(1)=1, C1(i) = C1(i-1)*A(i-1)
C1={1, A(1),A(1)*A(2),...,A1*A2*...*A(n-1)} O(N)
C2, C2(N)=1, C2(i)=C2(i+1)*A(i+1)
C2={A2*A3*..*A(N), A3*A4*...*A(N),...,1} O(N)
Now, B(i) = C1(i)*C2(i) O(N)
O(3N) time and O(2N) space
x = a[0] * a[1] * ... * a[n-1] O(n)
b[0] = log inverse (log (x) - log (a[0]))
b[1] = log inverse (log (x) - log (a[1]))
b[n] = log inverse (log (x) - log (a[n]))
Complx will come to O(2n) ~ O(n).
Note:- solution is from my Friend !
log(0) is not defined and log(N) is an expensive operation, but otherwise neat solution.
i think with 3 additional similar size arrays, it might be possible to construct B.
array B1: Walk A, calculate B1[i] = a[i-1] * a[i+1] (should be O(n))
array B2: Walk A calculate B2[i] = B2[i-1] * a[i] (should be O(n))
array B3: Walk A calculate B3[n-i] = B3[n-i+1] * a[i] (should be O(n))
B[i] = B1[i] * B2[i-2] * B3[i+2]
basically, idea would be to exclude the number itself so construct B1 by doing that.
then keep multiplications from [0-(i-2)] and [i+2 to n] in B2 and B3. this shall leave the
item at i behind.
Note:- Solution given by a Friend of mine
if any point of time you have a[i]=0 then whole product will go to zero as a[0]*a[1]*a[2]*..*a[n-1].. no all solution gonna be zero
how about this solution
public static void calcArray(int[] num1){
int[] num2 = new int[num1.length];
int index = 0;
for(int i =0;i<num1.length;i++){
num2[i] =1;
index = 0;
while(index < num1.length){
if(index!=i){
num2[i] *= num1[index];
index++;
}
else
index++;
}
System.out.println(num2[i]);
}
}
1) Loop through all the elements in A and obtain their product
prod=1
for i =0 to n-1 :
prod=prod*A[i]
in the above example it is 24
2) Now loop through B and set it by dividing the product by its corresponding number in A :
B[i]=prod/A[i]
Better approach - no extra space except array B, no division and total time is O(N):
void CreateArray(int *a, size_t size, int **b)
{
if (a && size && b)
{
*b = new int[size];
if (*b)
{
// 1. form array B such that b[0] = 1, b[1] = b[0] * a[0], b[2] = a[0] * a[1] = b[1] * a[1], ...
// b[i] = b[i-1] * a[i-1]
(*b)[0] = 1;
for (int i = 1; i < size; i++)
{
(*b)[i] = (*b)[i - 1] * a[i - 1];
}
// 2. set x = 1. b[N-1] = x * b[N-1]; x = x * a[N-1];
// b[N-2] = x * b[N-2] = a[N-1] * b[N-2] = a[N-1] * a[0] * ... * a[N-3]
// b[i] = x * b[i]; x = x * a[i]
int x = 1;
for (int i = size - 1; i >= 0; i--)
{
(*b)[i] = x * (*b)[i];
x = x * a[i];
}
}
}
}
static int[] multipleExcept(int[] nums) {
if(nums == null || nums.length == 0) return null;
int len = nums.length;
int[] ret = new int[len];
int[] fwd = new int[len];
int[] rev = new int[len];
fwd[0] = nums[0];
rev[len - 1] = nums[len - 1];
for(int i=1; i<len; i++) {
fwd[i] = fwd[i-1] * nums[i];
rev[len - i - 1] = rev[len - i] * nums[len - i - 1];
}
for(int i=0; i<len; i++) {
int n1 = 1;
int n2 = 1;
if(i > 0) n1 = fwd[i-1];
if(i < len - 1) n2 = rev[i+1];
ret[i] = n1 * n2;
}
return ret;
}
This solution can be optimized just writing down the concept
- arnab.banerjee.82@gmail.com September 09, 2008say A = { a1,a2,a3,a4}
0 1 2 3 4
prepare B1 = { 1, a1, a1*a2 , a1*a2*a3 , 1 }
prepare B2 = { 1 , a2*a3*a4 , a3*a4 , a4 }
Now, B[1] = a2*a3*a4 = B1[4] * B2[2]
B[2] = a1 * a3*a4 = B1[1] * B2[3]
B[3] = a1*a2 * a4 = B1[2] * B2[4]
B[4] = a1*a2*a3 = B1[3] * B2[1]
hence
B[i] = B1[i-1] * B2[ (i+1) % n]