Microsoft Corporation Interview Questions, Process, and Tips

Round duration - 60 minutes
Round difficulty - Medium

Timing-> EVENING(5 TO 6)
The interviewer was very sweet and calm.

Q1. 
Cycle Detection in a Singly Linked List
Determine if a given singly linked list of integers forms a cycle or not.
A cycle in a linked list occurs when a node's next points back to a previous node in the ...read more
Ans. 
Detect if a singly linked list forms a cycle by checking if a node's next pointer points back to a previous node.
• Use Floyd's Cycle Detection Algorithm to determine if there is a cycle in the linked list.

• Maintain two pointers, one moving at twice the speed of the other.

• If the two pointers meet at any point, there is a cycle in the linked list.
Answered by AI
Add your answer
Q2. 
Boundary Traversal of a Binary Tree
Given a binary tree of integers, your task is to return the boundary nodes of the tree in Anti-Clockwise direction starting from the root node.
Input:
The first line ...read more
Ans. 
Return the boundary nodes of a binary tree in Anti-Clockwise direction starting from the root node.
• Traverse the left boundary nodes in a top-down manner

• Traverse the leaf nodes in a left-right manner

• Traverse the right boundary nodes in a bottom-up manner

• Avoid duplicates in boundary nodes
Answered by AI
Add your answer

Round duration - 45 minutes
Round difficulty - Easy

It was in the late afternoon. I was vey nervous, but the interviewer was very friendly. I managed to solve the questions early, so we discussed general things about the company and its culture.

Q1. 
Rooms and Keys Problem Statement
Given some information about rooms in a military camp, where rooms are numbered from 0 to 'N-1'. Each room may contain keys to some other rooms. You can only visit a room ...read more
Ans. 
Determine if all rooms can be visited starting from room 0 with given keys information.
• Use depth-first search (DFS) to traverse through rooms and keys.

• Keep track of visited rooms to avoid infinite loops.

• Check if all rooms have been visited at the end.
Answered by AI
Add your answer
Q2. 
Detect the First Node of the Loop in a Singly Linked List
You are provided with a singly linked list that may contain a cycle. Your task is to return the node where the cycle begins, if such a cycle exist...read more
Ans. 
To detect the first node of the loop in a singly linked list, we can use Floyd's Cycle Detection Algorithm.
• Use Floyd's Cycle Detection Algorithm to find the meeting point of the slow and fast pointers in the linked list.

• Reset one of the pointers to the head of the linked list and move both pointers at the same speed until they meet at the start of the cycle.

• The node where the pointers meet is the first node of the loop
Answered by AI
Add your answer

Round duration - 30 minutes
Round difficulty - Medium

The duration of the round was 30 minutes. It was conducted in the morning hours. The interviewer asked me many questions regarding my internship experience and my project. Later we discussed some problem solving.

Round duration - 75 minutes
Round difficulty - Hard

This round was conducted early in the morning. The interviewer was highly experienced and very friendly. He discussed about his life journey and his experience with the company.
Overall the experience was good, getting interviewed by such experienced person

Q1. 
Time to Burn Tree Problem
You are given a binary tree consisting of 'N' unique nodes and a start node where the burning will commence. The task is to calculate the time in minutes required to completely b...read more
Ans. 
Calculate the time in minutes required to completely burn a binary tree starting from a given node.
• Traverse the tree to find the longest path from the start node to a leaf node.

• The time to burn the entire tree is equal to the length of the longest path.

• Simulate the burning process by incrementing the time for each level of the tree.
Answered by AI
Add your answer

Round duration - 1 hour
Round difficulty - Medium

Q1. 
First Missing Positive Problem Statement
You are provided with an integer array ARR of length 'N'. Your objective is to determine the first missing positive integer using linear time and constant space. T...read more
Ans. 
Find the smallest positive integer missing from an array of integers.
• Iterate through the array and mark positive integers as visited by changing the sign of the corresponding index.

• After marking all positive integers, iterate again to find the first positive integer with a positive value.

• Return the index of the first positive integer found plus one as the answer.
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Medium

Q1. 
Rearrange String Problem Statement
Given a string ‘S’, your task is to rearrange its characters so that no two adjacent characters are the same. If it's possible, return any such arrangement, otherwise re...read more
Ans. 
Given a string, rearrange its characters so that no two adjacent characters are the same.
• Iterate through the string and count the frequency of each character.

• Use a priority queue to rearrange the characters based on their frequency.

• Check if it's possible to rearrange the string without any two adjacent characters being the same.

• Return 'Yes' if possible, 'No' otherwise.
Answered by AI
Add your answer
Q2. 
Find Nodes at Distance K in a Binary Tree
Your task is to find all nodes that are exactly a distance K from a given node in an arbitrary binary tree. The distance is defined as the number of edges between ...read more
Ans. 
Find all nodes at distance K from a given node in a binary tree.
• Perform a depth-first search starting from the target node to find nodes at distance K.

• Use a recursive function to traverse the tree and keep track of the distance from the target node.

• Maintain a set to store visited nodes to avoid revisiting them.

• Return the list of nodes found at distance K from the target node.

• Example: If the target node is 5 and K is 2 ...read more
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Medium

Q1. 
My Calendar Problem Statement
Given N events, each represented with a start and end time as intervals, i.e., booking on the half-open interval [start, end). Initially, the calendar is empty. A new event c...read more
Ans. 
Given N events with start and end times, determine if each event can be added to the calendar without causing a triple booking.
• Iterate through each event and check if adding it causes a triple booking by comparing its interval with previous events

• Use a data structure like a list or dictionary to keep track of booked intervals

• Return 'True' if the event can be added without causing a triple booking, 'False' otherwise
Answered by AI
Add your answer

Round duration - 45 minutes
Round difficulty - Easy