Amazon Interview Question SDE1s
Team: Hyderabad
Country: India
Interview Type: Phone Interview
Not sure if you wanna do that. If it has a zero somewhere then I think the correct behaviour is to have all the other elements (except the zero element) yield zeroes.
public static int[] replaceTerms(int[] a ){
int product = 1;
int zeroes = 0 ;
for (int n : a) {
if(n == 0){
zeroes++;
continue;
}
product*=n;
}
if(zeroes>=2) {
Arrays.fill(a, 0);
return a;
}else if(zeroes == 1){
for (int i = 0 ; i<a.length ;i++) {
if (a[i] == 0) a[i] = product;
else a[i] = 0;
}
}else {
for (int i = 0 ; i<a.length ;i++)
a[i] = product/a[i];
}
return a;
}}
The problem can be solved via brute-force O(N^2) or in optimal O(N). I am proposing the following solution:
(i) compute tow cumulative products 'cpl[]' and 'cpr[]', one form left to right, the latter one form right to left
(ii) for each position 'idx' in the array compute the product of the left and right positions in respective cumulative arrayd, hence a[idx] = cpl[idx-1]*cpr[idx+1]; If index is out of bounds ignore it;
Notice that the left cumulative product need not be computed as you can keep track of the cumulative product 'on fly' as you finally go through the array a[]. In the following code the cpl[] is used for brevity.
A sample code is shown below:
public void exclusiveProduct(int a[]) {
int N = a.length;
int[] cpl = new int[N]; % cumulative products
int[] cpr = new int[N];
// Initialize cumulative products
cpl[0] = a[0];
cpr[N-1] = a[N-1];
for (int k = 1; k<N ;k++) {
int j = N-1-k;
cpr[j] = cpl[j+1] * a[j];
cpl[k] = cpl[k-1] * a[k];
}
// Replace elements within the input array
for (int k = 0; k<N ;k++) {
int left = (k-1)>0?cpl[k-1]:1;
int right = (k+1)<N?cpr[k+1]:1;
a[k] = left*right;
}
}
I hope it works.
function product( a ) {
if ( a.length ) return a.pop () * product ( a );
return 1;
};
function f ( arr ) {
var newArr = [];
if ( arr.slice () ) {
for ( var i = 0; i < arr.length; i++ ) {
var temp = Array.concat ( arr.slice ( 0, i ), arr.slice ( i + 1 ) );
newArr.push ( product ( temp ) );
};
};
return newArr;
};
O(n^2) but good starting ground before optimizing your code:
void arrayProduct(int arr[]) {
int arrLength = arr.length();
if (arrLength > 1) {
int product = 1;
for (int j = 0; j < arrLength ; j++) {
if (j != i) {
product *= arr[j];
}
}
arr[i] = product;
product = 1;
}
}
My bad, rushed the typing of the code after writing it on paper:
void arrayProduct(int arr[]) {
int arrLength = arr.length();
if (arrLength > 1) {
for (int i = 0; i < arrLength; i++) {
int product = 1;
for (int j = 0; j < arrLength; j++) {
if (j != i) {
product *= arr[j];
}
}
arr[i] = product;
product = 1;
}
}
}
Can be done in O(n)
void calculateArray(int []a){
int product=1;
for(int i=0;i<a.length;i++){
product=product*a[i];
}
for(int i=0;i<a.length;i++){
a[i]=product/a[i];
}
public static int[] arrayOfProduct(int[] a) {
int product=1;
int [] arrayProduct = new int[a.length];
for (int i = 0; i < a.length; i++) {
arrayProduct[i] = product;
product*=a[i];
}
product=1;
for (int i = a.length-1; i >= 0; i--) {
arrayProduct [i] *= product;
product*= a[i];
}
return arrayProduct ;
}
It can be done using an auxillary array. For each element in array A, store product of previous elements in auxillary array store[] in first pass from left to right. And in second pass, keep product of elements from right to left.
Example A[]={5,7,8,2}, Store[]={1,1,1,1}
Now move from left to right and fill Store[] like this,
Store[]={1,5,35,280}
Store[i] gives the value of product of elements on left side of A[i], excluding A[i].
Now move from right to left, keep product of right elements in a variable and replace the product accordingly.
Take a look at my implementation for clear understanding :)
void replaceElem(int arr[],int n)
{
int *store = new int[n];
memset(store,1,sizeof(store)); // Initialize each cell with 1
int temp=1;
for(int i=0;i<n;i++) // this stores product of left elements excluding the element
{
store[i]=temp;
temp=temp*arr[i];
}
temp=1;
for(int i=n-1;i>=0;i--) // this
{
store[i]=temp*store[i];
temp=temp*arr[i];
arr[i]=store[i]; // it replace the appropriate value
}
free(store);
}
import java.util.List;
import java.util.LinkedList;
public class ReplaceMatrixByProducts
{
public static void main(String[] args)
{
int[] a={2,3,1,4};
int product=1;
int zeroCount=0;
//Get product of all elements
for (int i = 0; i < a.length; i++)
{
if(a[i]==0) zeroCount++;
product*=product;
}
for (int i = 0; i < a.length; i++)
{
/*
* if there are more than 2 zeros in array then all the prodcuts will be zero
*/
if(zeroCount>1)
{
a[i]=0;
}
else if(zeroCount==1) //there is only one zero
{
if(a[i]==0)
a[i]=product;
else
a[i]=0;
}
else //there are no zeros
{
a[i]=product/a[i];
}
}
}
class Ex {
public static void multiplyRest(int[] a) {
int product = 1;
int zIdx = -1;
for (int i = 0; i < a.length; i++) {
if (a[i] != 0) {
product *= a[i];
} else {
if (zIdx != -1) {
fillWithZeros(a);
return;
}
zIdx = i;
}
}
if (zIdx != -1) {
fillWithZeros(a);
a[zIdx] = product;
return;
}
for (int i = 0; i < a.length; i++) {
a[i] = product / a[i];
}
}
private static void fillWithZeros(int[] a) {
for (int i = 0; i < a.length; i++) {
a[i] = 0;
}
}
}
class Ex {
public static void multiplyRest(int[] a) {
int product = 1;
int zIdx = -1;
for (int i = 0; i < a.length; i++) {
if (a[i] != 0) {
product *= a[i];
} else {
if (zIdx != -1) {
fillWithZeros(a);
return;
}
zIdx = i;
}
}
if (zIdx != -1) {
fillWithZeros(a);
a[zIdx] = product;
return;
}
for (int i = 0; i < a.length; i++) {
a[i] = product / a[i];
}
}
private static void fillWithZeros(int[] a) {
for (int i = 0; i < a.length; i++) {
a[i] = 0;
}
}
}
First, pass through the array and check how many 0s there are. If there is more than one zero, then all the array elements in the output array MUST be 0.
If there is only one 0, then replace it with a 1.
After our first pass through, we will go through the array and get the product of all the array elements. let's call this product x.
Finally, we go through the array and for each element "e" in the array, its corresponding value in the new array will be x/e.
This algorithm would, thus, run in O(3n) = O(n).
I'm pretty sure that it would also work with negative numbers.
public class Code {
public static void main(String[] args) {
Integer[] arryInt = {2,3,5};
Integer[] clone = arryInt.clone();
for(int i=0 ; i<arryInt.length; i++) {
int product = 1;
for(int j=arryInt.length-1;j>=0;j--)
{
if(j != i)
product = product * arryInt[j];
}
clone[i] = product;
}
System.out.println(Arrays.toString(clone));
}
}
public class Code {
public static void main(String[] args) {
Integer[] arryInt = {2,3,5};
Integer[] clone = arryInt.clone();
for(int i=0 ; i<arryInt.length; i++) {
int product = 1;
for(int j=arryInt.length-1;j>=0;j--)
{
if(j != i)
product = product * arryInt[j];
}
clone[i] = product;
}
System.out.println(Arrays.toString(clone));
}
}
public static void main(String[] args) {
Integer[] arryInt = { 2, 3, 5 };
Integer[] clone = arryInt.clone();
for (int i = 0; i < arryInt.length; i++) {
int product = 1;
for (int j = arryInt.length - 1; j >= 0; j--) {
if (j != i)
product = product * arryInt[j];
}
clone[i] = product;
}
System.out.println(Arrays.toString(clone));
}
function replaceArray(int[] arrArg) {
arrProd=1;
zerosCount=0;
oneZeroIndex=arrArg.length;
for(int i=0;i<arrArg.length;i++) {
if (arrArg[i]==0) {
zerosCount+=1;
oneZeroIndex=i;
} else {
arrProd *= arrArg[i]
}
if (zerosCount>1) {
//if more than one zero found then return array with zeros
for(int i=0;i<arrArg.length;i++) {
arrArg[i]=0;
return;
}
}
}
//I am just doing some fancy stuff here to eliminate the need of checking the Zero in each loop since I already
//have it's index in the first loop
//more complex, but more efficient.
for(int i=0; i<oneZeroIndex; i++) {
arrArg[i] = arrProd / arrArg[i];
}
//if no zeros found then completed
if (oneZeroIndex == arrArg.length) {
return;
}
arrArg[oneZeroIndex] = arrProd;
//This loop will only run if we have a zero.
for(int i=oneZeroIndex+1;i<arrArg.length;i++)
{
arrArg[i] = arrProd/arrArg[i];
}
return;
}
function replaceArray(int[] arrArg) {
arrProd=1;
zerosCount=0;
oneZeroIndex=arrArg.length;
for(int i=0;i<arrArg.length;i++) {
if (arrArg[i]==0) {
zerosCount+=1;
oneZeroIndex=i;
} else {
arrProd *= arrArg[i]
}
if (zerosCount>1) {
//if more than one zero found then return array with zeros
for(int i=0;i<arrArg.length;i++) {
arrArg[i]=0;
return;
}
}
}
//I am just doing some fancy stuff here to eliminate the need of checking the Zero in each loop since I already
//have it's index in the first loop
//more complex, but more efficient.
for(int i=0; i<oneZeroIndex; i++) {
arrArg[i] = arrProd / arrArg[i];
}
//if no zeros found then completed
if (oneZeroIndex == arrArg.length) {
return;
}
arrArg[oneZeroIndex] = arrProd;
//This loop will only run if we have a zero.
for(int i=oneZeroIndex+1;i<arrArg.length;i++)
{
arrArg[i] = arrProd/arrArg[i];
}
return;
}
#include<stdio.h>
#include<string.h>
int main ()
{
int array_in[] = {1,2,3,4,5};
long long product = 1;
int i;
int array_len = sizeof array_in / sizeof *array_in;
int array_out[array_len];
for (i =0; i < array_len ; i++) {
product = product*array_in[i] ;
}
for (i =0; i < array_len ; i++) {
array_out[i] = product/array_in[i];
printf("RESULT - %d\n", array_out[i]);
}
}
#include<stdio.h>
#include<string.h>
int main ()
{
int array_in[] = {1,2,3,4,5};
long long product = 1;
int i;
int array_len = sizeof array_in / sizeof *array_in;
int array_out[array_len];
for (i =0; i < array_len ; i++) {
product = product*array_in[i] ;
}
for (i =0; i < array_len ; i++) {
array_out[i] = product/array_in[i];
printf("RESULT - %d\n", array_out[i]);
}
}
One could divide the list into two for every element and find the product of each.
def findPdtLists(a,b):
print(a,b,sep='\t')
x=findPdtList(a)
y=findPdtList(b)
return x*y
def findPdtList(a):
pdt=1
for i in a:
pdt=pdt*i
return pdt
def replaceWidPdt(a):
t=[None]*len(a)
for i in range(len(a)):
x=findPdtLists(a[:i],a[i+1:])
t[i]=x
return t
if __name__=='__main__':
a=[1,2,3]
b=replaceWidPdt(a)
print(b)
public int[] product(int[] arr){
int[] returnArray = new int[arr.length];
int zeroElementIndex = -1;
int product = 1;
for(int i=0;i<arr.length;i++){
if(arr[i] == 0){
zeroElementIndex = i;
break;
}else{
product = product * arr[i];
}
}
if(zeroElementIndex != -1){
product =1;
for(int j=0;j<arr.length;j++){
if(j != zeroElementIndex)
{
returnArray[j] = 0;
product = product * arr[j];
}
}
returnArray[zeroElementIndex] = product;
}else{
for(int j=0;j<arr.length;j++){
returnArray[j] = product/arr[j];
}
}
return returnArray;
}
public int[] product(int[] arr){
int[] returnArray = new int[arr.length];
int zeroElementIndex = -1;
int product = 1;
for(int i=0;i<arr.length;i++){
if(arr[i] == 0){
zeroElementIndex = i;
break;
}else{
product = product * arr[i];
}
}
if(zeroElementIndex != -1){
product =1;
for(int j=0;j<arr.length;j++){
if(j != zeroElementIndex)
{
returnArray[j] = 0;
product = product * arr[j];
}
}
returnArray[zeroElementIndex] = product;
}else{
for(int j=0;j<arr.length;j++){
returnArray[j] = product/arr[j];
}
}
return returnArray;
}
public int[] product(int[] arr){
int[] returnArray = new int[arr.length];
int zeroElementIndex = -1;
int product = 1;
for(int i=0;i<arr.length;i++){
if(arr[i] == 0){
zeroElementIndex = i;
break;
}else{
product = product * arr[i];
}
}
if(zeroElementIndex != -1){
product =1;
for(int j=0;j<arr.length;j++){
if(j != zeroElementIndex)
{
returnArray[j] = 0;
product = product * arr[j];
}
}
returnArray[zeroElementIndex] = product;
}else{
for(int j=0;j<arr.length;j++){
returnArray[j] = product/arr[j];
}
}
return returnArray;
}
public int[] product(int[] arr){
int[] returnArray = new int[arr.length];
int zeroElementIndex = -1;
int product = 1;
for(int i=0;i<arr.length;i++){
if(arr[i] == 0){
zeroElementIndex = i;
break;
}else{
product = product * arr[i];
}
}
if(zeroElementIndex != -1){
product =1;
for(int j=0;j<arr.length;j++){
if(j != zeroElementIndex)
{
returnArray[j] = 0;
product = product * arr[j];
}
}
returnArray[zeroElementIndex] = product;
}else{
for(int j=0;j<arr.length;j++){
returnArray[j] = product/arr[j];
}
}
return returnArray;
}
public int[] product(int[] arr){
int[] returnArray = new int[arr.length];
int zeroElementIndex = -1;
int product = 1;
for(int i=0;i<arr.length;i++){
if(arr[i] == 0){
zeroElementIndex = i;
break;
}else{
product = product * arr[i];
}
}
if(zeroElementIndex != -1){
product =1;
for(int j=0;j<arr.length;j++){
if(j != zeroElementIndex)
{
returnArray[j] = 0;
product = product * arr[j];
}
}
returnArray[zeroElementIndex] = product;
}else{
for(int j=0;j<arr.length;j++){
returnArray[j] = product/arr[j];
}
}
return returnArray;
}
public int[] product(int[] arr){
int[] returnArray = new int[arr.length];
int zeroElementIndex = -1;
int product = 1;
for(int i=0;i<arr.length;i++){
if(arr[i] == 0){
zeroElementIndex = i;
break;
}else{
product = product * arr[i];
}
}
if(zeroElementIndex != -1){
product =1;
for(int j=0;j<arr.length;j++){
if(j != zeroElementIndex)
{
returnArray[j] = 0;
product = product * arr[j];
}
}
returnArray[zeroElementIndex] = product;
}else{
for(int j=0;j<arr.length;j++){
returnArray[j] = product/arr[j];
}
}
return returnArray;
}
public int[] product(int[] arr){
int[] returnArray = new int[arr.length];
int zeroElementIndex = -1;
int product = 1;
for(int i=0;i<arr.length;i++){
if(arr[i] == 0){
zeroElementIndex = i;
break;
}else{
product = product * arr[i];
}
}
if(zeroElementIndex != -1){
product =1;
for(int j=0;j<arr.length;j++){
if(j != zeroElementIndex)
{
returnArray[j] = 0;
product = product * arr[j];
}
}
returnArray[zeroElementIndex] = product;
}else{
for(int j=0;j<arr.length;j++){
returnArray[j] = product/arr[j];
}
}
return returnArray;
}
public int[] product(int[] arr){
int[] returnArray = new int[arr.length];
int zeroElementIndex = -1;
int product = 1;
for(int i=0;i<arr.length;i++){
if(arr[i] == 0){
zeroElementIndex = i;
break;
}else{
product = product * arr[i];
}
}
if(zeroElementIndex != -1){
product =1;
for(int j=0;j<arr.length;j++){
if(j != zeroElementIndex)
{
returnArray[j] = 0;
product = product * arr[j];
}
}
returnArray[zeroElementIndex] = product;
}else{
for(int j=0;j<arr.length;j++){
returnArray[j] = product/arr[j];
}
}
return returnArray;
}
void productArray(int arr[], int n)
{
int i, temp = 1;
/* Allocate memory for the product array */
int *prod = (int *)malloc(sizeof(int)*n);
/* Initialize the product array as 1 */
memset(prod, 1, n);
/* In this loop, temp variable contains product of
elements on left side excluding arr[i] */
for(i=0; i<n; i++)
{
prod[i] = temp;
temp *= arr[i];
}
/* Initialize temp to 1 for product on right side */
temp = 1;
/* In this loop, temp variable contains product of
elements on right side excluding arr[i] */
for(i= n-1; i>=0; i--)
{
prod[i] *= temp;
temp *= arr[i];
}
/* print the constructed prod array */
for (i=0; i<n; i++)
printf("%d ", prod[i]);
return;
}
Time Complexity: O(n)
Space Complexity: O(n)
Auxiliary Space: O(1)
public static int[] replaceTerms(int[] a ){
int product = 1;
int zeroes = 0 ;
for (int n : a) {
if(n == 0){
zeroes++;
continue;
}
product*=n;
}
if(zeroes>=2) {
Arrays.fill(a, 0);
return a;
}else if(zeroes == 1){
for (int i = 0 ; i<a.length ;i++) {
if (a[i] == 0) a[i] = product;
else a[i] = 0;
}
}else {
for (int i = 0 ; i<a.length ;i++)
a[i] = product/a[i];
}
return a;
}
If space is not an issue, then another idea besides the
product / array[i]
method is
Let N be the length of the array.
1. Create two temporary arrays,
prodLeft[ N ] & prodRight[ N ],
where, prodLeft[i] contains the product of all elements to the left of array[i], and prodRight[i] contains the product of all elements to the right of array[i]
2. for each element, replace
array[i] = prodLeft[i] * prodRight[i]
So the implementation of this code would look like
public void ReplaceWithProducts(int[] array)
{
if (array.length == 1)
return;
int count = CountZeroes(array);
if (count > 1)
{
// If there are more than 1 0's,
// all the elements will be ultimately 0
replaceWithZeros(array);
return;
}
if (count == 1)
{
// If there's only 1 zero, only the zero
// element will have a non-zero value.
// All other elements will be 0.
long product = 1;
int index = 0;
for (int i = 0; i < array.length; i++)
{
if(array[i] == 0)
{
index = i;
continue;
}
// Compute the product so far.
product = product * array[i];
// Keep setting the element to zero since
// we already have the element's contribution
// in the product.
array[i] = 0;
}
array[index] = product;
return;
}
// If there are no 0's.
int[] prodLeft = new int[array.length];
int[] prodRight = new int[array.length];
prodLeft[0] = 1; // Since there're no elements to the left
prodRight[array.length - 1] = 1; //Since there're no elements to the right of the last one.
for (int i = 1; i < array.length; i++)
{
prodLeft[i] = array[i-1] * prodLeft[i-1];
}
for (int i = array.length -2; i >= 0; i--)
{
prodRight[i] = array[i+1] * prodRight[i+1;]
}
for (int i = 0; i < array.length; i++)
{
array[i] = prodLeft[i] * prodRight[i];
}
}
public int CountZeroes(int[] array)
{
int count = 0;
for (int i = 0; i < array.length; i++)
{
if(array[i] == 0)
{
count++;
}
}
return count;
}
public void replaceWithZeros(int[] array)
{
for (int i=-; i<array.length; i++)
{
array[i] = 0;
}
}
public class ArrayProduct {
static int arr[] = {1,2,3};
static int prod[]=new int[arr.length];
public static void main(String[] args) {
product(arr);
}
public static void product(int[] a)
{
int array_size=arr.length;
int temp=1;
boolean zero_element=false;
for(int i=0;i<array_size;i++)
{
prod[i]=temp;
temp=temp*a[i];
if(a[i]==0)
break;
}
temp=1;
for(int i=array_size-1;i>=0;i--)
{
prod[i]=prod[i]*temp;
temp=temp*a[i];
}
for(int i=0;i<array_size;i++)
{
System.out.print(prod[i] + " ");
}
}
}
public class ArrayProduct {
static int arr[] = {1,2,3};
static int prod[]=new int[arr.length];
public static void main(String[] args) {
product(arr);
}
public static void product(int[] a)
{
int array_size=arr.length;
int temp=1;
boolean zero_element=false;
for(int i=0;i<array_size;i++)
{
prod[i]=temp;
temp=temp*a[i];
if(a[i]==0)
break;
}
temp=1;
for(int i=array_size-1;i>=0;i--)
{
prod[i]=prod[i]*temp;
temp=temp*a[i];
}
for(int i=0;i<array_size;i++)
{
System.out.print(prod[i] + " ");
}
}
}
if one element is zero, find the product p of all elements except zero. Set zero as p, rest as zero.
arr=[1,3,0,2]
p=6
arr=[0,0,6,0]
if more than one element is zero, replace every element with zero
arr=[1,0,2,0,3]
arr=[0,0,0,0,0]
else
find product p of all elements
replace every element with p/element
arr=[1,3,4,2]
p=24
arr=[24,8,6,12]
Step 1: Calculate product of the entire array
Step 2: ans[i]=product/element[i]
Here element refers to the current element at a particular index. ans is the new element that will replace it.
Complexity: O(n)+O(n)=O(n)
public static void ArrayProduct(int arr[])
{
int product = 1;
System.out.println(Arrays.toString(arr));
for(int i = 0; i < arr.length; i++)
product *= arr[i];
for (int i = 0; i < arr.length; i++)
arr[i] = product / arr[i];
System.out.println(Arrays.toString(arr));
}
Input: [2, 3, 4, 5, 6]
Output: [360, 240, 180, 144, 120]
Let me know if i am wrong.
for(int i = 0; i < arr.length; i++)
{
if(arr[i] == 0)
continue;
product *= arr[i];
}
for (int i = 0; i < arr.length; i++)
{
if(arr[i] == 0)
continue;
arr[i] = product / arr[i];
}
I guess this will do.
This does not work correctly. If arr[i] is 0, it should be the product of all the other elements when you are done, you code leaves it to be 0. Also, all other elements should be 0 in that case, not product / arr[i], since product is missing the multiplication by 0.
The case with zero is easy to generalize. Scan for zeroes as you calculate product. If you fine only one zero, the element with its index is the product of all other elements. If you find more than one zero, all element will be zero at the end, no need to calculate further. If none of them are zero, you can do the product/a[i] thing at the end.
Calculate product of entire array checking for zero's and neglecting them.
- africa1001 February 20, 2015On second pass through array if we calculate for each element product/element[i] if element is nonzero and assign for each zero element just product