Amazon.com Interview Question
Web:
www.amazon.com
|
HQ:
Seattle, WA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
1,572 Interview Reviews |
Back to all Amazon.com Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Senior Software Engineer at Amazon.com:
Sep 28, 2011
Given an array of integers A[1...n], compute the array B[1...n] such that B[k] is the product of all the elements of A, except A[k]. Part ii) Try to do it without division (some mobile devices don't have division). Was asked to write code for part ii.
Add Tags
[?]
See more for this Amazon.com Senior Software Engineer Interview
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (6)
4 of 4 people found this helpful
Oct 16, 2011
@Shilpa while your answer is correct, it is O(n^2). This can be done in O(n) with no auxillary space.
Two passes of the array A :
After first pass
B[i+1] = A1 * A2 * A3 * .... Ai
So in second pass, by traversing A in reverse order and multiplying we can get the desired result.
Two passes of the array A :
After first pass
B[i+1] = A1 * A2 * A3 * .... Ai
So in second pass, by traversing A in reverse order and multiplying we can get the desired result.
Helpful Answer?
Yes |
No
Inappropriate?
0 of 2 people found this helpful
Oct 27, 2011
@AV seems your method is still O(n^2)
or a extra array is needed; like this:
void product (int * a, int* b,int n)
{
int * c= new int [n];
for (int i=0;i<n;i++)
{
if (i==0){ b[i]=1;c[n-i-1]=1;continue;}
else {b[i]=b[i-1]*a[i-1];c[n-i-1]=c[c-i]*a[c-i];}
}
for (int i=0;i<n;i++) b[i]*=c[i];
delete [] c;
}
or a extra array is needed; like this:
void product (int * a, int* b,int n)
{
int * c= new int [n];
for (int i=0;i<n;i++)
{
if (i==0){ b[i]=1;c[n-i-1]=1;continue;}
else {b[i]=b[i-1]*a[i-1];c[n-i-1]=c[c-i]*a[c-i];}
}
for (int i=0;i<n;i++) b[i]*=c[i];
delete [] c;
}
Helpful Answer?
Yes |
No
Inappropriate?
Nov 15, 2011
long Totl = 1;
for ( i = 0; i < length; i++ ) // Get total product
{
Totl *= arry1[i];
}
for ( i = 0; i < j; i++ )
{
if ( arry1[i] )
prdArry[i] = Totl / arry1[i];
else
prdArry[i] = 0;
}
for ( i = 0; i < length; i++ ) // Get total product
{
Totl *= arry1[i];
}
for ( i = 0; i < j; i++ )
{
if ( arry1[i] )
prdArry[i] = Totl / arry1[i];
else
prdArry[i] = 0;
}
Helpful Answer?
Yes |
No
Inappropriate?
0 of 1 people found this helpful
Dec 1, 2011
It can be almost done in O(n) time in two steps.
#1. Determine the product of all numbers O(n)
#2. Divide the product at its index & store it to b. Complexity O(n);
For example, Let a[] = {1,2,3,4,5};//make sure doesn't have zero.
and b[] as a new array;
int product=1;
for(int i=0; i<a.length; i++){
product *= a[i];
}
for(int j=0; j<a.length; j++){
b[j] = product/a[i];
}
The complexity is O(2n) which is almost O(n) or theeta(n)
II) Division is a collection of repeated subtraction. Instead of dividing a[i] with product, subtract a[i] with a[i] times. This'll be O(n2).
#1. Determine the product of all numbers O(n)
#2. Divide the product at its index & store it to b. Complexity O(n);
For example, Let a[] = {1,2,3,4,5};//make sure doesn't have zero.
and b[] as a new array;
int product=1;
for(int i=0; i<a.length; i++){
product *= a[i];
}
for(int j=0; j<a.length; j++){
b[j] = product/a[i];
}
The complexity is O(2n) which is almost O(n) or theeta(n)
II) Division is a collection of repeated subtraction. Instead of dividing a[i] with product, subtract a[i] with a[i] times. This'll be O(n2).
Helpful Answer?
Yes |
No
Inappropriate?
Dec 8, 2011
Linear time guys.
#include "stdafx.h"
#include <iostream>
using namespace std;
void printmultipliers(int a[], int b[], int n)
{
int totalProduct = 1;
cout << "b[] ";
for(int i = 0; i < n; i++)
{
totalProduct *= a[i];
b[i]= totalProduct;
cout << b[i] << " ";
}
cout << "\n";
int reverseproduct = 1;
int j = n -1;
while(j >= 0)
{
if(j == (n -1))
{
cout << b[j -1] << " ";
}
else if(j == 0)
{
cout << reverseproduct;
}
else
{
cout << b[j-1] * reverseproduct<< " ";
}
reverseproduct *= a[j];
j--;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[] = {1, 2, 3, 4};
int b[4];
printmultipliers(a, b, 4);
return 0;
}
#include "stdafx.h"
#include <iostream>
using namespace std;
void printmultipliers(int a[], int b[], int n)
{
int totalProduct = 1;
cout << "b[] ";
for(int i = 0; i < n; i++)
{
totalProduct *= a[i];
b[i]= totalProduct;
cout << b[i] << " ";
}
cout << "\n";
int reverseproduct = 1;
int j = n -1;
while(j >= 0)
{
if(j == (n -1))
{
cout << b[j -1] << " ";
}
else if(j == 0)
{
cout << reverseproduct;
}
else
{
cout << b[j-1] * reverseproduct<< " ";
}
reverseproduct *= a[j];
j--;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[] = {1, 2, 3, 4};
int b[4];
printmultipliers(a, b, 4);
return 0;
}
Helpful Answer?
Yes |
No
Inappropriate?
To comment on this
question,
Sign In with Facebook or
Sign Up
You might also be interested in: Interview Questions, Senior Software Engineer Interview Questions, Amazon.com Interview
1 of 4 people found this helpful
by Shilpa Jindal:
public void solveAns()
{
Integer a[] = {1,2,3,4,5};
Integer b[5] = new Integer[5]();
for ( i =0; i<5; i++)
{
b[i] = getProduct(a, i);
}
}
private Integer getProduct(Integer[] a, int index)
{
Integer prod = 1;
for ( i =0; i<a.length; i+)
{
if ( i != index )
{
prod *= a[i];
}
}
return prod;
}