Ivycomptech Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

int main() {
    int a[20],n,k;
	scanf("%d",&n);
	for(int i =0 ;i<n;i++) {
		scanf("%d",&a[i]);
	}
	int c = 0;
	for ( int i = 0; i< n;i++) {
		for (int j = i+1;j<n;j++) {
			if(a[i]>a[j]) {
				printf("%d %d\n",a[i],a[j]);
				c++;
			}
		}

}

- einstein September 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Modifed version of mergesort algorithm could give us the no of inversions in the array. I tested this on
(1), (1,1,1,1), (1,2,3,4,5,6), (3,5,7,2,8)

package arrays;

public class FindIInversionCount {

	public static int[] temp_data;
	public static int inversion_count = 0;

	public static void main(String[] args) {
		int[] a = {3,5,7,2,8};
		temp_data = new int[a.length];
		inversion_count = merge_and_count(a, 0, a.length - 1);

//		for (int i : temp_data) {
//			System.out.println(i);
//
//		}
		System.out.println("inversion count: " + inversion_count);
	}

	private static int merge_and_count(int[] a, int low, int high) {
		if (high - low > 1) {
			// more than two element

			int mid = (int) Math.floor((high + low) / 2);

			merge_and_count(a, low, mid);
			merge_and_count(a, mid + 1, high);

			// merge the data and count the inversions
			int i = low;
			int j = mid + 1;
			int count = low;
			while (i <= mid && j <= high) {
				if (a[i] <= a[j]) {
					temp_data[count++] = a[i];
					i++;
				} else if (a[i] > a[j]) {
					temp_data[count++] = a[j];
					j++;
					for (int k = i; k <= mid; k++) {
						inversion_count++;
					}
				}
			}

			if (j <= high) {
				while (j <= high) {
					temp_data[count++] = a[j];
					j++;
				}
			}
			if (i <= mid) {
				while (i <= mid) {
					temp_data[count++] = a[i];
					i++;
					inversion_count++;
				}
			}
		} else {
			// we have to deal with less than two elements
			if (high == low + 1) {
				if (a[low] > a[high]) {
					int tmp = a[low];
					a[low] = a[high];
					a[high] = tmp;
					inversion_count++;
				}
			} else if (high == low) {
				System.out.println("One element no sorting needed");
				temp_data[low] = a[low];
			}
		}
		return inversion_count;
	}
}

- sriniatiisc October 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think I have solution.
I am not sure about running time as I haven't calculated it yet.

Let's say we have an array of 11 elements (10,14,12,18,7,9,13,2,6,15,1)
Possible inversions :
(10,8) (10,7) (10,9) (10,2) (10,6) (10,1)
(14,12) (14,8) (14,7) (14,9) (14,13) (14,2) (14,6) (14,1)
(12,8) (12,7) (12,9) (12,2) (12,6) (12,1)
(8,7) (8,2) (8,6) (8,1)
(7,2) (7,6) (7,1)
(9,2) (9,6) (9,1)
(13,2) (13,6) (13,1)
(2,1)
(6,1)
(15,1)

Total : 36 Inversions

Now solution :

1. Let's define element with their positions.

10-1
14-2
12-3
8-4
7-5
9-6-
13-7
2-8
6-9
15-10
1-11

2. Find Minimum element , in the above case we have 1 at position 11 , so all above 1 will be greater than 1 -- 10 Inversion.

3. Find next minimum element and exclude 1 , in above case it's 2 at position 8 -- 7 Inversion.

4. Repeat step 3, next minimum element 6 at position 9 , Now exclude 2 (as it already been processed - Inversion (9 (position of 6 ) -1 (2 is already processed) - 1 (as element 6 itself )
--7 Inversion.

5. Repeat step 3 & 4 and in each iteration we will get number of inversions.

6. At last add all inversions--10+7+7+4+3+3+0+1+1+0+0 = 36 Inversion total.

Let me know if it doesn't apply to all case.
I will try to optimize it and write the running time.

Thanks,

Pankaj T.

- Pankaj October 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry, the above output was not mentioned correctly.
The Output should be 3. ( It has 3 inversions: 3>2,, 5>2, 7>2)

- veeru September 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I forgot to mention the length of the array is unknown and your code should be optimized in less than O(n^2).

- veeru September 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

number of inversions = sum of distance of (current position of each element, its position in sorted array) / 2.
Prove by induction. n = 1 case is trial.
n = k to n = k+1: suppose the largest element is inserted to position i.
elements behind it increase the distance by 1, there are k+1-i of them;
itself has the distance of k+1-i.
This insertion created k+1-i new inversions.
So the conclusion is valid for n=k+1.

Back to the question, now it's easy to learn it has a solution of O(n*log(n)) with sorting and then counting distances.

Any idea on an O(n) solution?

- cx9 September 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi cx9,

I have mentioned the condition i < j of the given array. If you sort the array, the original positions (i, j) will differ.

In the eg(given in question), there are only 3 inversions.

If you sort the array then the number of inversions will become n(n+1) / 2. = 5 (5+1) / 2. = 15 which is wrong answer.

- Veeru September 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Maybe you don't understand what I mean.
In your example: {3, 5, 7, 2, 8}
The positions of elements are:
p(3) = 1, p(5) = 2, p(7) = 3, p(2) = 4, p(8) = 5;
in the sorted array {2, 3, 5, 7, 8}
p'(2) = 1, p'(3) = 2, p'(5) = 3, p'(7) = 4, p'(8) = 5;
And the distance I talked about is such as:
|p(3)-p'(3)| = |1-2| = 1.
So the sum is |1-2| + |2-3| + |3-4| + |4-1| + |5-5| = 6;
Output is 6/2 = 3.

My algo needs O(n) extra space.

- cx9 September 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ok cx9, 
I understood your logic. But when I tried for below array, it's not getting expected answer.
arr = {5,1,6,4,3,9}
Expected Output: 6  [ (5,1),  5,4), 5,3), (6,4), (6,3), (4,3)]

sortedarr = {1,3,4,5,6,9}

Sum of their distances = (|4-1| + |2-1| + |3-5| + |4-3| + |5-2| + |6-6|) / 2  =  10 / 2  =  5 which is incorrect number of inversions.

Please correct me  if I missed any steps.

- Veeru September 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, Veeru you are right. There is logical incorrectness in my algo. This statement in my first reply "suppose the largest element is inserted to position i. elements behind it increase the distance by 1elements behind it increase the distance by 1" doesn't hold. It's easy to give a counter example. So my algo is a wrong one.

- cx9 September 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

divide and conquer, similar to merge sort. O(nlgn)

- patpat September 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For each element in an array
--->Insert into a BST and count the number of successors in the BST.
the no if successors is the no of inversions for that element.
Since we need the count of the successors we can increase the efficiency by maintaining the number of nodes in right subtree at each node.
This should be a nlogn .

- sk January 11, 2013 | Flag Reply


Add a Comment
Name:

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

Books

is a comprehensive book on 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