Software development engineer in test - a randomly filled array of 2N numbers ....
Software Design Engineers in Test SDET FAQ
(Continued from previous question...)
21. Software development engineer in test - a randomly filled array of 2N numbers ....
A randomly filled array of 2N numbers ( N odd and N even) is given . arrange the array in such a way that odd numbers are at even indexes and even numbers are at odd indexes.
there are number of possible solutions for it but for MS you need to give the best possible solution.
best possible is : O(n) time and O(1) space complexityalgorithm:
1. keep two pointers one at 0th index (even) and other is at 1st index(odd) of the array..
2. move both pointer towards other end by 2 position at a time and
3.keep checking if first pointer encounters a index where even number is at even place then stop first pointer there .and if 2nd encounters odd number at odd index then stop 2nd pointer . otherwise keep moving both of them until one of them reaches to the other end .
4. if both have stopped at 3rd step then swap numbers at the index pointed by two pointer and go to step 2.
Since we require only one pass over the array hence it is O(n) algorithm without using any extra space.
try out this algorithm with an example.
(Continued on next question...)
Other Interview Questions