Community

Start a Thread


Notifications
Subscribe You’re not receiving notifications from this thread.

How Out Of Order (Main Thread)

Here is the interview question prompt, presented for reference.

This was submitted by user Hackleman.

Determine how "out of order" a list is by writing a function that returns the number of inversions in that list.

Two elements of a list L, L[i] and L[j], form an inversion if L[i] < L[j] but i > j.

For example, the list [5, 4, 3, 2, 1] has 10 inversions since every element is out of order. They are the following: (5, 4), (5,3), (5,2), (5,1), (4,3), (4,2), (4,1), (3,2), (3,1), (2,1).

The list [2, 1, 4, 3, 5] has two inversions: (2, 1) and (4, 3).

Do this in better than O(N^2).

Constraints

  • Length of the given array <= 100000
  • Values in the array ranges from -1000000000 to 1000000000
  • Expected time complexity : O(nlogn)
  • Expected space complexity : O(1)

You can see the full challenge with visuals at this link.

Challenges • Asked over 4 years ago by Anonymous

Jake from AlgoDaily Commented on Nov 07, 2019:

This is the main discussion thread generated for How Out Of Order.

Anonymous Commented on Nov 07, 2019:

It would be helpful to describe the inversions in the first example:
(5,4) (5,3) (5,2) (5,1)
(4,3) (4,2) (4,1)
(3,2) (3,1)
(2,1)

Jake from AlgoDaily Commented on Nov 28, 2019:

Yes, great point! Added.

Anonymous Commented on Feb 01, 2020:

The given is the first element of list instead of list. The result of below console printout:

function inversions(list) {
console.log(list);
...

5
AssertionError: expected 0 to equal 10
2
AssertionError: expected 0 to equal 3

Ashish Bhattarai Commented on Mar 28, 2020:

Hello there... test function should be inversions not inversion...