Microsoft Interview Question
Software Engineer / Developers1) 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)
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
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
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)
How about this ?
- Anonymous December 22, 2009i) 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.