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

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

Why

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

?

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

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

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!

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.

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

Can we assume than numbers are different?

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

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

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

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

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

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

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

Running Time 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;
}
for(int i=0;i<pos;i++)
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;
}
}``````

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;
}
for(int i=0;i<pos;i++)
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;
}

}``````

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;
}
for(int i=0;i<pos;i++)
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;
}

}``````

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

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

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.

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

Comment hidden because of low score. Click to expand.

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.