Microsoft Corporation Software Engineer Intern Trainee Interview Questions and Answers

Numerical and logical aptitude test

There are 5 rounds on datastructure and algorithm

Round duration - 45 minutes
Round difficulty - Medium

The interview was with a Korean employee. 

Q1. 
Bridge in Graph Problem Statement
Given an undirected graph with V vertices and E edges, your task is to find all the bridges in this graph. A bridge is an edge that, when removed, increases the number of...read more
Ans. 
Find all the bridges in an undirected graph.
• Use Tarjan's algorithm to find bridges in the graph.

• A bridge is an edge whose removal increases the number of connected components.

• Check for bridges by removing each edge and checking the number of connected components.

• Return the edges that are bridges in non-decreasing order.
Answered by AI
Add your answer

Round duration - 45 Minutes
Round difficulty - Medium

Interviewer was an Indian employee. 

Q1. 
Longest Palindromic Substring Problem Statement
You are provided with a string STR of length N. The goal is to identify the longest palindromic substring within this string. In cases where multiple palind...read more
Ans. 
Identify the longest palindromic substring in a given string.
• Iterate through the string and expand around each character to find palindromes

• Keep track of the longest palindrome found

• Return the longest palindrome with the smallest start index
Answered by AI
Add your answer

Round duration - 45 Minutes
Round difficulty - Hard

Interviewer was an Indian employee.

Q1. 
Alien Dictionary Problem Statement
You are provided with a sorted dictionary (by lexical order) in an alien language. Your task is to determine the character order of the alien language from this dictiona...read more
Ans. 
Given a sorted alien dictionary in an array of strings, determine the character order of the alien language.
• Iterate through the words in the dictionary to build a graph of character dependencies.

• Perform a topological sort on the graph to determine the character order.

• Return the character order as a list of characters.
Answered by AI
Add your answer

Round duration - 45 Minutes
Round difficulty - Hard

Interviewer was an Indian employee. 

Q1. 
Problem: Ninja's Robot
The Ninja has a robot which navigates an infinite number line starting at position 0 with an initial speed of +1. The robot follows a set of instructions which includes ‘A’ (Acceler...read more
Ans. 
Determine the minimum length of instruction sequence for a robot to reach a given target on an infinite number line.
• Start at position 0 with speed +1, update position and speed based on 'A' and 'R' instructions

• For each test case, find the shortest sequence of instructions to reach the target

• Consider both positive and negative positions for the robot
Answered by AI
Add your answer

Round duration - 120 Minutes
Round difficulty - Easy

The round was conducted in day around 3PM.

Q1. 
Partition Equal Subset Sum Problem
Given an array ARR consisting of 'N' positive integers, determine if it is possible to partition the array into two subsets such that the sum of the elements in both sub...read more
Ans. 
The problem is to determine if it is possible to partition an array into two subsets with equal sum.
• Use dynamic programming to solve this problem efficiently.

• Create a 2D array to store the results of subproblems.

• Check if the sum of the array is even before attempting to partition it.

• Iterate through the array and update the 2D array based on the sum of subsets.

• Return true if a subset with half the sum is found, false ot...read more
Answered by AI
Add your answer

Round duration - 30 Minutes
Round difficulty - Easy

The interview was preponed and was conducted at 9AM.
The interviewer was friendly and I had saw him earlier at pre-placement talk.

Q1. 
Convert Sentence to Pascal Case
Given a string STR, your task is to remove spaces from STR and convert it to Pascal case format. The function should return the modified STR.
In Pascal case, words are con...read more
Ans. 
Convert a given string to Pascal case format by removing spaces and capitalizing the first letter of each word.
• Iterate through each character in the string

• If the character is a space, skip it

• If the character is not a space and the previous character is a space or it is the first character, capitalize it
Answered by AI
Add your answer
Q2. Write an SQL query to retrieve the Nth highest salary from a database.
Ans. 
SQL query to retrieve the Nth highest salary from a database
• Use the ORDER BY clause to sort salaries in descending order

• Use the LIMIT clause to retrieve the Nth highest salary

• Consider handling cases where there might be ties for the Nth highest salary
Answered by AI
Add your answer

Round duration - 30 Minutes
Round difficulty - Easy

This round was conducted 15mins after 1st round.

Q1. 
Remove the Kth Node from the End of a Linked List
You are given a singly Linked List with 'N' nodes containing integer data and an integer 'K'. Your task is to delete the Kth node from the end of this Lin...read more
Ans. 
Remove the Kth node from the end of a singly linked list.
• Traverse the list to find the length 'N'.

• Calculate the position of the node to be removed from the beginning as 'N - K + 1'.

• Remove the node at the calculated position.

• Handle edge cases like removing the head or tail of the list.

• Update the pointers accordingly after removal.
Answered by AI
Add your answer