## Amazon Interview Question

Software Engineer / DevelopersThe second question of computing A' from A can be done in 0(n).

void find_A_Dash(int arr[MAX])

{

int product = 1,i;

int Num_of_zero = 0;

for(i=0;i<MAX;i++)

{

if(arr[i] == 0)

Num_of_zero ++;

else

product = product * arr[i];

if(Num_of_zero > 1)

break;

}

for(i=0;i<MAX;i++)

{

if(Num_of_zero >1)

{

arr[i] = 0;

continue;

}

arr[i] = (arr[i] == 0)? product: (Num_of_zero == 1)?0:product / arr[i] ;

}

}

Maintain two arrays..A and B..in A[i] store the product from 1st element till the i-1 element and in B[i] store it from i+1 till the nth element.(Start A from the front and B from the back). Can be done in O(n) time.

Resulting O/P array is just the product of A[i] and B[i].

If anyone is able to do it in O(1) space without using / operator..please suggest a brief idea.

2)

```
void MakeMagic(int src[], int dst[], int N)
{
if (!N) return;
int * p = new int [N];
int index = N-1;
p[index] = 1;
p[index-1] = src[index];
for (--index; index > 0; --index)
p[index-1] = src[index] * p[index];
int q = 1;
for (index = 0; index < N; q *= src[index++])
dst[index] = q * p[index];
delete [] p;
}
```

Hi, I think if we cannot divide we can replace it with substraction. I.e. let P=a1*..*aN. Then ln(P)=ln(a1)+...+ln(aN). Thus we first go through an array and calculate common product. Then a[i] = exp(ln(P)-ln(a[i])). That's all folks.

1. Take product,P, of all the elements of A

for(int i = 0; i < A.length(); i++)

{

A'[i] = P/A[i];

}

Well, it's simple math.

Log(A*B) = Log(A) + Log(B) (here I assume all elements to be positive, otherwise logic will be more complex. Also Log is logarithm with base of e). Thus Log(A*B*..*Z) = Log(A)+Log(B)+...+Log(Z). For an array we need A[i] = P/A[i] without '/' operation. But with logarithms we have Log(A[i]) = Log(P) - Log(A[i]). And A[i] = exp(Log(A[i]) = exp(Log(P) - Log(A[i])). P is calculated as A[0]*A[1]*...*A[N-1]. But the things are nice if everything in the array is positive, if we have negatives or zero it takes more checks and tricks. I don't know if the original task allows negatives/zeroes in the array.

```
void no_division(int *ia, int n)
{
if(n <= 1)
return;
int *A = new int[n];
int *B = new int[n];
for(int i = 1; i < n; ++i)
{
if(i == 1)
A[i] = ia[0];
else
A[i] = A[i-1]*ia[i-1];
}
A[0] = B[n-1] = 1;
for(int i = n-2; i > -1; --i)
{
if(i == n-2)
B[i] = ia[n-1];
else
B[i] = B[i+1]*ia[i+1];
}
for(int i = 0; i < n; ++i)
ia[i] = A[i]*B[i];
delete[] B;
delete[] A;
}
```

<pre lang="java" line="1" title="CodeMonkey50563" class="run-this">import java.util.*;

import java.lang.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

System.out.print("Hello World");

}

}

</pre><pre title="CodeMonkey50563" input="yes">static void productOfRest(int[] a)

{

int[] b = new int[a.length];

int prod = 1;

for (int i = 0; i < b.length; i++) {

b[i] = prod;

prod *= a[i];

}

prod = 1;

for (int i = b.length; i--> 0;) {

b[i] *= prod;

prod *= a[i];

}

}</pre>

the solution where we keep 2 arrays [0..pos-1],[pos+1..n] and multiply them is same as

for i in 0..n

if (i != pos) prod*=A[i]

So, i don't see any benefit..

the optimization may be that we can maintain a product FOR ONCE, and divide it as and when we get a A[pos] to get the answer. BUT given that divide is not acceptable Aleks' answer seems good. we can maintain sum of logs FOR ONCE and subtract from it any log(A[pos]), given pos. (if calculating logs is costly .. cache them as well using a hashmap)..

exp of result sum should give the answer..

the solution where we keep 2 arrays [0..pos-1],[pos+1..n] and multiply them is same as

for i in 0..n

if (i != pos) prod*=A[i]

So, i don't see any benefit..

the optimization may be that we can maintain a product FOR ONCE, and divide it as and when we get a A[pos] to get the answer. BUT given that divide is not acceptable Aleks' answer seems good. we can maintain sum of logs FOR ONCE and subtract from it any log(A[pos]), given pos. (if calculating logs is costly .. cache them as well using a hashmap)..

exp of result sum should give the answer..

the solution where we keep 2 arrays [0..pos-1],[pos+1..n] and multiply them is same as

```
for i in 0..n
if (i != pos) prod*=A[i]
```

So, i don't see any benefit..

the optimization may be that we can maintain a product FOR ONCE, and divide it as and when we get a A[pos] to get the answer. BUT given that divide is not acceptable Aleks' answer seems good. we can maintain sum of logs FOR ONCE and subtract from it any log(A[pos]), given pos. (if calculating logs is costly .. cache them as well using a hashmap)..

exp of result sum should give the answer..

the solution where we keep 2 arrays [0..pos-1],[pos+1..n] and multiply them is same as

```
for i in 0..n
if (i != pos) prod*=A[i]
```

So, i don't see any benefit..

the optimization may be that we can maintain a product FOR ONCE, and divide it as and when we get a A[pos] to get the answer. BUT given that divide is not acceptable Aleks' answer seems good. we can maintain sum of logs FOR ONCE and subtract from it any log(A[pos]), given pos. (if calculating logs is costly .. cache them as well using a hashmap)..

exp of result sum should give the answer..

This is for the case when we can't use division operation. Maintain two arrays such that:

A[i] contains product of all elements in the input array from 0 to i - 1.

B[i] contains product of all elments from i + 1 to n.

The answer would be:

- logan September 30, 2010