Bloomberg LP Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
This can return wrong results... say in array we have single 2.
You add it to hash table on first loop.
And found it again in hash when looking for 4-2.
So you will print 2+2 but there is only single 2 in array.
You should check 4 - arr[i] in hashtable before each add to hastable.
it will be faster and more correct.
Also your solution will print correct pairs twise.
For C++ fans:
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool isOne (int i) { return i==1; }
int main(int argc, char**argv)
{
vector<int> a = {1, 2, 9, 3, 4, 5, 6};
int k = 7;
sort(a.begin(), a.end());
int i = 0;
int j = a.size() - 1;
while (i < j) {
int d = k - a[j] - a[i];
if (d == 0) {
cout << a[i] << " - " << a[j] << endl;
i++;
j--;
}
else if (d < 0)
j--;
else
i++;
}
}
This solution takes O(nlogn)+O(n) time.
int main()
{
int n,i,j,t,k;
cin>>n;
int a[n];
for(i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
cin>>k;
i=0;j=n-1;
while(i<j)
{
t=a[i]+a[j];
if(t==k)
{cout<<a[i]<<" "<<a[j];return 0;}
else if(t<k) i++;
else j--;
}
}
We can also solve this in O(n) time by Hashing.
If space is not a problem it can it can be done in O(n) using hashtables scan through the array and store entries in a hashtable and check if 4-no is there in the hashtable if found return pair.
public List<Integer> pairs(int[] a) { List<Intger> pairsList=new List<Intege>(); Hashtable<Integer,Integer> entries=new Hashtable<Integer,Integer>(); for(int i=0;i<a.lenght();i++) { if(entries.containsKey(4-a[i]) { pairsList.add(a[i]); pairsList.add(4-a[i]); return pairsList; } else entries.add(a[i],a[i]); } return pairsList; }
If space is not a problem it can it can be done in O(n) using hashtables scan through the array and store entries in a hashtable and check if 4-no is there in the hashtable if found return pair.
public List<Integer> pairs(int[] a)
{
List<Intger> pairsList=new List<Intege>();
Hashtable<Integer,Integer> entries=new Hashtable<Integer,Integer>();
for(int i=0;i<a.lenght();i++)
{
if(entries.containsKey(4-a[i])
{
pairsList.add(a[i]);
pairsList.add(4-a[i]);
return pairsList;
}
else entries.add(a[i],a[i]);
}
return pairsList;
}
Sorry the typos got frustrating
If space is not a problem it can it can be done in O(n) using hashtables scan through the array and store entries in a hashtable and check if 4-no is there in the hashtable if found return pair.
Time Complexity O(n);
public List<Integer> pairs(int[] a,int n)
{
List<Intger> pairsList=new List<Intege>();
Hashtable<Integer,Integer> entries=new Hashtable<Integer,Integer>();
for(int i=0;i<a.lenght();i++)
{
if(entries.containsKey(4-a[i])
{
pairsList.add(a[i]);
pairsList.add(n-a[i]);
return pairsList;
}
else entries.add(a[i],a[i]);
}
return pairsList;
}
public class pairofNum {
public static void main(String args[]){
int i =0,j=0,sum=0,temp =0;
int[] arr = {9,6,-3,1,7};
int[] pair = new int[2];
boolean flag = false;
for(i=0;i<arr.length-1;i++){
temp = 0;
for(j=i+1;j<arr.length;j++){
temp = arr[i]+arr[j];
if(temp == 4){
pair[0] = arr[i];
pair[1] = arr[j];
flag = true;
}
}
if(flag)
break;
}
System.out.println(pair[0]+" "+pair[1]);
}
}
Here is a Recursive version:
...
int a[] = { 9, 6, -2, 1, -3, 7, -5 };
int n = 7;
FindSumOfPairs( &a[0], n, 4 );
...
void FindSumOfPairs( int a[], int n, int sum )
{
if( --n == 0 )
return;
FindSumOfPairs( &a[1], n, sum );
for( int i = 0; i < n; i++ )
{
if( a[0] + a[i+1] == sum )
cout << a[0] << "+" << a[i+1] << "=" << sum << endl;
}
}
...
Output:
-3+7=4
6+-2=4
9+-5=4
import java.util.HashSet;
public class Pair {
public void sum(int[] array, int sum) {
HashSet<Integer> hs = new HashSet<Integer>();
for(int i= 0; i<array.length; i++) {
hs.add(array[i]);
}
for(int i=0; i<array.length; i++) {
int temp = sum - array[i];
if(hs.contains(temp))
System.out.println("("+temp+","+array[i]+")");
}
}
public static void main(String [] args) {
int [] array = {9,6,-3,1,7};
int sum = 4;
Pair obj = new Pair();
obj.sum(array, sum);
}
}
//O(N) public void printSums(int X, int[] arr) { HashTable table = new HashTable(); for (int i =0; i< arr.length; i++) { table.add(arr[i],true); } for(int i =0; i<arr.length; i++) { int temp = 4- arr[i]; if(table.ContainKey(temp)) { print(arr[i].toString() +" "+temp); } }}
- Edmond February 11, 2014