Amazon Interview Question Software Engineer / Developers
Team: General
Country: United States
Interview Type: In-Person
@aakashv2.1 : I merely meant to say that this question is trivial if you can divide. But you can make a division operator by binary searching multipliers. When faced with a/b, let a/b = c and binary search for c, calculating b*c and comparing that to a.
Really, since this requires no extra space (absent overflows), this may be a better approach than anything else in some cases. This takes O(d) time where d is the number of bits of precision an integer value can have.
Use divide an conqueror.
Divide the array in 2 parts and when merging multiple the with the product of the array being merged in.
Eg.
[1 2 3 4]
[1 2] [3 4]
[1] [2] [3] [4]
This is how the B will be built where B has on values as [1 1 1 1]
[1*2] [1*1] [1*4] [1*3]
[2 1] [4 3]
[2*12 1*12 4*2 3*2]
[24 12 4 6]
Use divide an conqueror.
Divide the array in 2 parts and when merging multiple the with the product of the array being merged in.
Eg.
[1 2 3 4]
[1 2] [3 4]
[1] [2] [3] [4]
This is how the B will be built where B has on values as [1 1 1 1]
[1*2] [1*1] [1*4] [1*3]
[2 1] [4 3]
[2*12 1*12 4*2 3*2]
[24 12 4 6]
func(array a, array b){
value temp = 1;
for(i=0; i<n-1; i++){
b[i] *= temp;
temp *= a[i];
}
temp = 1;
for(i=n-1; i>=0; i--){
b[i] *= temp;
temp *= a[i];
}
}
I think the code above is outputing the total product for each index
A little change will set it right
func(array a, array b){
value temp = 1;
for(i=0; i<n-1; i++){
// change these two lines..they are not correct
b[i] = temp;
temp = b[i]*a[i];
}
temp = 1;
for(i=n-1; i>=0; i--){
b[i] *= temp;
temp *= a[i];
}
}
<pre lang="" line="1" title="CodeMonkey26729" class="run-this">#include<stdio.h>
#include<iostream>
using namespace std;
int main(){
int a[]={2,4,6,8};
int length=4;
int p[length];
int q[length];
//cumulative array by multiplying all but the element
p[0]=1;
p[1]=a[0];
for(int i=2; i<length;i++){
p[i]=p[i-1]*a[i-1];
}
//reverse cumulative by multiplying all but elements
q[length-1]=1;
q[length-2]=a[length-1];
for(int i=length-3; i>=0;i--){
q[i]=q[i+1]*a[i+1];
}
//display result
for (int i=0;i<length;i++){
cout<<p[i]*q[i]<<"\t";
}
}
//e.g A=[a,b,c,d];
//p=[1,a,a*b,a*b*c];
//q=[b*c*d,c*d,d,1];
//result equals multiplication of p & q;
//can we reduce space complexity??</pre><pre title="CodeMonkey26729" input="yes">;
</pre>
Tried using Recursion
public class dc_product {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr ={1,2,3,4,5,6};
int[] brr=new int[arr.length];
int j;
for (j=0;j<arr.length;j++)
{
brr[j]=prod(arr,j,0);
System.out.println(brr[j]);
}
}
public static int prod(int[] a, int i, int m)
{
if (m==0 && i==0 )
{
if (a.length == 1)
return a[i];
return prod(a,i+1,1);
}
if (m==0 && i==a.length-1 )
return prod(a,i-1,-1);
if (i==0 || i==a.length-1)
return a[i];
if (m==0)
return prod(a,i-1,-1)*prod(a,i+1,1);
if (m==-1)
return a[i]*prod(a,i-1,-1);
if (m==1)
return a[i]*prod(a,i+1,1);
return (Integer) null;
}
}
We can do this by going left-to-right on A , calculating left of i , store in b, then from right-to-left calculating right of i multiply by b
- aziz November 09, 2011Psedo code
M=1
for(i=0;i<n;i++)
{
B[i]=M;
M=M*A[i];
}
M=1
for(i=n-1;i>=0;i--)
{
B[i]=B[i]*M;
M=M*A[i];
}