## Zillow Interview Question for Software Engineer / Developers

• 0

Comment hidden because of low score. Click to expand.
1
of 0 vote

This solution can be optimized just writing down the concept

say 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 = a2*a3*a4 = B1 * B2
B = a1 * a3*a4 = B1 * B2
B = a1*a2 * a4 = B1 * B2
B = a1*a2*a3 = B1 * B2

hence
B[i] = B1[i-1] * B2[ (i+1) % n]

Comment hidden because of low score. Click to expand.
0

formatting gone ... :(
take 0 1 2 .. as index of the array B1,B2

Comment hidden because of low score. Click to expand.
1
of 1 vote

Construct 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

Comment hidden because of low score. Click to expand.
0

Why C1={1, A(1),A(1)*A(2),...,A1*A2*...*A(n-1)} is O(n)? It should be O(n^2).

Comment hidden because of low score. Click to expand.
0

This is an excellent idea

Comment hidden because of low score. Click to expand.
0
of 0 vote

x = a * a * ... * a[n-1] O(n)

Complx will come to O(2n) ~ O(n).

Note:- solution is from my Friend !

Comment hidden because of low score. Click to expand.
0

log(0) is not defined and log(N) is an expensive operation, but otherwise neat solution.

Comment hidden because of low score. Click to expand.
0

doesn't work with odd number of negative's in the array i.e. negative logarithm

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

Darshan...did we answer ur question ?

Comment hidden because of low score. Click to expand.
0

what if a[i]==0????

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

ya ya ya ya

Comment hidden because of low score. Click to expand.
0

if any point of time you have a[i]=0 then whole product will go to zero as a*a*a*..*a[n-1].. no all solution gonna be zero

Comment hidden because of low score. Click to expand.
0

Compute B=1,a,a*a,a*a*a,.....,a*a*...a[n-1] (O(n) as B[i] can be computed using a[i-1]and B[i-1])
Compute C=a*a*..a[n], a*a*..a[n] , ....., 1 (O(n) as C[i] can be computed using a[i+1]and C[i+1])

Result, R[i] = B[i]*C[i]

Comment hidden because of low score. Click to expand.
0
of 0 vote

is this o(n)?

Comment hidden because of low score. Click to expand.
0
of 0 vote

A={ 1,2,3,4} hence
B={(2*3*4),(1*3*4),(1*2*4),(1*2*3)}

Comment hidden because of low score. Click to expand.
0

Is this O(n)?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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]

Comment hidden because of low score. Click to expand.
0

can't use division.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Guys, based on the question here's what I see: B[i] = A * ... * A[i-1] * A[i] * A[i+1] * ... A[N] / A [i] = A * ... * A[i-1] * A[i+1] * ... A[N]. You basically need to multiply all before i and all after i and that will take you O(N). What I'm missing here?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 = 1, b = b * a, b = a * a = b * a, ...
//    b[i] = b[i-1] * a[i-1]
(*b) = 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 * ... * 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];
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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 = nums;
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;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.