|
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
| 