## Zillow Interview Question for Software Engineer / Developers

• 0
of 0 votes

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
of 0 votes

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
of 0 votes

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
of 0 votes

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)

b = log inverse (log (x) - log (a))

b = log inverse (log (x) - log (a))

b[n] = log inverse (log (x) - log (a[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
of 0 votes

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
of 0 votes

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
of 0 votes

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

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

Please elaborate your second solution with an example.

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
of 0 votes

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
of 0 votes

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
of 0 votes

Is this O(n)?

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

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

}

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
of 0 votes

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

Add a Comment
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.

Learn More

### 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.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More