Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Your code is similar to what i had answered. I guess its close to the being correct (not checking NPE and corner cases)
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.
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));
}
}
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?
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}.
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?
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...
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 +" ");
}
}
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) :)
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;
}
}
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].
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;
}
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]);
}
}
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.
//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];
- mahadev September 18, 2012