Microsoft Corporation SDE Intern Interview Questions, Process, and Tips

Round duration - 60 Minutes
Round difficulty - Medium

The interviewer asked me 2 questions related to DS/Algo in this round . Both the questions were of Easy-Medium difficulty and I was also required to code them in a production ready manner.

Q1. 
Maximum Sum Path in a Binary Tree Problem Statement
You are provided with a binary tree consisting of N nodes where each node has an integer value. The task is to determine the maximum sum achievable by a...read more
Ans. 
Find the maximum sum achievable by a simple path between any two nodes in a binary tree.
• Traverse the binary tree to find all possible paths and calculate their sums.

• Keep track of the maximum sum encountered during traversal.

• Consider paths that may include the same node twice.

• Implement a recursive function to explore all possible paths.

• Handle cases where nodes have negative values.
Answered by AI
Add your answer
Q2. 
Intersection of Two Arrays Problem Statement
Given two arrays A and B with sizes N and M respectively, both sorted in non-decreasing order, determine their intersection.
The intersection of two arrays in...read more
Ans. 
The problem involves finding the intersection of two sorted arrays efficiently.
• Use two pointers to iterate through both arrays simultaneously.

• Compare elements at the pointers and move the pointers accordingly.

• Handle cases where elements are equal, and update the intersection array.

• Return the intersection array as the result.
Answered by AI
Add your answer

Round duration - 50 Minutes
Round difficulty - Medium

This round had 2 questions of DS/Algo to solve under 50 minutes and one question related to Operating Systems.

Q1. 
Next Greater Element Problem Statement
You are provided with an array or list ARR containing N positive integers. Your task is to determine the Next Greater Element (NGE) for each element in the array.
T...read more
Ans. 
Find the Next Greater Element for each element in an array.
• Iterate through the array from right to left

• Use a stack to keep track of elements with no greater element to the right

• Pop elements from the stack until finding a greater element or stack is empty
Answered by AI
Add your answer
Q2. 
Number In Arithmetic Progression Problem
Given three integers X, C, and Y, where X is the first term of an arithmetic sequence with a common difference of C, determine if Y is part of this arithmetic sequ...read more
Ans. 
Check if a given number is part of an arithmetic sequence with a given first term and common difference.
• Calculate the arithmetic sequence using the formula: nth term = X + (n-1) * C

• Check if Y is equal to any term in the sequence to determine if it belongs to the sequence

• Return 'True' if Y belongs to the sequence, otherwise return 'False'
Answered by AI
Add your answer
Q3. Can you define process and threads in operating systems?
Ans. 
Processes are instances of programs in execution, while threads are smaller units within a process that can execute independently.
• A process is a program in execution, consisting of code, data, and resources.

• Threads are smaller units within a process that can execute independently.

• Processes have their own memory space, while threads share the same memory space within a process.

• Processes are heavyweight, while threads ar...read more
Answered by AI
Add your answer

Round duration - 50 Minutes
Round difficulty - Medium

This round had 2 questions of DSA of Easy-Medium difficulty and at the end I was asked a Puzzle to check my general problem solving ability.

Q1. 
Max Product Subset Problem Statement
Given an array/list arr of size n, determine the maximum product possible by taking any subset of the array/list arr. Return the result modulo 10^9+7 since the product ...read more
Ans. 
Find the maximum product of a subset of an array modulo 10^9+7.
• Iterate through the array and keep track of the maximum positive product and minimum negative product encountered so far.

• Handle cases where the array contains zeros separately.

• Return the maximum product modulo 10^9+7.
Answered by AI
Add your answer
Q2. 
Populating Next Right Pointers in Each Node
Given a complete binary tree with 'N' nodes, your task is to determine the 'next' node immediately to the right in level order for each node in the given tree.
...read more
Ans. 
Implement a function to update 'next' pointers in a complete binary tree.
• Iterate level by level using a queue

• Connect nodes at each level using 'next' pointers

• Handle null nodes appropriately

• Ensure the tree is a complete binary tree
Answered by AI
Add your answer
Q3. You have two wires of different lengths that are both capable of burning for exactly one hour when ignited at both ends. How can you measure a time interval of 45 minutes using these two wires?
Add your answer

Round duration - 50 Minutes
Round difficulty - Medium

This round consisted of 2 questions from DSA where I was first asked to explain my approach to the interviewer with proper complexity analysis and then code the problems. The interviewer was quite friendly and also provided me some hints when I was stuck.

Q1. 
Stack with getMin Operation
Create a stack data structure that supports not only the usual push and pop operations but also getMin(), which retrieves the minimum element, all in O(1) time complexity witho...read more
Ans. 
Implement a stack with push, pop, top, isEmpty, and getMin operations in O(1) time complexity without using extra space.
• Use two stacks - one to store the actual elements and another to store the minimum element at each level.

• When pushing an element, check if it is smaller than the current minimum and update the minimum stack accordingly.

• When popping an element, also pop from the minimum stack if the popped element is t...read more
Answered by AI
Add your answer
Q2. 
Split Array Into Maximum Subarrays Problem Statement
You are given an integer array arr of size N. Your task is to split the array into the maximum number of subarrays such that the first and last occurre...read more
Ans. 
Given an array, split it into maximum subarrays with first and last occurrence of each element in a single subarray.
• Iterate through the array and keep track of the first and last occurrence of each element.

• Use a hashmap to store the indices of each element.

• Split the array whenever the last occurrence of an element is found.
Answered by AI
Add your answer

Round duration - 90 mintues
Round difficulty - Easy

Timing it is around 1 pm, Environment is very friendly.

Q1. 
Equilibrium Index Problem Statement
Given an array Arr consisting of N integers, your task is to find the equilibrium index of the array.
An index is considered as an equilibrium index if the sum of elem...read more
Ans. 
Find the equilibrium index of an array where sum of elements on left equals sum of elements on right.
• Iterate through the array and calculate the total sum of elements.

• For each index, calculate the sum of elements on the left and right side and check for equilibrium.

• Return the left-most equilibrium index found, or -1 if none exist.
Answered by AI
Add your answer
Q2. 
Maximum Meetings Problem Statement
Given the schedule of N meetings with their start time Start[i] and end time End[i], you need to determine which meetings can be organized in a single meeting room such ...read more
Ans. 
Given N meetings with start and end times, find the maximum number of meetings that can be organized in a single room without overlap.
• Sort the meetings based on end times.

• Iterate through the sorted meetings and select the next meeting whose start time is greater than or equal to the end time of the previous meeting.

• Return the selected meetings in the order they are organized.
Answered by AI
Add your answer

Round duration - 90 mintues
Round difficulty - Hard

Timing it is around 1 pm and Environment is good .

Q1. Explain how to overload the pre and post-increment operators in object-oriented programming.
Ans. 
Overloading pre and post-increment operators in OOP involves defining special member functions for the class.
• Define member functions for pre-increment (++obj) and post-increment (obj++) operators in the class.

• For pre-increment, return a reference to the modified object after incrementing the value.

• For post-increment, return a copy of the original object before incrementing the value.

• Example: class Counter { int value; ...read more
Answered by AI
Add your answer
Q2. 
Longest Zero Sum Subarray Problem
Given an array of integers consisting of both positive and negative numbers, find the length of the longest subarray whose sum is zero. This problem will be presented wit...read more
Ans. 
Find the length of the longest subarray with zero sum in an array of integers.
• Iterate through the array and keep track of the running sum using a hashmap.

• If the running sum is seen before, it means there is a subarray with zero sum.

• Calculate the length of the subarray with zero sum and update the maximum length found so far.
Answered by AI
Add your answer