Amazon Interview Question Software Engineer / Developers


Country: India
Interview Type: In-Person


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

//logic
// loop on input array
// //STEP A calculate product
// count number of 0 in numzero
// if numzero > 1 break;
// Also, calculate prod = product of all elements excluding 0
// //STEP B determine output array element based on num zero
// if numzero > 1
// all elements of out array are 0
// else if numzero == 1
// if(input[i] == 0)
// output[i] = prod
// else
// output[i] = 0
// else if numzero == 0
// output[i] = prod/input[i];

#include "iostream"
using namespace std;

void Mularray(int in[],int out[],int size)
{
	int numberOfZero= 0;
	int prod = 1;

	for(int i = 0; i < size; ++i)
	{
		if(in[i] == 0)
		{
			++numberOfZero;
			if(numberOfZero >1) 
				break; // No need to traverse all out elements are 0
		}
		else
			prod = prod * in[i];
	}
	if(numberOfZero > 1)
	{
		for(int i = 0; i < size ; ++i)
		{
			out[i] = 0;
		}
	}
	else if(numberOfZero ==1)
	{
		for(int i = 0; i < size; ++i)
		{
			if(in[i] == 0)
				out[i] =prod;
			else
				out[i] = 0;
		}
	}
	else //numberOfZero == 0
	{
		for(int i = 0; i < size; ++i)
		out[i] = prod/in[i];
	}
}

void print(int a[],int size)
{
	for(int i = 0 ;i < size;++i)
	{
		cout << a[i] << "==>";
	}
}
int main ()
{
	int a[] = {3,4,0,6,5};
	print(a,5);
	cout << endl;
	cout << endl;
	int b[5] ;
	Mularray(a,b,5);
	print(b,5);
	return 0;
}

- mahadev on September 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your code is similar to what i had answered. I guess its close to the being correct (not checking NPE and corner cases)

- scorpionking on September 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

could you please elaborate ??? what do you mean by corner cases?

- mahadev on September 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

well what i mean is that interviwer was satisfied with my ans, but as i did not get through i dont know if there exists something better.

- scorpionking on September 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What do u mean by NPE?
can any one explain

- einstein on September 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

public class ProductArray {
public static Integer[] getProdArray(int[] input){
Integer[] output = new Integer[input.length];
int wholeProduct=1;
int zeroCount=0;
for(int i=0;i<input.length;i++)
{
if (input[i]==0)
zeroCount++;
else{
wholeProduct*=input[i];
}
}
for(int i=0;i<output.length;i++)
{
if (zeroCount==0){
output[i]=wholeProduct/input[i];
}
else if((zeroCount==1)&&(input[i]==0)){
output[i]=wholeProduct;
}
else{
output[i]=0;
}
}

return output;
}

public static void main(String[] args) {
int[] input = {1,2,0,3};
Utils.printArray(getProdArray(input));
int[] input2 = {1,2,-3,3};
Utils.printArray(getProdArray(input2));
int[] input3 = {1};
Utils.printArray(getProdArray(input3));
}
}

- Mugunth on September 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for each element you can compute the product value of all other numbers
(if elt[index] !=elt[i])
but the optimal way is to compute the product initially and for each no divide the product value by it.

Java code :

public class Product {

    public static void main(String[] args) {
     int num[]={1,2,3,4,5};
     int result[];
     result=prod(num);
     System.out.println(result);
    }

    private static int[] prod(int[] num) {
        int product[]=new int[num.length],p=1;
        for(int x:num)
        {
            p*=x;
        }
        System.out.println("total product: "+p);
        for(int i=0;i<num.length;i++)
        {
            product[i]=p/num[i];
            System.out.println(product[i]);
        }
        return product;
    }
}

There may even more optimal way, but my idea is this. But i didn't get this, what is a corner case?

- smilelearner on September 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If the given array has a zero then the whole product will be zero which leads all the value of output array will be zero(assuming here that all kind of exceptions are handled). But the position has zero will have some value also this is not a big deal when input array has more than one zero.

Ex. Input: {1, 2, 0, 3}. Your output: {0, 0, 0, 0} but the required output is {0, 0, 6, 0}.

- Ramesh on September 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yeah, thats right. and is there any other cases we need to concern? what is NPE and corner cases because as scorpionking mentioned for shiva. (not checking NPE and corner cases) so what else?

- smilelearner on September 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

One of the things you need to consider is whether the number is exceeding the MAX_INT value. Then probably you want to use Big Integer. In addition to that, if you have an array from 1 to 200, your answer will be exponential. So you need to address that. You need to ask the interviewer all these questions.

That is what I learn from my 1st failure (with Microsoft). You need to ASK ASK and ASK...

- Vijay on September 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

public class ArrayMultiply {
private static double[]temp={1.3,4.2,5,7,9.2,4.4,0.9,3};
public static double multiplyvalue(double[] a)
{
double returnvalue=1;
for(double c:a)
returnvalue*=c;
return returnvalue;
}
public static double multiplyvalueExceptOneZero(double[]a)
{
double returnvalue=1;
int counter=0;
for(double c:a)
{
if(c==0&&counter++!=1)
;
else
returnvalue*=c;

}
return returnvalue;
}
public static double[] multiplyArray(double[] a)
{
double[] b =a;
double multiplyvalue = multiplyvalueExceptOneZero(a);
double multiplyvalue1=multiplyvalue(a);
for(int i=0;i<b.length;i++)
{
if(multiplyvalue1==0&&b[i]!=0)
b[i]=0;
else if(multiplyvalue==0&&b[i]!=0)
b[i]=0;
else if(multiplyvalue1==0&&b[i]==0)
b[i]=multiplyvalue;
else if(multiplyvalue!=0)
b[i]=multiplyvalue/b[i];
}
return b;
}
public static void main(String args[])
{
//System.out.println(multiplyvalue(temp));
//System.out.println(multiplyvalueExceptOneZero(temp));
for(double a :multiplyArray(temp))
System.out.print(a +" ");
}
}

- Haomin Xiang on September 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use recursion....
When goin down the array calculate product . So when in call for index i we have the product till i-1.
e.g array = 1 2 3 4 5
initially for index 0 , the left product is nothing so consider it 1, and right product is not known
for index 1 , the left product will be 1
similarly when we reach 5 the left product will be 24.

now when we reach last index .... return.
the trick is as we go back the calls go on returning the right products ...
here the last call i.e of 5 will return 1.
that of 4 will return 5 and so on ,

So at a call (while going back ) say we are at 3 the left product is already there as we calculated while goin down , also now we have the right product returned while coming back

So the answer is (leftProduct * rightProduct) :)

- AK on September 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class CatalanNumbers
{
    public static int Catalan(int n)
    {
    //    if(n==0 || n==1) return 1;
        double prod = 1;
        for(int i=2;i<=n;i++)
        {
            prod = prod*(n+i)/i;
        }
        return (int)prod;
    }
}

- Anonymous on September 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why there is an need to compute using double and cast again it to int and returning it?

- smilelearner on September 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

No. of unique BST for 1 to n is equal to the n the term in the Catalan Series.

- Anonymous on September 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The most efficient answer is to not use divide at all. Basically you need 1 temporary array and 1 result array, and 3 loops.

Assuming input array is a, length is n.

The first loop is to put a[0] * a[1] *...*a[i-1] into temp[i]
The second loop starts from the end of the array, put a[i+1] * a[i+2] *...*a[n] into result[i];
The third loop do result[i] *= temp[i], which makes result[i] = a[0] * a[1] * ... * a[i-1] * a[i+1] *... a[n].

- bdknight on September 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i don't get it, can you give some code or explain it? why dividing is not efficient?

- smilelearner on September 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static long[] products(int[] a) {
		if(a == null || a.length == 0) {
			throw new NullPointerException("The array is empty");
		}
		long[] products = new long[a.length];
		long product = 1L;
		for(int i=0; i<=a.length-1; i++) {
			for(int j=0; j<=a.length-1; j++) {
				if(i==j)
					continue;
				product*=a[j];
			}
			products[i] = product;
			product=1L;
		}
		
		return products;
	}

- Anonymous on September 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int MulRecur(int a[], int prod, int i, int n)
{
    int temp,ret;
    if (i == n)
    {
          temp = a[i];
          a[i] = prod;
          return temp;
    }
    ret = MulRecur(a, prod * a[i], i+1 , n);
    temp = a[i];
    a[i] = prod * ret ;
    return temp * ret;
}

- Anonymous on September 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

nt main() {
int a[20],n;
scanf("%d",&n);
for(int i =0 ;i<n;i++) {
scanf("%d",&a[i]);
}
int mul = 1;
int t =0;
for(int i =0 ;i<n;i++) {
if(a[i] == 0)
t++;
else {
mul = mul *a[i];
}
}
for(int i =0 ;i<n;i++) {
if(t <n && a[i] == 0 ) {
a[i] = mul;
}
else if(t==n-1) {
a[i] = 0;
}
else if(a[i]!=0 && t < n) {
a[i] = 0;
}
else if(t==0) {
a[i] = mul/a[i];
}
}
for(int i =0 ;i<n;i++) {
printf("%d ",a[i]);
}
}

- einstein on September 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I feel that the purpose of the question is to reduce the number of multiplications. We have to store the intermediate results somewhere.

- amit on December 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) compute the product of non-zero elements in the array. assuming no overflows.
2) count the number of zeros in the array (do this while walking the array in above step)
3) walk the array and do the following
- if the current element is non-zero, and the count of zeros is > 0, then result for this position is zero. Reason: there is a zero in some other position.
- if the current element is non-zero, and the count of zeros is = 0, then the result for this position is totalproduct/current value. Reason: there are no zeros anywhere.
- if the current element is zero, and the count of zeros is = 1, then the result for this position is totalproduct. Reason: the only zero in the array is in this position.
- if the current element is zero, and the count of zeros is > 1, then the result for this position is zero. Reason: there is atleast one more zero other than the one in the current position.

- Bertlee on July 08, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More