Bloomberg LP Interview Question for Software Engineer Interns


Country: England
Interview Type: Phone Interview




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

This solution was written on stackoverflow, I just remembered having a similar question in an assignment once.

There are 3 approaches to this solution:

Let the sum be T and n be the size of array

Approach 1:
The naive way to do this would be to check all combinations (n choose 2). This exhaustive search is O(n2).

Approach 2:
A better way would be to sort the array. This takes O(n log n)
Then for each x in array A, use binary search to look for T-x. This will take O(nlogn).
So, overall search is O(n log n)

Approach 3 :
The best way would be to insert every element into a hash table (without sorting). This takes O(n) as constant time insertion.
Then for every x, we can just look up its complement, T-x, which is O(1).
Overall the run time of this approach is O(n).

- Ayan October 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The hash map solution will not work for duplicate elements.

- T December 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

@T: HashMap soln can work if you put count of occurrence i.e frequency in map's value. Decrement value if pair is found,.

- prodigy January 16, 2016 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

There are 3 approaches to this solution:

Let the sum be T and n be the size of array

Approach 1:
The naive way to do this would be to check all combinations (n choose 2). This exhaustive search is O(n2).

Approach 2:
A better way would be to sort the array. This takes O(n log n)
Then for each x in array A, use binary search to look for T-x. This will take O(nlogn).
So, overall search is O(n log n)

Approach 3 :
The best way would be to insert every element into a hash table (without sorting). This takes O(n) as constant time insertion.
Then for every x, we can just look up its complement, T-x, which is O(1).
Overall the run time of this approach is O(n).


(Source: stackO)

- Ayan October 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

c++, brute force, O(n^2)

void printBigPair(vector<int>& arr, int N) {
    unsigned int i, j;

    for (i = 0; i < arr.size(); i++) {
        for (j = i + 1; j < arr.size(); j++) {
            if (arr[i] + arr[j] > N) cout << "(" << arr[i] << ", " << arr[j] << ") ";
        }
    }
    cout << "\n";
}

- kyduke October 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function printPairs(A,N) {
    A.sort();
    
    for (var l = 0, r = A.length - 1; l < r; ) {
    	var a = A[l],
    		b = A[r];
        var sum = a + b;
        if (sum > N) r--;
        else if (sum < N) l++;
        else {
        	console.log(a,b);
        	if (l < A.length - 1 && (A[l+1]+b) <= sum) l++;
        	else r--;
        }
    }

}

- optimizer October 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(nlog(n))
js:

function printPairs(A,N) {
    A.sort();
    
    for (var l = 0, r = A.length - 1; l < r; ) {
    	var a = A[l],
    		b = A[r];
        var sum = a + b;
        if (sum > N) r--;
        else if (sum < N) l++;
        else {
        	console.log(a,b);
        	if (l < A.length - 1 && (A[l+1]+b) <= sum) l++;
        	else r--;
        }
    }

}

- Anonymous October 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Any better solution than n^2 ?

- Shiva October 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void findPairs(int[] a,int sum){

        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        Set<Integer> set = new HashSet<>();

        for (int n : a){

            if(set.contains(sum-n)) System.out.println(sum - n + " " + n);
            else set.add(n);
        }

- goku0609 October 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void findPairs(int[] a,int sum){

ArrayList<ArrayList<Integer>> result = new ArrayList<>();
Set<Integer> set = new HashSet<>();

for (int n : a){

if(set.contains(sum-n)) System.out.println(sum - n + " " + n);
else set.add(n);
}

- goku0609 October 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void findPairs(int iArr[SIZE],int N)
{
	int diff =0;
	for(int i=0;i<SIZE;i++)
	{
		for(int j=i+1;j<SIZE;j++)
		{
			diff = N - iArr[i];
			if(iArr[j]==diff)
				cout << endl <<" findpairs "<<iArr[i] << "," << iArr[j];
		}
	}
}

- SV October 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Written in python
O(n)

def sum_N(A, N):
    d = dict()
    l = []
    for i in A:
        if (N-i) not in d:
            d[i] = 1
        else:
            l.append((i, N-i))

    return l

z  = sum_N([1, 2, 3, 5, 5, 9], 10)
print(z)

- Anish Adhikari November 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def sum_N(A, N):
    d = dict()
    l = []
    for i in A:
        if (N-i) not in d:
            d[i] = 1
        else:
            l.append((i, N-i))

    return l

z  = sum_N([1, 2, 3, 5, 5, 9], 10)
print(z)

- Anish Adhikari November 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

max runtime is O(n)

- anish531213 November 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

def sum_N(A, N):
d = dict()
l = []
for i in A:
if (N-i) not in d:
d[i] = 1
else:
l.append((i, N-i))

return l

z = sum_N([1, 2, 3, 5, 5, 9], 10)
print(z)

- Anish Adhikari November 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Iterative using O(nlogn)
    public static void pairWithSum(int[] input, int sum) {

        Arrays.sort(input); //sorting in increasing order
        
        int l = 0;
        int r = input.length - 1;

        while (l < r) {
            if (input[l] + input[r] == sum) {
//                count++;
                System.out.println("Pair with given sum " + sum + " is (" + input[l] + ", " + input[r] + ")");
                // break;
                l++;
                r--;
            } else if (input[l] + input[r] > sum) {
                r--;
            } else {
                l++;
            }
        }
    }

    
    //using O(n)
    private static final int MAX = 100000; // Max size of Hashmap

    static void printpairsUsingMap(int arr[], int sum) {

        // Declares and initializes the whole array as false
        boolean[] map = new boolean[MAX];

        for (int i = 0; i < arr.length; ++i) {
            int find = sum - arr[i];

            if (find >= 0 && map[find]) {
                System.out.println("Pair with given sum " + sum + " is (" + arr[i] + ", " + find + ")");
            } else {
                map[arr[i]] = true;
            }
        }
    }

- shobhit657 November 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

p A.combination(2).find_all { |pair| N == pair.reduce(:+) }

Prints

[[3, 7], [6, 4]]

for an A given in question and N=10.
Written in Ruby

- Phil Pirozhkov November 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My O(n) solution in Scala:

import scala.annotation.tailrec

object ZeroSumArray {
  def findZeroSumPairs(arr: Array[Int], targetSum: Int): List[(Int, Int)] = {
    val v = arr.toList.groupBy(x => x)

    @tailrec
    def go(in: List[Int], targetSum: Int, result: List[(Int, Int)]): List[(Int, Int)] = {
      in match {
        case Nil => result
        case (h::t) if h <= targetSum-h => go(t, targetSum, result)
        case (h::t) if h >  targetSum-h =>
          val pairs = v.getOrElse(targetSum-h, Nil).map(_ => (h, targetSum-h))
          go(t, targetSum, pairs ++ result)
      }
    }

    go(arr.toList, targetSum, Nil)
  }

  def main(args: Array[String]): Unit = {
    val arr1 = Array(1, 4, 5, 7, 8, -1, -1, 1, -6, -8, -3)
    println(findZeroSumPairs(arr1, 0))
    println(findZeroSumPairs(arr1, 8))
    println(findZeroSumPairs(arr1, 5))
    println(findZeroSumPairs(arr1, 6))

    /*
      Result:
      List((1,-1), (1,-1), (8,-8), (1,-1), (1,-1))
      List((7,1), (7,1))
      List((8,-3), (4,1), (4,1))
      List((7,-1), (7,-1), (5,1), (5,1))
     */
  }
}

- akmo75 November 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<string>
#include<vector>
#include<thread>
#include<algorithm>

using namespace std;

void bruteForce(vector<int> &v,int n)
{
    auto nbInstr=0;
    for(auto i=0;i<v.size()-1;++i)
    {
        for(auto j=i+1;j<v.size();++j)
        {
            if(v[i]+v[j]==n)
                cout<<"("<<v[i]<<","<<v[j]<<")"<<endl;
            nbInstr++;
        }
    }
    cout<<"For a vector of size ("<<v.size()<<"), bruteForce took ("<<nbInstr<<") iteration"<<endl;
}

void sorting(vector<int> &v,int n)
{
    auto nbInstr=0;
    sort(v.begin(),v.end());
    for(auto i=0;i<v.size()-1;++i)
    {
         for(auto j=i+1;j<v.size();++j)
        {
            if(n-v[i]==v[j])
                cout<<"("<<v[i]<<","<<v[j]<<")"<<endl;
            nbInstr++;
        }
    }
    cout<<"For a vector of size ("<<v.size()<<"), sorting took ("<<nbInstr<<") iteration"<<endl;
}

void third(vector<int> &v,int n)
{
   auto nbInstr=0;
   vector<int> tmp(n,0);
   
   for(auto i=0;i<v.size();++i)
   {
       if(v[i]<n)
            tmp[v[i]]=v[i];
        nbInstr++;
    }
    for(auto i=0;i<tmp.size()/2;++i)
    {
        if(tmp[i]!=0 && tmp[n-i]!=0)
            cout<<"("<<tmp[i]<<","<<tmp[n-i]<<")"<<endl;
        nbInstr++;
    }
    cout<<"For a vector of size ("<<v.size()<<"), sorting took ("<<nbInstr<<") iteration"<<endl;
}

int main()
{
   vector<int> v= {3,7,2,5,6,4,1,0,8};
   bruteForce(v,8);
   sorting(v,8);
   third(v,8);

}

- Anonymous November 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<string>
#include<vector>
#include<thread>
#include<algorithm>

using namespace std;

void bruteForce(vector<int> &v,int n)
{
    auto nbInstr=0;
    for(auto i=0;i<v.size()-1;++i)
    {
        for(auto j=i+1;j<v.size();++j)
        {
            if(v[i]+v[j]==n)
                cout<<"("<<v[i]<<","<<v[j]<<")"<<endl;
            nbInstr++;
        }
    }
    cout<<"For a vector of size ("<<v.size()<<"), bruteForce took ("<<nbInstr<<") iteration"<<endl;
}

void sorting(vector<int> &v,int n)
{
    auto nbInstr=0;
    sort(v.begin(),v.end());
    for(auto i=0;i<v.size()-1;++i)
    {
         for(auto j=i+1;j<v.size();++j)
        {
            if(n-v[i]==v[j])
                cout<<"("<<v[i]<<","<<v[j]<<")"<<endl;
            nbInstr++;
        }
    }
    cout<<"For a vector of size ("<<v.size()<<"), sorting took ("<<nbInstr<<") iteration"<<endl;
}

void third(vector<int> &v,int n)
{
   auto nbInstr=0;
   vector<int> tmp(n,0);
   
   for(auto i=0;i<v.size();++i)
   {
       if(v[i]<n)
            tmp[v[i]]=v[i];
        nbInstr++;
    }
    for(auto i=0;i<tmp.size()/2;++i)
    {
        if(tmp[i]!=0 && tmp[n-i]!=0)
            cout<<"("<<tmp[i]<<","<<tmp[n-i]<<")"<<endl;
        nbInstr++;
    }
    cout<<"For a vector of size ("<<v.size()<<"), sorting took ("<<nbInstr<<") iteration"<<endl;
}

int main()
{
   vector<int> v= {3,7,2,5,6,4,1,0,8};
   bruteForce(v,8);
   sorting(v,8);
   third(v,8);

}

- Dali November 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for (int i=0;i<n.length;i++)
		{
			for (int j=1;j<n.length;j++)
			{
			
				
				if ( n[i] + n[j] == x){
					
				if (i < j)
				{
				System.out.println(n[i] + " " +  n[j]);
				}
				}
			}
			
			
		}

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

for (int i=0;i<n.length;i++)
		{
			for (int j=1;j<n.length;j++)
			{
			
				
				if ( n[i] + n[j] == x){
					
				if (i < j)
				{
				System.out.println(n[i] + " " +  n[j]);
				}
				}
			}
			
			
		}

- sam March 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;

int main()
{
int n,m;
cin>>n>>m;

int j;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];

for(int i=1;i<n;i++)
{
j=0;
while(j<i )
{
if( arr[j]+arr[i] == m )
cout<<"{ "<<arr[j]<<","<<arr[i]<<" }"<<endl;
j++;
}
}

}

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

#include<iostream>
using namespace std;

int main()
{
	int n,m;
	cin>>n>>m;
	
	int j;
	int arr[n];
	for(int i=0;i<n;i++)
		cin>>arr[i];
		
	for(int i=1;i<n;i++)
	{
		j=0;
		while(j<i )
		{
			if( arr[j]+arr[i] == m )
				cout<<"{ "<<arr[j]<<","<<arr[i]<<" }"<<endl;
		j++;
		}			
	}
	
}

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

#include<iostream>
using namespace std;

int main()
{
	int n,m;
	cin>>n>>m;
	
	int j;
	int arr[n];
	for(int i=0;i<n;i++)
		cin>>arr[i];
		
	for(int i=1;i<n;i++)
	{
		j=0;
		while(j<i )
		{
			if( arr[j]+arr[i] == m )
				cout<<"{ "<<arr[j]<<","<<arr[i]<<" }"<<endl;
		j++;
		}			
	}
	
}

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

//Find unique pair in an array
        int[] findPair = {3,7,2,5,6,4,3,5,4};
        int length = findPair.length;
        List<Integer> myList = new ArrayList<Integer>();

        for(int i = 0; i < length; i++){
            if(myList.contains(i))
            continue;
            for(int j = i+1; j < length; j++){
                if(myList.contains(j))
                    continue;
                if((findPair[i]+findPair[j]) == 9){
                    System.out.println("Found Pair " + findPair[i] + ","+ findPair[j]);
                    myList.add(findPair[i]);
                    myList.add(findPair[j]);
                }

            }
        }

- HS September 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Find unique pair in an array
        int[] findPair = {3,7,2,5,6,4,3,5,4};
        int length = findPair.length;
        List<Integer> myList = new ArrayList<Integer>();

        for(int i = 0; i < length; i++){
            if(myList.contains(i))
            continue;
            for(int j = i+1; j < length; j++){
                if(myList.contains(j))
                    continue;
                if((findPair[i]+findPair[j]) == 9){
                    System.out.println("Found Pair " + findPair[i] + ","+ findPair[j]);
                    myList.add(findPair[i]);
                    myList.add(findPair[j]);
                }

            }
        }

- HS September 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Find unique pair in an array
int[] findPair = {3,7,2,5,6,4,3,5,4};
int length = findPair.length;
List<Integer> myList = new ArrayList<Integer>();

for(int i = 0; i < length; i++){
if(myList.contains(i))
continue;
for(int j = i+1; j < length; j++){
if(myList.contains(j))
continue;
if((findPair[i]+findPair[j]) == 9){
System.out.println("Found Pair " + findPair[i] + ","+ findPair[j]);
myList.add(findPair[i]);
myList.add(findPair[j]);
}

}
}

- HS September 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def sumEqualNum(inp_list, N):
    dict_of_seen_comp = {}
    setSeen = set()
    pairs= []
    for i in inp_list:
        if i in dict_of_seen_comp:
            dict_of_seen_comp[i] = 1
        elif i not in setSeen:
            dict_of_seen_comp[N-i] = 0
            setSeen.add(i)
    for pair_value, count in dict_of_seen_comp.items():
        if count == 1:
            pairs.append((pair_value, N-pair_value))
    return pairs
print(sumEqualNum([3,7,2,5,6,4], 10))

- sg_coffee September 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include<map>
using namespace std;
int main()
{
int arr[]={3,7,2,5,6,4};
int num=9;
map<int ,int> map_out;
for(int i=0; i <sizeof(arr)/sizeof(int);i++)
{
        map_out[arr[i]]=num-arr[i];
}
map<int ,int> ::iterator itr;
for(itr=map_out.begin() ;itr != map_out.end();itr++)
cout << "{" <<itr->first << ","<< itr->second <<"}"<<endl;
}

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

O(n) solution using a hash table in Python.

def countPairs(arr, k):
    temp = dict()
    for a in arr:
        if a in temp:
            temp[a] += 1
        else:
            temp[a] = 1
        
    count = 0    
    for a in arr:
        if k-a in temp:
            count += temp[k-a]
            
        if k-a == a:
            count -= 1
            
    return count / 2
    
arr = [3, 3]
k = 6
print countPairs(arr, k)

Below is the Algorithm.

1) Create a map to store frequency of each number in the array.

2) In the next traversal, for every element check if it can be combined with
any other element (other than itself!) to give the desired sum.
Increment the counter accordingly.

3) After completion of second traversal, we would have twice the required value
stored in counter because every pair is counted two times.
Hence divide count by 2 and return.

- Prem Nagarajan October 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) solution using hash table in python.

def countPairs(arr, k):
    temp = dict()
    for a in arr:
        if a in temp:
            temp[a] += 1
        else:
            temp[a] = 1
        
    count = 0    
    for a in arr:
        if k-a in temp:
            count += temp[k-a]
            
        if k-a == a:
            count -= 1
            
    return count / 2
    
arr = [3, 3]
k = 6
print countPairs(arr, k)

Below is the Algorithm.

1) Create a map to store frequency of each number in the array.

2) In the next traversal, for every element check if it can be combined with
any other element (other than itself!) to give the desired sum.
Increment the counter accordingly.

3) After completion of second traversal, we would have twice the required value
stored in counter because every pair is counted two times.
Hence divide count by 2 and return.

- Prem October 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) solution using hash table in python.

def countPairs(arr, k):
    temp = dict()
    for a in arr:
        if a in temp:
            temp[a] += 1
        else:
            temp[a] = 1
        
    count = 0    
    for a in arr:
        if k-a in temp:
            count += temp[k-a]
            
        if k-a == a:
            count -= 1
            
    return count / 2
    
arr = [3, 3]
k = 6
print countPairs(arr, k)

Below is the Algorithm.

1) Create a map to store frequency of each number in the array.

2) In the next traversal, for every element check if it can be combined with
any other element (other than itself!) to give the desired sum.
Increment the counter accordingly.

3) After completion of second traversal, we would have twice the required value
stored in counter because every pair is counted two times.
Hence divide count by 2 and return.

- prem.cmnagar October 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//
// Given an array A = [3, 7, 2,5,6,4] for a number N, print the pairs 
// from that array A that sums up to N. You should print each pair once.
//
//   -- nonameno October 29, 2015 in England
//      Bloomberg LP Interview Question for Software Engineer Interns
//
// Run with VM arguments -ea to enable assert testing
//
// (c) 2016 Perry Anderson, All Rights Reserved, worldwide.
//
//

import java.util.Vector;

class Pair<L,R> {
    private L l;
    private R r;
    public Pair(L l, R r){
        this.l = l;
        this.r = r;
    }
    public L getL(){ return l; }
    public R getR(){ return r; }
    public void setL(L l){ this.l = l; }
    public void setR(R r){ this.r = r; }
    public String toString() { return "{ " + l + ", " + r + " }"; }
}

public class LPMain009 {

	static boolean duplicateFound(Vector<Pair<Integer,Integer>> 
	   pairs, Pair<Integer,Integer> newPair) {
		for ( Pair<Integer,Integer> pair : pairs ) {
			if ( pair.getL() == newPair.getR() 
			&&  pair.getR() == newPair.getL() )
				return true;
		}
		return false;
	}
	
	static Integer[][] sortPairs(Integer[] data, int N) {
		
		Vector<Pair<Integer,Integer>> pairs 
		   = new Vector<Pair<Integer,Integer>>();
		
		/*
		 * First we take each two number combination except
		 * for the same number compared against itself and
		 * see if the total is equal to N
		 */
		for (int x = 0; x < data.length; x++) {
			for (int y = 0; y < data.length; y++) {
				if ( data[x] != data[y] )
					if ( data[x] + data[y] == N ) {
						Pair<Integer, Integer> newPair 
						   = new Pair<Integer, Integer>(data[x],data[y]);
						if ( !duplicateFound(pairs,newPair))
							pairs.add(newPair);
					}
			}
		}
		
		Integer[][] results = new Integer[pairs.size()][2]; 
		int i = 0;
		for ( Pair<Integer,Integer> pair : pairs ) {
			Integer[] dual = { pair.getL(), pair.getR() };
			results[i++] = dual;
		}
		
		return results;
		
	}

	public static void main(String[] args) {

		Integer[] data1 = new Integer[] { 3,7,2,5,6,4 };
		Integer result1 = 10;
		Integer[][] test1 = new Integer[][] { { 3, 7 } , { 6, 4 } };
		
		
		/*
		 * Due to a glitch in the JVM we have to compare the arrays
		 * using a manual approach;
		 */
		
//		assert Arrays.equals(sortPairs(data1,result1), test1);
//		assert !Arrays.equals(sortPairs(data1,result1), test1);

		Integer[][] check = sortPairs(data1,result1);
		for ( int i=0; i<test1.length; i++ )
			if ( check[i][0] != test1[i][0] 
				|| check[i][1] != test1[i][1] )
				System.out.println("Different");	
	
		/*
		 * As per specification we need to print out the result.
		 */
		
		for ( int i=0; i<check.length; i++ ) {
			System.out.println(
					new Pair<Integer,Integer>(check[i][0],check[i][1]));
		}
		
	}

}

- perry.anderson November 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//
// Given an array A = [3, 7, 2,5,6,4] for a number N, print the pairs 
// from that array A that sums up to N. You should print each pair once.
//
//   -- nonameno October 29, 2015 in England
//      Bloomberg LP Interview Question for Software Engineer Interns
//
// Run with VM arguments -ea to enable assert testing
//
// (c) 2016 Perry Anderson, All Rights Reserved, worldwide.
//
//

import java.util.Vector;

class Pair<L,R> {
    private L l;
    private R r;
    public Pair(L l, R r){
        this.l = l;
        this.r = r;
    }
    public L getL(){ return l; }
    public R getR(){ return r; }
    public void setL(L l){ this.l = l; }
    public void setR(R r){ this.r = r; }
    public String toString() { return "{ " + l + ", " + r + " }"; }
}

public class LPMain009 {

	static boolean duplicateFound(Vector<Pair<Integer,Integer>> 
	   pairs, Pair<Integer,Integer> newPair) {
		for ( Pair<Integer,Integer> pair : pairs ) {
			if ( pair.getL() == newPair.getR() 
			&&  pair.getR() == newPair.getL() )
				return true;
		}
		return false;
	}
	
	static Integer[][] sortPairs(Integer[] data, int N) {
		
		Vector<Pair<Integer,Integer>> pairs 
		   = new Vector<Pair<Integer,Integer>>();
		
		/*
		 * First we take each two number combination except
		 * for the same number compared against itself and
		 * see if the total is equal to N
		 */
		for (int x = 0; x < data.length; x++) {
			for (int y = 0; y < data.length; y++) {
				if ( data[x] != data[y] )
					if ( data[x] + data[y] == N ) {
						Pair<Integer, Integer> newPair 
						   = new Pair<Integer, Integer>(data[x],data[y]);
						if ( !duplicateFound(pairs,newPair))
							pairs.add(newPair);
					}
			}
		}
		
		Integer[][] results = new Integer[pairs.size()][2]; 
		int i = 0;
		for ( Pair<Integer,Integer> pair : pairs ) {
			Integer[] dual = { pair.getL(), pair.getR() };
			results[i++] = dual;
		}
		
		return results;
		
	}

	public static void main(String[] args) {

		Integer[] data1 = new Integer[] { 3,7,2,5,6,4 };
		Integer result1 = 10;
		Integer[][] test1 = new Integer[][] { { 3, 7 } , { 6, 4 } };
		
		
		/*
		 * Due to a glitch in the JVM we have to compare the arrays
		 * using a manual approach;
		 */
		
//		assert Arrays.equals(sortPairs(data1,result1), test1);
//		assert !Arrays.equals(sortPairs(data1,result1), test1);

		Integer[][] check = sortPairs(data1,result1);
		for ( int i=0; i<test1.length; i++ )
			if ( check[i][0] != test1[i][0] 
				|| check[i][1] != test1[i][1] )
				System.out.println("Different");	
	
		/*
		 * As per specification we need to print out the result.
		 */
		
		for ( int i=0; i<check.length; i++ ) {
			System.out.println(
					new Pair<Integer,Integer>(check[i][0],check[i][1]));
		}
		
	}

}

- perry.anderson November 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//
// Given an array A = [3, 7, 2,5,6,4] for a number N, print the pairs 
// from that array A that sums up to N. You should print each pair once.
//
//   -- nonameno October 29, 2015 in England
//      Bloomberg LP Interview Question for Software Engineer Interns
//
// Run with VM arguments -ea to enable assert testing
//
// (c) 2016 Perry Anderson, All Rights Reserved, worldwide.
//
//

import java.util.Vector;

/*
 * The AWT Point class could have been used removing the
 * need to replicate much of the functionality here. However,
 * adding our own Pair class allows us to customize this
 * class for our purposes such that we override the toString()
 * method to show a preferred pair display.
 */
class Pair<L,R> {
    private L l;
    private R r;
    public Pair(L l, R r){
        this.l = l;
        this.r = r;
    }
    public L getL(){ return l; }
    public R getR(){ return r; }
    public void setL(L l){ this.l = l; }
    public void setR(R r){ this.r = r; }
    public String toString() { return "{ " + l + ", " + r + " }"; }
}

public class LPMain009 {

	/*
	 * The specification says "pairs from that array" so we
	 * can only assume that a single selection cannot be used
	 * twice to be considered a pair. We also have to print
	 * each pair once implying that we only need to store 
	 * each pair once. 
	 */
	
	static boolean duplicateFound(Vector<Pair<Integer,Integer>> 
	   pairs, Pair<Integer,Integer> newPair) {
		for ( Pair<Integer,Integer> pair : pairs ) {
			if ( pair.getL() == newPair.getR() 
			&&  pair.getR() == newPair.getL() )
				return true;
		}
		return false;
	}
	
	static Integer[][] sortPairs(Integer[] data, int N) {
		
		Vector<Pair<Integer,Integer>> pairs 
		   = new Vector<Pair<Integer,Integer>>();
		
		/*
		 * First we take each two number combination except
		 * for the same number compared against itself and
		 * see if the total is equal to N
		 */
		for (int x = 0; x < data.length; x++) {
			for (int y = 0; y < data.length; y++) {
				if ( data[x] != data[y] )
					if ( data[x] + data[y] == N ) {
						Pair<Integer, Integer> newPair 
						   = new Pair<Integer, Integer>(data[x],data[y]);
						if ( !duplicateFound(pairs,newPair))
							pairs.add(newPair);
					}
			}
		}
		
		/*
		 * Then, it is good programming practice to return the same type
		 * of data in a container as was used to pass the parameters.
		 */
		Integer[][] results = new Integer[pairs.size()][2]; 
		int i = 0;
		for ( Pair<Integer,Integer> pair : pairs ) {
			Integer[] dual = { pair.getL(), pair.getR() };
			results[i++] = dual;
		}
		
		return results;
		
	}

	public static void main(String[] args) {

		Integer[] data1 = new Integer[] { 3,7,2,5,6,4 };
		Integer result1 = 10;
		Integer[][] test1 = new Integer[][] { { 3, 7 } , { 6, 4 } };
		
		
		/*
		 * Due to a glitch in the JVM we have to compare the arrays
		 * using a manual approach;
		 */
		
//		assert Arrays.equals(sortPairs(data1,result1), test1);
//		assert !Arrays.equals(sortPairs(data1,result1), test1);

		Integer[][] check = sortPairs(data1,result1);
		for ( int i=0; i<test1.length; i++ )
			if ( check[i][0] != test1[i][0] 
				|| check[i][1] != test1[i][1] )
				System.out.println("Different");	
	
		/*
		 * As per specification we need to print out the result.
		 */
		
		for ( int i=0; i<check.length; i++ ) {
			System.out.println(
					new Pair<Integer,Integer>(check[i][0],check[i][1]));
		}
		
	}

}

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

//
// Given an array A = [3, 7, 2,5,6,4] for a number N, print the pairs 
// from that array A that sums up to N. You should print each pair once.
//
//   -- nonameno October 29, 2015 in England
//      Bloomberg LP Interview Question for Software Engineer Interns
//
// Run with VM arguments -ea to enable assert testing
//
// (c) 2016 Perry Anderson, All Rights Reserved, worldwide.
//
//

import java.util.Vector;

/*
 * The AWT Point class could have been used removing the
 * need to replicate much of the functionality here. However,
 * adding our own Pair class allows us to customize this
 * class for our purposes such that we override the toString()
 * method to show a preferred pair display.
 */
class Pair<L,R> {
    private L l;
    private R r;
    public Pair(L l, R r){
        this.l = l;
        this.r = r;
    }
    public L getL(){ return l; }
    public R getR(){ return r; }
    public void setL(L l){ this.l = l; }
    public void setR(R r){ this.r = r; }
    public String toString() { return "{ " + l + ", " + r + " }"; }
}

public class LPMain009 {

	/*
	 * The specification says "pairs from that array" so we
	 * can only assume that a single selection cannot be used
	 * twice to be considered a pair. We also have to print
	 * each pair once implying that we only need to store 
	 * each pair once. 
	 */
	
	static boolean duplicateFound(Vector<Pair<Integer,Integer>> 
	   pairs, Pair<Integer,Integer> newPair) {
		for ( Pair<Integer,Integer> pair : pairs ) {
			if ( pair.getL() == newPair.getR() 
			&&  pair.getR() == newPair.getL() )
				return true;
		}
		return false;
	}
	
	static Integer[][] sortPairs(Integer[] data, int N) {
		
		Vector<Pair<Integer,Integer>> pairs 
		   = new Vector<Pair<Integer,Integer>>();
		
		/*
		 * First we take each two number combination except
		 * for the same number compared against itself and
		 * see if the total is equal to N
		 */
		for (int x = 0; x < data.length; x++) {
			for (int y = 0; y < data.length; y++) {
				if ( data[x] != data[y] )
					if ( data[x] + data[y] == N ) {
						Pair<Integer, Integer> newPair 
						   = new Pair<Integer, Integer>(data[x],data[y]);
						if ( !duplicateFound(pairs,newPair))
							pairs.add(newPair);
					}
			}
		}
		
		/*
		 * Then, it is good programming practice to return the same type
		 * of data in a container as was used to pass the parameters.
		 */
		Integer[][] results = new Integer[pairs.size()][2]; 
		int i = 0;
		for ( Pair<Integer,Integer> pair : pairs ) {
			Integer[] dual = { pair.getL(), pair.getR() };
			results[i++] = dual;
		}
		
		return results;
		
	}

	public static void main(String[] args) {

		Integer[] data1 = new Integer[] { 3,7,2,5,6,4 };
		Integer result1 = 10;
		Integer[][] test1 = new Integer[][] { { 3, 7 } , { 6, 4 } };
		
		
		/*
		 * Due to a glitch in the JVM we have to compare the arrays
		 * using a manual approach;
		 */
		
//		assert Arrays.equals(sortPairs(data1,result1), test1);
//		assert !Arrays.equals(sortPairs(data1,result1), test1);

		Integer[][] check = sortPairs(data1,result1);
		for ( int i=0; i<test1.length; i++ )
			if ( check[i][0] != test1[i][0] 
				|| check[i][1] != test1[i][1] )
				System.out.println("Different");	
	
		/*
		 * As per specification we need to print out the result.
		 */
		
		for ( int i=0; i<check.length; i++ ) {
			System.out.println(
					new Pair<Integer,Integer>(check[i][0],check[i][1]));
		}
		
	}

}

- perry.anderson November 30, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

static void pair_sum()
{
int[] array = {3,7,2,5,6,4};
int N = 8;
Arrays.sort(array);
int i = 0, j =1;
while (i < j && j < array.length)
{
if ( array[i] + array[j] == N)
{
System.out.println("Pair("+ array[i] + ", " + array[j]+")");
i++;
j++;
}
if ( array[i] + array[j] < N)
{
j++;
}
else
{
j = i+ 1;
}
}
}

- rsl October 29, 2015 | 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