Zillow Interview Question for Software Engineer / Developers






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[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]

- arnab.banerjee.82@gmail.com September 09, 2008 | Flag Reply
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

- arnab.banerjee.82@gmail.com September 09, 2008 | Flag
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

- Handong (hdchen @ gmail.com) January 27, 2009 | Flag Reply
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).

- Paco August 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is an excellent idea

- averill November 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 !

- oxygen August 12, 2007 | Flag Reply
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.

- Anonymous January 24, 2012 | Flag
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

- Anonymous June 25, 2013 | Flag
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

- oxygen August 12, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Darshan...did we answer ur question ?

- oxygen August 12, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Rama.B May 27, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Please elaborate your second solution with an example.

- Anonymous April 11, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ya ya ya ya

- shiv June 30, 2008 | Flag Reply
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[0]*a[1]*a[2]*..*a[n-1].. no all solution gonna be zero

- atul.iiitm August 06, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Compute B=1,a[1],a[1]*a[2],a[1]*a[2]*a[3],.....,a[1]*a[2]*...a[n-1] (O(n) as B[i] can be computed using a[i-1]and B[i-1])
Compute C=a[2]*a[3]*..a[n], a[3]*a[4]*..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]

- Ajay Mishra August 07, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

is this o(n)?

- Anonymous October 06, 2008 | Flag Reply
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)}

- Danish January 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Is this O(n)?

- Paco August 15, 2014 | Flag
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]);
}

}

- KL March 01, 2014 | Flag Reply
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]

- Anonymous March 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can't use division.

- Nguyen January 04, 2015 | Flag
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[0] * ... * A[i-1] * A[i] * A[i+1] * ... A[N] / A [i] = A[0] * ... * 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?

- AK November 13, 2014 | Flag Reply
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[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];
            }
        }
    }
}

- AK November 16, 2014 | Flag Reply
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[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;
  }

- xelways March 16, 2015 | Flag Reply


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