Bloomberg LP Interview Question Software Engineer Interns
Country: England
Interview Type: Phone Interview
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)
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.
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)
//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;
}
}
}
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))
*/
}
}
#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);
}
#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);
}
//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]);
}
}
}
//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]);
}
}
}
//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]);
}
}
}
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))
#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;
}
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.
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.
//
// 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]));
}
}
}
//
// 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]));
}
}
}
//
// 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]));
}
}
}
//
// 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]));
}
}
}
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;
}
}
}
This solution was written on stackoverflow, I just remembered having a similar question in an assignment once.
- Ayan October 29, 2015There 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).