Microsoft Interview Question Software Engineer in Tests
@Anonymous... sorting is O(n log n)...
For O(n):
use a hashset to keep x-a[i]
for every i, check if a[i] is present in the set
O(n) space and time
Using map blindly over here will not help because you need to output "Unique" pairs that sum upto 'S'. If you simply use hash map then you will output duplicate pairs also:
consider this case:
a[] = {9,10,9,10,9,10}
your output will be (9,10) , (9,10) , (9,10)
(Also in your approach you don't even bothered to remove an element form hash table once corresponding number is found. This would have a side effect of outputting the same pair twice).
So to remedy the above situation you can just keep the freq. of each entry in Hash Table as 1 and reducing it to 0 as you find a particular pair.
So for above array a[] = {9,10,9,10,9,10}
Let the Sum be 19
We will have the following Hash Table(say H) that stores S-a[i] for each i:
H[9] = 1
H[10] = 1
Scan through the array:
First entry found is 9. H[19-9] = H[10] = 1. So output (9,10).Set H[9] = H[10] = 0
Now after that whenever we encounter 9 or 10 we cannot output them since the corresponding entry in the hash Table is 0.
Thanks.
for(int i=0,j=1; i<n; i++)
{
while(a[i]+a[j] < sum)
j++;
if(a[i]+a[j] == sum)
{
cout << a[i] << " " << a[j] << endl;
j=i+1;
}
}
o(n) sol'n:
public static void getSums(int[] a, int sVal)
{
int i= 0;
int j = a.Length-1;
while (i < j)
{
if (a[i] + a[j] == sVal)
{
Console.WriteLine(a[i]);
Console.WriteLine(a[j]);
Console.WriteLine("\n");
i++;
j = (a.Length - 1);
}
else if ((j - 1) == i)
{
i++; j = (a.Length - 1);
}
else
{
j--;
}
}
}
Pseudo code
1) Partition the set by n/2. All Elements N/2 and below on the left. All Elements > N/2 on the right. (Possible in O(n))
2) Put all elements in left in a hash map ensuring no duplicates. (keep a int countN/2 = 0, on one fine update to 1 and on a pair update to 2. Output pair(n/2,n/2) dis regard any other n/2
3) For all elements on the right basically > n/2 check for n - element in the hashmap. If exists ouput pair and remove element from hashmap.
findpair(int a[],int l,int h,vector pair<int,int>)
- Anonymous January 17, 2011{
if(l<h)
{
if(a[l]+a[h] == x) pair.add(l,h);
else if (a[l]+a[h]> x)
{
findpair(a,l,h-1);
findpair(a,l+1,h);
}
}
}
main(){
let a[n] be the array of n interger.
sort(a)
vector pair<int,int>;
findpair(a,0,n-1,pair);
print pair;
}