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

- Yong June 08, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes it can be done using inversion count in merge sort

- Kundan June 23, 2020 | Flag
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).

- Chinmoy June 02, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Dharan Aditya June 07, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Dharan Aditya June 07, 2020 | Flag
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))

- yongzpub June 08, 2020 | Flag Reply
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)

- Anonymous June 15, 2020 | Flag Reply
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.

- Kundan Kumar June 23, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How exactly is the sum 7 here? Can anyone explain

- Sharath June 28, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Ankesh July 09, 2020 | Flag
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;
            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;
     }

- Ashis Kumar July 19, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Rishav Saxena October 30, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Rishav Saxena October 30, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

this can be done using map

- Anonymous July 20, 2020 | Flag Reply
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)

- it is cool.. October 20, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

in fact its similar to next greatest,its opposite of that

- garimaguptaprincy April 03, 2022 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More