Search the Community

Showing results for tags 'inversions'.

  • Search By Tags

    Type tags separated by commas.
  • Search By Author

Jabber


Skype


Location


Interests


What is your purpose of joining this website ?

Found 1 result


  1. Count Inversions

    What is an inversion? Let A be an array of n distinct numbers. If i < j and A > 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 > A[j]) countInversions++; The overall time complexity for this approach isO(n^2) Using Merge Sort to count the number of inversions in O(n logn) time The approach using Merge Sort to count the number of inversions is detailed in this blog post ( https://codeground.in/blog/index.php/2016/11/13/technical-interview-question-on-data-structure-and-algorithms-count-the-number-of-inversions-in-an-array/ ). Was this useful? If you’re interested, you can read more about more such puzzles for Tech Interviews ( https://codeground.in/blog/index.php/category/interview-preparation/data-structures-algorithms-tech-interview-questions/ )or you can take do some online programming challenges ( https://codeground.in/screening-tests/coding-contests.html )