## 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).

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

The hash map solution will not work for duplicate elements.

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

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)

Comment hidden because of low score. Click to expand.
1
of 1 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.

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

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

}

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

}

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

Any better solution than n^2 ?

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

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

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

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

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

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

max runtime is O(n)

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)

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

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

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))
*/
}
}``````

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

}

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

}

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

}``````

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

}``````

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

}

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

}``````

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

}``````

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

}
}``````

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

}
}``````

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

}
}

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

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

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.

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.

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

}

}``````

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

}

}``````

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

}

}``````

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

}

}``````

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

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