Microsoft Software Engineer -2 Interview Experience

1st round (online coding):

Given an array that contains both positive and negative integers, find the product of the maximum product subarray.
Sort an almost sorted array where only two elements are swapped.
Given an integer value and a pointer to the head of the linked list, delete all the nodes from the list that are greater than the specified value.

2nd Round (DSA):

Find the median of a BST. The BST can have duplicates. Had to write production-level code using recursion and backtracking. I told him various approaches, however, he was looking for the median in one scan only using two pointers.

3rd Round (DSA):

Introduction and detailed project discussion.
Find the majority element in an array. The majority element is the element that occurs more than half the size of the array. We discussed various approaches and finally had to write working code for one of them.
Left View of a Binary Tree. Working code was required, along with questions about the code. For example, why a static variable was used and how it could be done without using any static or global variables.
Some questions about pointers, such as: Structure of a linked list: c struct node { int val; node *next; };

So, what will happen if you remove * from node *next? And some more in-depth questions about pointers.

4th Round (Design):

Design a real-time URL spam filtering service. We have information about billions of URLs indicating whether they are spam or not. We need to come up with an architecture solution to store all the URLs and retrieve the information with minimum latency. There were some constraints, like being given very small memory, so only a few URLs could be loaded into memory for a query.
Implement your own malloc and free for application X, which should control the heap memory usage of application X. Discussed various approaches for assigning memory for a request.

5th Round (HR):

6th Round (Hiring manager):

Introduction.
Detailed discussion of a recent project.
Some behavioral questions.
Given the preorder traversal of a binary search tree, construct the BST. Full working code was required.
Given events, like switch on, switch off, pull chair. Design an architecture to count the number of events in a given time frame. The time frame could be minutes, hours, or days.

Microsoft