## Microsoft Interview Question for SDE-3s

Country: India

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

Yes it can be done using inversion count in merge sort

Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

Can you describe the algorithm. I am not able to figure out the algorithm using fenwick Tree.

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a question to find inversion, could use any algorithm, like Merge, to implement under O(nLog(n))

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````x = list(map(int, input().split()))
max_min_val = 0
sum = 0
for i in range(len(x)-2, -1, -1):
val = x[i+1]
if max_min_val < val and val < x[i]:
max_min_val = val

sum += max_min_val

print(sum)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be easily solve using count inversion logic using merge sort.

Comment hidden because of low score. Click to expand.
0
of 0 vote

How exactly is the sum 7 here? Can anyone explain

Comment hidden because of low score. Click to expand.
0

The questions is apparently about the sum of NUMBER of shadow balls and not the sum of shadow balls. So, 7 has 3 shadow balls, 3 has 2 shadow balls and so on.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/*
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;
}
}
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;
}``````

Comment hidden because of low score. Click to expand.
0

Is your solution working for {1,2,4,3,5}?
Output: 1->0
2->0
4->1
3->0
5->0
So, it should be 0+0+1+0+0=1, but, the above solution is giving 0.

Comment hidden because of low score. Click to expand.
0

Check this solution for the below test case:
Input: {1,2,4,3,5}
Expected Output: 1
Code's Output: 0

Comment hidden because of low score. Click to expand.
0
of 0 vote

this can be done using map

Comment hidden because of low score. Click to expand.
0
of 0 vote

bs = map(list(int, input().rstrip().split()))
ln = len(bs)
for i in range(l):
a = bs[i]
ss = 0
for k in range(i,l):
if bs[k] <= a:
ss += 1
sk += ss
print(sk)

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.