Microsoft Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Instead of using HashMap:
if 1) numbers are non-negetive
2) a known upper limit
We can use an int[] and solve the problem.
Initially int[] is zeros. When we meet a number(num) use that as index and flag it to '1' and check if there is another arr[(key-num)] and check if that is also flagged as 1. If so, then we have a pair.
It is of order O(n).
ex: input = [1,2,3,4,7,8]. Key: 7.
Array: a[] = {0,0,0....}
for i in length(input) {
a[input[i]] = 1
if(a[key-input[i]] == 1){
print "Pair found"
}
}
Somewhere we have to pay the price: either memory or speed (computation). If using HashMap, insert and find operations do cost computation time.
Using array will cost memory but less computation.
I have a doubt here.... what if the number is a negative number?
eg:) Given array is [0, -1, ....]
how can we take the number in the array as an index? We can't have a negative index right?
The algorithm is good but how can we implement it? :(
input a[] = {1,11,10,9,8,3,4,5,7,6,2,0} Key =10;
int first = 0,last = 11;
Sort the array
while(first<last)
{
if(a[first]+a[last]==x)
{
printf("pair found %d %d\n",a[first],a[last]);
first++;
last--;
}
else if(a[first]+a[last] >=x)
{
last--;
}
else
{
first++;
}
}
While this solution works for your input data, it would ONLY work if there are no missing numbers as shown in the initial problem.
I think this solution will also work for missing numbers. This solution is sorting the numbers and in case it does not find array elements with sum = Key value, it wont print anything and continue the loop until first > last
-- else if(a[first]+a[last] >=x)
I don't think we need ">=", we just need ">", the equality is already matched in IF statement. Hence it should be
else if(a[first]+a[last] >x)
public static void GetAddition(int[] array, int x)
{
int elem = 0;
int[][] arrRes = new int[array.Length][];
int resIndex = 0;
for (int i = 0; i < array.Length; i++)
{
elem = array[i];
int tempres = 0;
for (int j = 0; j < array.Length; j++)
{
if (i != j)
{
tempres = elem + array[j];
if (tempres == x)
{
arrRes[resIndex] = new int[] { elem, array[j] };
resIndex++;
}
}
}
}
}
You can do this with hashing.Example below:
- aka October 16, 2012Start with an empty hash.
5 -0 = 5 does this exist in hash?No so put in array[5]
5 -1 = 4 does this exist in hash?No so put in array[5, 1]
5 -2 = 3 does this exist in hash?No so put in array[5, 1, 2]
5 -6 = -1 does this exist in hash?No so put in array[5 ,1, 2, 6]
5 -3 = 2 does this exist in hash?Yes so put in array[5 , 1, 2, 6, 3] note here the 3+2
5 -4 = 1 does this exist in hash?Yes so put in array[5, 1, 2, 6, 3,4] note here 4+1