## Interview Question Software Engineer / Developers

• 0

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

Comment hidden because of low score. Click to expand.
3
of 3 vote

I am not sure about linear but you can do it O(nlogn)
1.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

Comment hidden because of low score. Click to expand.
0

It require O(n) memory space

Comment hidden because of low score. Click to expand.
0

couldn't follow the counting part of it... can u plz elaborate it

Comment hidden because of low score. Click to expand.
0

in the second step. you are trying to do a binary search for the number. While doing binary search , one has to count the number of times right subtree is called from root to the number. this gives you number of elements in the right sub array that are greater than the current number

Comment hidden because of low score. Click to expand.
1
of 1 vote

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 }));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

question is not about the cosnuctive pairs it can be possible when i =1 and j =5 and a[1] > a[5]

Comment hidden because of low score. Click to expand.
0
of 0 vote

You can do it in NlogN using Divide and conquer method(Merge Sort).

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

No where close to linear time complexity..

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.