Given an array of +ve and ve integers, rearrange it so that u have +ves on .......
Software QA/Tests Interview Questions from Microsoft
(Continued from previous question...)
Given an array of +ve and ve integers, rearrange it so that u have +ves on .......
Q:
Microsoft Interview Question for Software Engineer in Tests about Algorithm
Given an array of +ve and ve integers, rearrange it so that u have +ves on one end and ves on other,BUT RETAIN ORDER OF APPEARANCE..
for eg,
1,7,5,9,12,15
A:
5,12,1,7,9,15
do it in O(n) without using any extra space.
1.Represent them as linked lists.
2.In the first pass, keep scanning for negative numbers.
3.When you hit the first negative number, compare it with the next number. If it's a positive number, swap both.
4.Continue step 3 until you have pushed the first negative number to the next occurring negative number in the list.
5.When you do this in the first pass, you will end up with all negative numbers accumulated in "pockets" but not necessarily together.
6.In the 2nd pass,scan for the first negative number. Redirect the previous number to point to the next positive number appearing after the negative number pocket. Similarly, the end of the positive numbers pockets should be made to point to the beginning of the same negative number pocket.
7.Repeat step 6 until end of list.
Essentially, you are creating chunks of positives and negatives and then rearranging the chunks to collect the positives on one side and negatives on the other.
(Continued on next question...)
Other Interview Questions
