Linkedin Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

public static int[] getProdArray(int[] data){
		int numberOfZeros = 0, prod = 1;

		for(int i=0;i<data.length;i++){
			if(data[i]!=0)
				prod *= data[i];
			else
				numberOfZeros++;

			if(numberOfZeros>=2){
				prod = 0;
				break;
			}
		}

		int[] result = new int[data.length];
		for(int i=0;i<data.length;i++){
			if(data[i]!=0)
				result[i] = prod / data[i];
			else
				result[i] = prod;
		}

		return result;
	}

- Byll September 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

hmm! Simple and straight...
Thanks

- Jerky September 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

a[]={1,2,0,3,4};
Shouldnt the output be res[]={0,0,24,0,0};
I am not sure why you are ignoring 0 s in your product. Please correct me if I havent understood the question correctly.

- Learnder November 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Any comments about the limitations imposed due to prod being int? How to exactly put this into words.

- bhumik3 November 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

doesn't work when numZero=1

- goalchaser December 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Should separate numOfZero == 0 case and numOfZero == 1 case

public class SelfExcludingProduct {
	public int[] selfExcludingProduct (int[] input) {
		if (input == null) 
			throw new NullPointerException ("Null input array!");
		int[] productArray = new int[input.length];
		if (input.length == 0) 
			return productArray;
		int product = 1;
		int numOfZeros = 0;
		for (int i = 0; i < input.length; i++) {
			if (input[i] != 0)
				product *= input[i];
			else
				numOfZeros++;
			if (numOfZeros >= 2) {
				return productArray;
			}
		}
		for (int i = 0; i < input.length; i++) {
			if (numOfZeros == 0) {
				productArray[i] = product / input[i];
			}
			else {
				if (input[i] == 0) 
					productArray[i] = product;
				else
					productArray[i] = 0;
			}
				
		}
		
		return productArray;
			
	}

}

- DoraShine December 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

for input : {3, 0, 4, 1}; this code might not work ..output should come as : {0,12,0,0}
but will come out to be diff i.e.{4,12,3,12}

so a little correction here:

public static int[] selfExcludingProduct(int[] input){
		int[] result = new int[input.length];
		int numberOfZeros = 0;int prod=1;
		for(int i=0;i<input.length;i++){
			if(input[i]!=0){
				prod *=input[i];
			}
			else{
				numberOfZeros++;
			}
			if(numberOfZeros>=2){
				prod = 0;
				break;
			}
		}
		
		for(int i =0;i<input.length;i++){
			if(input[i]!=0){
				result[i]  = prod/input[i];
			}
			else{
				result[i] = prod;
				prod = 0;
			}
		}
		return result;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = {3, 0, 4, 1};
		int[] result = selfExcludingProduct(arr);
		for(int i:result){
			System.out.println(i);
		}
	}

- Resh January 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

public int[] selfExcludingProduct(int[] input) 
{
	int[] output = new int[input.length];
	for(int i = 0; i<input.length; i++)
	{
		int product = 1;
		for(int j = 0; j<input.length; j++)
			if (j!=i)
				product*=input[j];
		output[i] = product;
	}
	return output;
}

Easy.

- Grendus April 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 8 votes

It can be done in O(n) time.
1) You have to compute the product from the whole array
2) Then the result can be computed in the following way

output[i] = product / input[i]

3) You just have to take care of the corner cases which is zero elements
a) If the array has more then one zero elements then the output will contain only zeros
b) If the array has one zero then the output for the input[i] == 0 is equal product from the remaining elements and the remaining elements are equal 0.

You can check my implementation for better understanding though it was down-voted by someone who misunderstand that solution.

- thelineofcode April 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int [] product(int [] input){
int [] dp = new int [input.length] ;
int [] front = new int [input.length] ;
int [] rear = new int [input.length] ;
front [0] = 1 ;
rear [rear.length - 1] = 1;
for (int i = 1 ; i < front.length ; ++i){
front [i] = front [i - 1] * input [i - 1] ;

}


for (int i = rear.length - 2; i >= 0 ; --i){
rear [i] = rear[i + 1] * input [ i + 1] ;

}

for (int i = 0 ; i < input.length ; ++i){
dp [i] = front [i] * rear [i];
}


return dp;
}

- Scott April 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int [] product(int [] input){
		int [] dp = new int [input.length] ;
		int [] front = new int [input.length] ;
		int [] rear = new int [input.length] ;
		front [0] = 1 ;
		rear [rear.length - 1] = 1;
		for (int i = 1 ; i < front.length ; ++i){
			front [i] = front [i - 1] * input [i - 1] ;
			
		}
		
		
		for (int i = rear.length - 2; i >= 0 ;  --i){
			rear [i] = rear[i + 1] * input [ i + 1] ;
		
		}
		
		for (int i = 0 ; i < input.length ; ++i){
			dp [i] = front [i] * rear [i];
		}
		
		
		return dp;

}

- Scott April 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class SelfExcludingProduct {



public static int[] selfExcludingProduct(int arr[]){
if( arr == null ) return null;
int selfExcludingProduct[] = new int[arr.length];
int leftProduct =1;
selfExcludingProduct[0] = 1;
for(int i =1 ; i < arr.length ; i++){
leftProduct = leftProduct*arr[i-1] ;
selfExcludingProduct[i] =leftProduct;
}
printArray(selfExcludingProduct);
leftProduct =1;
for(int i = arr.length -2 ; i >= 0 ; i--){
leftProduct = leftProduct*arr[i+1] ;
selfExcludingProduct[i] =selfExcludingProduct[i]*leftProduct;
}
printArray(selfExcludingProduct);
return selfExcludingProduct;
}
public static void main(String args[]){
int arr[] ={3, 1, 4, 2,10};
printArray(arr);
selfExcludingProduct(arr);
}

public static void printArray(int arr[]){
if( arr == null ) return ;
for(int i= 0 ; i <arr.length ; i++) {
System.out.print(arr[i]+" ");
}
System.out.println();

}
}

- Anonymous April 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] selfExcludingProduct(int[] input) {
		
		if(input == null || input.length == 0)
			return null;
		
		int product = 1;
		int nonZeroProduct = 1;
		
		int[] prod = new int[input.length];
		
		for(int i : input) {
			if(i!=0) {
				nonZeroProduct*=i;
			}
			product*=i;
		}
		
		for(int i=0; i< input.length;i++) {
			if(input[i] == 0) {
				prod[i] = nonZeroProduct;
			}
			else {
				prod[i] = product/input[i];
			}
		}
		
		return prod;
	}

This should cover a case where ONLY one element in array is 0, the self-excluding product of 0 is a non-zero value.

{3,1,4,2,0} ==> {0, 0, 0, 0, 24}

- balaji2104 April 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Although very good, fails a corner case of input array having 2 zeros - that should be handled as well.

Expected Result : {3,1,4,0,0} ==> {0, 0, 0, 0, 0}

Your algo would give : {3,1,4,0,0} ==> {0, 0, 0, 12, 12}

- tinybells April 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void Main(string[] args)
        {
            var input = new List<int>() { 3, 1, 4, 2 };
            var results = GetProductsOfAllOthers(input);

            Console.WriteLine("input: " + string.Join(", ", input.Select(e => e.ToString()).ToArray()));
            Console.WriteLine("output: " + string.Join(", ", results.Select(e => e.ToString()).ToArray()));
            Console.ReadLine();
        }

        static List<int> GetProductsOfAllOthers(List<int> list)
        {
            int firstZeroIndex = -1;

            int product = 1;
            
            for (int i = 0; i < list.Count; ++i)
            {
                var newProduct = product * list[i];
                if (newProduct == 0)
                {
                    if (firstZeroIndex == -1)
                    {
                        firstZeroIndex = i;
                    }
                    else
                    {
                        product = 0;
                        break;
                    }
                }
                else
                {
                    product = newProduct;
                }

            }

            var results = new List<int>();

            for (int i = 0; i < list.Count; ++i)
            {
                if (list[i] == 0 && product != 0)
                {
                    results.Add(product);
                }
                else if (firstZeroIndex == -1)
                {
                    results.Add(product / list[i]);
                }
                else
                {
                    results.Add(0);
                }
            }

            return results;
        }

- dgroft April 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function findMultiplication(arr) {
    var result = [], start = 0;
    
    while (start < arr.length) {
        var mul = 1;
        for (var i=0; i < arr.length; i++) {
            if (start !== i) {
                mul *= arr[i];
            }   
        }
        result.push(mul);
        start++;
    }
    
    return result;

}

- Anonymous April 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function findMultiplication (arr) {
    var result = [], start = 0;
    
    while (start < arr.length) {
        var mul = 1;
        for  (var i = 0; i <  arr.length;  i++)  {
            if (start !== i) {
                mul *= arr[i];
            }   
        }
        result.push(mul);
        start++;
    }
    
    return result;

}

- findSolution April 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function findMultiplication(arr) {
var result = [], start = 0;

while (start < arr.length) {
var mul = 1;
for (var i=0; i < arr.length; i++) {
if (start !== i) {
mul *= arr[i];
}
}
result.push(mul);
start++;
}

return result;

}

- findSolution April 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

only allocate one array instead of two arrays in some of the solutions above. also handles 0.

public int[] selfExcludingProduct(int[] input) {
    // implementation...
    
    int [] front = new int[input.length];
    front[0] = 1;
    for(int i =1;i<front.length;i++){
        front[i] = front[i-1]*input[i-1];
    }
    
    int temp = 1;
    for(int i =front.length-1;i>=0;i--){
        front[i] = front[i]*temp;
        temp*=input[i];
    }
    
    return front;

}

- sh88990 April 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) algo
get product of all elements
for each element display (product/element[i])

- kevseb1993 August 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class ExcludingProductArray {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] input = { 3,1,4,0,0 };
		selfExcludingProduct(input);
		for (int i = 0; i < input.length; i++) {
			System.out.print(input[i] + " ");
		}

	}

	private static void selfExcludingProduct(int[] input) {
		// TODO Auto-generated method stub
		int ArrayProduct = 1;
		int zeroProduct = 1;
		int zeroElementCount = 0;
		for (int i = 0; i < input.length; i++) {
			if (input[i] != 0 && zeroElementCount < 2) {
				zeroProduct *= input[i];
			}
			if (input[i] == 0) {
				zeroElementCount++;
				if (zeroElementCount > 1)
					zeroProduct = 0;
			}
			ArrayProduct *= input[i];
		}
		for (int i = 0; i < input.length; i++) {
			if (input[i] == 0)
				input[i] = zeroProduct;
			else
				input[i] = (ArrayProduct / input[i]);
		}
	}
}

- sLion August 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Guys, you are seriously messing this one up. The top answer is 12 lines of code and in O(N^2)

Here's the most elegant solution I can think of in O(n):

def transform(array):
    product = reduce( lambda x , y : x * y , array )
    return map ( lambda x : product / x, array)

That's it.

For those a little less familiar with map and reduce:

def transform(array):
	product = 1
	for num in array:
		product*=num
	return [product/num for num in array]

- Anjishnu October 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Mr. Genius, How would your elegant solution handle an array with zeros ?
[2, 3, 4, 0, 7, 8, 0, 1] ??

- Rookie October 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you are hired!

- your.boss October 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I used C++ and there are three situations.
1) Two zeros in original array - all entries in the result should be zero
2) One zero in original array - all entries except the one has zero in original array should be zero and the one has zero should has the product value
3) No zero in original array - just use product / arr[i]

int[] fill_product(int arr[]){
	int product = 1;
	int numOfZeros = 0;
	int size = sizeof(arr)/sizeof(arr[0]);

	for(int i = 0; i<size; i++){
		if(arr[i]==0)
			numOfZeros++;
		else
			product *= arr[i];

		if(numOfZeros>1)
			break;
	}

	int result[size];
	fill(result,result+size,0);

	if(numOfZeros>=2)
		return result;
	
	if(numOfZeros==1){
		for(int i = 0; i<size; i++){
			if(arr[i]==0)
				result[i] = product;
		}
		return result;
	}

	for(int i = 0; i<size; i++)
		result[i] = product / arr[i];

	return result;
}

- mosaic0123 January 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For your point- 1) Two zeros in original array - all entries in the result should be zero.
I think two zeros are fine as well, if one zero is at zero index.

- Sunny January 19, 2016 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
-1
of 5 votes

Formatted version:

public static void main(String[] args) {
        int prod = 1;
        int noOfZeros = 0;
        int[] arr = { 3, 0, 0, 2 };
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != 0) {
                prod *= arr[i];
            } else {
                noOfZeros++;
                if (noOfZeros > 1) {
                    break;
                }
            }
        }
        if (noOfZeros > 1) {
            Arrays.fill(arr, 0);
        } else {
            for (int i = 0; i < arr.length; i++) {
                if (noOfZeros == 1) {
                    if (arr[i] == 0) {
                        arr[i] = prod;
                    } else {
                        arr[i] = 0;
                    }
                } else {
                    arr[i] = prod / arr[i];
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }

- thelineofcode April 02, 2014 | Flag


Add a Comment
Name:

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

Books

is a comprehensive book on 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