Amazon Interview Question for SDE-2s


Team: Kindle
Country: India
Interview Type: In-Person




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

Modify mergesort to return inversions also (while sorting the input array).
Normally mergesort returns "void" so you can make it return "int" to also return number of inversions.

The main change is to modify the merge routine inside mergesort (which usually returns nothing, but now will return an integer which is the count of the number of inversions BETWEEN elements in left array and right array).

When merging the left half array L and right half array R, we usually have two counters i_L and i_R pointing into the two arrays (pointing at the current numbers we are comparing and considering for placement in the output array).

So when you do the comparison, if L[i_L] <= R[i_R], you will move L[i_L] into the merged array as normal and increment i_L++. So no change for this case (please note, include the = case as part of this case, not the next one).

What is different now is if L[i_L] > R[i_R], you will move R[i_R] .. blah blah as usual but you will ALSO increment a counter like: crossing_count += L.length - i_L

Why? Because the element R[i_R] you are moving into merged array is inverted with respect to all the remaining elements in the L array (and there are L.length - i_L ) of them.

So that's what you do. You modify merge subroutin to increment a counter whenever something from the the right array is picked to be placed in the merged array. And you increment it by the number of remaining elements in the L array. Convince yourself that this will count ALL the crossing inversions (inversions between elements in L and R).

How does it look overall when the new merge function is placed in mergesort?

// return value is the number of inversions in array A[start..end]
int mergesort( double A[ ], int start, int end )
{
	if( start >= end ) return 0;

	int mid = low + (high - low)/2;

	int inversions1 = mergesort(low, mid);  //how many in left array
	int inversions2 = mergesort(mid+1, high);  //how many in right
	int inversions_crossing = merge(A, low, high, med);  //how many crossing type?

	return inversions1 + inversions2 + inversions3;
}

- S O U N D W A V E March 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

return inversions1 + inversions2 + inversions_crossing;

*

- S O U N D W A V E March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your solution is correct. However, I think the question is vague.
Does the interviewer ask the #swaps required to sort the array
or is it just #swaps required, comparing each element with the other

- puneet.sohi March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

My one doubt is in the process of finding inversion you are also sorting the array.
Dont you think that sorting should not be done as its the side effect of using modified merge-sort. Whereas in question sorting is nowhere mentioned.

Please reply

- pavi.8081 March 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I told him to create a tree with array data from start, if it is going left in the tree, keep increasing total inversion count, if it is going right do nothing, at the end you will have total no of inversions.
He seems to be satisfied with the algo, but not with my code, did so many boundary errors.

- Grace March 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I wonder how that will work. Can you please explain a little more? For the same example {3,6,10,4,5,7,8}; you have to count twice when you want to insert 4.

- rssr March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

int c=0;

struct tnode *addnode(struct tnode *root,int num)
{
       if(root==NULL)
       {
          root=(struct tnode *) malloc(sizeof(struct tnode));
          root->left=NULL;
          root->right=NULL;
          root->val=num;
       }
       else
       {
           if(num<root->val)
           {
              c++;
              if(root->right==NULL)
                 root->left=addnode(root->left,num);
              else
                 root->right=addnode(root->right,num);
           }
           else
              root->right=addnode(root->right,num);
       }
       return root;
}

void getinversion(int a[],int n)
{
    int i=0,count=0;
    struct tnode *root=NULL;
    root=addnode(root,a[0]);
    for(i=1;i<n;i++)
    {
       root=addnode(root,a[i]);
    }
}

- Nitin March 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>

main()
{
        int a[7] = {3,6,10,4,5,7,8},i,j,count = 0;

        for(i = 0;i<6;i++)
        {
                for(j = i+1;j<7;j++)
                {
                        if(a[i] > a[j])
                        {
                                count++;
                                printf("{%d,%d}\n",a[i],a[j]);
                        }
                }
        }

        printf("no of inversions :%d\n",count);
}

- mahesh March 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In the above code why not change the line

a[i] > a[j]

to

a[i] != a[j]

the reason is one number will always be greater than the other, and you can pick them in any order, if you picked x, y you could have picked y,x equal. So it seems to me the only case where there is not an inversion is when the numbers are equal

- Dave March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

As far as I can understand, inversion happens, whenever a[i]>a[j], for all i<j. Above solution looks good to me. I don't know how a[i]!=a[j] will help.

- kx March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Dave: The question states that exchange should happen only if a[i] > a[j] and not otherwise

- puneet.sohi March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

obviously, no of nodes in right side of the current node in the tree will be added to the total number of inversions, while going to left, for that purpose all the nodes has to keep the count of number of nodes to its right, which can be tracked while creating the tree itself, idea was to tweak the tree creation code, so that these features could be fit. But I couldn't produce it in limited time.

- Grace March 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Maybe I have not understood the question correctly but I really do not see any need to use any data structure to compute number of inversions.

If we just need to get number of inversions, we need to calculate number of pairs (x,y) where x > y. Imagine the array in a sorted fashion. If x=largest number, then there can be (n-1) pairs using the other elements. Similarly, if x=2nd largest, there can be (n-2) pairs using remaining elements, and so on.

So, total number of inversions = 1+2+3+...+(n-1) = n*(n-1)/2.

- DevGuy March 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree with this answer. It does not look like we need some complex data structure for this.

- Jay March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Valid only in case if there are no duplicates.

- Victor March 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We need a data structure to hold all the unique values and store them in sorted order. Then your solution applies. Thanks for the math at the end.

- Vineeth March 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The question is vague but it appears to require that the second number selected has to be to the right of the first in the original array i.e. we can't select numbers at random.

@Vineeth - no need to sort. Assuming no duplicates then for n numbers there is a number where n-1 numbers are larger than it, a number where n-2 numbers are larger etc.

- James March 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about finding the Longest Decreasing subsequence in the array from 1 to n and then suppose the size is n then the number of inversions can be (n-1) + (n-2) + (n-3) + .......+ 1 = (n-1)*n / 2

- msoumya396 March 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think there is vagueness in the question.
What does the examiner intend to do? Sort the array? Or just a comparison between different elements

- puneet.sohi March 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If we want to sort the array,
as mentioned previously, use mergesort to count the #swaps, itwill give most time efficient solution with minimum #swaps.
Some people are using a version of insertions/selection sort, this will not be as efficient as mergesort in time or #swaps

As a small eg, sorting arr = {10, 6, 5}
Mergesort takes 2 swaps
Insertion sort takes 3 swaps

- puneet.sohi March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If there is no duplication, picking any 2 numbers should always be the inversion.

3 - 0
3,6 - 1 (6,3) -> 0 +1
3,6,10 - 3 (6,3)(10,6)(10,3) -> 1 + 2
3,6,10,4 - 6 (6,3)(10,6)(10,3)(4,3)(6,4),(10,4) -> 3 + 3
3,6,10,4,5 - 10 (6,3)(10,6)(10,3)(4,3)(6,4),(10,4)(5,3)(6,5)(10,5)(5,4) -> 6 + 4
3,6,10,4,5,7 - 10 + 5
3,6,10,4,5,7,8 - 15 + 6

:
:
:

f(n) = f(n-1) + (n - 1)

So running the function n times will get the answer.

function getNumberOfInversion(data) {
var prev = 0;
var result = 0;
for(var i = 1;i<=data.length;i++) {
result = prev + (i-1);
prev = result;
}
return result;
}

- MangchiAndJjoe March 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about sort it first,

After the array is sorted, we do the binary search. Each side will calculate the number of inversion.

- No name March 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

doesn't sorting get rid of any possible inversion? As far as I understand the question, inversion is all about the order of the elements in the current list.

- kx March 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

So from my interpretation, an inversion is just anytime a number is greater than any other number in the list regardless of where they are situated in the array. So this gives us the ability to sort the array and not alter the results.

So in my JS implementation in O(nlgn) time:
1. Sort the input array

time: O(nlgn)

2. Keep track of all duplicate values in array. We do this with a JS object (which acts as a set).

-- key = duplicated value
-- value = array of indexes

time: O(n)

3. Starting from the end of the array, we look at its index.

The number of inversions for that number and every other number to the left of it will be equal to:
=it's array index - the number of duplicates of that particular value in question that are to the left

eg. for [1,2,2]
for 2(end value): the number of inversions = 2 - 1 = 1
for 2(middle value): the number of inversions = 1 - 0 = 1
for 1 (first value): the number of inversions = 0 - 0 = 0

time: O(n)

try running this in jsfiddle: jsfiddle.net/ 7v7XN/1/

function getInv() {
    var arraySorted = input.sort(); // n lg n
    var numInv = 0;

    var setTracker = {
        objInputCount: {},
        add: function (input, index) {
            if (this.objInputCount[input]) {
                this.objInputCount[input].push(index);
            } else { // if doesnt exist
                this.objInputCount[input] = [index];
            }
            console.log(this.objInputCount);
        }
    };

    for (var index in arraySorted) {
        setTracker.add(arraySorted[index], index);
    }

    for (var itr = arraySorted.length - 1; itr > -1; itr--) {
        var initInvCount = itr;
        var numCurObjInputVal = setTracker.objInputCount[arraySorted[itr]];

        console.log("inside if control flow");
        console.log(numCurObjInputVal);
        for (var dupIndex in numCurObjInputVal) {
            if (numCurObjInputVal[dupIndex] > itr) {
                console.log("subtracting");
                numInv--;
            }
        }
        numInv += initInvCount;
    }

    return (numInv);
}

var input = [3, 2, 1, 0, 3, 2];
console.log(getInv(input));

- theol88 March 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int count = 0;
for(i = 0;i<n;i++)
        {
               int j = i+1; 
                while(a[j) < a[i] && j > 0)
                {
                        count++;
                        printf("%d, %d", ap[i], a[j]);
                }
        }

- Anonymous April 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int findInversions(int[] ar){
	if(ar.length==0){
		return 0;
	}
	int totInversions=0;
	TreeMap<Integer,Integer> tm=new TreeMap<Integer,Integer>();
	for(int i=0;i<ar.length;i++){
		tm.put(ar[i], 0);
		for(Map.Entry<Integer,Integer> entry : tm.entrySet()) {
			  Integer key = entry.getKey();
			  Integer value = entry.getValue();
			  if(key<ar[i]){
				  entry.setValue(value+1);
			  }
			  else{
				  break;
			  }
		}
	}
	
	for(Map.Entry<Integer,Integer> entry : tm.entrySet()) {
		  Integer value = entry.getValue();
		  totInversions+=value;
	}
	
	return totInversions;
}

- abhishek June 12, 2014 | 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