Interview Questions

There is an array (with +ve integer) we need to sort the array ONLY .....

Software QA/Tests Interview Questions from Microsoft


(Continued from previous question...)

There is an array (with +ve integer) we need to sort the array ONLY .....

Question:
There is an array (with +ve integer) we need to sort the array ONLY with the help of the following function.
Flip(Array a, int size, int flipPos)
so if the array is
a = 3,2,6,8,1,9
and i call
Flip(a, 6, 3)
then a = 6,2,3,8,1,9.



maybe an answer:


finding smallest element:
- min = A[0]
- for i = 1 to (n-1)
if ( min > A[i] )
min = A[i]; Flip (A, n, i);
So, O(n) time to get smallest.


Once smallest is found, print it to output stream,and call Flip(A, n, n-1) which puts the last element in the array to first place, finally n-- as we removed smallest. Repeatedly we can do it to get O(n^2) sorting.


maybe an answer2:


void sort ( int A[] , int n )
{
if( n < 0 )return;

int idx=0,max=INT_MIN,max_idx=-1;

for( idx=0;idx<n;idx++ )
{
if( A[idx] < max )
{
max=A[idx];
max_idx=idx;

}

}

Flip( A , n ,max_idx);
Flip( A , n , n-1 ); /* gets the largest element at end of the array */
sort( A , n-1 );
}

(Continued on next question...)

Other Interview Questions