## Amazon Interview Question for Software Engineer / Developers

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

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.

``````for(i to n)
print A[i] * B[i]``````

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

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

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

Now do it without / operator. I guess he forgot to mention this. :)

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

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.

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

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

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

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.

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

To be precise better use a[i] = (int)(exp(ln(P)-ln(a[i]))+.5);

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

1. Take product,P, of all the elements of A
for(int i = 0; i < A.length(); i++)
{
A'[i] = P/A[i];
}

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

OK. I missed the / part :).

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

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.

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

division is costly that is why it was not allowed to use. Logarithm is even more costly. This is not the solution which is expected.

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

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

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

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

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

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

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

the simplest solution is to start at the end of the array and multiply as you make your way to the beginning.

``````int k = 1;
for(int i = length(A) -1,i>0,i--){
A'[i]=A[i]*k
k=A'[i]}``````

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

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

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

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

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

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

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

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

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.