Amazon Interview Question
SDE-2sTeam: Kindle
Country: India
Interview Type: In-Person
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
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.
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.
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]);
}
}
#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);
}
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
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.
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.
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.
I agree with this answer. It does not look like we need some complex data structure for this.
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.
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.
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
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
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;
}
How about sort it first,
After the array is sorted, we do the binary search. Each side will calculate the number of inversion.
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));
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;
}
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?
- S O U N D W A V E March 03, 2014