Microsoft Corporation Interview Questions, Process, and Tips

Round duration - 60 minutes
Round difficulty - Medium

It was a video call round, that began with a brief introduction of the interviewer followed by mine. Then the interviewer asked me to solve 2 data structure questions in a text editor while sharing my screen. Also, we had a brief discussion of the time complexity of the programs I had written, which I had to optimize to the best time complexity as well.

Q1. 
Spiral Matrix Problem Statement
You are given a N x M matrix of integers. Your task is to return the spiral path of the matrix elements.
Input
The first line contains an integer 'T' which denotes the nu...read more
Ans. 
The task is to return the spiral path of elements in a given matrix.
• Iterate through the matrix in a spiral path by keeping track of boundaries.

• Print elements in the order of top, right, bottom, and left sides of the matrix.

• Handle cases where the matrix is not a square (N != M) separately.

• Consider edge cases like single row, single column, and empty matrix.
Answered by AI
Add your answer
Q2. 
Sort 0 1 2 Problem Statement
Given an integer array arr of size 'N' containing only 0s, 1s, and 2s, write an algorithm to sort the array.
Input:
The first line contains an integer 'T' representing the n...read more
Ans. 
Sort an array of 0s, 1s, and 2s in linear time complexity.
• Use three pointers to keep track of the positions of 0s, 1s, and 2s in the array.

• Iterate through the array and swap elements based on the values encountered.

• This approach sorts the array in a single scan without using any extra space.
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Easy

It was a face-to-face round in the Hyderabad Office at 8 in the morning. This round consisted of various types of questions. It began with a brief description of my interest in technology and a discussion about any major problems I faced working and how I resolved it. Then it continued with various data structure questions, followed by operating system, database, and system design questions. I had majorly worked with the project Jarvis Personal Assistant, so I was asked to design the complete workflow of the project.

Q1. 
Mirror String Problem Statement
Given a string S containing only uppercase English characters, determine if S is identical to its reflection in the mirror.
Example:
Input:
S = "AMAMA"
Output:
YES
Ex...read more
Ans. 
Determine if a given string is identical to its reflection in the mirror.
• Iterate through the string and compare characters from start and end simultaneously.

• If characters are not equal, return 'NO'.

• If all characters match, return 'YES'.
Answered by AI
Add your answer

Round duration - 90 minutes
Round difficulty - Easy

This round was the online coding test conducted on the platform Mettl. The languages allowed were C, C++, Java and Python. There were three questions. One was of graphs (Depth-first search), other was a big integer problem and the third was a string problem.

Q1. 
Graph Coloring Problem Statement
You are provided with a graph consisting of N vertices, numbered from 1 to N, and M edges. Your task is to color the graph using two colors, Blue and Red, such that no two...read more
Ans. 
Given a graph with vertices and edges, determine if it can be colored using two colors without adjacent vertices sharing the same color.
• Check if the graph is bipartite using graph coloring algorithm like BFS or DFS.

• If the graph is bipartite, return 'Possible' with a valid coloring assignment.

• If the graph is not bipartite, return 'Impossible'.
Answered by AI
Add your answer
Q2. 
String Compression Problem Statement
Write a program to perform basic string compression. For each character that repeats consecutively more than once, replace the consecutive duplicate occurrences with t...read more
Ans. 
Write a program to compress a string by replacing consecutive duplicate characters with the character followed by the number of repetitions.
• Iterate through the string and count consecutive occurrences of each character

• Append the character and its count to a new string

• Return the compressed string if it is shorter than the original, else return the original string

• Handle edge cases like single characters or when compresse
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Easy

This was a pen and paper subjective interview round. You were expected to write full code on paper. Make sure you use proper names for the variables and write comments explaining very clearly what the code does. Also, try writing code in good handwriting which can be understood by the interviewer.

Q1. Find the total number of palindromic substrings in a given string.
Ans. 
Count total palindromic substrings in a given string.
• Iterate through each character in the string and consider it as the center of a palindrome. Expand outwards to find all palindromic substrings.

• Use dynamic programming to efficiently check if a substring is a palindrome.

• Consider both odd-length and even-length palindromes.

• Example: Input 'ababa', output 7 (a, b, a, b, a, aba, aba)
Answered by AI
Add your answer

Round duration - 45 minutes
Round difficulty - Easy

The interview took place in the morning and the interviewer was very friendly.

Q1. 
Count Inversions Problem Statement
Let A[0 ... n-1] be an array of n distinct positive integers. An inversion of A is a pair of indices (i, j) such that i < j and A[i] > A[j]. Given an integer array...read more
Ans. 
Count the number of inversions in an array of distinct positive integers.
• Use merge sort algorithm to count inversions efficiently.

• Divide the array into two halves and recursively count inversions in each half.

• Merge the two sorted halves while counting split inversions.

• Time complexity can be optimized to O(n log n) using merge sort.

• Example: For input A = [2, 4, 1, 3, 5], the output should be 3.
Answered by AI
Add your answer
Q2. 
Sum Tree Conversion Problem Statement
Transform a given binary tree into a sum tree where each node is replaced by the sum of its immediate children's values. Leaf nodes should be replaced with 0. Then, p...read more
Ans. 
Convert a binary tree into a sum tree by replacing each node with the sum of its children's values, and return the preorder traversal.
• Traverse the tree recursively and replace each node with the sum of its children's values

• Leaf nodes should be replaced with 0

• Perform a preorder traversal on the transformed sum tree to get the final result
Answered by AI
Add your answer

Round duration - 30 minutes
Round difficulty - Easy

The HR Interview round was held in the morning and it was right after my technical interview.

Round duration - 90 minutes
Round difficulty - Medium

This round was of 90 minutes, consisting of 3 coding questions from easy to medium level. It was conducted in the morning hours. The invigilators were the staff of my college only. The platform was very smooth and almost all the programming languages were allowed.

Q1. 
Valid Parentheses Problem Statement
Given a string 'STR' consisting solely of the characters “{”, “}”, “(”, “)”, “[” and “]”, determine if the parentheses are balanced.
Input:
The first line contains an...read more
Ans. 
The task is to determine if a given string consisting of parentheses is balanced or not.
• Use a stack data structure to keep track of opening parentheses.

• Iterate through the string and push opening parentheses onto the stack.

• When encountering a closing parenthesis, pop the top element from the stack and check if it matches the corresponding opening parenthesis.

• If the stack is empty at the end of the iteration and all par...read more
Answered by AI
Add your answer
Q2. 
Trapping Rain Water Problem Statement
You are given a long type array/list ARR of size N, representing an elevation map. The value ARR[i] denotes the elevation of the ith bar. Your task is to determine th...read more
Ans. 
Calculate the total amount of rainwater that can be trapped between given elevations in an array.
• Iterate through the array and calculate the maximum height on the left and right of each bar.

• Calculate the amount of water that can be trapped at each bar by taking the minimum of the maximum heights on the left and right.

• Sum up the trapped water at each bar to get the total trapped water for the entire array.
Answered by AI
Add your answer
Q3. 
Travelling Salesman Problem
Given a list of cities numbered from 0 to N-1 and a matrix DISTANCE consisting of 'N' rows and 'N' columns, representing the distances between each pair of cities, find the sho...read more
Ans. 
Implement a function to find the shortest route visiting each city exactly once and returning to the starting city.
• Use backtracking to explore all possible routes and find the minimum distance.

• Keep track of visited cities to ensure each city is visited exactly once.

• Consider pruning techniques like dynamic programming to optimize the solution.

• Example: Start at city 0, visit cities 1 and 2 in any order, and return to cit...read more
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Easy

This round was a group fly round. Team from Microsoft came for invigilation and guidance. We were divided into small groups, and a mentor was allotted to us. There were 2 questions and time was 60 minutes. First question was based on system design and second one was coding question. We were asked to write on paper and discuss with mentors. We were marked on the basis of how we discussed our ideas with our mentor and how clearly we presented our idea.

Q1. Design a search engine for a global retail application. Please include:
• Assumptions
• System considerations
• Design components
Ans. 
Design a search engine for a global retail application.
• Assumptions: assume the search engine will need to handle a large volume of products and users from around the world

• System considerations: scalability, speed, relevance of search results, multi-language support

• Design components: indexing system, query processing, ranking algorithm, user interface
Answered by AI
Add your answer
Q2. 
Longest Palindromic Subsequence Problem Statement
Ninja receives a PS5 from Santa, locked in a safe with a password. The password is the length of the longest palindromic subsequence in the given string S...read more
Ans. 
The task is to find the length of the longest palindromic subsequence in a given string.
• Iterate through the string and create a 2D array to store the lengths of palindromic subsequences.

• Use dynamic programming to fill the array based on the characters of the string.

• The final answer will be the value at the last index of the array.

• Example: For input 'CACBDBA', the longest palindromic subsequence is 'CBDC', so the output
Answered by AI
Add your answer

Round duration - 30 minutes
Round difficulty - Medium

The interview was early in the morning. The environment was very tensed, we all were very nervous for the first round of interview. The interviewers were very friendly, they were helping us a lot .

Q1. 
Binary Search Tree Insertion
Given the root node of a binary search tree and a positive integer, you need to insert a new node with the given value into the BST so that the resulting tree maintains the pr...read more
Ans. 
Insert a new node with a given value into a binary search tree while maintaining the properties of a BST.
• Traverse the BST starting from the root node to find the correct position for insertion.

• Compare the value to be inserted with the current node's value to determine whether to go left or right.

• Create a new node with the given value and insert it at the appropriate position in the BST.

• Ensure that the resulting tree ma...read more
Answered by AI
Add your answer

Round duration - 30 minutes
Round difficulty - Easy

This round was conducted in the afternoon. The environment was friendly. Interviewer was very friendly and helping.

Q1. 
Sort Stack Problem Statement
You are given a stack S. Your task is to sort the stack recursively in descending order.
Constraints:
• Looping through the stack is not allowed.
• Return the stack sorted ...read more
Ans. 
Sort a given stack in descending order recursively without using loops.
• Use recursion to pop elements from the stack and insert them in the correct position.

• Maintain a temporary stack to hold elements while sorting.

• Compare the top element of the stack with the top element of the temporary stack to insert in descending order.
Answered by AI
Add your answer

Round duration - 30 minutes
Round difficulty - Medium

I was conducted in the evening. The interviewer was very friendly and asked me questions mostly about me and my future plans.