## Facebook Interview Question for Software Engineer / Developers

• 3

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
11
of 13 vote

I use hash map to record the sum of two pair and find two pairs which has the same sum. Time is O(n^2)

``````struct Node
{
int x;
int y;
Node(int a=0, int b=0):x(a),y(b){};
};
vector<int> Print4Sum(vector<int> A){
int tsum, l = A.size();
vector<int> ans;
if (l < 4) return ans;

map<int, Node> hashmap;
for (int i = 0; i < l-1; ++i)
for (int j = i+1; j < l; ++j)
{
tsum = A[i] + A[j];
if (hashmap.find(tsum) == hashmap.end()){
Node tnode = Node(i,j);
hashmap[tsum] = tnode;
}else{
Node tnode = hashmap[tsum];
int x = tnode.x, y = tnode.y;
if (x != i && x != j && y != i && y != j)
{
ans.push_back(i);
ans.push_back(j);
ans.push_back(x);
ans.push_back(y);
sort(ans.begin(), ans.end());
return ans;
}
}
}
return ans;
}``````

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

if tsum corresponds to more than 3 pairs, this won't work, will it? How about putting all the (x, y) that has same num[x]+num[y] into a vector:

``map<int, vector<Node>> hashmap;``

then

``````auto iter:hashmap
if(iter.second.size() >=2)
{
}``````

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

If there are duplicates in array, this solution will not work. Any one has idea?

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

I can only think out two algorithms.
First one is sorting array and traversing the array like 3-sum problem;
Second one is using hashing to record pair sums.

The first one's time complexity is O(n^3) and the second one's time complexity is O(n^2). Could anyone share a O(n^2) complexity at most with sorting? Thanks.

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

how do you get 2nd with O(n^2)? Correct me if I am wrong.
Computing sum of pair is O(n^2), find out two pair with different indices in one element in set is O(n^3) because the length of pairs is O(n^2) and finding out pairs with different indices in O(n^2) is at least O(n), right?

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

T Dog is right.

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

public static void printVal(int[] arr) {
if (arr.length == 0 || arr.length < 4) return;
HashMap<Integer, ArrayList<Pair>> map = new HashMap<Integer, ArrayList<Pair>>();
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
Pair p = new Pair(i,j);
if (map.containsKey(arr[i] + arr[j])) {
} else {
ArrayList<Pair> arrList = new ArrayList<Pair>();
map.put(arr[i] + arr[j], arrList);
}
}
}

for (Integer i : map.keySet()) {
ArrayList<Pair> list = map.get(i);
if (list.size() == 2) {
System.out.println(list.get(0).one + " " + list.get(0).two + " " +
list.get(1).one + " " + list.get(1).two);
}
if (list.size() > 2) {
for (int k = 0; k < list.size() - 1; k++) {
for (int m = k + 1; m < list.size(); m++) {
System.out.println(list.get(k).one + " " + list.get(k).two
+ " " + list.get(m).one + " " + list.get(m).two);
}
}
}
}
}

public class Pair {
int one;
int two;
public Pair(int o, int t) {
one = o;
two = t;
}
}

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

what would the time complexity of this be?

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

is it O(n^2)?

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

What I think that is important about this problem and a way to reduce the O() is that A + B = C + D is also the same as B + A = D + C and it should be checked again. What we can do is get all the possible combinations of 2 digits within that array and save the result. Such an operation will take O ( n!/2*(n-2)! ) and is basically the formula to calculate the possible combinations between k elements (in this case 2) in a list of n elements

Here is my code in PHP to print all the possible combinations:

``````\$list = array(3,4,7,1,2,9,8);
\$results = array();

for (\$i=0; \$i<count(\$list); \$i++) {
for (\$j=\$i+1; \$j<count(\$list); \$j++) {
\$sum = \$list[\$i] + \$list[\$j];
if (isset(\$results[\$sum])) {
//we have a match
foreach (\$results[\$sum] as \$pair) {
echo \$pair[0].",".\$pair[1].",".\$i.",".\$j."<br/>";
}
}
\$results[\$sum][] = array(\$i,\$j);
}
}``````

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

I wasnt logged in when i commented but let me know if you have any questions. Also the formula for combinations is n!/k!*(n-k)!

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

first step: record the number and their indeces using map;
second step: sort the array
third step: start = 0, end = len - 1, find the two number from the left numbers if their sum equals to array[start] + a[end], else start++ or end--, time complexity is O(n^2)
Is that right?

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

I can think of the below

1. Have 2 windows; and keep them 2 digits apart
2. Each window has 2 pointers; max, Min, and variable: Sum as sum btw max, min pointers
3. get sum of left window and right; if they are same print it out
4. Slide the windows by a digit to right.
5. On slide we know the old index of min; subtract the value from the Sum; we konw the new index of max so add that value to the Sum

the complexity should be o(n)

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

How is this supposed to work?

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

u see a bug?

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

this is not clear at all, it will be great, if you code this.

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

It doesn't consider the N^2 combinations....A+C = B+D won't work

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

In addition to the n^2 algorithm(s) mentioned above, there's a pseudopolynomial algorithm: d(n) = d(n-x) where x is one of the numbers and n is between zero and 2*largest number. Sorry about the confusing explanation.

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

Assuming array elements will traversed from Left to Right...like a..b.c..d..
and Minimum size of array should be 4...

so
#define LHS (A,B) A+B
#define RHS (C,D) C+B

....in a loop..
for ( int i=0; i <n-4;++i)
for ( int j=i+1;j<n-3;++j)
for ( int k=j+1;k<n-2;++k)
for (int l=k+1;k<n-1;++l)
{
if ( LHS(a[i],a[j]) == RHS(a[k][a[l])
cout<<i<<j<<k<<l<<"Are the indexes" <<endl;
i=j=k=l=n;
}

....
in case if the array element traverse any order..need to execute one more function in reverse order..

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

is this O(n^4)?

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

its not O(n^4) ...it is ((n+1)/2)^4));

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

in the above example array size 7;
(n^4) will be 7^4 --> 2401;
similarly (n^3) will be 7^3 --> 343

so with the above approach it will be ((n+1)/2)^4 --> 256

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

I think a general solution will b of the complexity O(n^3).

1. Make a structure like
struct ds
{
int value;
int index;
};

2. Sort according to values. // This process is nlogn

3. Iterate trough all pair (A,B) // This process is O(n^2)
a).compute sum = A+B
b).search two indexes(i,j) in sorted array such that :
Array[i]+array[j]=sum // ths process is O(n) in sorted array

So complexity is O(n^3).
This can be improved using hashing.

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

C#

int[] ar = { 3, 4, 7, 1, 2, 9, 8 };

for (int i=0; i<6;i++)
for (int j = 1; j < 6; j++)
for (int k = 2; k < 6; k++)
for (int p = 3; p < 6; p++)
{
int[] s = { ar[i], ar[j], ar[k], ar[p] };
if (s.Distinct().Count() == 4)
{
if (ar[i] + ar[j] == ar[k] + ar[p])
{
Console.WriteLine(ar[i] + "," + ar[j] + "," + ar[k] + "," + ar[p]);
}
}
}

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

can it be not done like this
assuming you have array of n

array[n] = 1,2,3,4,....n

take a two dimensional array (could be optimized)\
sum[n][n-1] = {
array[0]+array[1], array[0]+array[2], ..array[0]+array[n-1],
array[1]+array[2],array[1]+array[3],...array[1]+array[n-1],
.
.
array[n-2]+array[n-1]
}
this operation will take O(n^2 )

now search for equal values in
sum[0][] with sum[1][] to sum[n-1][]
similarly for
sum[1][] with sum[2][] to sum[n-1][]
till
sum[n-3][] with sum[n-2][]

this is again O(n^2)

so total complexity should be max 2(n^2)

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

Here, arr[0][0] = (3+4) and arr[1][1]= (4+3) . Both are same but that is not expected..

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

my java approach

``````public static void printSumPairs(int[] a){
HashMap<Integer,List<Point>> map = new  HashMap<Integer,List<Point>> ();
List<Point> list;
for(int i=0; i< a.length; i++){
for(int j=i+1; j<a.length; j++){
list = map.get(a[i]+a[j]);
if(list==null){
list = new ArrayList<Point>();
}
map.put(a[i]+a[j],list);
}
}

for (Integer key : map.keySet()) {
list = map.get(key);
if(list.size()>1){
for(int i=0; i< list.size()-1; i++)
{
if(list.get(i).x!=list.get(i+1).x && list.get(i).y!=list.get(i+1).y
&& list.get(i).x!=list.get(i+1).y
&& list.get(i).y!=list.get(i+1).x){
System.out.println(a[list.get(i).x]+"+"+a[list.get(i).y]+" = " +
a[list.get(i+1).x]+"+"+a[list.get(i+1).y]);
}
}
}
}
}
}

class Point{
int x;
int y;
Point(int a, int b){
x=a;
y=b;
}``````

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

O(n^2) using hash tables.
C++:

``````#include <unordered_map>
#include <set>
#include <vector>
#include <iostream>

typedef std::vector<int> IntVector;
typedef std::pair<int, int> IntPair;
typedef std::set<IntPair> PairSet;
typedef std::unordered_map<int, PairSet> SumMap;

{
int ar[] = {3, 4, 7, 1, 2, 9, 8};

SumMap map;

int i, j;
for (i = 0; i < 7; ++i) {
for (j = i+1; j < 7; ++j) {
int sum = ar[i] + ar[j];
map[sum].insert(IntPair(i, j));
}
}

// Find pairs
for (const auto &mit: map) {
const PairSet &set = mit.second;
PairSet::const_iterator sit, send;
PairSet::const_iterator sit2;
for (sit = set.begin(), send = set.end(); sit != send; ++sit) {
for (sit2 = ++PairSet::const_iterator(sit); sit2 != send; ++sit2) {
int A = sit->first;
int B = sit->second;
int C = sit2->first;
int D = sit2->second;

if (A != C and B != D) {
std::cout << "(" << A << ", "
<< B << ", " << C
<< ", " << D << ")\n";

return;
}
}
}
}
}``````

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

``and``

// Time complexity : O(n^2) - traversing every pair of indexes in the array
// Memory complexity : O(n^2) - every pair is stored in the hashtable in the worst case
void ABCD(int * arr, int n, int & a, int & b, int & c, int & d)
{
// a hash table to store sum values : SUM -> (i, j)
unordered_map<int, pair<int, int> > sum;
for (int i=0; i<n; i++)
{
for (int j=i+1; j<n; j++)
{
int s2 = arr[i] + arr[j];
// if the current sum was previously found we are done
if (sum.find(s2) != sum.end())
{
// the 2 indexes from the hash table
a = sum[s2].first;
b = sum[s2].second;
// the current indexes
c = i;
d = j;
// done
return;
}
// if the current sum wasn't previously found, HASH IT
// SUM -> (i, j)
else
sum[s2] = pair<int, int>(i,j);
}
}
}

``and``

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

There are two ways this can be solved:
1 - use 4-depth loops to iterate through all combinations of pairs. This is O(1) of size but O(n^4) of time
2 - use hashtable of lists of pairs to cache all sums as they are met and use 2-depth loops to find out all pairs of numbers. Then for each sum print out all pairs permutations.
This uses O(n^2) of size but O(n^2) of time. Actually this reduces to 2n^2 in case all numbers are equal but this it's O(n) complexity is not changed though

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

1. Sort the Array
2. Take two pointers left (start of the array) and right (end of the array)
3. Find the sum of the left and right value in the array
4. Look up iteratively the sum within the subarray , if sum is found print it
4.a if sum is greater value then increment left side ( i ) or else reduce the (j) value

``````public static void indexSumPair(int arr[])
{
//Return the array if Size less than 4
if(arr.length < 4)
{		return;	}
// Sort the array
Arrays.sort(arr);
// Take two pointer left and right
int left =0;
int right = arr.length-1;

// decrease the right pointer on each pass * array is sorted
for(;left<right;right--)
{
// Take sum of left and right
int outSum = arr[left] + arr[right];
int i = left;
int j = right -1;
// Apply Logic of Pairs in Array of Integers whose Sum is equal to a given Number
// look up the sum within the subarray
while(i<j)
{
if( arr[i]+arr[j] == outSum)
{
System.out.println( " ("+arr[i]+" , "+arr[j]+ ") = "+" ("+arr[left]+" , "+arr[right]+")" );
i++;
j--;
}
//
else if( arr[i]+arr[j] < outSum)
{
i++;
}
else if( arr[i]+arr[j] > outSum)
{
j--;
}
}
}``````

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

1. Sort the Array
2. Take two pointers left (start of the array) and right (end of the array)
3. Find the sum of the left and right value in the array
4. Look up iteratively the sum within the subarray , if sum is found print it
4.a if sum is greater value then increment left side ( i ) or else reduce the (j) value

-- This solution do not use any extra space , no HashMap

``````public static void indexSumPair(int arr[])
{
//Return the array if Size less than 4
if(arr.length < 4)
{		return;	}
// Sort the array
Arrays.sort(arr);
// Take two pointer left and right
int left =0;
int right = arr.length-1;

// decrease the right pointer on each pass * array is sorted
for(;left<right;right--)
{
// Take sum of left and right
int outSum = arr[left] + arr[right];
int i = left;
int j = right -1;
// Apply Logic of Pairs in Array of Integers whose Sum is equal to a given Number
// look up the sum within the subarray
while(i<j)
{
if( arr[i]+arr[j] == outSum)
{
System.out.println( " ("+arr[i]+" , "+arr[j]+ ") = "+" ("+arr[left]+" , "+arr[right]+")" );
i++;
j--;
}
//
else if( arr[i]+arr[j] < outSum)
{
i++;
}
else if( arr[i]+arr[j] > outSum)
{
j--;
}
}
}``````

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

bankertapan, are you the author? Very good solution, I just could not find how to inject the "find all integers that sum to X" problem solution here, but everything is pretty simple :). Good O(n^2) solution with O(1) extra space

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

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

this will work only for quadruples that include arr[0], this will fail in a test like 2,4,1, 600,4

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

I don't think the code above is completely correct according to the question. It says "Find the index", not the values. So if you sort the array first, how would you know which index based on the code above?

The code above prints:
(2 , 8) = (1 , 9)
(3 , 7) = (1 , 9)
(2 , 7) = (1 , 8)
(2 , 3) = (1 , 4)

So one solution would be to have another array that is not modified, and lookup the index for each printed value.

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

The code provided can not deal with cases like: 0 1 4 5 8 10
since it only consider the result including the smallest number.

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

the above code is wrong.. The following input

``new int[] {1,2,3,4,5}``

. The out put is

``````(2 , 4) =  (1 , 5)
(2 , 3) =  (1 , 4)``````

.
But there is one more result which is

``(2, 5) = (3, 4)``

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

This solution makes absolutely NO sense.

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

I agree with juliusjun. I don't think this approach is right.

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

Python solution using a dictionary and itertools.combinations

``````import itertools

def find_same_sums(integers):
sums = {}
for i, iv in enumerate(integers):
for j, jv in enumerate(integers):
if i == j:
continue
tup = (iv, jv) if iv <= jv else (jv, iv)
for tups in sums.itervalues():
if len(tups) < 2:
continue
for combination in itertools.combinations(tups, 2):
yield combination

for same in find_same_sums([3,4,7,1,2,9,8]):
print same``````

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

``````def find_pairs_with_same_sums(list):
sums = {}
for i in range(len(list)):
for k in range(i+1, len(list)):
sums[i, k] = list[i] + list[k]

print 'Dictionary of sums:'
print sums

flipped = {}
for key, value in sums.iteritems():
if value not in flipped:
flipped[value] = [key]
else:
flipped[value].append(key)

print 'Flipped dictionary of sums'
print flipped

for key, value in flipped.iteritems():
if len(value) > 1:
for i in range(len(value)):
for k in range(i+1, len(value)):
print 'SUM = {key}'.format(key=key),
print value[i] + value[k]

list = [3,4,7,1,2,9,8]
find_pairs_with_same_sums(list)``````

Dictionary of sums:
{(0, 1): 7, (1, 2): 11, (2, 5): 16, (1, 3): 5, (4, 6): 10, (1, 5): 13, (4, 5): 11, (5, 6): 17, (1, 4): 6, (2, 4): 9, (0, 6): 11, (2, 6): 15, (0, 5): 12, (3, 6): 9, (0, 4): 5, (2, 3): 8, (1, 6): 12, (0, 3): 4, (3, 4): 3, (0, 2): 10, (3, 5): 10}
Flipped dictionary of sums
{3: [(3, 4)], 4: [(0, 3)], 5: [(1, 3), (0, 4)], 6: [(1, 4)], 7: [(0, 1)], 8: [(2, 3)], 9: [(2, 4), (3, 6)], 10: [(4, 6), (0, 2), (3, 5)], 11: [(1, 2), (4, 5), (0, 6)], 12: [(0, 5), (1, 6)], 13: [(1, 5)], 15: [(2, 6)], 16: [(2, 5)], 17: [(5, 6)]}
SUM = 5 (1, 3, 0, 4)
SUM = 9 (2, 4, 3, 6)
SUM = 10 (4, 6, 0, 2)
SUM = 10 (4, 6, 3, 5)
SUM = 10 (0, 2, 3, 5)
SUM = 11 (1, 2, 4, 5)
SUM = 11 (1, 2, 0, 6)
SUM = 11 (4, 5, 0, 6)
SUM = 12 (0, 5, 1, 6)

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

Sort the array.
For each interval (i,j), find m,n in the interval which have the same sum.

``````struct ValIndx{
int value;
int index;
ValIndx(int v, int i):value(v), index(i){}
};
static int ValIndxCompare(const ValIndx& v1, const ValIndx& v2){
return v1.value < v2.value;
}
vector<ValIndx> v;
void find(vector<int>& nums){
int len = (int)nums.size();
if(len == 0)    return;
for(int i = 0; i < len; i ++){
ValIndx vi(nums[i],i);
v.push_back(vi);
}
sort(v.begin(), v.end(), ValIndxCompare);
for(int i = 0; i < len; i ++){
for(int j = i+1; j < len; j ++){
int sum = v[i].value + v[j].value;
int begin = i+1;
int end = j;
while(begin < end){
int part = v[begin].value + v[end].value;
if(part == sum){
cout << v[i].index << " " << v[j].index << " "
<< v[begin].index << " " << v[end].index << endl;
begin++;
end--;
}
if(part < sum){
begin++;
}
if(part > sum){
end--;
}
}
}
}
}``````

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

It's actually much more verbose than the other answers and relies on creating a separate sum object. But I find it easier to dissect at least.

``````@interface SumOfIndexes : NSObject

@property int firstIndex;
@property int secondIndex;
@property int sum;

@end

@implementation SumOfIndexes
@end

@implementation Calculator

{
NSArray *sums = [self createSumsFromArray:inputArray];

NSArray *matchingSums = [self matchingSums:sums];

return [self arrayOfIndexFromSums:matchingSums];
}

- (NSArray*)createSumsFromArray:(NSArray*)inputArray
{
NSMutableArray *sums = [[NSMutableArray alloc]init];

for (int a = 0; a < inputArray.count; a++)
{
for (int b = a; b < inputArray.count; b++)
{
if (b != a)
{
SumOfIndexes *newSum = [[SumOfIndexes alloc]init];
newSum.firstIndex = a;

newSum.secondIndex = b;
newSum.sum = [inputArray[newSum.firstIndex]intValue] + [inputArray[newSum.secondIndex]intValue];

}
}

}

return sums;
}

- (NSArray*)matchingSums:(NSArray*)sums
{
NSArray *matchingSums = [[NSArray alloc]init];

for (SumOfIndexes *aSum in sums)
{
NSPredicate *matchingSumsPred = [NSPredicate predicateWithFormat:@"sum == %@", @(aSum.sum)];

NSArray *currentMatchingSums = [sums filteredArrayUsingPredicate:matchingSumsPred];

if (currentMatchingSums.count > 1)
{
matchingSums = currentMatchingSums;
break;
}
}

return matchingSums;
}

- (NSArray*)arrayOfIndexFromSums:(NSArray*)sums
{
NSMutableArray *indexes = [[NSMutableArray alloc]init];

for (SumOfIndexes *aSum in sums)
{

if (indexes.count >= 4)
{
break;
}
}

return indexes;
}

@end``````

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

Here is a python implementation:

``````def eq_sums(arr):
if not arr:
return None

a, b, c, d = None, None, None, None
hash = {}
for i, x in enumerate(arr):
for j, y in enumerate(arr[i:]):
_found = hash.get(x+y)
print _found
if _found and _found != "%s-%s" % (x, y):
a, b = i, j
c, d = int(_found.split('-')[0]), int(_found.split('-')[1])
break
else:
hash.update({x+y: "%s-%s" % (x, y) })

return a, b, c, d

x = eq_sums([3,4,7,1,2,9,8])
print x``````

This is still a O(n^2) solution

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

A slight variations to print all sums (A + B = C + D )

``````let sums = [ ((x, y) , x + y ) | x <-  [3,4,7,1,2,9,8] , y <-  [3,4,7,1,2,9,8] , x < y ]
let combinations = [ ( fst i , fst j ) | i <- m , j <- m , (snd i ) == (snd j) && (fst i) /= (fst j) ]

gives :

[((3,7),(1,9)),((3,7),(2,8)),((3,9),(4,8)),((3,8),(4,7)),((3,8),(2,9)),((4,7),(3,8)),((4,7),(2,9)),((4,8),(3,9)),((1,4),(2,3)),((1,9),(3,7)),((1,9),(2,8)),((1,8),(2,7)),((2,3),(1,4)),((2,7),(1,8)),((2,9),(3,8)),((2,9),(4,7)),((2,8),(3,7)),((2,8),(1,9))]``````

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

Removing repeated sums :

{{
let combinations = [ ( fst i , fst j ) | i <- m , j <- m , (snd i ) == (snd j) && (fst i) /= (fst j) && (fst (fst i)) > (fst (fst j)) ]

[((3,7),(1,9)),((3,7),(2,8)),((3,8),(2,9)),((4,7),(3,8)),((4,7),(2,9)),((4,8),(3,9)),((2,3),(1,4)),((2,7),(1,8)),((2,8),(1,9))]

}}}

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

``````let combinations = [ ( fst i , fst j ) | i <- m , j <- m , (snd i ) == (snd j) && (fst i) /= (fst j) && (fst (fst i)) > (fst (fst j)) ]

[((3,7),(1,9)),((3,7),(2,8)),((3,8),(2,9)),((4,7),(3,8)),((4,7),(2,9)),((4,8),(3,9)),((2,3),(1,4)),((2,7),(1,8)),((2,8),(1,9))]``````

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

In PHP:

``````function printPairs(\$arr){

\$temp = array();
\$lenght = count(\$arr);

for(\$i=0;\$i<\$lenght-1;\$i++) {
\$j = \$lenght-1;
while(\$j>\$i) {
\$temp[\$arr[\$i]+\$arr[\$j]][] = array(\$i,\$j);
\$j--;
}
}
\$l = count(\$temp);

for(\$i=0;\$i<\$l;\$i++)
{
if(count(\$temp[\$i]) > 2){

for(\$k=0;\$k<count(\$temp[\$i])-1;\$k++) {
\$j=count(\$temp[\$i])-1;
while(\$j>\$k) {
echo '('.implode(',', \$temp[\$i][\$k]).','.implode(',', \$temp[\$i][\$j]).')';
\$j--;
}
}
} elseif(count(\$temp[\$i]) == 2) {
echo '('.implode(',', \$temp[\$i][0]).','.implode(',',\$temp[\$i][1]).')';
}
}

}``````

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

JAVA:
No sorting. Time O(n^2). Space O(n)

``````public static void printAllABCD(int[] vals) {
int sum = 0;
HashMap<Integer, ArrayList<Integer>> sumMap = new HashMap<Integer, ArrayList<Integer>>();
ArrayList<Integer> tmp;
int[][] sums = new int[vals.length][vals.length];
//Store all possible sums and indexes of the elements that give the sum
for (int i = 0; i < vals.length - 1; i++) {
for (int j = i + 1; j < vals.length; j++) {
if (sumMap.containsKey(vals[i] + vals[j])) {
tmp = sumMap.get(vals[i] + vals[j]);
if (tmp.contains(j) || tmp.contains(i)) {
continue;
} else {
}
} else {
tmp = new ArrayList<Integer>();
sumMap.put(vals[i] + vals[j], tmp);
}
}
}
//Iterate over the stored sums and output combination of indexes
for (Integer i : sumMap.keySet()) {
tmp = sumMap.get(i);
if (tmp.size() == 4) {
System.out.println(tmp + " = " + i);
} else if (tmp.size() > 4) {
for (int k = 0; k < tmp.size() - 2;) {
for (int j = k + 2; j < tmp.size();) {
System.out.println("[" + tmp.get(k) + ", " + tmp.get(k + 1) + ", " + tmp.get(j) + ", " + tmp.get(j + 1) + "] = " + i);
j = j + 2;
}
k = k + 2;
}
}
}
}``````

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

Isn't the space complexity O(n^2) here? You iterate through and store every possible pair, and there are n^2 pairs.

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

``````public static void findABEqualCDPoints(int[] values) {
Map<Integer, Index> sums = new HashMap<Integer, Index>();

for (int i=0; i<values.length; i++) {
for (int j=i+1; j<values.length; j++) {
int sum = values[i] + values[j];

if (sums.containsKey(sum)) {
Index point = sums.get(sum);

if (!point.isEqual(i, j) && point.indexOne < i && point.indexOne < j && point.indexTwo < i && point.indexTwo < j) {
System.out.println(sum);
System.out.println(point.indexOne + " " + point.indexTwo + " " + i + " " + j);
return;
}
} else {
sums.put(sum, new Index(i, j));
}
}
}
}``````

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

This solution actually maintains the correct keys in the array as the question states.

``````function findQuad(array \$arr) {
asort(\$arr);
\$keys = array_keys(\$arr);
\$vals = array_values(\$arr);
\$right = count(\$vals) - 1;
for (\$left = 0; \$left < \$right; \$right--) {
\$sum = \$vals[\$left] + \$vals[\$right];
\$i = \$left;
\$j = \$right - 1;
while (\$i < \$j) {
\$currSum = \$vals[\$i] + \$vals[\$j];
if (\$currSum == \$sum) {
echo \$keys[\$left] . ', ' . \$keys[\$right] . ', ' . \$keys[\$i] . ', ' . \$keys[\$j];
return;
} elseif (\$currSum < \$sum) {
\$i++;
} else {
\$j--;
}
}
}
}

echo implode(', ', \$sample) . "\n";

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

O(n^2)

``````import java.util.HashMap;
import java.util.Random;

public class Main {

private static Random rand = new Random();

//1

static public void main(String[] args){
int numTries = 10;
for(int i = 0; i < numTries; i++){
int n = Math.abs(rand.nextInt() % 20 + 5);
int[] input = new int[n];
for(int j = 0; j < n; j++){
input[j] = rand.nextInt() % 20;
}
solveEqn(input);
}
}

private static void solveEqn(int[] input){
HashMap<Integer, Indices> map = new HashMap<Integer, Indices>();
for(int i = 0; i < input.length - 1; i++){
for(int j = i + 1; j < input.length; j++){
int sum = input[i] + input[j];
Indices indices = map.get(sum);
if(indices != null){
if(indices.geti() != i && indices.getj() != j){
System.out.println(input[indices.geti()] + " + " + input[indices.getj()] + " = " + input[i] + " + " + input[j]);
return;
}
}
map.put(sum, new Indices(i, j));
}
}
System.out.println("No solution found.");
}

private static class Indices{
int i;
int j;

public Indices(int i, int j){
this.i = i;
this.j = j;
}

public int geti(){
return i;
}

public int getj(){
return j;
}
}

}``````

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

Here is the meat of the problem I'll let the consumer print the output to the console.

``````public static List<int> FindABEqualsCD(int[] A)
{
var memo = new Dictionary<int, List<int>>();
for(int i = 0; i < A.Length; i++)
{
for(int j = i + 1; j < A.Length, j++)
{
int t = A[i] + A[j]
if(!memo.ContainsKey(t))
{
memo.Add(t, new List<int>() { i, j };
}
else
{

return memo[t];
}
}
}
}

return null;``````

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

``````#include <unordered_map>
#include <vector>

using namespace std;

typedef pair<int, int> Pair;

vector<int> foursum(int in[], int len)
{
unordered_map<int, Pair> map;
vector<int> v;
for (int i = 0; i < len - 1; ++i)
{
for (int j = i + 1; j < len; ++j)
{
unordered_map<int, Pair>::iterator match = map.find(in[i] + in[j]);
if (match != map.end())
{
v.push_back(match->second.first);
v.push_back(match->second.second);
v.push_back(in[i]);
v.push_back(in[j]);
return v;
}
map[in[i] + in[j]] = Pair(in[i], in[j]);
}
}
return v;
}``````

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

``````public class findABEqualCDPoints {

public static void main(String args[]) {
int a[] = { 3, 4, 7, 1, 2, 9, 8 };
printSumPairsABCD(a);
}

public static void printSumPairsABCD(int[] a) {

HashMap<Integer, List<Index>> map = new HashMap<Integer, List<Index>>();
List<Index> list = new ArrayList<>();

for (int i = 0; i < a.length; i++) {
for (int j = i + 1; j < a.length; j++) {

Integer key = a[i] + a[j];
list = map.get(key);
if (list == null) {
list = new ArrayList<Index>();
} else {
for (Index index : list) {
System.out.println(a[index.indexA] + " " + a[index.indexB] + " -- " + a[j] + " " + a[i]);

if (index.indexA != i && index.indexB != j && index.indexB != i && index.indexA != j) {
System.out.println(index.indexA + " " +
index.indexB + " -- " + j + " " + i);
}
}
}
map.put(key, list);

}
}
}

static class Index {
int indexA;
int indexB;

Index(int indexA, int indexB) {
this.indexA = indexA;
this.indexB = indexB;
}
}
}``````

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

``````public static void print4Sum(int[] arr){
getSums(arr).values().forEach((x) -> printAllCombinations(x));
}

private static void printAllCombinations(List<Pair<Integer,Integer>> list){
for (int i = 0; i < list.size() - 1; i++){
Pair<Integer,Integer> p1 = list.get(i);
for (int j = i+1 ; j < list.size(); j++){
Pair<Integer,Integer> p2 = list.get(j);
System.out.printf("(%d,%d,%d,%d)\r\n",p1.getKey(),p1.getValue(),p2.getKey(),p2.getValue());
}
}
}

private static HashMap<Integer, List<Pair<Integer,Integer>>> getSums(int[] arr){
HashMap<Integer, List<Pair<Integer,Integer>>> result = new HashMap<Integer, List<Pair<Integer, Integer>>>();
if (arr.length < 4){
return result;
}
for (int i = 0 ; i < arr.length-1; i++){
if (i > 0 && arr[i] == arr[i-1]){
continue;
}
for (int j = i+1; j < arr.length; j++){
if (j > i + 1 && arr[j] == arr[j-1]){
continue;
}
int sum = arr[i] + arr[j];
List<Pair<Integer,Integer>> list;
if (!result.containsKey(sum)){
list = new ArrayList<>();
result.put(sum , list);
}
else{
list = result.get(sum);
}
}
}
return result;
}``````

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

``````import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;

public class SumOfTwoPairsInArray {

private static HashMap<Integer, ArrayList<Pair>> hm = new HashMap<Integer, ArrayList<Pair>>();
public static void checkIfTwoPairsHaveSameSum(int array[]) {

for(int i=0; i<array.length; i++) {
for(int j=i+1; j<array.length; j++) {
if(!hm.containsKey(array[i]+array[j])) {
ArrayList<Pair> arrayList = new ArrayList<Pair>();
hm.put(array[i]+array[j], arrayList);
}
else {
}
}
}
Iterator<Integer> itr = hm.keySet().iterator();
while(itr.hasNext()) {
Integer key = itr.next();
ArrayList<Pair> arrayList = hm.get(key);
if(arrayList.size() > 1) {
for(int i=0; i<arrayList.size(); i++) {
System.out.print("(" + arrayList.get(i).i + " , " + arrayList.get(i).j + " )");
}
System.out.println();
}

}
}
public static void main(String args[]) {
int array[] = {3,4,7,1,2,9,8};
checkIfTwoPairsHaveSameSum(array);
}
}

class Pair {
int i;
int j;
Pair(int i, int j) {
this.i = i;
this.j = j;
}
}``````

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

package arrays;

import java.util.HashMap;

public class FindSum {

public static void main(String[] args) {
System.out.println( "checking ");
int nums [] = {3,-4,7,1,2,-9,8};
HashMap <Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i =0; i < nums.length; i++)
map.put( nums[i], i);

for (int i =0; i< nums.length; i++){
int A= nums[i];
for (int j =i+1; j< nums.length -2 ; j++){
int B = nums[j];
int C = nums[j+1];
int D = A+B-C;
System.out.println("A+B-C = " + D );
System.out.println(" map contains? " + map.containsKey(D));

if(map.containsKey(D)){
int D_index = map.get(D) ;
System.out.println( "D_index from hashmap " + D_index);

System.out.println(i + "->"+nums[i]+ " ," +j + "->" +nums[j] + " ,"+
(j+1) + "->" +nums[j+1] +" ,"+map.get(D)+"->" + nums[+map.get(D)]);
}
}
}
}
}

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

Here is my answer with o(n^2) and use of Hash Map
The idea is A+B-C = D, loop through i & j, and check for D in hash map
package arrays;

``````import java.util.HashMap;

public class FindSum {

public static void main(String[] args) {
System.out.println( "checking ");
int nums [] = {3,-4,7,1,2,-9,8};
HashMap <Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i =0; i < nums.length; i++)
map.put( nums[i], i);

for (int i =0; i< nums.length; i++){
int A= nums[i];
for (int j =i+1; j< nums.length -2 ; j++){
int B = nums[j];
int C = nums[j+1];
int D = A+B-C;
System.out.println("A+B-C = " + D );
System.out.println("    map contains? " + map.containsKey(D));

if(map.containsKey(D)){
int  D_index = map.get(D) ;
System.out.println( "D_index from hashmap " + D_index);

System.out.println(i + "->"+nums[i]+ "  ," +j + "->" +nums[j] + "  ,"+
(j+1) + "->" +nums[j+1] +"  ,"+map.get(D)+"->" + nums[+map.get(D)]);
}
}
}
}
}``````

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

``````package arrays;

import java.util.HashMap;

public class FindSum {

public static void main(String[] args) {
System.out.println( "checking ");
int nums [] = {3,-4,7,1,2,-9,8};
HashMap <Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i =0; i < nums.length; i++)
map.put( nums[i], i);

for (int i =0; i< nums.length; i++){
int A= nums[i];
for (int j =i+1; j< nums.length -2 ; j++){
int B = nums[j];
int C = nums[j+1];
int D = A+B-C;
System.out.println("A+B-C = " + D );
System.out.println("    map contains? " + map.containsKey(D));

if(map.containsKey(D)){
int  D_index = map.get(D) ;
System.out.println( "D_index from hashmap " + D_index);

System.out.println(i + "->"+nums[i]+ "  ," +j + "->" +nums[j] + "  ,"+
(j+1) + "->" +nums[j+1] +"  ,"+map.get(D)+"->" + nums[+map.get(D)]);
}
}
}
}
}``````

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

``````import java.util.HashMap;

public class FindSum {

public static void main(String[] args) {
System.out.println( "checking ");
int nums [] = {3,-4,7,1,2,-9,8};
HashMap <Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i =0; i < nums.length; i++)
map.put( nums[i], i);

for (int i =0; i< nums.length; i++){
int A= nums[i];
for (int j =i+1; j< nums.length -2 ; j++){
int B = nums[j];
int C = nums[j+1];
int D = A+B-C;
System.out.println("A+B-C = " + D );
System.out.println("    map contains? " + map.containsKey(D));

if(map.containsKey(D)){
int  D_index = map.get(D) ;
System.out.println( "D_index from hashmap " + D_index);

System.out.println(i + "->"+nums[i]+ "  ," +j + "->" +nums[j] + "  ,"+
(j+1) + "->" +nums[j+1] +"  ,"+map.get(D)+"->" + nums[+map.get(D)]);
}
}
}
}
}``````

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

O(n^2) in java:

``````public static void main(String[] args) {
int[] arr = {3, 4, 7, 1, 2, 9, 8};
findFactors(arr);
}

static class Factors {
public Factors(int A, int B) {
this.A = A;
this.B = B;
}
int A;
int B;
}

public static void findFactors(int[] arr) {
Map<Integer, Factors> m = new HashMap<>();
int aux = 0;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
aux = arr[i] + arr[j];
if (m.containsKey(aux)) {
System.out.println(arr[i] + " + " + arr[j] + " = " + arr[m.get(aux).A] + " + " + arr[m.get(aux).B]);
System.out.println("(" + i + "," + j + "," + m.get(aux).A + "," + m.get(aux).B + ")");
} else {
m.put(aux, new Factors(i, j));
}
}
}
}``````

Output:
4 + 7 = 3 + 8
(1,2,0,6)
4 + 1 = 3 + 2
(1,3,0,4)
4 + 8 = 3 + 9
(1,6,0,5)
1 + 9 = 3 + 7
(3,5,0,2)
1 + 8 = 7 + 2
(3,6,2,4)
2 + 9 = 3 + 8
(4,5,0,6)
2 + 8 = 3 + 7
(4,6,0,2)

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

``````#include<bits/stdc++.h>
using namespace std;

int main(void)
{
int A[] = {3,4,7,1,2,9,8};
int N = sizeof(A)/sizeof(A[0]);
sort(A,A+N);
map<int,pair<int,int> > M;
vector<int> P;
for(int i=0;i<N-1;i++)
for(int j=i+1;j<N;j++)
{
int sum = A[i] + A[j];
if(M.find(sum) == M.end())
M.insert(make_pair(sum,make_pair(i,j)));
else
{
int C = M.find(sum)->second.first;
int D = M.find(sum)->second.second;
if(i != C && i != D && j != C && j != D)
cout<<A[i]<<" "<<A[j]<<" "<<A[C]<<" "<<A[D]<<endl;
}
}
return 0;
}``````

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

``````#include<iostream>
using namespace std;

bool isPairWiseSumEqual(int arr[], int start, int end)
{
for(int i=0;i<end;i++)
{
for(int j=i;j<=end;j++)
{
if(arr[i] > arr[j])
swap(arr[i], arr[j]);
}
}
if(arr[0]+arr[end] == arr[1]+arr[end-1])
{
cout<<arr[0]<<" + "<<arr[end]<<" = "<<arr[1]<<" + "<<arr[end-1]<<endl;
return true;
}
return false;
}

int i = 1;
void getFourNumbers(int arr[], int startA, int endA, int data[], int startD, int endD)
{
if(startA<=endA+1)
{
if(startD == endD+1)
{
int temp[endD+1];
for(int i=0;i<=endD;i++)
{
temp[i] = data[i];
}
bool check = isPairWiseSumEqual(temp, 0, endD);
i++;
return;
}
data[startD] = arr[startA];

getFourNumbers(arr, startA+1, endA, data, startD+1, endD);
getFourNumbers(arr, startA+1, endA, data, startD, endD);
}
}

void function(int arr[], int size)
{
int data[4];
getFourNumbers(arr, 0, size, data, 0, 3);
}

int main()
{
int arr[] = {3,4,7,1,2,9,8};
int size = sizeof(arr)/sizeof(*arr);

function(arr, size-1);

cout<<endl;
system("PAUSE");
return 0;
}``````

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

import java.util.*;
import java.util.Map.Entry;

public class ABCDArraySum {

static class Indices {
int x;
int y;

public Indices(int x, int y) {
this.x = x;
this.y = y;
}
}

static class Result {
Indices AB;
Indices CD;
int sum;

public Result(Indices AB, Indices CD, int sum) {
this.AB = AB;
this.CD = CD;
this.sum = sum;
}
}

public static void main(String[] args) {
Result res = getIndices(new int[] { 3, 4, 7, 1, 2, 9, 8 });
System.out.println("Sum Obtained: " + res.sum);
System.out.println("Indices: (" + res.AB.x + "," + res.AB.y + ")("
+ res.CD.x + "," + res.CD.y + ")");

}

private static Result getIndices(int[] arr) {
Result res = null;
Map<Integer, List<Indices>> resultMap = new HashMap<Integer, List<Indices>>();

int sum = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
sum = arr[i] + arr[j];
if (!resultMap.containsKey(sum)) {
resultMap.put(sum, new ArrayList<Indices>());
}

List<Indices> temp = resultMap.get(sum);
Indices ind = new Indices(i, j);
}
}

Set<Entry<Integer, List<Indices>>> set = resultMap.entrySet();
Iterator<Entry<Integer, List<Indices>>> iter = set.iterator();

while (iter.hasNext()) {
Entry<Integer, List<Indices>> val = iter.next();
if (val.getValue().size() >= 2) {
res = new Result(val.getValue().get(0), val.getValue().get(1),
arr[val.getValue().get(0).x]
+ arr[val.getValue().get(0).y]);
break;
}
}
return res;
}
}

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

Brute force runtime complexity of this algorithm is O(N^2).

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.