60+ Microsoft Corporation Software Developer Intern Interview Questions and Answers

Implement functions to calculate mean, median, and mode of an array of integers.

• Implement a function mean() to calculate the mean of the array by summing all elements and dividing by the total count.

• Implement a function median() to calculate the median of the array by sorting the array and finding the middle element(s).

• Implement a function mode() to find the mode of the array by counting frequencies and returning the smallest element with the highest frequency.

The problem involves finding the number of ways to achieve a target sum by rolling a given number of dice with a certain number of faces.

• Use dynamic programming to keep track of the number of ways to achieve each sum from 1 to the target sum.

• Iterate through the dice and faces to update the number of ways to reach each sum.

• Return the number of ways to achieve the target sum modulo 10^9 + 7.

Calculate the Nth term of a geometric progression series given the first term, common ratio, and term number.

• Use the formula for the Nth term of a GP series: A * (R^(N-1))

• Ensure to take the modulo 10^9 + 7 as the output

• Handle multiple test cases efficiently within the given time limit

Evaluate arithmetic expressions in infix notation with given operators and precedence rules.

• Parse the infix expression to postfix using a stack.

• Evaluate the postfix expression using a stack.

• Handle operators precedence and parentheses while evaluating.

• Ensure no division by zero cases and operands fit in 32-bit integer.

Compute the count of distinct subsequences of a string with possible duplicates.

• Use dynamic programming to keep track of distinct subsequences.

• Consider the cases where the current character is included or excluded in the subsequence.

• Use a hashmap to store the last occurrence index of each character to handle duplicates efficiently.

To delete the Kth node from the end of a singly linked list efficiently without finding the length of the list and using O(1) extra space.

• Use two pointers approach - one pointer moves K steps ahead of the other.

• When the first pointer reaches the end, the second pointer will be at the Kth node from the end.

• Adjust the pointers to remove the Kth node efficiently.

• Ensure to handle edge cases like deleting the head or tail node.

• Example: For input 1 -> 2 -> 3 -> 4 -> NULL and K = 2,...read more

Check if two binary trees are identical by comparing their nodes in level order.

• Traverse both trees in level order and compare corresponding nodes for equality

• Use a queue to keep track of nodes to be compared

• Return false if nodes are not equal or if one tree has more nodes than the other

Rotate a square matrix by 90 degrees in an anti-clockwise direction using constant extra space.

• Iterate through each layer of the matrix from outer to inner layers

• Swap elements in groups of 4 to rotate the matrix

• Handle odd-sized matrices separately by adjusting the loop boundaries

Calculate minimum left shift operations to achieve longest common prefix between two strings.

• Apply left shift operations to string B to find longest common prefix with string A

• Count number of shifts needed to achieve longest common prefix

• Handle circular rotation of characters in string B

• Return minimum number of left shift operations for each test case

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.

Connect adjacent nodes at the same level in a binary tree by populating each node's 'next' pointer.

• Traverse the tree level by level using a queue.

• For each level, connect nodes from left to right using their 'next' pointers.

• Set the 'next' pointer of the rightmost node in each level to NULL.

• Example: For the given binary tree, connect nodes 2->3, 4->5, 5->6, and set 1, 3, 6 'next' pointers to NULL.

The problem involves finding the length of the longest palindromic subsequence in a given string of lowercase English letters.

• Iterate through the string and create a 2D array to store the lengths of palindromic subsequences for each substring.

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

• Consider the base cases where the length of the substring is 1 or 2.

• Update the array based on whether the characters at the start and end of the substring ma...read more

Identify and list nodes in a Binary Tree that do not have a sibling.

• Traverse the Binary Tree in level order and keep track of nodes without siblings.

• Check if each node has a sibling by comparing with its parent's other child.

• Output the values of nodes without siblings in ascending order.

• Handle cases where the root node is considered a sibling node.

Determine minimum operations to make all array elements equal using addition, subtraction, multiplication, or division.

• Iterate through array to find the maximum and minimum elements.

• Calculate the difference between maximum and minimum elements.

• The minimum number of operations needed is the difference between the maximum and minimum elements.

Find the median of two sorted arrays by merging them and calculating the middle element(s).

• Merge the two sorted arrays into one sorted array.

• Calculate the median based on the total number of elements in the merged array.

• If the total number of elements is even, take the mean of the two middle elements as the median.

The task is to determine the number of islands in a grid of 0s and 1s connected horizontally, vertically, or diagonally.

• Iterate through the grid and perform depth-first search (DFS) to find connected 1s forming islands

• Mark visited cells to avoid counting the same island multiple times

• Count the number of islands found during DFS traversal

The N Queens Problem involves finding all possible placements of N queens on an N x N chessboard without threatening each other.

• Use backtracking algorithm to explore all possible configurations

• Check if the current placement is safe by verifying rows, columns, and diagonals

• Print valid configurations where queens do not attack each other

Find pairs of elements in an array that sum up to a given value, sorted in a specific order.

• Iterate through the array and for each element, check if the complement (S - current element) exists in a set.

• If the complement exists, add the pair to the result list.

• Sort the result list based on the criteria mentioned in the problem statement.

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.

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 city 0 for the first test case.

• Example: Start at city 0, visi...read more

Determine the minimum number of platforms needed at a railway station so that no train has to wait.

• Sort the arrival and departure times arrays in ascending order.

• Use two pointers to iterate through the arrays and keep track of the number of platforms needed.

• Increment the number of platforms needed when a train arrives and decrement when a train departs.

• Return the maximum number of platforms needed at any point.

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'.

Find the contiguous subarray with the maximum product of elements in an array.

• Iterate through the array and keep track of the maximum and minimum product ending at each index.

• Update the maximum product by taking the maximum of current element, current element * previous maximum, and current element * previous minimum.

• Update the minimum product by taking the minimum of current element, current element * previous maximum, and current element * previous minimum.

• Return the maximu...read more

Given coefficients of a quadratic equation, find the real roots or return -1 if no real roots exist.

• Calculate the discriminant (B^2 - 4AC) to determine the nature of roots.

• If discriminant is positive, roots are real and distinct. If zero, roots are real and repeated. If negative, roots are imaginary.

• Use the quadratic formula to find the roots: (-B ± sqrt(discriminant)) / 2A.

• Return the roots as integers, rounding down if necessary.

Find the Lowest Common Ancestor of two nodes in a binary tree.

• Traverse the binary tree to find the paths from the root to nodes X and Y.

• Compare the paths to find the last common node, which is the LCA.

• Handle cases where one node is an ancestor of the other.

• Consider using recursion to solve the problem efficiently.

Given a string of digits from 2 to 9, determine all possible strings that can be generated using T9 keypad letter mappings.

• Create a mapping of digits to corresponding letters on a T9 keypad

• Use recursion to generate all possible combinations of letters for the input string

• Sort the generated strings lexicographically

• Return the array of generated strings

Find the largest common ancestor of two nodes in a binary search tree.

• Implement a function to find the largest common ancestor of two nodes in a binary search tree.

• Use level order traversal input to construct the tree.

• Ensure both nodes are present in the tree.

• Return the value of the largest common ancestor.

The task is to find the total number of ways to make change for a specified value using given denominations.

• Use dynamic programming to solve this problem efficiently.

• Create a 2D array to store the number of ways to make change for each value up to the specified value.

• Iterate through each denomination and update the array accordingly.

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

Validate if a given binary tree is a Binary Search Tree (BST) or not.

• Check if the left subtree of a node contains only nodes with data less than the node's data.

• Check if the right subtree of a node contains only nodes with data greater than the node's data.

• Ensure that both the left and right subtrees are also binary search trees.

Find the number of distinct pairs of participants with a given difference in their chosen numbers.

• Iterate through the list of numbers and check for pairs with the required difference 'K'.

• Use a hash set to keep track of unique pairs to avoid counting duplicates.

• Return the size of the hash set as the number of distinct pairs.

Given a string, find the longest palindromic substring, prioritizing the one with the smallest start index.

• Iterate through the string and expand around each character to find palindromes

• Keep track of the longest palindrome found and its starting index

• Return the longest palindromic substring with the smallest start index

Find the smallest substring in a given string that contains all characters from another given string.

• Use a sliding window approach to find the smallest window in S that contains all characters in X.

• Maintain a frequency map for characters in X and a window map for characters in the current window.

• Slide the window to the right, updating the window map and shrinking the window from the left if all characters in X are present.

• Keep track of the smallest window found so far.

• Return ...read more

Given an encrypted string with repeated substrings represented by counts, find the K'th character of the decrypted string.

• Parse the encrypted string to extract substrings and their counts

• Iterate through the decrypted string to find the K'th character

• Handle cases where counts are more than one digit or in parts

Find the sum of the subarray with the maximum sum among all subarrays in an array of integers.

• Iterate through the array and keep track of the maximum sum subarray seen so far.

• Use Kadane's algorithm to efficiently find the maximum subarray sum.

• Consider the case where all elements in the array are negative.

• Handle the case where the array contains only one element.

Calculate the total area covered by two overlapping rectangles on a 2-D coordinate plane.

• Parse input coordinates for two rectangles

• Calculate the area of each rectangle

• Find the overlapping area by determining the intersection of the rectangles

• Calculate the total area by adding the areas of both rectangles and subtracting the overlapping area

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.

Swap two numbers without using a temporary variable.

• Use bitwise XOR operation to swap the values of X and Y without using a temporary variable.

• The XOR operation works by flipping the bits of the numbers.

• After swapping, X = X XOR Y and Y = X XOR Y.

• Finally, X = X XOR Y to get the original value of Y in X.

Calculate minimum steps for a Knight to reach target position on a chessboard.

• Use BFS algorithm to find shortest path from Knight's starting position to target position.

• Consider all possible moves of the Knight on the chessboard.

• Track visited positions to avoid revisiting them during traversal.

Convert infix expression to postfix expression.

• Use a stack to keep track of operators and operands.

• Follow the rules of precedence for operators.

• Handle parentheses to ensure correct order of operations.

Find the most frequent and lexicographically smallest word in string 'A' that is not present in string 'B'.

• Split strings 'A' and 'B' into words

• Count frequency of each word in 'A'

• Check if word is not in 'B' and is the most frequent and lexicographically smallest

• Return the word or -1 if no such word exists

Find the minimum length subarray with sum greater than X in a given array.

• Iterate through the array while maintaining a sliding window to find the subarray with sum greater than X.

• Keep track of the minimum length subarray found so far.

• Return the subarray with the minimum length and sum greater than X.

Given a string, partition it into palindromic substrings and return all possible partitions.

• Use backtracking to generate all possible partitions by checking if each substring is a palindrome.

• Keep track of the current partition and add it to the result when the entire string is processed.

• Optimize by using memoization to store the results of subproblems to avoid redundant calculations.

Flatten a multi-level linked list into a single-level linked list and return the head of the singly linked list.

• Traverse the multi-level linked list using depth-first search (DFS).

• Maintain a stack to keep track of nodes with child pointers.

• Connect the child nodes to the current node's next pointer and update the current node.

• Continue this process until all nodes are flattened into a single-level linked list.

Sort an array of 0s, 1s, and 2s in increasing order.

• Use a three-pointer approach to partition the array into sections for 0s, 1s, and 2s.

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

• After sorting, the array will have 0s at the beginning, followed by 1s, and then 2s.

Design a Least Recently Used (LRU) cache data structure that supports get and put operations with capacity constraint.

• Implement a doubly linked list to maintain the order of keys based on their recent usage.

• Use a hashmap to store key-value pairs for quick access and update.

• When capacity is reached, evict the least recently used item before inserting a new item.

• Update the order of keys in the linked list whenever a key is accessed or updated.

• Handle get and put operations effic...read more

Reverse a given stack of integers using recursion without using extra space or loops.

• Use recursion to pop all elements from the original stack and store them in function call stack.

• Once the stack is empty, push the elements back in reverse order using recursion.

• Make use of the top(), pop(), and push() stack methods provided.

• Example: If the input stack is [1, 2, 3], after reversal it should be [3, 2, 1].

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 maintains the binary search tree properties after insertion.

Compute the division of two integers and output the result formatted to contain exactly N decimal places.

• Read the input values for X, Y, and N

• Perform the division X / Y

• Format the result to contain exactly N decimal places

• Output the result as a string with N decimal places

Find all distinct triplets in an array that sum up to zero.

• Use a nested loop to iterate through all possible triplets.

• Sort the array to easily identify duplicates and skip them.

• Use two-pointer technique to find the remaining element for each pair.

• Handle edge cases like duplicates and empty list of triplets.

• Return the list of triplets found in any order.

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.

Calculate the smallest angle between the hour and minute hands of a clock given a specific time.

• Calculate the angle formed by the hour hand with respect to 12 o'clock position

• Calculate the angle formed by the minute hand with respect to 12 o'clock position

• Find the absolute difference between the two angles and take the minimum of the two possible angles

• Return the floor value of the calculated angle

Determine the minimum number of operations needed to transform one string into another by moving characters to the end.

• Iterate through each character in str1 and check if it matches the first character in str2.

• If a match is found, calculate the number of operations needed to move the characters to the end.

• Return the minimum number of operations needed for each test case, or -1 if transformation is not possible.

Implement a function to find diagonal paths in a binary tree.

• Traverse the binary tree in a diagonal manner, starting from the rightmost path and moving downwards.

• Use a hashmap to store nodes at each diagonal level and then traverse the hashmap to get the diagonal paths.

• Handle the case where nodes without left or right children are present by using -1.

• Return the diagonal traversal as a single line with nodes arranged by their diagonal paths.

Find the number of BSTs possible with each element of an array as the root node.

• Iterate through each element of the array and calculate the number of BSTs possible with that element as the root node.

• Use dynamic programming to calculate the number of BSTs for each element efficiently.

• Output the results modulo (10^9 + 7) to handle large numbers.

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.

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

Given a string with wildcard characters, determine if it can be transformed to match another string.

• Iterate through both strings simultaneously, handling wildcard characters '?' and '*' accordingly.

• Use dynamic programming to keep track of matching characters.

• Handle cases where '*' can match an empty sequence or multiple characters.

• Return true if at the end both strings match, false otherwise.

Reverse a singly linked list of integers and return the head of the reversed linked list.

• Iterate through the linked list and reverse the pointers to point to the previous node instead of the next node.

• Keep track of the previous, current, and next nodes while reversing the linked list.

• Update the head of the reversed linked list to be the last node encountered.

• Ensure to handle edge cases like an empty linked list or a linked list with only one node.

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 parentheses have been matched, the string is balanced.

• If the ...read more

Optimal strategy to minimize number of drops to find highest floor an egg can be dropped without breaking.

• Start by dropping the first egg from a lower floor and incrementally increase the floor until it breaks.

• Once the first egg breaks, use the second egg to perform a binary search between the last successful drop and the floor below the breaking point.

• This strategy ensures the minimum number of drops required to find the highest floor.

Mutexes and semaphores are synchronization mechanisms used in concurrent programming to control access to shared resources.

• Mutexes are used to provide mutual exclusion, allowing only one thread to access a resource at a time.

• Semaphores can be used to control access to a resource by multiple threads, with the ability to allow a certain number of threads to access it simultaneously.

• Mutexes are binary semaphores with a lock and unlock mechanism.

• Semaphores can have a count greate...read more

Design an elevator system for a single building with N floors.

• Create a data structure to track the current floor of the elevator and the requested floors.

• Implement algorithms for elevator movement such as FIFO, SCAN, or LOOK.

• Consider factors like peak hours, weight capacity, and emergency situations.

• Include features like door open/close buttons, emergency stop button, and floor selection panel.

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

The minimum number of operations required to set all elements of a binary matrix to 0 or 1.

• Count the number of 0s and 1s in each row and column separately.

• For each row and column, choose the minimum between the count of 0s and 1s as the number of operations needed.

• Sum up the minimum operations for all rows and columns to get the total minimum operations.

Print all permutations of a string

• Use recursion to swap each character with every other character in the string

• Repeat the process for the remaining characters

• Stop when there are no more characters to swap

• Use a set to avoid duplicates