Amazon Interview Question
Software Engineer / DevelopersCopy the given array in new array.
Sort the new array.
search for the index of each element of given array,say i, into new sorted array,say j.
if j < i then num_of_inv += 1
@Googler, can u plz check this logic for
2,4,3,1
here the number of inversions are 4 ((2,1), (4,3), (4,1), (3,1)).
But as per ur logic, we get 1 as the number of inversions.
//basically merge sort, but count the inverse when merge the array
int CountInversion(vector<int>& a, vector<int>& b, int left, int right)
{
if( left >= right) return 0;
int count = 0;
int mid = left + (right - left)/2;
count += CountInversion(a,b,left,mid);
count += CountInversion(a,b,mid+1,right);
for(int i=left; i<=right; i++)
b[i] = a[i];
int i1 = left, i2 = mid+1;
for(int i=left; i<=right; i++)
{
if(i1>=mid) {a[i] = b[i2]; i2++;}
else if(i2>=right) {a[i] = b[i1]; i1++; count += (right - mid);}
else if(b[i1] > b[i2]) {a[i] = b[i2]; i2++;}
else if(b[i1] <= b[i2]) {count += (i2 - mid); a[i] = b[i1]; i1++;}
}
return count;
}
Please check my code
#include<stdio.h>
int mergeandcountinversion(int a[],int begin,int middle,int end,int z)
{
int length=end-begin+1;
int tmp[length];
int i1=begin,i2=middle+1,it=0,i=0;
for(i=0;i<length;i++)
{
if(i1>middle)
{
for(;i2<=end;i2++)
{
tmp[it]=a[i2];
it++;
}
break;
}
if(i2>end)
{
for(;i1<=middle;i1++)
{
tmp[it]=a[i1];
it++;
}
break;
}
if(a[i1]<=a[i2])
{
tmp[it]=a[i1];
it++;
i1++;
}
else if(a[i2]<a[i1])
{
tmp[it]=a[i2];
it++;
i2++;
z+=middle-i1+1;
}
}
i1=begin;
for(i=0;i<length;i++)
{
a[i1++]=tmp[i];
}
return z;
}
int m_sort(int a[],int begin,int end)
{
int middle=(begin+end)/2,x=0,y=0;
if(begin==end)
return 0;
x=m_sort(a,begin,middle);
y=m_sort(a,middle+1,end);
return x+y+mergeandcountinversion(a,begin,middle,end,0);
}
int mergesort(int a[],int n)
{
return m_sort(a,0,n-1);
}
int main()
{
int a[]={4,5,3,1,2};
int n=5,i=0;
printf("%d\n",mergesort(a,n));
}
Feedbacks are welcome
This might help!
- Anonymous June 01, 2011geeksforgeeks.org/?p=3968