## Facebook Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
30
of 32 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;
}``````

Comment hidden because of low score. Click to expand.
0

Nice

Comment hidden because of low score. Click to expand.
5

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];
}``````

Comment hidden because of low score. Click to expand.
0

Can anyone explain math background of this solution, please?

Comment hidden because of low score. Click to expand.
0

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).

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
9
of 9 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``````

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]``````

Comment hidden because of low score. Click to expand.
0

Thank you for explaining it

Comment hidden because of low score. Click to expand.
0

thanks for the explanation

Comment hidden because of low score. Click to expand.
0

cheers

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

Does division as repeated subtraction also doesn't count?

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
1
of 1 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)

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

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

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).

Comment hidden because of low score. Click to expand.
0

Can you please explain on the concept behind this?

Comment hidden because of low score. Click to expand.
0

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?)

Comment hidden because of low score. Click to expand.
0

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;
}``````

Comment hidden because of low score. Click to expand.
0

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

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;
}

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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;
}``````

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.

Comment hidden because of low score. Click to expand.
0

Division not allowed. Constraint!!

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.

Comment hidden because of low score. Click to expand.
0

division not allowed, l2r

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

Multiplying anagram values

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

Multiplying anagram values

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);
}``````

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]+",");
}
}

}``````

Comment hidden because of low score. Click to expand.
0

n^2.

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;
}``````

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 };
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;
}
}
}

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]);
}
}

}

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,
*/``````

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]);
}

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;
}

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]]

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;
}``````

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``````

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));

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)?

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)``````

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);
});``````

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

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

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;
{
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.printPattern();
}
}``````

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``````

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

JavaScript solution:

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

for (let i = 0; i < input.length; i++) {
output[i] = front[i] * rear[i];
}
return output
}``````

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

I have not looked at all the solutions in this thread, but the ones I did look at had O(N**2) complexity metric. Below I offer 2 solutions: one naive O(N**2) and one that executes in O(N) time.

``````# input [2,3,1,4]
# output [12,8,24,6]
#
# Multiply all fields except it's own position.
#
# Restrictions:
# 1. no use of division
# 2. complexity in O(n)
#

# O(N**2) solution
def multiply_list_O_nn(l: list) -> list:
res = [1] * len(l)
for i in range(len(l)):
for j in range(len(l)):
res[i] *= l[j] if i != j else 1

return res

# O(N) solution
def multiply_list_O_n(l: list) -> list:
tree_mul_children = []
tree_mul_others = []

# First compute tree_mul_children
last_row = l
tree_mul_children.append(l)
while len(last_row) > 1:
new_row = []
for i in range(0, len(last_row), 2):
if i + 1 < len(last_row):
s = last_row[i] * last_row[i + 1]
else:
s = last_row[i]

new_row.append(s)
tree_mul_children.append(new_row)
last_row = new_row

tree_mul_children.reverse()

# Now compute tree_mul_others
tree_mul_others.append([1])
for i in range(1, len(tree_mul_children)):
row = tree_mul_children[i]
new_row = []
for j in range(len(row)):
mul_others = tree_mul_others[i - 1][j // 2] * row[(j % 2 + 1) % 2 + j // 2 * 2]
new_row.append(mul_others)
tree_mul_others.append(new_row)

return tree_mul_others[-1]

print(multiply_list_O_nn([2, 3, 1, 4]))

print(multiply_list_O_n([2, 3, 1, 4]))``````

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

Comment hidden because of low score. Click to expand.
0

What is p here...?

Comment hidden because of low score. Click to expand.
0

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

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.

### 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.