Microsoft Interview Question
Software Engineer in TestsUsing a hash_map. complexity depends on hash function but in general recent hash functions give a amortized O(1) insertion and amortized O(1) retrieval.
Assuming the values in the hash_map are all positive.
-> For every value 'val' in the array,
if sum-val >=0
if sum-val exists in the hash_map, add to the matching pairs vector.
else insert 'val' in the hash_map
-> print all elements of the matching pairs vector.
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using std::cout;using std::vector;using std::endl;
typedef int DataType;
typedef std::unordered_map<DataType, int> MyHashMap;
void printVecPair (vector<DataType> v) {
cout << v[0]<<" : "<<v[1]<<endl;
}
int main(){
MyHashMap valsMap; //declare unordered map
vector<DataType> array {12,20,13,4,1,2,8,6,7,7,3,5,9};
DataType sum=14,val=0;
vector<vector<DataType> > matches; //vector to store pairs of values whose sum = sum
DataType len = array.size();
vector<DataType>::const_iterator arrItr;
MyHashMap::iterator mapItr = valsMap.begin();
//for every val in the array if (sum-val) >0 see if there exists a value (sum-val)
for ( arrItr=array.begin(); arrItr!=array.end(); arrItr++ ){
val = *arrItr;
if((sum-val)<0)
continue;
mapItr = valsMap.find((sum-val));
if(mapItr==valsMap.end()){ //if sum-val not found then insert
valsMap.insert(MyHashMap::value_type(val, 1));
}else //else add it to the matches vector
matches.push_back(vector<DataType>{val,(sum-val)});
}
cout<<"value pairs whose sum = "<<sum<<endl;
for_each (matches.begin(),matches.end(),printVecPair);
}
Let me know if there are any bugs. Thanks
1. A[n] array and SUM .Take temp array B[n]
2. for each i=0 to n-1
if A[i] > SUM/2
B[i] = SUM - A[i]
else
B[i] = A[i]
3. Now B[n] array contains elements <= SUM/2 .
4. if B[n] contains duplicate element, then B[i] and SUM-B[i] elements gives SUM of two elements.
else
A[n] does not contains two such numbers to give SUM.
5. Time complexity o(n) & Space complexity O(n)
6. The above logic is Problem reducing i.e finding Two numbers sum problem to duplicate problem
what is the array is {3,3} and X=8?
B[] will still have duplicates, but 3 and (8-3) is not the answer, am i right?
may be we need to maintain B as 2D, with B[][i] as 0 or 1, if we have array element > X/2, then set B[][i] as 1 and while finding pairs see if B[i][] is duplicate and B[][i] and 0 and 1.
please correct me if i am wrong.
logic is same as above guys and this code will handle even negative nos.
O(n) time and space.
#include<stdio.h>
void pair(int a[], int l, int sum)
{
int i, j, min;
if(l<2)
{
printf("no pair");
return ;
}
min = a[0];
for( i = 1 ;i<l;i++)
{
if(min > a[i] )
min = a[i];
}
if(min<0)
{
min*= -1;
sum += min;
sum += min;
for( i = 0 ;i<l;i++)
a[i] += min;
}
else
min = 0;
int hash[sum];
for( i = 0 ;i<sum;i++)
{
hash[i] = sum+1;
}
for( i = 0 ;i<l;i++)
{
if(sum >= a[i] )
{
if (hash[a[i]] == sum+1)
{
hash[sum-a[i]] = 0;
}
else if(hash[a[i]] == 0)
{
printf("\npair found{%d, %d}.\n", a[i]- min, sum-a[i]-min);
}
}
}
}
int main()
{
int a[] = {5,2,1,4,6,12,2,3};
pair(a, 8, 3);
return 0;
}
- Jit December 04, 2010