Microsoft Interview Question for Software Engineer / Developers






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

How about this ?

i) Go on splitting the main list into different list each either increasing or decreasing.
Say L is split into L1, L2, L3,... Ln. And L1, L3,... Ln are in increasing order and L2, L4, L6..Ln-1 are in decreasing order.
ii) Now reverse L2, L4, L6.. lists.
iii) merge all of them.

each step takes O(n) time. So this is done in O(n) time.

Splitting can be done by storing into array of lists.

- Anonymous December 22, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can Merge sort not work it ?

- nks December 18, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) In O(N) traverse and modify the given list such that we have two lists (two heads), one that is prepared of all sublists having ascending order and another having sublists in descending order. Theses lists might not be in sorted (any order) order.

2) Now sorted these two lists in NlogN time.

3) Now we have two sorted lists. Merge them in O(N) time.

Complexity: N+2NlogN+N = O(NlogN)

- AbhiM December 21, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

how are u making use of their partial sorted nature ? a simple sort on the given list also takes O(nlgn) rt ?

- anon December 22, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

how are u making use of their partial sorted nature ? a simple sort on the given list also takes O(nlgn) rt ?

- anon December 22, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For the above algorithm,

How did you think that you can merge in O(n) time !!!! ??

- Anonymous January 06, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why not? As the two list are already in the same order, all you need to do is sweep them once

- Anonymous March 29, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

guys .. keep in mind its not a list (array) its a link list .. and to make it interesting how can we sort it using constant space ..

- intuidev January 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1.separate ascending or descending order linklist and while doing so reverse the descending link list
2.start from the head of each link list .. do the comparison and merge them into one ..

- intuidev January 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

why take too much of trouble...

just implement your own swap function.
then use any O(nlgn) algorithm.
ofcourse this swap function doens't have only two arguments. i think 4 arguments are needed.

- a.p February 08, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Keep a result list initialized to null.
Now find whether the first list is in ascending order, if so simly copy them in esult list, if not first reverse and then copy in result list
Now start finding the second list, reverse it and merge in result list until end comes.

- netappreject May 09, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

one simple way
1..first traverse the main list
2..while traversing compare the consecutive 2 nos..
3..put the smaller ones in newlist1
4..put the larger ones in newlist2
5..after reachin te end of te list,reverse te newlist2
6..merge newlist2 wit newlist1
......................................tatzall

- Anonymous June 20, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

one simple way
1..first traverse the main list
2..while traversing compare the consecutive 2 nos..
3..put the smaller ones in newlist1
4..put the larger ones in newlist2
5..after reachin te end of te list,reverse te newlist2
6..merge newlist2 wit newlist1
......................................tatzall

- vigneshk.cit June 20, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

it is as simple as continuously applying a procedure of merging two adjacent sorted lists.
For example,
1,2,3,12,11,2,10,6

Round 1. Merge 1,2,3,12 and 11,2, merge 10 and 6, the result is 1,2,2,3,11,12, 6,10
Round 2. Merge 1,2,2,3,11,12 and 6,10' the result is 1,2,2,3,6,10,11,12

It's O(log m) where m is the number of sorted sublists, note m <=n ( number of elements in the lists)
Using two pointers,pointing two positions in the two sorted sublist, the merge can be done in place, so space is O(1)

- jiex.cs December 03, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry , I mean O(nlogm)

- jiex.cs December 03, 2011 | Flag


Add a Comment
Name:

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

Books

is a comprehensive book on 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