Facebook Interview Question for Software Engineer / Developers


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

- ronnie.alonso October 13, 2014 | Flag Reply
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)
{
	//output all the valid quadruple
}

- Anonymous October 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Amy February 27, 2015 | Flag
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.

- T_Dog October 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- qlxf October 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

T Dog is right.

- juliusjun November 07, 2014 | Flag
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])) {
map.get(arr[i] + arr[j]).add(p);
} else {
ArrayList<Pair> arrList = new ArrayList<Pair>();
arrList.add(p);
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;
}
}

- Anonymous October 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what would the time complexity of this be?

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

is it O(n^2)?

- Anonymous October 11, 2014 | Flag
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);
    }
}

- Fastest and shortest solution in PHP in O ( n!/2*(n-2)! ) November 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- guilleg88 November 20, 2014 | Flag
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?

- Q October 10, 2014 | Flag Reply
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)

- r October 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How is this supposed to work?

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

u see a bug?

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

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

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

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

- sudharshan October 11, 2014 | Flag
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.

- Anonymous October 10, 2014 | Flag Reply
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..

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

is this O(n^4)?

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

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

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

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

- Johnson October 10, 2014 | Flag
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.

- Rahul Sharma October 10, 2014 | Flag Reply
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]);
}
}
}

Console.Read();

- Misa October 10, 2014 | Flag Reply
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)

- Anonymous October 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- India October 10, 2014 | Flag
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>();
				}
				list.add(new Point(i,j));
				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;
	}

- Anonymous October 10, 2014 | Flag Reply
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;

void twoPairsSum()
{
	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;
				}
			}
		}
	}
}

- Victor October 11, 2014 | Flag Reply
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

- hatemfaheem October 12, 2014 | Flag Reply
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

- alisovenko October 12, 2014 | Flag Reply
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--;
			}
		}
	}

- Anonymous October 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 votes

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

- bankertapan October 12, 2014 | Flag
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

- alisovenko October 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

only considering quadruplets involving arr[0]

- just_do_it October 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- hirajhil October 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- xdg October 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- victor November 02, 2014 | Flag
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)

- Anuj November 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This solution makes absolutely NO sense.

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

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

- Anonymous November 10, 2014 | Flag
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)
      sums.setdefault(iv + jv, set()).add(tup)
  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

- Igor October 16, 2014 | Flag Reply
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)

- Elena Henderson October 16, 2014 | Flag Reply
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--;
                    }
                }
            }
        }
    }

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

Here's an answer in Objective-C
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*)findIndexesOfNumbersThatCanBeAddedTogetherFrom:(NSArray*)inputArray
{
    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];
                
                [sums addObject:newSum];
            }
        }
        
    }
    
    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)
    {
        [indexes addObject:@(aSum.firstIndex)];
        [indexes addObject:@(aSum.secondIndex)];
        
        if (indexes.count >= 4)
        {
            break;
        }
    }
    
    return indexes;
}

@end

- Mark October 19, 2014 | Flag Reply
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

- Karthik Ravindra October 19, 2014 | Flag Reply
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))]

- Anonymous October 21, 2014 | Flag Reply
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))]

}}}

- Anonymous October 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- AD October 21, 2014 | Flag
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]).')';
        }
    }

}

- Bianca October 21, 2014 | Flag Reply
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 {
                        tmp.add(j);
                        tmp.add(i);
                    }
                } else {
                    tmp = new ArrayList<Integer>();
                    tmp.add(j);
                    tmp.add(i);
                    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;
                }
            }
        }
    }

- walD October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- naji247 October 27, 2014 | Flag
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));
                }
            }
        }
    }

- Anonymous October 28, 2014 | Flag Reply
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";
findQuad($sample);

- Nick November 02, 2014 | Flag Reply
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;
		}
	}
	
}

- cubed November 06, 2014 | Flag Reply
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
			{
				memo[t].Add(i);
				memo[t].Add(j);

				return memo[t];
			}
		}
	}
}

return null;

- Nelson Perez January 05, 2015 | Flag Reply
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;
}

- Nick January 14, 2015 | Flag Reply
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>();
                    list.add(new Index(i, j));
                } 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);
                        }
                    }
                    list.add(new Index(i, j));
                }
                map.put(key, list);

            }
        }
    }

    static class Index {
        int indexA;
        int indexB;

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

- Magemello January 31, 2015 | Flag Reply
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);
                }
                list.add(new Pair<>(i, j));
            }
        }
        return result;
    }

- GK February 01, 2015 | Flag Reply
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>();
					arrayList.add(new Pair(i,j));
					hm.put(array[i]+array[j], arrayList);
				}
				else {
					hm.get(array[i]+array[j]).add(new Pair(i,j));
				}
			}
		}
		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;
	}
}

- anirudh690 February 11, 2015 | Flag Reply
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)]);
}
}
}
}
}

- KaKathy March 16, 2015 | Flag Reply
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)]);
	    		   }	   
	    	   }   
	       }  
	  }
}

- KaKathy March 16, 2015 | Flag Reply
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)]);
	    		   }	   
	    	   }   
	       }  
	  }
    }

- KaKathy March 16, 2015 | Flag Reply
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)]);
				    		   }	   
				    	   }   
				       }  
				  }
			}

- KaKathy March 16, 2015 | Flag Reply
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)

- NL March 23, 2015 | Flag Reply
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;
}

- Goku June 20, 2015 | Flag Reply
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;
}

- skum July 08, 2015 | Flag Reply
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);
temp.add(temp.size(), ind);
}
}

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

- Srikar Rao March 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Albert Pinto February 07, 2018 | Flag Reply


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