Microsoft Interview Question Software Engineer / Developers
since array is sorted(ascending order)
In begining startp point to first array index and endp points to last array index, this is done bcos we want to travel each element only once and the sum of two elements shud be equal to X.
note here SUM = arr[startp]+arr[endp]
if SUM < X that means we want to increase sum , for that we need to increment the startp(array being in ascending order),similarly if SUM > X we want to lower the SUM for that endp needs to be decreased.....
for the case when SUM = X, we have found the array indexes but since numbers can repeat so we need the inner do while loops to cover all the posibitilites of pairing the numbers whose sum = X....
also note that if we have 'a' numbers having value P and 'b' numbers having value Q such that P + Q = X and a+b = n, and we want to print array index of all the pair formed then complexity can't be less than O(a*b) because of the number of combinations formed. In worst case O(n^2) when a = b = n/2. thats why we have avoided printing all the pairs(although we print the lists seperately and not the pairs).
I hope i have clarified, if thrs any doubt u r welcome...
1. nlgn solution for unsorted array
Take the array and apply the concept of mergesort. The only change is that while merging you keep track of the pairs that can sum up to the given numbers.
2. O(n) solution for the sorted array
Take 2 pointers. One at the start of the array and the other at the end of the array. Add the no. pointed by the pointers and compare to the sum
case 1: Sum matches - Print that pair and increment the first pointer and decrement the second pointer.
case 2: Sum is greater than the sum of the pair- Increment the first pointer only
Case 3: Sum is less than the sum of the pair- Decrement the second pointer only
Do the above till first pointer is less than the second pointer and you will have all the pairs.
a) if i m not wrong, the solution to part a) can't be found in O(log n) because the array is not sorted and so u need to visit each number atleast once so theoritically it can't be less than O(n). if its O(nlogn), for this the solution is first sort the array, it takes O(nlogn) time. then follow the solution of part b.
- Lokendra Kumar Singh August 01, 2007b)assuming that array is sorted in ascending order, take two pointer startp and endp pointing to begining and end of array.
now test
while(startp < endp)
{
if(arr[startp]+arr[endp] == X)
{
list1 = empty
list2 = empty
do
{
add the array index startp in list1
temp = arr[startp]
}while(temp==arr[++startp]&& startp<endp);
do
{
add the array index startp in list2
temp = arr[endp]
}while(temp==arr[--endp]&& startp<endp);
print "any element frm list1 can pair with any element frm list2"
print list1
print list2
}
else if(arr[startp]+arr[endp] < X)
{
startp++
}
else
endp--;
}