Technical Interview Question on Data Structure and Algorithms: Count the number of inversions in an array

count-inversions

What is an inversion?

Let A be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A.

For example, the array {2,3,8,6,1} has 5 inversions: (2,1) (3,1) (8,6) (8,1) and (6,1)

Trivial Solution to count the number of inversions in an array

countInversions = 0;

for i = 1 to N

   for j = i+1 to N

       if(A[i] > A[j])

            countInversions++;

The overall time complexity for this approach is O(n^2)

Using Merge Sort to count the number of inversions in O(n logn) time

merge-sort

Merge-Sort is a divide-and-conquer strategy where the array is divided into two halves, each half is sorted and the the sorted halves are merged back together in sorted order.

MERGE-SORT(A, start, end)    {

   if(start < end)   {

       mid = (start + end) / 2;

       MERGE-SORT(A, start, mid);

       MERGE-SORT(A, mid + 1, end);

       MERGE(A, start, mid, end);

   }

}

The Merge Operation in Merge Sort is described below. The values in the two halves are copied to two temporary arrays. The elements from these arrays are then added back into the main array in sorted order.

merge-operation

MERGE(A, start, mid, end)    {

    firstArray = new Array of size mid – start + 2;

    secondArray = new Array of size end – mid + 1;

    Copy values from A[start: mid] to firstArray[0: mid-start];

    Copy values from A[mid+1: end] to secondArray[0: end-mid-1];

    firstArray[mid-start+1] = 

    secondArray[end-mid] = 

    i = 0, j = 0;

    for k = start to end   {

        if(firstArray[i] <= secondArray[j])   {

            A[k] = firstArray[i];

            i++;

        } else  {

            A[k] = secondArray[j];

            j++;

        }

    }

}    

Can you think of how you would modify MERGE-SORT to count the number of inversions? Take your time and think about your solution before reading further.

Modified Merge-Sort

int MERGE-SORT(A, start, end)    {

   int countInversions = 0;

   if(start < end)   {

       mid = (start + end) / 2;

       countInversions += MERGE-SORT(A, start, mid);

       countInversions += MERGE-SORT(A, mid + 1, end);

       countInversions += MERGE(A, start, mid, end);

   }

   return countInversions;

}

int MERGE(A, start, mid, end)    {

    firstArray = new Array of size mid – start + 2;

    secondArray = new Array of size end – mid + 1;

    Copy values from A[start: mid] to firstArray[0: mid-start];

    Copy values from A[mid+1: end] to secondArray[0: end-mid-1];

    firstArray[mid-start+1] = 

    secondArray[end-mid] = 

    i = 0, j = 0, countInversions = 0;

    for k = start to end   {

        if(firstArray[i] <= secondArray[j])   {

            A[k] = firstArray[i];

            i++;

        } else  {

            A[k] = secondArray[j];

            j++;

            countInversions += firstArray.length – i - 1;

        }

    }

    return countInversions;

}       

Do you think this will work? Please simulate this once yourself and see!

 

This content was brought to you by CodeGround Online Testing PlatformCodeGround is an online assessment and test evaluation system focused on helping Recruiters in initial screening of potential candidates from an ocean of job seekers in an automated way.

CodeGround supports Online Aptitude TestsSpoken English Communication Skills AssessmentsCoding Contests in JAVA, C, C++, Ruby, Python, JavaScript and PHP.  CodeGround also supports Automated asynchronous interviews. CodeGround Screening Tests can be used by Recruiters during campus hiring or to screen walkin candidates.

Please follow and like us:
0
Share this: