Amazon Interview Question
Software EngineersTeam: Market Place
Country: United States
Interview Type: Phone Interview
int[] array = {1,2,3,4,5};
int allMultiplication = 1;
for (int i = 0; i < array.length; i++) {
allMultiplication = allMultiplication * array[i];
}
for (int i = 0; i < array.length; i++) {
array[i] = allMultiplication / array[i];
}
for (int i = 0; i <array.length; i++) {
System.out.println(array[i]);
}
function productArray1(arr) {
let temp = 1;
let resultArray = [];
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
temp *= arr[j];
}
resultArray.push(temp/arr[i]);
temp = 1;
}
return resultArray;
}
function productArray2(arr) {
let temp = 1;
let resultArray = [];
for (let i = 0; i < arr.length; i++) {
temp *= arr[i]
}
for(let i = 0; i < arr.length; i++) {
resultArray.push(temp / arr[i]);
}
console.log(resultArray);
};
let a = [1,2,3,4,5];
var t0 = performance.now();
productArray1(a);
var t1 = performance.now();
console.log("Call to 1 took " + (t1 - t0) + " milliseconds."); // 0.105 ms runtime
var t0 = performance.now();
productArray2(a);
var t1 = performance.now();
console.log("Call to 2 took " + (t1 - t0) + " milliseconds."); //0.710 ms runtime
Here's my JavaCode .
import java.util.Scanner;
/**
* Created by ejangpa on 1/12/2017.
*/
public class SumOfMulitplicationExceptNumber {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] arrayA = new int[n];
for(int i = 0; i < n; i++) {
arrayA[i] = scanner.nextInt();
}
int[] arrayB = new int[n];
int multiplicationValue = 1;
for(int i = 0; i < n; i++) {
multiplicationValue = multiplicationValue * arrayA[i];
}
if(multiplicationValue > 0) {
sumOfProduct(arrayA, arrayB, multiplicationValue);
} else {
return;
}
}
static void sumOfProduct(int[] arrayA, int[] arrayB, int multiplicationValue) {
for(int i = 0; i < arrayA.length; i++) {
arrayB[i] = multiplicationValue / arrayA[i];
}
printArray(arrayB);
}
static void printArray(int[] arrayB) {
for(int i = 0; i < arrayB.length; i++) {
System.out.print(arrayB[i] + " ");
}
System.out.println();
}
}
package com.abhishek;
public class TestArrayProduct {
public static void main(String[] args) {
TestArrayProduct t = new TestArrayProduct();
int[] nums = { 1, 2, 3, 4 };
int[] outputArr = t.arrProductExceptSelf(nums);
for (int i : outputArr)
System.out.print(i + " ");
System.out.println();
}
int[] arrProductExceptSelf(int[] nums) {
/*
* in the output array, the value at each index
* is the product of all elements left of the index and all elements right of the index
* so in one pass, scan the array from left to right (scan from 2nd element) and for each index store the
* product of elements left of the index
* in next pass, scan the array from right to left (scan from 2nd last element) and for each index get
* the product of all elements to the right of the index
* Then multiply this product with the already calculated product of left side to get the output
*/
if (null == nums || nums.length == 0) {
return nums;
}
int[] outputArr = new int[nums.length];
// scan array from left to right and for each index
// store the product of elements left of the index
outputArr[0] = 1;
for (int i = 1; i < nums.length; i++) {
outputArr[i] = outputArr[i - 1] * nums[i - 1];
}
// scan array from right to left
int product = 1;
for (int j = nums.length - 1; j >= 0; j--) {
outputArr[j] = outputArr[j] * product;
product = product * nums[j];
}
return outputArr;
}
}
package com.abhishek;
public class TestArrayProduct {
public static void main(String[] args) {
// TODO Auto-generated method stub
TestArrayProduct t = new TestArrayProduct();
int[] nums = { 1, 2, 3, 4 };
int[] outputArr = t.arrProductExceptSelf(nums);
for (int i : outputArr)
System.out.print(i + " ");
System.out.println();
}
int[] arrProductExceptSelf(int[] nums) {
/*
* in the output array, the value at each index
* is the product of all elements left of the index and all elements right of the index
* so in one pass, scan the array from left to right (scan from 2nd element) and for each index store the
* product of elements left of the index
* in next pass, scan the array from right to left (scan from 2nd last element) and for each index get
* the product of all elements to the right of the index
* Then multiply this product with the already calculated product of left side to get the output
*/
if (null == nums || nums.length == 0) {
return nums;
}
int[] outputArr = new int[nums.length];
// scan array from left to right and for each index
// store the product of elements left of the index
outputArr[0] = 1;
for (int i = 1; i < nums.length; i++) {
outputArr[i] = outputArr[i - 1] * nums[i - 1];
}
// scan array from right to left
int product = 1;
for (int j = nums.length - 1; j >= 0; j--) {
outputArr[j] = outputArr[j] * product;
product = product * nums[j];
}
return outputArr;
}
public int[] productExceptSelf(int[] nums) {
if (null == nums || nums.length == 0) {
return nums;
}
int[] lproductArr = new int[nums.length];
int[] outputArr = new int[nums.length];
lproductArr[0] = 1;
for (int i = 1; i < nums.length; i++) {
lproductArr[i] = lproductArr[i - 1] * nums[i - 1];
}
int product = 1;
outputArr[nums.length - 1] = lproductArr[nums.length - 1];
for (int j = nums.length - 2; j >= 0; j--) {
product = product * nums[j + 1];
outputArr[j] = lproductArr[j] * product;
}
return outputArr;
}
}
Here test cases handled
Case 1: when no zero
ex: 1 2 3 4 5 => 120, 60, 40, 30, 24
Case 2: when one zero
ex: 1 2 3 0 => 0, 0, 0, 6
Case 3: when two zero
ex: 1 0 0 2 => 0, 0, 0, 0
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class ProductArray {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String []inString = br.readLine().split(" ");
int len = inString.length;
int [] intArray = new int[len];
int i=0;
for(String str: inString){
intArray[i] = Integer.parseInt(str);
i++;
}
int [] newProductArray = generateNewArray(intArray);
for(int value: newProductArray){
System.out.print(value+" ");
}
}
public static int [] generateNewArray(int [] array){
int oneZero = 1;
int allProduct = 1;
int zeroCount = 0;
int len = array.length;
for(int i=0; i<len; i++){
if(array[i]==0){
if(zeroCount==0){
zeroCount = 1;
}else{
allProduct = 0;
zeroCount = 2;
}
}else {
allProduct*=array[i];
}
}
int [] newArray = new int[len];
if(zeroCount == 2){
Arrays.fill(newArray, 0);
}else {
for(int i=0; i<len; i++){
if(zeroCount ==1){
if(array[i]==0){
newArray[i] = allProduct;
}else {
newArray[i] = 0;
}
}else{
newArray[i] = (int)allProduct/array[i];
}
}
}
return newArray;
}
}
func createArrayForGivenArray(inputArr:[Int]) -> [Int] {
var newArr = [Int]()
var newElement = 1
for index in 0...inputArr.count-1 {
let currentElement = inputArr[index]
for item in inputArr {
if item != currentElement {
newElement = item*newElement
}
}
newArr.append(newElement)
newElement = 1
}
return newArr
}
// Swift Way to solve this.
func createArrayForGivenArray(inputArr:[Int]) -> [Int] {
var newArr = [Int]()
var newElement = 1
for index in 0...inputArr.count-1 {
let currentElement = inputArr[index]
for item in inputArr {
if item != currentElement {
newElement = item*newElement
}
}
newArr.append(newElement)
newElement = 1
}
return newArr
}
public class ArrayMultiplier {
public Integer [] getMultipliedArray(Integer[] input) {
Integer multiplication = 1;
Integer[] returnArray = new Integer[input.length];
int zeroIndex =-1;
boolean morethanOneZero = false;
for (int i = 0; i < input.length; i++) {
if(input[i]!=0)
multiplication*=input[i];
else{
if(zeroIndex <0)
zeroIndex=i;
else {
morethanOneZero = true;
}
}
}
for (int i = 0; i < input.length; i++) {
if(zeroIndex >-1){
if(i==zeroIndex && !morethanOneZero){
returnArray[i]=multiplication;
}else{
returnArray[i]=0;
}
}
else{
returnArray[i] = multiplication / input[i];
}
}
return returnArray;
}
public static void main(String[] args) {
Integer[] input = {1, 0, 3, 1, 5};
Integer[] returnArr= new ArrayMultiplier().getMultipliedArray(input);
for (int i = 0; i < returnArr.length; i++) {
System.out.print(returnArr[i] + " , ");
}
}
}
public class ArrayMultiplier {
public Integer [] getMultipliedArray(Integer[] input) {
Integer multiplication = 1;
Integer[] returnArray = new Integer[input.length];
int zeroIndex =-1;
boolean morethanOneZero = false;
for (int i = 0; i < input.length; i++) {
if(input[i]!=0)
multiplication*=input[i];
else{
if(zeroIndex <0)
zeroIndex=i;
else {
morethanOneZero = true;
}
}
}
for (int i = 0; i < input.length; i++) {
if(zeroIndex >-1){
if(i==zeroIndex && !morethanOneZero){
returnArray[i]=multiplication;
}else{
returnArray[i]=0;
}
}
else{
returnArray[i] = multiplication / input[i];
}
}
return returnArray;
}
public static void main(String[] args) {
Integer[] input = {1, 0, 3, 1, 5};
Integer[] returnArr= new ArrayMultiplier().getMultipliedArray(input);
for (int i = 0; i < returnArr.length; i++) {
System.out.print(returnArr[i] + " , ");
}
}
}
public Integer [] getMultipliedArray(Integer[] input) {
Integer multiplication = 1;
Integer[] returnArray = new Integer[input.length];
int zeroIndex =-1;
boolean morethanOneZero = false;
for (int i = 0; i < input.length; i++) {
if(input[i]!=0)
multiplication*=input[i];
else{
if(zeroIndex <0)
zeroIndex=i;
else {
morethanOneZero = true;
}
}
}
for (int i = 0; i < input.length; i++) {
if(zeroIndex >-1){
if(i==zeroIndex && !morethanOneZero){
returnArray[i]=multiplication;
}else{
returnArray[i]=0;
}
}
else{
returnArray[i] = multiplication / input[i];
}
}
return returnArray;
}
public int[] product(int[] arr){
int[] res = new int[arr.length];
int nonZeroProduct = 1;
int zeroCount = 0;
for(int a : arr){
if(a == 0){
zeroCount++;
if(zeroCount > 1){
//No chance to have a non zero res for any element
return res;
}
continue;
}
| nonZeroProduct *= a;
}
for(int i=0; i<res.length; ++i){
int curr = res[i];
if(curr == 0){
res[i] = nonZeroProduct;
}else{
res[i] = nonZeroProduct / curr;
}
}
return res;
}
PYTHON CODE --> ALL TEST CASES HANDLED
#a= [1,2,3,4,5]
# b =[120,60,40,30,24]
# case 2
#a = [1,2,3,4,0]
# b = [0,0,0,0,24]
a = [2,4,0,5,0]
mul = 1
index = []
for i in range(len(a)):
if a[i]==0:
index.append(i)
else:
mul = mul*a[i]
print(mul)
b = [0]*(len(a))
if len(index)==0:
for i in range(len(b)):
b[i] = mul//a[i]
else:
for i in index:
b[i]=mul
print (a)
print (b)
/**
*
*/
package com.learn.hazlecast.DistributedRun;
public class IndexValueFind {
public static void main(String[] args) {
int[]arr={2,3,4,5,6,7};
int[]newarr=new int[arr.length];
int product=1;
for(int j=0;j<arr.length;j++){
product*=arr[j];
}
for(int m=0;m<arr.length;m++){
newarr[m]=product/arr[m];
}
for(int j:newarr)
{
System.out.println(j);
}
}
}
static long[] calculatesProductsOfAllItemsExceptOne(int[] items) {
long[] products = new long[items.length];
long productOfNonZero = 1L;
int indexOfZero = -1;
for (int i = 0; i < items.length; i++) {
if (items[i] != 0) {
productOfNonZero *= items[i];
} else {
if (indexOfZero == -1) {
indexOfZero = i;
} else {
return products;
}
}
}
if (indexOfZero == -1) {
for (int i = 0; i < products.length; i++) {
products[i] = productOfNonZero/items[i];
}
} else {
products[indexOfZero] = productOfNonZero;
}
return products;
}
def Find(mylist):
multiplication=1
Zerocount=0
for i in mylist:
if i!=0:
multiplication*=i
else:
Zerocount +=1
if Zerocount ==1 :
return [multiplication if i==0 else 0 for i in mylist]
elif Zerocount > 1:
return [0 for i in mylist]
return [multiplication/i for i in mylist]
print Find([1,2,3,4,5,0]) #returns [0, 0, 0, 0, 0, 120]
public int[] GetNewArray(int[] values)
{
int[] newValues = new int[values.Length];
int zeroCount = 0;
int fullProduct = 1;
foreach (int value in values)
{
if(value == 0)
{
zeroCount++;
continue;
}
fullProduct *= value;
}
if(zeroCount > 1) //for sure will return an array with all zeroes
return newValues; //requires ZeroMem if it were C++
for (int i = 0; i < values.Length; i++)
{
if (values[i].value == 0)
newValues[i] = fullProduct;
else if (zeroCount== 1)
newValues[i] = 0;
else
newValues[i] = fullProduct / values[i];
}
}
#include <stdio.h>
#include <stdlib.h>
#define ARRSZ 5
void prodArray(void);
int arr[5] = {1,2,4,6,8};
void main(void)
{
prodArray();
}
void prodArray(void)
{
int i, j;
int prodarr[5];
char idx;
int prod = 1;
for (i = 0; i < 5; i++)
{
prod *= arr[i];
}
for (j = 0; j < 5; j++)
{
prodarr[j] = prod / arr[j];
printf("%d\t",prodarr[j]);
}
}
public class ArrayIndexProduct {
public static void main(String[] args) {
int[] input1 = { 1, 2, 3, 4, 5 };
printArray(productAllOtherValues(input1));
int[] input2 = { 1, 2, 3, 0, 5 };
printArray(productAllOtherValues(input2));
int[] input3 = { 1, 0, 3, 0, 5 };
printArray(productAllOtherValues(input3));
int[] input4 = { 1, 2, 3, 0, 5 };
printArray(productAllOtherValues(input4));
int[] input5 = { 0, 2, 3, 100, 5 };
printArray(productAllOtherValues(input5));
int[] input6 = { 1, 2, 3, 50, 0 };
printArray(productAllOtherValues(input6));
}
public static int[] productAllOtherValues(int[] A) {
int[] res = new int[A.length];
int product1 = 1;
boolean hasZeroValue = false;
int zerosCounter = 0;
for (int i = 0; i < A.length; i++) {
if (A[i] != 0) {
product1 *= A[i];
} else {
hasZeroValue = true;
product1 *= 1;
zerosCounter++;
}
}
for (int i = 0; i < res.length; i++) {
if (A[i] == 0) {
if (zerosCounter > 1) {
res[i] = 0;
} else {
res[i] = product1;
}
} else if (hasZeroValue) {
res[i] = 0;
} else {
res[i] = product1 / A[i];
}
}
return res;
}
private static void printArray(int[] res) {
for (int i : res) {
System.out.print(i + " ");
}
System.out.println();
}
}
public class ArrayIndexProduct {
public static void main(String[] args) {
int[] input1 = { 1, 2, 3, 4, 5 };
printArray(productAllOtherValues(input1));
int[] input2 = { 1, 2, 3, 0, 5 };
printArray(productAllOtherValues(input2));
int[] input3 = { 1, 0, 3, 0, 5 };
printArray(productAllOtherValues(input3));
int[] input4 = { 1, 2, 3, 0, 5 };
printArray(productAllOtherValues(input4));
int[] input5 = { 0, 2, 3, 100, 5 };
printArray(productAllOtherValues(input5));
int[] input6 = { 1, 2, 3, 50, 0 };
printArray(productAllOtherValues(input6));
}
public static int[] productAllOtherValues(int[] A) {
int[] res = new int[A.length];
int product1 = 1;
boolean hasZeroValue = false;
int zerosCounter = 0;
for (int i = 0; i < A.length; i++) {
if (A[i] != 0) {
product1 *= A[i];
} else {
hasZeroValue = true;
product1 *= 1;
zerosCounter++;
}
}
for (int i = 0; i < res.length; i++) {
if (A[i] == 0) {
if (zerosCounter > 1) {
res[i] = 0;
} else {
res[i] = product1;
}
} else if (hasZeroValue) {
res[i] = 0;
} else {
res[i] = product1 / A[i];
}
}
return res;
}
private static void printArray(int[] res) {
for (int i : res) {
System.out.print(i + " ");
}
System.out.println();
}
}
public static int[] productAllOtherValues(int[] A) {
int[] res = new int[A.length];
int product1 = 1;
boolean hasZeroValue = false;
int zerosCounter = 0;
for (int i = 0; i < A.length; i++) {
if (A[i] != 0) {
product1 *= A[i];
} else {
hasZeroValue = true;
product1 *= 1;
zerosCounter++;
}
}
for (int i = 0; i < res.length; i++) {
if (A[i] == 0) {
if (zerosCounter > 1) {
res[i] = 0;
} else {
res[i] = product1;
}
} else if (hasZeroValue) {
res[i] = 0;
} else {
res[i] = product1 / A[i];
}
}
return res;
}
public static int[] productAllOtherValues(int[] A) {
int[] res = new int[A.length];
int product1 = 1;
boolean hasZeroValue = false;
int zerosCounter = 0;
for (int i = 0; i < A.length; i++) {
if (A[i] != 0) {
product1 *= A[i];
} else {
hasZeroValue = true;
product1 *= 1;
zerosCounter++;
}
}
for (int i = 0; i < res.length; i++) {
if (A[i] == 0) {
if (zerosCounter > 1) {
res[i] = 0;
} else {
res[i] = product1;
}
} else if (hasZeroValue) {
res[i] = 0;} else {res[i] = product1 / A[i];}}return res;}
public class Challenge6 {
public static void main(String[] args) {
int[] a={1,2,3,4,5};
int[] b=new int[a.length];
for( int i=0;i<a.length;i++){/* n-1 times*/
int value=1;
for(int j=0;j<a.length;j++){/* n-1 times */
if(a[i]!=a[j])
value=value*a[j];
}
b[i]=value;
}
System.out.println(b[0]);
System.out.println(b[1]);
System.out.println(b[2]);
System.out.println(b[3]);
System.out.println(b[4]);
}
}
Logic is simple :
1) find the sum of total array and divide it by the number in each position
- {1,2,3} -> {6,6,6} -> {6/1, 6/2, 6/3} -> {6,3,2}
void Multiply(int[] arr) {
int[] mapArr = new int[arr.length];
int prod = 1;
for(int i = 0; i < arr.length; i++) {
prod *= arr[i];
}
for(int i = 0; i < mapArr.length; i++) {
mapArr[i] = prod;
}
for(int i = 0; i < mapArr.length; i++) {
arr[i] = mapArr[i] / arr[i];
System.out.println(arr[i]);
}
}
void Multiply(int[] arr) {
int[] mapArr = new int[arr.length];
int prod = 1;
for(int i = 0; i < arr.length; i++) {
prod *= arr[i];
}
for(int i = 0; i < mapArr.length; i++) {
mapArr[i] = prod;
}
for(int i = 0; i < mapArr.length; i++) {
arr[i] = mapArr[i] / arr[i];
System.out.println(arr[i]);
}
}
void Multiply(int[] arr) {
int[] mapArr = new int[arr.length];
int prod = 1;
for(int i = 0; i < arr.length; i++) {
prod *= arr[i];
}
for(int i = 0; i < mapArr.length; i++) {
mapArr[i] = prod;
}
for(int i = 0; i < mapArr.length; i++) {
arr[i] = mapArr[i] / arr[i];
System.out.println(arr[i]);
}
}
public class Experiment {
void Multiply(int[] arr) {
int[] mapArr = new int[arr.length];
int prod = 1;
for(int i = 0; i < arr.length; i++) {
prod *= arr[i];
}
for(int i = 0; i < mapArr.length; i++) {
mapArr[i] = prod;
}
for(int i = 0; i < mapArr.length; i++) {
arr[i] = mapArr[i] / arr[i];
System.out.println(arr[i]);
}
}
public static void main(String[] args) {
Experiment e = new Experiment();
int[] arr = {1,2,3};
e.Multiply(arr);
}
}
Solution of O(n^2):
public int[] prodWithoutIndex(int[] arr) {
int len = arr.length;
int[] prodWithoutIndexArr = new int[len];
for (int i = 0; i < len; i++) {
int prodWithoutIndex = 1;
for (int j = 0; j < len; j++) {
if (j != i)
prodWithoutIndex = prodWithoutIndex*arr[j];
}
prodWithoutIndexArr[i] = prodWithoutIndex;
}
return prodWithoutIndexArr;
}
Better solution with runtime O(n):
public int[] getProdWithoutInd2(int[] arr) {
int len = arr.length;
int prod = 1;
for (int i = 0; i < len; i++)
prod = prod*arr[i];
int[] prodWithoutIndexArr = new int[len];
for (int i = 0; i < len; i++) {
prodWithoutIndexArr[i] = prod/arr[i];
}
return prodWithoutIndexArr;
}
I haven't tested the above code, but should work fine
O(n) solution-
The idea is is keeping the values in array multiplied from the last element index and using the multiplied value for calculating the previous value.
-Traverse array from last
-pickup element from last-1(not required for last element to multiply)
- multiply it multiply it by last element(it is multiplied value for next iteration)
-store it value at current index
-repeat above step until first element
int[] inArr = { 1, 2, 3, 4, 5 };
int[] outArr = new int[inArr.length];
int allProduct = 1;
// n
for (int i = 0; i < inArr.length; i++) {
allProduct *= inArr[i];
}
// n
for (int i = 0; i < inArr.length; i++) {
outArr[i] = allProduct / inArr[i];
}
// O(2n)
System.out.println(Arrays.toString(outArr));
int[] inArr = { 1, 2, 3, 4, 5 };
int[] outArr = new int[inArr.length];
int allProduct = 1;
// n
for (int i = 0; i < inArr.length; i++) {
allProduct *= inArr[i];
}
// n
for (int i = 0; i < inArr.length; i++) {
outArr[i] = allProduct / inArr[i];
}
// O(2n)
System.out.println(Arrays.toString(outArr));
int[] inArr = { 1, 2, 3, 4, 5 };
int[] outArr = new int[inArr.length];
int allProduct = 1;
// n
for (int i = 0; i < inArr.length; i++) {
allProduct *= inArr[i];
}
// n
for (int i = 0; i < inArr.length; i++) {
outArr[i] = allProduct / inArr[i];
}
// O(2n)
System.out.println(Arrays.toString(outArr));
Solution for O(N) that works on cases with 0 in the array
e.g
1 2 3 4 5
120 60 40 30 24
--
1 2 3 0 5
0 0 0 30 0
--
1 0 3 0 5
0 0 0 0 0
--
1 2 3 0 5
0 0 0 30 0
--
0 2 3 100 5
3000 0 0 0 0
--
1 2 3 50 0
0 0 0 0 300
--
- henperetz January 11, 2017