Facebook Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

Maintain two arrays - front [ ] and rear [ ]
front maintains the product before the current index
rear maintains the product after the current index
then the product of current index i = front[i]*rear[i]

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

- arsragavan March 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice

- Anonymous March 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
5
of 11 votes

You can do this using one array and save some space:

public static void products2(int[] a) {

		int n = a.length;
		int[] products = new int[n];
		int p = 1;
		for (int i = 0; i < n; ++i) {
			products[i] = p;
			p *= a[i];
		}
		p = 1;
		for (int i = n - 1; i >= 0; --i) {
			products[i] = p * products[i];
			p *= a[i];
		}

		System.out.println(Arrays.toString(products));
	}

To make things even more interesting we can do this recursively:

public static int recursive(int[] a, int[] products, int index, int p) {

		if (index == a.length) {
			return 1;
		}
		products[index] = p;
		int result = recursive(a, products, index + 1, p * a[index]);
		products[index] = products[index] * result;

		return result * a[index];
	}

- thelineofcode March 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can anyone explain math background of this solution, please?

- EasyForSpammers August 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The question asks us to find the product of all the other numbers in the array for each number.
We can model this by saying that the output for any number in the input array is equal to the product of all the numbers to the left of that number, multiplied by the product of all the numbers to the right of that number.
To cater for the edge cases, we can say that the product of numbers to the left of the first element is equal to 1, and similarly, the product of numbers to the right of the last element is also equal to 1.
We can find the products of numbers to the left of all the numbers in the array by maintaining a separate array that tracks the cumulative product of all the numbers to the left of the corresponding number in the input array (this is the "rear" array in the answer).
By setting the first number in this rear array to 1, we can easily calculate the rest of the cumulative products by iterating through and multiplying each number with the previous entry in the rear array.
Similarly, we can create the array of cumulative products from the right of the array (the "front" array) by iterating from right to left.
Once we have this, we can then create our output array by multiplying the corresponding rear entry with its corresponding front entry.
Each pass consists of n operations, so its complexity is O(n).

- michaelbarlow7 March 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your code does not handle if int a[] = {3}
Correct me if I am wrong. Thats a special case.

- anonymous March 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 vote

I would like to explain it with example instead of code. Because code would be really easy:

arr = 2, 3, 1, 4

// maintain two arrays which can be done in O(n)

arr1 = 2,  6,   6,  24 (arrays multiply each number with previous and current)
arr2 = 24, 12, 4, 4    (arrays multiplied from end)

In above two arrays, put 1 in beginning of arr1 and end of arr2:
arr1 = 1, 2,  6,   6,  24, 1
arr2 = 24, 12, 4, 4,   1

Then to find number at index 'i' you would just do:

arr1[i]*arr2[i+1]

- shivamk March 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thank you for explaining it

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

thanks for the explanation

- byteattack May 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

cheers

- bunnybare October 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Does division as repeated subtraction also doesn't count?

- Learner March 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Repeated subtraction is not an O(n) operation, depending on your implementation.

- Ganesh Ram Sundaram March 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

public int GetQuotient(int a, int b)
{
	if (a < b)
		return 0;
	if (a == b)
		return 1;
	else 
	{
		int q = (int) Math.Pow(e, (Math.Log(a) - Math.Log(b)));
		return q;
	}
}

public void ChangeArray(int[] arr, int n)
{
	int product = 1;
	for (int i = 0; i< n; i++)
	{
		product *= arr[i];
	}

	for(int i = 0; i< n; i++)
	{
		arr[i] = GetQuotient(product, arr[i]);
	}
}

The GetQuotient method does not add complexity because its a formulated mathematical calculation.

So the complexity of the program is still O(n).

- PrateekS. March 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please explain on the concept behind this?

- Aravind March 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

he's trying to use the fact that

(x/y) = e^log(x/y) = e^{logx - logy}

but he should test his code, especially with y==0 (log 0 == infinity?)

- S O U N D W A V E March 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is an elegant solution.
And in fact way "out-of-the-box thinking" than any other solution.

It doesn't require more storage space also.
And computation cycles are never counted as part of complexity

Also, even if there is a single 0 in the array, the output array will be ALL zero

So I guess he can add a line in the main program
like so

if(arr[I] == 0)
{
	for(int j=0; j< n; j++ )
		arr[j] = 0;
	
	return;
}

- Samtg March 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually Samtg, your solution is not quite correct.

They're right.
I should add the case to check for zero because here's what I missed

1. If there are no zeros in the array, then this program functions correctly

2. If there's 1 zero in the array, then all the elements are zero EXCEPT the element that was originally zero since it will be replaced with the product of all other numbers except zero

3. If there are more than 1 zero's in the array, then ALL the elements will be zero

- PrateekS. March 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
int main()
{
int a[4],b[4],i,n;
for(i=0;i<4;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<4;i++)
{
if(i==0)
{
b[i]=a[i+1]*a[i+2]*a[i+3];
}
else if(i==1)
{
b[i]=a[i-1]*a[i+1]*a[i+2];
}
else if(i==2)
{
b[i]=a[i-2]*a[i-1]*a[i+1];
}
else
{
b[i]=a[i-3]*a[i-2]*a[i-1];
}
}
for(i=0;i<4;i++)
{
printf("%d ",b[i]);
}
return 0;
}

- prashantgupta1061992 March 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this will work only for array with 4 elements, if the inout array is dynamic it will fail

- anandkiran2007 March 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what if you have array of 50 size.
Will you use 50 if-else ladder.

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

void multiplyAllOthers(int arr[], int n)
{
	int* copy = new int[n];
	memcpy(copy, arr, sizeof(int) * n);

	//multiply all others in the left
	for(int productSoFar = 1, i = 0; i < n; ++i){
		arr[i] *= productSoFar;
		productSoFar = arr[i];
	}
	//multiply all others in the right
	for(int productSoFar = 1, i = n-1; i >= 0; --i){
		arr[i] *= productSoFar;
		productSoFar *= copy[i];
	}

        delete[] copy;
}

time:O(n), space:O(n)

- uuuouou March 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice solution but think the operations in the first loop are reversed. I mean, they should be
arr[i] = productSoFar;
productSoFar *= arr[i];

- Ganesh Ram Sundaram March 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int main()
{
    vector<double> A = {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0};
    vector<double> M(A.size()); 

    const int N = A.size();
    double m = 1.0;

    for (int i = 0; i < N; i++) {
        M[i] = m;       // m = A[0] * A[1] * .... * A[i - 1]
        m *= A[i];      // update m
    }    

    m = 1;
    for (int i = N - 1; i >=0; i--) {
        M[i] *= m;      // m = A[i+1] * ... * A[N-1]
        m *= A[i];      // update m
    }
   
    for (double d : M) cout << d << " "; cout << endl;

    return 0;
}

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

Shouldn't it be so simple...
1. Multiple all element in first go
2. Divide the result by current element to get result at that position.

- Naveen Maanju March 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Division not allowed. Constraint!!

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

multiply all the array elements and then divide the product with present element.

- Dev_Kashyap March 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

division not allowed, l2r

- bunnybare October 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Multiplying anagram values

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

Multiplying anagram values

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

public static void main(String[] args) {
		
		for (int i = 0; i < a.length; i++) {
			
			System.out.println(multiply(i, a.length, 1, a, 0));
			System.out.println("countAll : "+countAll);
		}
	}
public static int multiply(int i, int n, int r, int a[], int count) {
			
			int j = i + 1;
			
			if(j >= n)
				r = r * a[j - n];
			else
				r = r * a[j];
		
			count++;
			
		
			if(count+1 == n)
				return r;
			
			return multiply(j, n, r, a, count);
		}

- san4you88 March 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my code

1. Identify the current index and set the value of that element as 1
2. Multiple the elements in the array , that will be product of 3 numbers

public class MultiplyNumber {
	
	public static int[] Multiply(int[] arr,int len)
	{
		int[] output = new int[arr.length];
		int start = 0;
		int k = 1;
		int temp = 0;
		int currentIndex = 0;
		for(int i = 0 ; i < arr.length; i ++)
		{
			start = 0;
			k = 1;
			temp = arr[i];
			arr[i] = 1;
			currentIndex = i;
				while(start != len)
				{
					k =  k * arr[start];
					start ++;
				}
				arr[currentIndex] = temp;
				output[i] = k;
		}
		return output;
	}

	public static void main(String[] args) {

		int[] a = {2,3,1,4};
		int[] out = Multiply(a,a.length);
		for(int i = 0 ; i <out.length; i ++)
		{
			System.out.print(out[i]+",");
		}
	}

}

- anandkiran2007 March 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

n^2.

- bunnybare October 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

function insideOutProduct(a) {
    if (!a || a.length <= 1) {
        return a;
    }
    var before = a.map(function(n, i) { return a.reduce(function(prev, curr, j) { return j < i ? prev*curr : prev; }, 1); });
    var after = a.map(function(n, i) { return a.reduce(function(prev, curr, j) { return j > i ? prev*curr : prev; }, 1); });
    var product = a.map(function(n, i) { return before[i] * after[i]; });
    return product;
}

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

public class FaceBookProblem1 {

public static void main(String[] args) {
int input[] = { 2, 3, 1, 4 };
fillArray(input, 0, input.length, 1);
for (int i = 0; i < input.length; i++) {
System.out.println(input[i]);
}
}

private static int fillArray(int[] array, int index, int length, int value) {
if (index == (length - 1)) {
int val = array[index];
array[index] = value;
return val;
} else {
int val = fillArray(array, index + 1, length, value * array[index]);
int retVal = val * array[index];
array[index] = value * val;
return retVal;
}
}
}

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

python

def multiplyList(input,pos,val):
    if pos == len(input):
        return 1
    retVal = multiplyList(input,pos+1,input[pos]*val)
    newretVal = retVal*input[pos]
    input[pos] = retVal*val 
    return newretVal

input = [2,3,1,4]
multiplyList(input,0,1)
print input

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

{
public static void main(String[] args) {
int[] input = {2, 3, 1, 4};
int[] output = new int[input.length];

int index;
for (index = 0; index < input.length; index ++) {
output[index] = 1;
}

int m = 1;
for (index = 0; index < input.length; index ++) {
output[index] = m;
m = m * input[index];
}

m = 1;
for (index = input.length - 1; index >= 0; index --) {
output[index] = output[index] * m;
m = m * input[index];
}

for (index = 0; index < output.length; index ++) {
System.out.println(output[index]);
}
}



}

- acton July 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

-(int)products:(int [])a :(int )currIndex :(int )forIndex :(int )len
{
    int static output[] = {1,1,1,1};
    
    if(currIndex == len)
        return 1;
    
    int result = [self products:a :currIndex+1 :forIndex :len];
    output[forIndex] = result;
    
    if(currIndex == forIndex)
        return result;
    else
        return a[currIndex] * result;
}
// Input
int a[] = {2,3,1,4};
    printf("\nproducts : ");
    for(int i=0;i<4;i++)
    {
        int result = [self products:a :0 :i :4];
        printf("%d, ",result);
    }
// Output
/*
products : 12, 8, 24, 6, 
*/

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

public static void main(String[] args){
int[] a={2,3,1,4};
solve(a,0);
}


static void solve(int[] a,int index){
//result array
int[] r = new int[a.length];
int t=1;

//multiple from left
for(int i=0;i<a.length;i++){
r[i]=t;
t=t*a[i];
}

t=1;

//multiple from right
for(int i=(a.length-1);i>=0;i--){
r[i]=t*r[i];
t=t*a[i];
}

//complete
for(int i=0;i<a.length;i++){
System.out.println(r[i]);
}

- Youngsam September 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static int[] multiplyOthers(int [] a) {
int [] p = new int[a.length];

for (int i = 0; i < a.length; i ++) {
int multiplior = 1;
for(int j=0; j<a.length; j++) {
if(i != j) {
multiplior = multiplior * a[j];
}
}
p[i] = multiplior;
}
return p;
}

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

1. long product = a[0]*a[1]*..*a[n]
2. return [product/a[0], product/a[1].. product/a[n]]

- neo October 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] solve(int[] input) {
    int[] output = new int[input.length];

    int product = 1;
    for (int i = 0; i < input.length; i++) {
      output[i] = product;
      product = product * input[i];
    }

    product = 1;
    for (int i = input.length - 1; i >= 0; i--) {
      output[i] = output[i] * product;
      product = product * input[i];
    }
    return output;
  }

- rachitisthere October 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Or you could just implement the division function with a while-loop. It's sneaky but it fulfills the requirements.

def mult_rest_indices(array):
    sum = 1
    for i in array: 
        sum*=i
        
    result= []
    for i in array:
        k=0
        x=sum
        while x>0:
            x-=i
            k+=1
        result.append(k)
    print result

- ghirlwhocodes October 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function mul(a, b) {
return a * b;
}

function genArray(a) {
var res = [];

a.map(function(item, i) {
res.push(a.filter(function( ai) {
return ai !== item;
}).reduce(mul));
});
return res;
}

console.log(genArray(a));

- Satheesh November 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{ iinput = [2,3,1,4]

def main():
output = []
allMulti = reduce(lambda x, y: x*y, iinput)

for i in xrange(0, len(iinput)):
output.append(allMulti / iinput[i])

return output

print main() }}

is it O(n)?

- vasilia May 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I came up with two different solutions, one using recursion and one one without it. I'm not sure of the big o for the one with recursion but the one with out t should meet the requirements.

def multi(a_list, count, nlist):
    total = 1
    if count >= len(a_list):
        return
    for element in a_list:
        if a_list[count] != element:
            total *= element
    nlist.append(total)
    count += 1
    multi(a_list, count, nlist)
    return nlist

def mulit1(a_list):
    nlist = []
    total = 1
    for element in a_list:
        total *= element
    count = len(a_list)
    for element in a_list:
        nlist.append(total)
    i = 0
    for element in a_list:
        nlist[i] /= element
        i += 1
    return nlist

nlist = []
li = [1, 4, 5, 2, 3]
print multi(li, 0, nlist)
print mulit1(li)

- Anonymous December 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C# with Linq:

var l = new List<int>() {2, 3, 1, 4, 2};
            var m = l.Select(i =>
            {
                var sl = new List<int>(l);
                sl.Remove(i);
                return sl.Aggregate((a, b) => a*b);
            });

- lucidio November 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

input = 8
output =
1 1 1 1 1 1 1 2
3 2 2 2 2 2 2 2
3 3 3 3 3 3 3 4
5 4 4 4 4 4 4 4
5 5 5 5 5 5 5 6
7 6 6 6 6 6 6 6
7 7 7 7 7 7 7 8
pattern program in java

- vshah January 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

input = 8
output =
1 1 1 1 1 1 1 2
3 2 2 2 2 2 2 2
3 3 3 3 3 3 3 4
5 4 4 4 4 4 4 4
5 5 5 5 5 5 5 6
7 6 6 6 6 6 6 6
7 7 7 7 7 7 7 8
pattern program in java

- vshah January 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

input = 8
output =
1 1 1 1 1 1 1 2
3 2 2 2 2 2 2 2
3 3 3 3 3 3 3 4
5 4 4 4 4 4 4 4
5 5 5 5 5 5 5 6
7 6 6 6 6 6 6 6
7 7 7 7 7 7 7 8

import java.util.*;
class Test 
{
	int n;
	Scanner sc;
	void readNumber()
	{
	    sc=new Scanner(System.in);
            n = sc.nextInt();
	}
	void printPattern()
	{                  
	    // need to write the logic 

	}
	public static void main(String[] args) 
	{
        Test t = new Test();
		t.readNumber();
		t.printPattern();
	}
}

- vshah January 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

multiply :: [Int] -> [Int]
multiply xs =
  -- [1,2,3]
  let
    accum y ys =
      case ys of
        [] ->
          y : 1 : []
        z : zs ->
          z * y : z : zs

    -- [1,1,2]
    fromLeft =
      List.reverse (List.drop 1 (foldl (flip accum) [] xs))

    -- [6,3,1]
    fromRight =
      List.drop 1 (foldr accum [] xs)

  in
    -- fixed number (3) of traversals of xs => O(n)
    List.zipWith (*) fromLeft fromRight

- Maddie November 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Just use modular arithmetic with a large prime. Instead of divide, multiply by the inverse mod(p).
1. Calculate tp = the total product mod p
2. For each x: x = tp * x^(p - 2) mod p
note: p must be picked larger than the largest result

- erne.carvajal March 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is p here...?

- Ankit Garg March 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

that makes you code work in O(n * log(p)), which doesn't fit into given constraints

- daniel_de_darik March 08, 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