|
Given a array of random integers, sort the odd elements in descending order.......
Software QA/Tests Interview Questions from Microsoft
(Continued from previous question...)
Given a array of random integers, sort the odd elements in descending order.......
Question:
Given a array of random integers, sort the odd elements in descending order and even numbers in ascending order.
e.g. for i/p (1,4,5,2,3,6,7)
O/p = (7,5,3,1,2,4,6)
Optimize for time complexity.
maybe an answer:
just overwrite the > operator and do quicksort.
void swap(int& x, int& y)
{
int t;
t = x;
x = y;
y = t;
}
int Partition(int a[], int l, int r)
{
int v = a[r];
int i = l-1;
int j = r;
while(j>i)
{
while(true)
{
++i;
if(a[i]%2==1 && v%2==1)
{
if(a[i] >= v)
break;
}
else if(a[i]%2==1 && v%2==0)
{
continue;
}
else if(a[i]%2==0 && v%2==1)
{
break;
}
else
{
if(a[i]>=v)
break;
}
}
while(true)
{
--j;
if(a[j]%2==1 && v%2==1)
{
if(a[j]>=v)
break;
}
else if(a[j]%2==1 && v%2==0)
{
break;
}
else if(a[j]%2==0 && v%2==1)
{
continue;
}
else
{
if(a[j]<=v)
break;
}
}
if(i>j)
break;
swap(a[i], a[j]);
}
swap(a[i], a[r]);
return i;
}
void mySort(int a[], int l, int r)
{
if(l>=r)
return;
int m = Partition(a, l, r);
mySort(a, l, m-1)
;
mySort(a, m+1, r);
}
(Continued on next question...)
Other Interview Questions
| 