## Interview Question Software Engineer / Developers

- 0of 0 votes
Given an array of size N, say A[N], count the number of pairs such that for i<j A[i]>A[j]. The interviewer was expecting for a linear complexity algo.

**Country:**India

**Interview Type:**Phone Interview

Not possible in O(N).

There is a O(NlogN) solution, read in Cormen about 'inversions' problem in the merge sort chapter.

```
import java.util.Arrays;
public class Inversions {
public static int getInversions(int a[]) {
if (a.length <= 1) {
return 0;
}
int aleft[] = Arrays.copyOfRange(a, 0, a.length >> 1);
int aright[] = Arrays.copyOfRange(a, a.length >> 1, a.length);
int inversions = 0;
inversions += getInversions(aleft);
inversions += getInversions(aright);
int i1 = 0, i2 = 0, i = 0;
while (i1 < aleft.length && i2 < aright.length) {
if (aleft[i1] <= aright[i2]) {
a[i++] = aleft[i1++];
} else {
a[i++] = aright[i2++];
inversions += (aleft.length - i1);
}
}
while (i1 < aleft.length) {
a[i++] = aleft[i1++];
}
while (i2 < aright.length) {
a[i++] = aright[i2++];
}
return inversions;
}
public static void main(String args[]) {
System.out.println(getInversions(new int[] { 2, 3, 8, 6, 1 }));
System.out.println(getInversions(new int[] { 5, 4, 3, 5, 6, 7, 6, 4 }));
}
}
```

I am not sure about linear but you can do it O(nlogn)

- Siva on July 05, 2012 Edit | Flag Reply1.traverse from back and construct a binary search tree.

2. for each number in the array .. find it in binary search tree keeping count of number of right calls(In binary search tree depending on the condition , we make one of the two calls (left or right) ;add this count to sum

3. after the iteration of the array. sum is the answer