Microsoft Interview Question Software Engineer / Developers




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--;
}

- Lokendra Kumar Singh on August 01, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Lokendra,
Can you please explain your solution.
tnx

- John on August 06, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Lokendra Kumar Singh on August 07, 2007 | Flag
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.

- likexx on October 08, 2007 | Flag Reply
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.

- cometosandy on October 14, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Vamsi on November 30, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gauravk.18 on April 09, 2008 | Flag
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.

- gauravk.18 on April 09, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on September 07, 2008 | Flag


Add a Comment
Name:

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

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More