vishudon's blog

By vishudon, history, 15 months ago, In English

Dear community,

I hope you all are doing good and safe. I just want to know one thing. Recently I had a interview and the interviewer asked one question, how to solve inversion count problem.

I suggested two approaches to him (1. brute force, and 2. using merge sort). He was completely satisfied by my both the approaches.

But at last, he asked one question to me. Can we solve inversion count problem in O(n+k) where n <= k <= (n*n) ?

I couldn't suggest such approach to him. Also, my bad luck, I couldn't ask him about such approach. But, I am just curious to know is this really possible ? Can someone suggest some approach which could solve inversion count problem in O(n+k) where n <= k <= (n*n) ?

Thanks.

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

»
15 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Yes, it’s kinda similar to the bubble sort. At each step add element to the end of the array and move it to the left until it will end at the good position.

»
15 months ago, # |
  Vote: I like it +6 Vote: I do not like it

If $$$k = n \cdot n$$$, isn't it the same as the bruteforce bubble sort approach?