Interview Question Software Engineer / Developers


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

- Siva on July 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It require O(n) memory space

- Pramod Chandoria on July 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- R K on July 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Siva on July 07, 2012 | Flag
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 }));
	}
}

- kartikaditya on July 05, 2012 | Flag Reply
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]

- rajan Kakkar on July 05, 2012 | Flag Reply
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).

- Deven Bhooshan on July 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
1
of 1 vote

No where close to linear time complexity..

- teli.vaibhav on July 05, 2012 | Flag


Add a Comment
Name:

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

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More