## Microsoft Interview Question

SDE-3s**Country:**India

If we are looking for less than O(n^2) time, This can probably be done with a Fenwick tree which will give O(nLogn).

Can please provide the algorithm. I am not able to figure out the algorithm using Fenwick Tree

```
/*
Insertion sort worst case O(N*N) when input is descending order,
as input array is not fully descending order,
solving the way Insertion order will be < O(N*N)
*/
public static void main(String []args){
System.out.println("Hello World");
int[] arr = {7,3,2, 8,1};
int result =0;
Node root = new Node(arr[arr.length-1]);
for ( int i=arr.length-2; i>=0; i--){
int jumpCount = jump (root, arr[i]);
result+= jumpCount;
System.out.println("Shadow count: "+ result);
}
}
public static int jump(Node root, int n){
int jumpCount =0;
Node temp = root;
while(temp.val < n){
jumpCount++;
if(temp.next == null || temp.next.val > n) break;
else temp = temp.next;
}
if(temp.next == null){
temp.next = new Node(n);
}else{
Node _node = new Node(n);
_node.next = temp.next ;
temp.next = _node;
}
return jumpCount;
}
static class Node{
int val;
public Node(int val){this.val = val;}
Node next;
}
```

It could be done by sorting algorithm, like Merge, to calculate inversion, it will be O(nLog(n))

- Yong June 08, 2020