Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Disregarding the typos, you have a few issues
1) Using A[i] within your product increases overflow issues regardless if you use a long
2) Your space doubles (assuming you're given integers).
Yeah, sorry about typos, I am lazy and and abusing careercup lately to see if I can speed code solve a bunch of problems (yeah, I admit it).
1) I know. It's because of the nature of the problem, you can always throw out solution ideas for this.
2) Easy to alter if you are allowed to trample A[] without affecting the O( ) of time and space.
Whether you are using a result[] array or A[] trampled with result, we can still measure AUX space as being outside either, and "num passes" the same way.
I assure you, the simple change to "destruct and store results back in A[]" code keeps it
~2 passes
O(1) aux. space
I took the liberty of commenting your idea in return.
very 1st soln comes to my mind is...two steps
(1)in 1st scan multiply all array elements and store this value into a variable x
(2)and now in 2nd scan replace each array elements as..a[i]=x/a[i];
time complexity:-O(n)+O(n)=O(N)......space -O(1)
Thats nice solution, But there are many case where this approach can break your solution.
1> if 1st element is 0 than the whole multiplication will be zero. Also this apply to the last element.
2> Your multiplication can overflow if large input is provided. Large in terms of array size or element it self: In this case you have to use BigInteger in java
This is solvable by using recursion in place.
Given the array as below,
idx_1, idx_2....idx_i-1, idx_i, idx_i+1 ... idx_j
You'll need to find the products of Pi(idx_1,idx_i-1) and Pi(idx_i+1,idx_j) for any idx_i. Of course, you have the corner cases of Pi(idx_2,idx_j) and Pi(idx_1,idx_j-1). These are easily solvable with your recursion method input and your recursion method output.
That is, for every call onto the recursion method, you can enter Pi(idx_1,idx_i-1) and when you exit the stack, you can return Pi(idx_i+1,idx_j). Thus,you have both products available for you for idx_i.
This leaves you with O(n) time and O(1) space. However, if you have a huge array of numbers, it can be problematic because of the stack.
You could have picked better notation , because idx, three letters just get in the way.
Your recursion would be O(N^2) I think, just like the iterative brute force.
But there would be overlapping subproblems and optimal substructure (because, the PI(something) and PI(otherthing) in your post above overlaps for other idx positions) , so you can memoize your recursive function to give O(N).
And neither naive recursion nor memoized are O(1) aux. space.
Or you can bottom up DP for the same idea and fill out a suffixproduct[] array, then sweep from left to right, and at each position i
1) Calculate result[i] = prefixproduct * suffixproduct[i]
2) Update prefixproduct with A[i]
~2 linear passes, ~1 linear aux. space (suffix product[])
....
But all this can be beaten with ~2 passes, and O(1) aux. space
without any recursion, nor memoization, nor DP.
I don't see the potential of overlaps in equations made. Are you assuming that the recursion would require to go back to 0 for each product?
Of course, there is problems with this solution as I stated. I went ahead and implemented the recursion. It's been awhile, so let me know if you have concerns or what not.
public static void getIntegers(int[] a, int c, int idx) {
// push down a[i] down to avoid product
// for a[j], this pushes down Pi(j,j)
a[idx-1] = a[idx];
if (idx < ( a.length - 1)) {
getIntegers(a,c*a[idx],idx+1);
// push down Pi(i,j)
a[idx-1] = a[idx]*a[idx-1];
// assign Pi(0,i-1)*Pi(i+1,j)
a[idx] = c*a[idx];
} else {
// assign P(0,j-1)
a[idx] = c;
}
}
import java.math.BigInteger;
public class ProductTest {
public static void main(String[] args) {
int[] arr = {5,3,6,8,12,4,7,0};
BigInteger bigInt = new BigInteger("1");
int flagToZero = 0;
for(int i=0; i<arr.length;i++){
if(arr[i] != 0){
bigInt = bigInt.multiply(new BigInteger(String.valueOf(arr[i])));
}
else{
flagToZero = 1;
}
}
System.out.println("Product of complete Array : " + bigInt);
BigInteger remainingProducts;
if(flagToZero == 1){
for(int i=0; i<arr.length;i++){
if(arr[i] != 0){
System.out.println("Product of remaining elements : " + 0);
}
else{
System.out.println("Product of remaining elements : " + bigInt);
}
}
}
else{
for(int i=0; i<arr.length;i++){
if(arr[i] != 0){
remainingProducts = bigInt.divide(new BigInteger(String.valueOf(arr[i])));
System.out.println("Product of remaining elements : " + remainingProducts);
}
}
}
}
}
public class Mul_remai_nos {
public static void multipy(int[] a)
{
int multi_result = 1;
for(int i : a)
{
multi_result = multi_result*i;
}
for(int j=0;j< a.length;j++)
{
a[j] = multi_result/a[j];
}
}
public static void main(String[] args) {
int[] a = {1,2,3,4};
for(int i : a)
System.out.print(i+"\t");
multipy(a);
System.out.println();
for(int i : a)
System.out.print(i+"\t");
}
}
public class ArrayProduct {
public static void product(double arr[]) {
// Traverse the array linearly
for(int i = 1; i<= arr.length(); i++){
double num = arr[0]; // store the first number
int j = 0;
double multiply = 1.0;
// Left Shift the elements and multiply with every next number.
for(j = 0; j<arr.length() - 1; j++){
arr[j] = arr[j+1];
multiply = multiply * arr[j];
}
arr[j] = num;
System.out.println(multiply);
}
}
}
void getele()
{
int a[4] = {1,2,4,3};
int b[4] = {1,1,1,1};
int i =0,j = 0;
for(i = 0; i < 4; i++)
{
for(j = 0; j < 4; j++)
{
if(j == i)
{
continue;
}
b[i] *= a[j];
}
printf(" %d ", b[i]);
}
}
Is this OK?
package com.ashish;
public class ElementsProductinArray
{
private long[] longArray = null;
public ElementsProductinArray(){}
public ElementsProductinArray(long[] longArr)
{
this.longArray = longArr;
}
public void productOfElement()
{
for(int i=0;i<longArray.length;i++)
{
System.out.println(" "+getProduct(longArray, i));
}
}
public long getProduct(long[] ar, int index)
{
long product =1;
for(int i=0;i<ar.length;i++)
{
if(i==index)
continue;
else
product = product*ar[i];
}
return product;
}
public static void main(String[] ar)
{
ElementsProductinArray eA = new ElementsProductinArray(new long[]{1,2,4,3});
eA.productOfElement();
}
}
public class Mul {
static int arr[] = {1,1,2,3,4,5,0};
static void findMul(){
int zeroCount = 0;
int mul = 1;
for(int i=0; i < arr.length; i++){
if(arr[i] == 0){
zeroCount++;
if(zeroCount == 2)
break;
}
else{
mul = mul * arr[i];
}
}
if(zeroCount == 2){
for(int i=0; i < arr.length; i++){
arr[i] = 0;
}
}
else if(zeroCount == 1){
for(int i=0; i < arr.length; i++){
if(arr[i] == 0)
arr[i] = mul;
else
arr[i] = 0;
}
}
else{
for(int i=0; i < arr.length; i++){
if(arr[i] == 0)
arr[i] = mul;
else
arr[i] = mul/arr[i];
}
}
for(int i=0; i < arr.length; i++){
System.out.append(arr[i] +"\t");
}
}
public static void main(String args[]){
findMul();
}
}
static void prodArrByDivisionOpr(int []A){
int pro=1, l=A.length;
int []B=new int [l];
int []c=new int [l];
for(int i=0; i<l; i++){
B[i]=pro*A[i];
pro=B[i];
}
int p2=1;
for(int i=l-1; i>=0; i--){
c[i]=p2*A[i];
p2=c[i];
}
A[0]=c[1];
A[l-1]=B[l-2];
for(int i=1; i<l-1; i++){
A[i]=B[i-1]*c[i+1];
}
for(int a:A){
System.out.print(a+" ");
}
}
if (input.length ==0)
return;
output[0]=input[0];
for(int i=1;i <input.length;i++)
{
output[i]=output[i-1]*input[i-1];
System.out.println(output[i]);
}
int temp=input[input.length-1];
for (int i=input.length-2;i>=0 ;i--)
{
output[i]=output[i]*temp;
temp=temp*input[i];
}
for(int i=0; i< output.length;i++)
{
System.out.println(output[i]);
}
package com.company.careercup;
public class ArrayProduct {
static public void arrayProduct(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(" " + a[i]);
}
System.out.println();
int product = 1;
int flag = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] == 0) {
flag++;
} else {
product *= a[i];
}
}
for (int i = 0; i < a.length; i++) {
if (a[i] == 0) {
if (flag > 1) {
a[i] = 0;
} else {
a[i] = product;
}
} else if (flag != 0) {
a[i] = 0;
} else {
a[i] = product / a[i];
}
}
System.out.println();
for (int i = 0; i < a.length; i++) {
System.out.print(" " + a[i]);
}
}
public static void main(String[] args) {
int a[] = { 1, 0, 3, 0 };
arrayProduct(a);
}
}
You can do LinkedList addition and multiplication; so you can handle overflow situations.
- S O U N D W A V E October 22, 2013//assuming integers (modify as desired), and input array is A[ ] int zeropos= -1; long product=1; int result[A.length] = {0}; //begins life as all 0's // assume your function can modify result[ ] on behalf of calling function for(i=0; i < A.length ; i++) { if( A[i] == 0 ) { if( zeropos != -1 ) return; //saw 2 zeros, result[ ] all zeros is valid else zeropos=i, continue; //position of zero } product *= A[i]; // accumulate product of nonzero elements } //if we had 1 zero in A[ ], result[ ] is all zeroes except at zeropos: if(zeropos != -1) A[zeropos]=product, return; //we had no zeroes in A[] for(i=0; i < A.length ; i++) result[i] = prod/A[i]; return;