Microsoft Corporation Software Developer Intern Interview Questions, Process, and Tips

2Coding questions were there

Q1. Reverse string standard DSA
Add your answer
Q2. Tapping rainwater standard DSA
Add your answer

Round duration - 90 minutes
Round difficulty - Easy

There were 3 coding questions. All of them were pretty easy and solvable in less than 30 minutes. Some string and pattern matching + some number theory problems were there.

Q1. 
Arithmetic Expression Evaluation Problem Statement
You are provided with a string expression consisting of characters '+', '-', '*', '/', '(', ')' and digits '0' to '9', representing an arithmetic express...read more
Ans. Reverse Polish Notation
Infix Expressions are harder for Computers to evaluate because of the additional work needed to decide precedence, so we first convert infix expressions into either postfix or prefix expressions.  In this approach, we convert Infix expression into Postfix expression also known as Reverse Polish Notation, and then evaluate the postfix expression using stack.  Note in postfix expression, ...read more
Answered Anonymously
Add your answer
Q2. 
Maximum Product Subarray Problem Statement
Given an array of integers, determine the contiguous subarray that produces the maximum product of its elements.
Explanation:
A subarray can be derived from th...read more
Ans. Brute-force
Steps:
1. Create an ans variable and initialize it to INT_MIN.
2. Run a loop i = 0 to N and do:
   • Run a loop j = i to N and do:
     • Create a variable, say currentProduct and initialize it to 1.
     • Run a loop k = i to j and do:
       • currentProduct = currentProduct * arr[k]
       • Store the maximum of ans and the currentProduct in the ans variable.
3. Finally, return the ans variable.
Space Complexity: O(1)Explanation:
O(1)
 
Constant space is u...read more
Answered Anonymously
Add your answer
Q3. 
Angle Calculation Between Clock Hands
Given a specific time in hours and minutes, your task is to calculate the smallest possible angle between the hour hand and the minute hand of a clock.
Example:
Inp...read more
Ans. Using reference time
• The idea is to take the 12:00 i.e. H = 12  and M = 0 as reference time.
• First,  calculate the angle made by the hour hand with respect to 12:00 in H hours and M minutes. In 12 hours the hour hand moves by 360 degrees i.e. 30 degrees in 1 hour and 0.5 degrees in 1 minute. So in H hours and M minutes, the angle moved by hour hand is  0.5 * (H * 60 + M).
• Then, calculate the angle made by m...read more
Answered Anonymously
Add your answer

Round duration - 45 minutes
Round difficulty - Medium

This was a technical round. First after properly introducing ourselves(me and the interviewer), we started with the main interview. I was asked 2 questions, one DS and Algorithms and the other System Design question.

Q1. 
Problem Statement: Sibling Nodes
You are provided with a Binary Tree consisting of 'N' nodes, where each node holds an integer value. Your objective is to identify and list all nodes that do not possess a...read more
Ans. DFS Approach
The idea here is to use the fact that if a node of the binary tree has two child nodes, then both of them will be siblings to each other, and if a node of the binary tree has only one child, then that child will not have any sibling.
Example 
In above figure 1 has two children, so nodes 3 and 4 are siblings to each other. Also, 3 has only one child, i.e., 5 and 5 have no sibling node.

So, we will use a df...read more
Answered Anonymously
Add your answer
Q2. Design an elevator system for a single building with N floors.
Ans. 
Tip 1 : Discuss first about how the product(here, elevator) will function.
Tip 2 : Start making with the most basic classes for the elevator.
Tip 3 : One by one after making the basic class, add new functionalities to it, taking care of all corner cases.
Answered Anonymously
Add your answer

Round duration - 75 minutes
Round difficulty - Hard

This round was scheduled in the evening hours and all the participants were required to fill a form which was shared 2 days prior to the test date. This form was filled out probably for the security reasons and to ensure that no one disinterested participant gives the test.

Q1. 
Validate BST Problem Statement
Given a binary tree with N nodes, determine whether the tree is a Binary Search Tree (BST). If it is a BST, return true; otherwise, return false.
A binary search tree (BST)...read more
Ans. Approach 1
• For each node, store the minimum and maximum value allowed for that node.
• Initially, for the root node as all the integer values are allowed, the minimum value would be -10^9 and the maximum value should be 10^9. Here we can also use built-in INT_MIN and INT_MAX constants.
• If the value of that node is not in the bounded range of minimum and maximum value, then return false.
• For the left subtree of a node with da...read more
Answered Anonymously
Add your answer
Q2. 
Longest Palindromic Subsequence Problem Statement
Given a string A consisting of lowercase English letters, determine the length of the longest palindromic subsequence within A.
Explanation:
• A subsequ...read more
Ans. Recursive Approach
The main idea behind this approach is to use recursion. The idea is to compare the first character of the string A[i..j] with its last character. There are two possibilities:
1. If the first character of the string is the same as the last character, we include first and last characters in the palindrome and do a recursive call for the remaining substring A[i + 1, j - 1].
2. If the last character of the string...read more
Answered Anonymously
Add your answer

Round duration - 45 minutes
Round difficulty - Medium

There was only one female interviewer for this round. She continuously interacted with me and was giving me some good situational problems that were not very easy to answer. Basically those were open-minded questions which can be answered both ways and that's why I found it quiet hard as per my nature but at the end things went well for me.

Round duration - 120 Minutes
Round difficulty - Easy

Total 3 coding questions were there, out of which I don't remember the last one.

Q1. 
Ninja's Dance Competition Pairing Problem
Ninja is organizing a dance competition and wants to pair participants using a unique method. Each participant chooses a number upon entry, and Ninja selects a nu...read more
Ans. Sorting + Two Pointer
The brute force approach that we can think of is to check for every pair in the array and then count the number of pairs with a difference equal to ‘K’. 
 
But this brute force approach will not be valid in the case of duplicates. So, in order to handle duplicate pairs, we will sort the array first and then find the pair and finally skip the ones that are equal. 
 
Algorithm: 
1. S...read more
Answered Anonymously
Add your answer
Q2. 
Longest Common Prefix After Rotation
You are given two strings 'A' and 'B'. While string 'A' is constant, you may apply any number of left shift operations to string 'B'.
Explanation:
Your task is to calcu...read more
Ans. Brute Force
1. Let’s denote the length of A as M and the length of B as N.
2. Declare an ans variable to store the minimum number of left shifts required and a max variable in order to store the length of the longest common prefix encountered so far. Initialize the ans variable to 0.
3. Find out the common prefix of A and B and initialize max to the length of the common prefix. The length of the common prefix between two strings c...read more
Answered Anonymously
Add your answer

Round duration - 60 Minutes
Round difficulty - Easy

Q1. 
Rotate Matrix by 90 Degrees Problem Statement
Given a square matrix 'MATRIX' of non-negative integers, rotate the matrix by 90 degrees in an anti-clockwise direction using only constant extra space.
Inpu...read more
Ans. Transpose and Reverse
The idea is to find the transpose of the given matrix and then reverse the columns of the transposed matrix. For example:
For the given 2D matrix:
	[ [ 1,  2,  3 ],
	  [ 4,  5,  6 ],
	  [ 7,  8,  9 ] ]
After taking transpose, it will become:
	[ [ 1,  4,  7 ],
	  [ 2,  5,  8 ],
	  [ 3,  6,  9 ] ]
After reversing the columns, it will ...read more
Answered Anonymously
Add your answer
Q2. 
Problem: Sort an Array of 0s, 1s, and 2s
Given an array/list ARR consisting of integers where each element is either 0, 1, or 2, your task is to sort this array in increasing order.
Input:
The input sta...read more
Ans. NAIVE APPROACH
Simply, we will sort the array.
Space Complexity: O(1)Explanation:
O(1), i.e. constant space complexity. 
 
Since we are not using any extra space. Hence, the space complexity is constant.
Time Complexity: O(nlogn)Explanation:
O(Nlog(N)), where N is the length of the array/list.
 
Since we are using the inbuilt sort function. Hence, the time complexity is O(Nlog(N)).

Java (SE 1.8)

/*

    Time Compl...read more
Answered Anonymously
Add your answer

Round duration - 60 Minutes
Round difficulty - Easy

This was HR + Technical round
He started with questions on projects and Os and Dbms and Oops
Then asked one coding question

Q1. 
Number of Islands Problem Statement
You are given a non-empty grid that consists of only 0s and 1s. Your task is to determine the number of islands in this grid.
An island is defined as a group of 1s (re...read more
Ans. DFS
The problem boils down to find the number of connected components in the grid. 
 
If we are on a land cell and explore every cell connected to it 8-directionally (and recursively cells connected to those cells, and so on), then the total number of cells with land explored will be one island.
 
To ensure we don't count cells in the island more than once, we will mark 1(land) as 0 during the recursion call...read more
Answered Anonymously
Add your answer