Microsoft Corporation Interview Questions, Process, and Tips

2 DSA questions asked on codility platform. One was about backtracking, and another about 1D DP.

Q1. Given a binary tree, return false if there exists any node such that it has two children and left node has value greater than right, else return true.
Ans. 
Check if any node in binary tree violates left node value less than right node value rule.
• Traverse the binary tree using depth-first search (DFS) or breadth-first search (BFS) and check each node for the given condition.

• If a node has two children and the left child's value is greater than the right child's value, return false.

• If no such node is found, return true.

• Example: For a binary tree with nodes 5, 3, 7, 2, 4, 6, ...read more
Answered by AI
Add your answer
Q2. Remove duplicate characters from a string efficiently.
Ans. 
Use a hash set to efficiently remove duplicate characters from a string.
• Create a hash set to store unique characters.

• Iterate through the string and add each character to the hash set.

• If a character is already in the hash set, skip it.

• Convert the hash set back to a string to get the result.
Answered by AI
Add your answer

Q1. Process the given string
Add your answer
Q2. Sort the array in alternates
Ans. 
Sort the array in alternates
• Iterate through the array and separate the strings into two separate arrays based on their index being even or odd

• Sort both arrays separately

• Merge the two sorted arrays back into the original array in alternate positions
Answered by AI
Add your answer

6 questions asked in an interview

Q1. Slider window problem
Ans. 
The slider window problem involves finding the maximum sum of a subarray of a fixed size k within an array of integers.
• Use a sliding window approach to efficiently find the maximum sum subarray.

• Keep track of the current sum within the window and update it as you slide the window.

• Maintain a variable to store the maximum sum found so far.

• Example: Given array [1, 3, -1, -3, 5, 3, 6, 7] and window size k=3, the maximum sum
Answered by AI
Add your answer
Q2. Stock buy sell problem
Ans. 
The stock buy sell problem involves finding the maximum profit that can be made by buying and selling a stock at the right times.
• Calculate the difference between each pair of consecutive prices in the array

• Find the maximum subarray sum of the differences using Kadane's algorithm

• The maximum subarray sum is the maximum profit that can be made
Answered by AI
Add your answer

DSA, Graph, DP, Arrays