## Microsoft Interview Question Software Engineer / Developers

• 0

given an array of integer size N.
a) find all pairs whose some is some given value X.array is not sorted & values are distinct.in o(log n)

b) then interviewer added some constratints..
array is sorted. & values can repeat.in o(n) & space compl o(1)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.
b)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--;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Lokendra,
tnx

Comment hidden because of low score. Click to expand.
0

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...

Comment hidden because of low score. Click to expand.
0
of 0 vote

if it's sorted, it's kind like partition from both side.

Comment hidden because of low score. Click to expand.
0
of 0 vote

i hope the above program does not cover all the pairs. as when if the some is less than x then we can increase both index start and end. may be increasing the end can lead you one more pair which u skipped.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use hash to do (a) in O(n)

Comment hidden because of low score. Click to expand.
0

If you use hash you are using additional memory and the question is asking for o(1) space complexity..

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

Your solution seems not correct for (b). It is O(n) for one pair. Can you find all pairs in O(n)???

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.