Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
@kkr.ashish : the solution is correct however you can do it in two iterations rather than 3n
C++ code below for O(2n)
int * prodExceptCurrElem (int * arr, int len){
if (!arr || len<0) return NULL;
int * newArr = new int [len];
int i=0, prodSoFar =1;
for(;i<len;i++){
newArr[i] = prodSoFar;
prodSoFar *= arr[i];
}
prodSoFar = 1;
for (i=len-1; i>=0; i--){
newArr[i] *= prodSoFar;
prodSoFar *= arr[i];
}
return newArr;
}
How you can say O(n) ?
Because you are generating array {1,a,ab,abc,abcd,abcde} which will take multiple iterations.
{a[0]*a[1]*a[2]*...a[n-1] - (a[1]*a[2]...a[n-1] (a[0]-1)), a[0]*a[1]*a[2]*...a[n-1] - (a[0]*a[2]...a[n-1] (a[1]-1)), a[0]*a[1]*a[2]*...a[n-1] - (a[0]*a[1]*a[3]...a[n-1] (a[2]-1)), ...}
Complexity O(n)
input 1,2,3,6,2,8
1*2*3*6*2*8 = 576
576/1 = 576
576/2 = 288
576/3 = 192
576/6 = 82
576/2 = 288
a[0]*a[1]*a[2]*...a[n-1] - (a[1]*a[2]...a[n-1] (a[0]-1)) = 576 - 2*3*6*2*8 (1-1) = 576
a[0]*a[1]*a[2]*...a[n-1] - (a[0]*a[2]...a[n-1] (a[1]-1)) = 576 - 1*3*6*2*8 (2-1) = 288
a[0]*a[1]*a[2]*...a[n-1] - (a[0]*a[1]*a[3]...a[n-1] (a[2]-1)) = 576 - 1*2*6*2*8 (3-1) = 192
Verified. Excellent work. Thumps up
Construct 2 arrays F(forward) and B(backward).
F[i] = a[0]*a[1]*a[i-1]
B[i]=a[i+1]*...a[n-1]
F[0]=1;
B[n-1]=1;
Use dynamic programming to construct F and B
b[i]=F[i]*B[i].
static void ProductOfAllButItself()
{
const int size = 8;
var input = InitArray(size);
var output = new int[size];
output[0] = 1;
for (int i = 1; i < input.Length; i++)
{
output[i] = input[i - 1]*output[i - 1];
}
int product = 1;
for (int i = output.Length - 2; i >= 0; i--)
{
product *= input[i + 1];
output[i] *= product;
}
OutputArray(output);
}
O(2n) no additional buffer (only output array)
void count(int[] a, int N)
{
int[] l = new int[N];
int[] r = new int[N];
l[0]=1;r[N-1]=1;
for (int i = 1; i < N; i++)
{
l[i] = l[i-1]*a[i-1];
r[N-i-1] = r[N-i]*a[N-i];
}
for(int i=0;i<N;i++)
Console.WriteLn(l[i]*r[i]);
Calculate suffix product array, for input array A:
B[i] = Product of A[i+1], ..., A[n-1]
Do this by linear sweep from right:
B[n-1]=1;
for(i=n-2; i>=0; i--)
B[i]=A[i+i]*B[i+i];
Now go forwards and calculate prefix products on the fly, and place result in array R: R[i] = prefix_product_at_i * B[i]:
prefix_product=1;
for(i=0; i++; i<n) {
R[i]=prefix_product*B[i];
prefix_product *= A[i]
}
~2n runtime
~n space
This is laziest solution
I am going to explain with an example:
{a,b,c,d,e,f}
then
find this value====> abcdef
and then find
{ abcdef *(a^-1), abcdef* (b^-1), abcdef * (c^-1),abcdef * (d^-1), abcdef * (e^-1), abcdef * (f^-1) }
Conclusion:
Time complexity: O(2n)=O(n).
Space complexity=O(1).
Note: i am not using division operator.
To have a complete solution, you would need to mention an algorithm for finding a^(-1) without using division. After all, a^(-1) is sometimes *defined* as 1/a.
It looks like what you mean to say is that you will find a way to do something equivalent to division without dividing directly...which might be OK, but you'd need to give an algorithm for that.
Guys I have solved this simple approach.
{a[0]*a[1]*a[2]*...a[n-1] - (a[1]*a[2]...a[n-1] (a[0]-1)), a[0]*a[1]*a[2]*...a[n-1] - (a[0]*a[2]...a[n-1] (a[1]-1)), a[0]*a[1]*a[2]*...a[n-1] - (a[0]*a[1]*a[3]...a[n-1] (a[2]-1)), ...}
Complexity O(n)
P/A = P - BCDEF (A-1)
P/B = P - ACDEF (B-1)
P/C = P - ABDEF (C-1)
P/D = P- ABCEF (D-1)
etc
where A = a[0] B = a[1].... P= ABCDEF...
Vote it if you understood it.
kkr.ashish's approach is correct!
Here is my code:
#include<stdio.h>
void main() {
int A[] = {2, 4, 6, 8, 10, 12};
int N = sizeof(A)/sizeof(A[0]);
int O1[N], O2[N], O[N];
int i;
O1[0]=1;
O2[N-1]=1;
for(i=1; i<N; i++) {
O1[i] = O1[i-1]*A[i-1];
}
for(i=N-2; i>=0; i--) {
O2[i] = O2[i+1]*A[i+1];
}
for(i=0; i<N; i++) {
O[i] = O1[i]*O2[i];
}
printf("{");
for(i=0; i<N; i++) {
printf("%d, ", A[i]);
}
printf("\b\b}\n");
printf("{");
for(i=0; i<N; i++) {
printf("%d, ", O[i]);
}
printf("\b\b}\n");
}
O1 stores {1, A[0], A[0]A[1], ...., A[0]A[1]..A[N-2]}
O2 stores {A[1]A[2]..A[N-1], A[2]A[3]..A[N-1], ...., 1}
How about below approach.
arr[] = { a,b,c,d,e};
create another array res in such a way that
res [] = {abcd,acde,abde,abce,abcd };
let me know if i am correct?
what you are doing is correct but look at the complexity part.. you are accessing n-1 elements for every 1 element in output array
Complexity = O(n(n-1))= O(n2)
the question asked is to reduce the complexity
also your updated res[] is not correct the first elemeny should be bcde and abcde
int main()
{
int arr[]={1,2,3,4};
int size=sizeof(arr)/sizeof(arr[0]);
int *B=(int *)malloc(sizeof(int)*(size-1));
memset(B,0,sizeof(int)*(size-1));
int x=1;
for(int i=0;i<size;i++)
{
B[i]=x;
x=x*arr[i];
}
x=1;
for(int i=size-1;i>=0;i--)
{
B[i]=x*B[i];
x=x*arr[i];
}
for(int i=0;i<size;i++)
cout<<B[i]<<" ";
getchar();
return 0;
}
This can be done in O(nlogn) using divide and conquer
The basic idea of the algorithm is as follows:
1. We recursively solve two smaller arrays of size n/2 to get F and B
2. Compute f= a[0]*a[1]*…*a[n/2-1]; b = a[n/2]*a[n/2+1]*…*a[n-1]
3. Multiply each element in F by b, and multiply each element in B by f.
Time complexity analysis:
T(n) = 2T(n/2) + O(n) = O(nlogn)
#python
def new_array(array, index):
a = array
i = index
f = 1
b = 1
if i >=0:
# O(n)
for p in range(i):
f *= a[p]
for q in range(i+1, len(a)):
b *= a[q]
print f, b
return f * b
arr = [1,2,3,4,5]
new_arr = []
# O(n)
for m in range(len(arr)):
new_arr.append(new_array(arr, m))
print new_arr
And one more thing, you should think about the size of this kind of multiplication. It may not work for even a little large number. For example, array with size of 20 and full of 20s.
//Time Complexity O(nlogn)
#include<stdio.h>
int f(int *a,int i,int j){
int p=1,leftp=1,rightp=1;
int l;
for(l=i;l<=j;l++)
p*=a[l];
if(j==i){
a[i]=1;
return p;
}
int mid=i+(j-i)/2;
leftp=f(a,i,mid);
rightp=f(a,mid+1,j);
for(l=i;l<=mid;l++)
a[l]*=rightp;
for(l=mid+1;l<=j;l++)
a[l]*=leftp;
return p;
}
int main(){
int a[]={1,2,3,4,5,6,7,8};
int n=sizeof(a)/sizeof(a[0]),i;
int p=f(a,0,n-1);
printf("Product--%d\n",p);
for(i=0;i<n;i++)
printf("%d ",a[i]);
}
1 #include <iostream>
2 #include <string.h>
3 #include <assert.h>
4
5 int A[] = { 1, 2, 3, 4, 5, 6, 7 };
6 int O[7];
7
8 int OutputArray(int* Array, int Element, int Prev)
9 {
10 if(Array[Element] == 0)
11 memset(O, 0, sizeof(int)*7);
12 int Result = 1;
13 if(Element < 6)
14 {
15 Result = OutputArray(Array, Element + 1, Prev * Array[Element]);
16 O[Element] = Result * Prev;
17 return Result * Array[Element];
18 }
19 else if (Element == 6)
20 {
21 O[6] = Prev;
22 return A[6];
23 }
24
25 std::cout << "error" << std::endl;
26 return 1;
27
28
29 }
30 int main()
31 {
32 OutputArray(A, 0, 1);
33 for(int I = 0; I < 7; I++)
34 {
35 std::cout << O[I] << std::endl;
36 }
37 return 0;
38 }
39
package test;
public class ProductArray {
/**
* @param args
*/
public static void main(String[] args) {
int [] array = {4,2,5,1};
int [] b = getArray(array);
for(int i = 0;i<array.length;i++){
System.out.println(b[i]);
}
}
private static int [] getArray(int [] array){
int [] b = new int[array.length];
int mult = 1;
for(int i = array.length-1;i>=0;i--){
for(int j = array.length-1;j>=0;j--){
if(i!=j){
mult*=array[j];
}
}
b[i] = mult;
mult =1;
}
return b;
}
}
this one is simple
- kkr.ashish August 29, 2013you will need two array of same size
solution as example:
{a,b,c,d,e,f}
generate
{1,a,ab,abc,abcd,abcde}
and
{bcdef,cdef,def,ef,f,1}
now do a dot product of the above two array
you are done..
complexity O(3n)= O(n)
the above array are easily calculable as they can be generated the first from the front of array and other from back with 1 multiplcation for each element.