Facebook Interview Question for Interns


Country: United States
Interview Type: Phone Interview




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

The idea is simple. If the ordering of sums is known, we can easily reconstruct the array. Given the P array, calculate N (no. of elements in S).
Then observe,

S[0] = (P[0] + P[1] - P[n - 1]) / 2

Why?

P[0] = S[0]+S[1], P[1]=S[0]+S[2], P[n - 1] = S[1]+S[2]

Now run a loop to calculate the rest.

Code in Java:

int[] getOriginalArray(int[] P, int n) {
	int[] S = new int[n];
	S[0] = (P[0] + P[1] - P[n - 1]) / 2;
	for (int i = 1; i < n; i++) {
		S[i] = P[i] - S[0];
	}
	return S;
}

- Diptesh February 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why

P[n - 1] = S[1]+S[2]

?

- Anonymous November 11, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@emb. Could you give more explanation about the question with an example? Especially the 'note' part you have specified.

-Thanks

- Anonymous February 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

given: pairwise sum set, set of numbers
solution-
1- calculate the pairwise sum from set of numbers- nC2
2- get pairwisesum - nC2 such that the answer is numbers in pairwisesum but not in nC2 solution
3- for each number from resultset of 2, subtract each number from set of numbers to get a set of new numbers.

assumption- anything new sum we find in pairwise sum which cannot be achieved from given set can result in n number of values by subtracting n set values from set of numbers

- Anonymous February 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The naive solution could be something like the following:

def nextPeer(sortedItems, cval, sum, k):
        while k < len(sortedItems) :
              z = cval + sortedItems[k]
              if z == sum :
                      return k  
              else:
                      k += 1  
        return -1

def findPeer(sortedItems, sum, p1):
        while p1 < len(sortedItems):
             cval = sortedItems[p1]
             p2 = nextPeer(sortedItems, cval, sum, p1+1) 
             
             if p2 == -1:
                p1 += 1
             else:
                return (p1, p2)

        return (-1, -1)   
def myPair(xSet, sumSet):

    pairs = dict()
 
    sorted_x_set = sorted(xSet, key = lambda x: x, reverse = True)  
    sorted_sum_set = sorted(sumSet, key = lambda x: x, reverse = True)
    

    for s in sorted_sum_set:
        j = 0 
        while sorted_x_set[j] >  s :
             j+= 1
        (peer1, peer2) = findPeer(sorted_x_set, s,j) 
        if peer1 != -1 and peer2 != -1:
             pairs[s] = (sorted_x_set[peer1], sorted_x_set[peer2])
                   
    print(sorted_sum_set)
    print(sorted_x_set)
    for p in pairs:
        print(p, '::', pairs[p]) 

x = [2, 3, 4, 7,20,9]
z = [5, 11, 7, 6, 10, 9,23, 29,15,29]
myPair(x,z)

Sample Output:::
[29, 29, 23, 15, 11, 10, 9, 7, 6, 5]
[20, 9, 7, 4, 3, 2]
5 :: (3, 2)
6 :: (4, 2)
23 :: (20, 3)
7 :: (4, 3)
9 :: (7, 2)
10 :: (7, 3)
11 :: (9, 2)
29 :: (20, 9)
If multiple pairing are possible, this program will only generate one of them!

- fahmida.hamid February 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

Here is the fundamental idea.. I could be wrong and I am not writing the code.. just the idea.. (It takes the assumption that pairwise sums will be in order)

How many pairwise sums will there be for n terms?
For 3 terms, pairwise sums will be 2 + 1
for 4 terms, pairwise sums will be 3 + 2 + 1
so for n, the relation will come out as n - 1 + (n - 2) + ... + 1

now that you have the above, we can find n using pairwise sums set by incrementing i, adding it to current sum and that should equal the length of given array.

After that, term 1 is x1 + x2, term 2 is x1 + x3 and term n will be x2 + x3.

Compute term 1 + term 2 - term n -> This will be x1 + x2 + x1 + x3 - x2 - x3 = 2 * x1
div by 2 to get x1.
once you have x1, just subtract that from numbers till terms n - 1 for getting other terms.

x2 can be computed as x1 + x2 - x1 and so on. You will get all terms in n.

- Akash Singh February 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we assume than numbers are different?

- EPavlova February 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Could you explain what is given - sum of pairs or sum of pairs and numbers in the beginning. Initally I tought that we have only sum of pair of numbers and should find numbers in these sums, without having then in advance, but after I had a look on the proposed solutions , I noticed that you assume that you have numbers and their sum in unordered way and has to guess which numbers belongs to which sum. Please explain better

- EPavlova February 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For a0 = 1, till max_value a[0] could be (there is a constraints on the sums) try to generate all numbers taking into the account the current minimum sum. Each time we add new number we generate all sums of given number and previously added numbers and check if these sums actually exists, if not we try with another a[0] (first) number. If all sums exists we generate next number as difference between current minimum sum and a[0].

- EPavlova February 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If we assume that we know order of sums in P, we can do it as follows:
n = no. of elements in S. To be calculated based on size of P. Simple quadratic equation solver.
s[0]=(p[0]+p[1]-p[n-1])/2
Why? Because:
p[0]=s[0]+s[1]
p[1]=s[0]+s[2]
p[n-1]=s[1]+s[2]

Now run a loop and you're done.
Code in Java:

public int[] reconstruct(int[] p, int n) {
	int[] s = new int[n];
	s[0] = (p[0]+p[1]-p[n-1])/2;
	for (int i = 1; i < n; i++) {
		s[i]=p[i]-s[0];
	}
	return s;
}

- diptesh February 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about this, and thanks for the above suggestions.

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>

int P[] = { 6, 11, 101, 15, 105, 110 };
void getElementsofS(int P[], int size) {
	int *S = (int*)calloc(sizeof(int)*size, 1);
	assert(S != NULL);
	S[0] = (P[0] + P[1] - P[size - 1]) / 2;
	printf("S = %d ", S[0]);
	for (int i = 1; i < size; i++) {
		printf("%d ",S[i] = P[i - 1] - S[0]);
	}
}
int fact(unsigned int n){
	if (n == 1) return 1;
	return n * fact(n - 1);
}
int main(){
	int i = 3;
	int maxSize = (sizeof(P) / sizeof(P[0]));
	for (; i < maxSize; i++){
		if (fact(i - 1) == maxSize)
			break;
	}
	if (i == maxSize){
		printf("Array P is not of set Rule\n");
		return 0;
	}
	getElementsofS(P, i);
	return 0;
}

- praveen pandit March 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This solution is very close to what Diptesh has mentioned.
Posting it in C.
O(n) time complexity

First we need to determine the size of the S array.
We will be solving for P length = n*(n-1)/2
Which is x*y = 2*len(P) && x-y = 1 where x is the length of S.
We will also use the length to compute each entry in S.
eg.
P = {x1+x2, x1+x3, ...., x2+x3}
adding first 2 and subtracting the first sum of the next element.
2x1+x2+x3-(x2+x3) = 2x1
We will do this until we hit the last element in the P. Which is the only sum for last two elements in S.
Special case for the last two elements in S.
We will use the last two sums to compute P[i-2] & P[i-1] and subtract the known last element.
eg.
P = {....x2+x3,x2+x4,x3+x4}
So far our S computed will be
S = {x1,x2}
So we will subtract last known element from the last two sums
x2+x3 - x2 = x3
&&
x2+x4 - x2 = x4

#include <stdio.h>

int find_length_from_sum(int sum_set_length) {
	int other_factor;
	for (int i = 0; i < sum_set_length/2; ++i)
	{
		if ((2*sum_set_length) % i)
		{
			other_factor = (2*sum_set_length) / i;
			if (other_factor - i == 1)
			{
				return other_factor;
			}
		}
	}
	return 0;
}

int find_value(int current_index, int next_offset) {
	int 2x1_x2_x3 = P[current_index] + P[current_index+1];
	int x2_x3 = p[current_index + next_offset - 1];
	int 2x1 = 2x1_x2_x3 - x2_x3;
	int x1 = 2x1/2;
	return x1;
}

int main(int argc, char const *argv[])
{
	int length = find_length_from_sum(P.length);
	int S[length];
	int current_index = 0;
	int next_offset = length;
	for (int i = 0; i < length && current_index < P.length; ++i)
	{
		S[i] = find_value(current_index, next_offset);
		current_index = current_index + next_offset - 1;
		next_offset = next_offset - 1;
	}
	S[i+1] = P[current_index-2] - S[i];
	S[i+2] = P[current_index-1] - S[i];
	return 0;
}

- killbot April 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Running Time O(n)
Additional space O(n)

import java.util.ArrayList;
import java.util.HashMap;

public class arrayelements {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
int[] parray={6,11,101,15,105,110};
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
ArrayList<Integer> array=new ArrayList<Integer>();
int n=0,index=0,sum=0;
n=method(parray);
int pos=n;
while(n>0)
{sum=0;
	for(int i=index;i<(index+n);i++)
sum+=parray[i];	
map.put(n, sum);
index+=n;
n--;
}
int first=0,prev=0;
for(int k=2;k<=pos;k++)
{
	first= (map.get(k)-(map.get(k-1)-prev))/k;
	prev=first;
}
array.add(first);
for(int i=0;i<pos;i++)
	array.add(parray[i]-first);
System.out.println(array);
	}

	private static int method(int[] parray) {
		// TODO Auto-generated method stub
		for(int i=1;i<=parray.length/2;i++)
		{
			if(i*i+i == (parray.length*2) )
				return i;
		}
	return -1;
	}
}

- Bharaneedharan Dhanaraj April 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.HashMap;

public class arrayelements {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
int[] parray={6,11,101,15,105,110};
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
ArrayList<Integer> array=new ArrayList<Integer>();
int n=0,index=0,sum=0;
n=method(parray);
int pos=n;
while(n>0)
{sum=0;
	for(int i=index;i<(index+n);i++)
sum+=parray[i];	
map.put(n, sum);
index+=n;
n--;
}
int first=0,prev=0;
for(int k=2;k<=pos;k++)
{
	first= (map.get(k)-(map.get(k-1)-prev))/k;
	prev=first;
}
array.add(first);
for(int i=0;i<pos;i++)
	array.add(parray[i]-first);
System.out.println(array);
	}

	private static int method(int[] parray) {
		// TODO Auto-generated method stub
		for(int i=1;i<=parray.length/2;i++)
		{
			if(i*i+i == (parray.length*2) )
				return i;
		}
	return -1;
	}

}

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

import java.util.ArrayList;
import java.util.HashMap;

public class arrayelements {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
int[] parray={6,11,101,15,105,110};
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
ArrayList<Integer> array=new ArrayList<Integer>();
int n=0,index=0,sum=0;
n=method(parray);
int pos=n;
while(n>0)
{sum=0;
	for(int i=index;i<(index+n);i++)
sum+=parray[i];	
map.put(n, sum);
index+=n;
n--;
}
int first=0,prev=0;
for(int k=2;k<=pos;k++)
{
	first= (map.get(k)-(map.get(k-1)-prev))/k;
	prev=first;
}
array.add(first);
for(int i=0;i<pos;i++)
	array.add(parray[i]-first);
System.out.println(array);
	}

	private static int method(int[] parray) {
		// TODO Auto-generated method stub
		for(int i=1;i<=parray.length/2;i++)
		{
			if(i*i+i == (parray.length*2) )
				return i;
		}
	return -1;
	}

}

- Bharaneedharan Dhanaraj April 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

my working php solution
time complexity : O( (n * (n-2)) + 3 + n) with helper variables.
memory: almost same with time complextiy.
space complexity :

function getSublistSize($length)
{
    $i = 2;
    $n = 0;

    while ($i <= $length) {
        if (is_int($length / $i)) {
            if ($length == $i * ($i + 1) / 2) {
                return ($i + 1);
            }
        }

        ++$i;
    }

    return $n;
}

function findSubstractList(array $list)
{
    $length = count($list);

    $n = getSublistSize($length);
    $nth = $n - 1;

    $substractList = [];
    $substractTotal = array_sum($list) / ($length / 2); // A + B + C + D

    /**
     * formula : A = (list[0] + list[1] - list[nth -1]) / 2
     * list[0] = A + B,
     * list[1] = A + C,
     * list[nth - 1] = B + C
     *
     * =>  ((A + B) + (A + C) - (B + C)) / 2
     * => (A + A + (B + C - B - C)) / 2
     * => (2A + 0) / 2 => 2A / 2
     * => A
     */
    $substractList[] = (($list[0] + $list[1]) - $list[$nth]) / 2;

    for ($i = 0; $i < $nth; ++$i) {
        $substractList[] = ($list[$i] - $substractList[0]);
    }

//    $substractList[3] = $substractTotal - ($list[$nth - 1] + $substractList[0]);


    return $substractList;
}


$list = [5, 8, 14, 28, 40, 11, 17, 31, 43, 20, 34, 46, 40, 52, 66];

print_r(findSubstractList($list));

/**
 * P ) [6, 11, 101, 15, 105, 110];
 * S ) [1, 5, 10, 100]
 *
 * P ) [5, 8, 14, 28, 40, 11, 17, 31, 43, 20, 34, 46, 40, 52, 66];
 * S ) [1, 4, 7, 13, 27, 39]
 *
*/

- Feyyaz Esato─člu April 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

my working php solution
time complexity : O( (n * (n-2)) + 3 + n) with helper variables.
space complexity : almost same with time complextiy.

function getSublistSize($length)
{
    $i = 2;
    $n = 0;

    while ($i <= $length) {
        if (is_int($length / $i)) {
            if ($length == $i * ($i + 1) / 2) {
                return ($i + 1);
            }
        }

        ++$i;
    }

    return $n;
}

function findSubstractList(array $list)
{
    $length = count($list);

    $n = getSublistSize($length);
    $nth = $n - 1;

    $substractList = [];
    $substractTotal = array_sum($list) / ($length / 2); // A + B + C + D

    /**
     * formula : A = (list[0] + list[1] - list[nth -1]) / 2
     * list[0] = A + B,
     * list[1] = A + C,
     * list[nth - 1] = B + C
     *
     * =>  ((A + B) + (A + C) - (B + C)) / 2
     * => (A + A + (B + C - B - C)) / 2
     * => (2A + 0) / 2 => 2A / 2
     * => A
     */
    $substractList[] = (($list[0] + $list[1]) - $list[$nth]) / 2;

    for ($i = 0; $i < $nth; ++$i) {
        $substractList[] = ($list[$i] - $substractList[0]);
    }

//    $substractList[3] = $substractTotal - ($list[$nth - 1] + $substractList[0]);


    return $substractList;
}


$list = [5, 8, 14, 28, 40, 11, 17, 31, 43, 20, 34, 46, 40, 52, 66];

print_r(findSubstractList($list));

/**
 * P ) [6, 11, 101, 15, 105, 110];
 * S ) [1, 5, 10, 100]
 *
 * P ) [5, 8, 14, 28, 40, 11, 17, 31, 43, 20, 34, 46, 40, 52, 66];
 * S ) [1, 4, 7, 13, 27, 39]
 *
*/

- Feyyaz Esato─člu April 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't think you can compute this if order in P is not specified. The order in P must be P1 = x1+x2, P2 = x1+x3, P3 = x1+x4... P_last = x(n-1) + xn.
Otherwise, each permutation of the P could give a set of xk solution.

- DavidHo April 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include <stdio.h>
#define MAX 100000

void printPairs(int arr[], int arr_size, int sum)
{
int i, temp;
bool binMap[MAX] = { 0 }; /*initialize hash map as 0*/

for (i = 0; i < arr_size; i++)
{
temp = sum - arr[i];
if (temp >= 0 && binMap[temp] == 1)
printf("Pair with given sum %d is (%d, %d) \n",
sum, arr[i], temp);
binMap[arr[i]] = 1;
}
}

/* Driver program to test above function */
int main()
{
int A[] = { x1, x2, x3, x4 };
int Sum[] = { x1 + x2, x1 + x3, x1 + x4, x2 + x3, x2 + x4, x3 + x4,};

int arr_size = 4;

for (int i = 0; i<arr_size; i++)
printPairs(A, arr_size, Sum[i]);

getchar();
return 0;
}

- Basu February 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.


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