60+ Microsoft Corporation Software Developer Interview Questions and Answers for Freshers

Given an array representing number of buses at each bus stop, determine how many buses originate from each stop.

• Iterate through the array and for each element, increment the count of buses originating from the corresponding bus stop.

• Use an array to store the count of buses originating from each stop.

• Remember to consider the constraint of 1-based indexing for bus stops.

The Ninja must collect fruits from trees in consecutive order, maximizing the number of fruits in two baskets.

• Iterate through the trees while keeping track of the types of fruits collected in each basket.

• Use a sliding window approach to find the maximum number of fruits collected.

• Keep track of the count of each fruit type encountered to handle the condition of only two types of fruits in each basket.

Check if one string can be transformed into another by cyclically rotating it to the right.

• Iterate through all possible rotations of string P and check if any of them match string Q.

• Use string concatenation to simulate cyclic rotations efficiently.

• Compare the rotated strings with string Q to determine if they are equivalent.

Design a data structure supporting insert, delete, search, and getRandom operations in constant time.

• Use a combination of hashmap and array to achieve O(1) time complexity for all operations.

• For insert operation, check if element exists in hashmap, if not add to array and hashmap.

• For remove operation, check if element exists in hashmap, if yes, remove from array and hashmap.

• For search operation, check if element exists in hashmap.

• For getRandom operation, generate a random ind...read more

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

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

• Sort the array to easily identify duplicates and skip unnecessary calculations.

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

Given an array of strings, determine the number of unique strings that cannot be transformed into another string by swapping characters at odd or even indices.

• Iterate through each string in the array and check if it can be transformed into another string by swapping characters at odd or even indices.

• Keep track of unique strings that cannot be transformed and return the count.

• Example: For array = ["abcd", "cbad", "bdac", "adcb"], the output is 2 as only "bdac" is unique.

Find the Kth largest element in an array of distinct positive integers.

• Sort the array in non-increasing order and return the Kth element.

• Use a sorting algorithm like quicksort or heapsort for efficiency.

• Ensure the array contains distinct positive integers for accurate results.

Calculate the total sum of all root to leaf paths in an arbitrary binary tree.

• Traverse the tree in a depth-first manner to calculate the sum of each root to leaf path.

• Keep track of the current path sum and update it as you traverse the tree.

• Return the total sum modulo (10^9 + 7) as the final result.

Identify the celebrity at a party where one person knows everyone but is not known by anyone.

• Use a two-pointer approach to eliminate non-celebrity candidates.

• Start with two pointers at the beginning and end of the party.

• If A knows B, A cannot be the celebrity; move A to the right.

• If A does not know B, B cannot be the celebrity; move B to the left.

• Repeat until only one person remains, check if this person is known by everyone.

• Return the ID of the celebrity or -1 if none exists...read more

Find the length of the longest mountain subarray in an array of integers.

• Iterate through the array to find peaks.

• Expand from peaks to find ascending and descending slopes.

• Track the length of the mountain subarray and return the maximum length.

Determine maximum profit from buying and selling stocks on different days.

• Iterate through the array of stock prices and calculate the profit for each pair of days.

• Keep track of the maximum profit obtained by selling and buying stocks on different days.

• Return the maximum profit achieved.

Given a string of digits, find all potential valid IP addresses that can be formed from it.

• Split the string into four parts and check if each part is a valid IP segment (0-255).

• Use backtracking to generate all possible combinations of valid IP addresses.

• Ensure that the IP address does not contain leading zeroes.

• Return the valid IP addresses in lexicographical order.

The task is to determine the number of possible ways to roll all the dice such that the sum of the face-up numbers equals the given 'target' sum.

• Use dynamic programming to solve the problem efficiently.

• Create a 2D array to store the number of ways to achieve each sum with the given number of dice.

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

• Return the result modulo 10^9 + 7.

• Optimize the solution to use no more than O(S) extra space by u...read more

Group anagrams in an array of strings based on character frequency.

• Iterate through each string in the input array

• For each string, sort the characters and use the sorted string as a key in a hashmap to group anagrams

• Return the grouped anagrams as arrays of strings

The problem involves finding the minimum cost path in a matrix by moving right, down, or diagonally down-right.

• Use dynamic programming to keep track of the minimum cost at each cell

• Consider the three possible directions for movement and calculate the cost accordingly

• Start from the top-left cell and iterate through the matrix to find the minimum cost path

Convert a Binary Search Tree to a sorted Doubly Linked List efficiently.

• Implement a function to convert a BST to a sorted DLL.

• Use in-order traversal to efficiently convert the BST to DLL.

• Maintain pointers for the head and tail of the DLL.

• Ensure the left child of a node becomes the previous node and the right child becomes the next node in the DLL.

Calculate the time in minutes required to completely burn a binary tree starting from a given node.

• Perform a depth-first search (DFS) to calculate the time taken to burn the entire tree.

• Track the time taken for each node to catch fire and burn the tree accordingly.

• Consider the adjacency of nodes to determine the spread of fire.

• Handle cases where the start node is at different levels in the tree.

• Optimize the solution to handle large binary trees efficiently.

Implement Merge Sort algorithm to sort a given sequence of numbers in non-descending order.

• Divide the input array into two halves recursively until each array has only one element.

• Merge the sorted halves to produce a completely sorted array.

• Time complexity of Merge Sort is O(n log n).

Convert a binary tree into a sum tree by replacing each node with the sum of its children's values, and return the preorder traversal.

• Traverse the tree recursively and replace each node with the sum of its children's values

• Leaf nodes should be replaced with 0

• Perform a preorder traversal on the transformed sum tree to get the final result

Generate all possible binary strings by replacing '?' with '0' or '1'.

• Iterate through the input string and replace '?' with '0' and '1' recursively to generate all possible strings.

• Use backtracking to explore all possible combinations.

• Sort the generated strings lexicographically before returning the final result.

Convert a binary tree into a linked list following pre-order traversal order.

• Perform pre-order traversal of the binary tree and convert it into a linked list.

• Use the right pointer of the binary tree as the 'next' pointer for the linked list.

• Set the left pointer to NULL for each node in the linked list.

• Example: Input - 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1, Output - 1 2 4 7 3 5 6

Determine maximum profit from at most 2 stock transactions over 'N' days.

• Iterate through the prices array to find the maximum profit from 2 transactions.

• Keep track of the maximum profit by buying and selling stocks at the right times.

• Consider edge cases like when there are no profitable transactions.

Calculate the total number of stories a ninja can hear from a storyteller based on given conditions and constraints.

• Calculate the number of stories Ninja can buy with available coins and without free stories.

• Calculate the number of free stories Ninja can get based on the number of stories bought.

• Add the total number of bought and free stories to get the final result.

Design a 2-player Tic-Tac-Toe game on an N x N grid where players take turns placing their marks, and the first player to get N marks in a row wins.

• Implement a function move(row, col, player) to handle each player's move and check for a win condition.

• Keep track of the board state and update it after each move.

• Check for winning conditions horizontally, vertically, and diagonally after each move.

• Return the result (0 for no win, 1 for Player 1 win, 2 for Player 2 win) after each...read more

Find the position of the lone '1' bit in the binary representation of a given non-negative integer.

• Iterate through the bits of the integer to find the position of the lone '1'.

• Use bitwise operations to check if there is exactly one '1' bit in the binary representation.

• Return the position of the lone '1' or -1 if there isn't exactly one '1'.

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.

Find and return the Gray code sequence for a given number.

• Generate Gray code sequence by following the conditions provided in the problem statement.

• Ensure that consecutive numbers in the sequence differ by exactly 1 bit.

• Start the sequence with 0 and include numbers up to 2^grayNumber - 1.

• Return the sequence in decimal form as a list/vector.

• If multiple valid sequences exist, return any of them.

Count the number of squares in a given matrix modulo 10^9 + 7.

• Iterate through all possible square sizes from 1 to min(N, M)

• For each square size, count the number of squares that can fit in the matrix

• Return the total count modulo 10^9 + 7

The task is to return the spiral path of elements in a given matrix.

• Iterate over the matrix in a spiral path by keeping track of the boundaries.

• Print the elements in the spiral path as you traverse the matrix.

• Handle cases where the matrix is not a square matrix separately.

Given an amount and coin denominations, find the smallest no of coins to form the amount.

• Use dynamic programming to solve the problem

• Create a table to store the minimum number of coins required for each amount

• Iterate through the denominations and update the table accordingly

• Return the minimum number of coins required for the given amount

Find the length of the longest duplicate substring in a given string.

• Use binary search to find the length of the longest duplicate substring.

• Implement Rabin-Karp algorithm for efficient substring search.

• Consider using a rolling hash function for substring comparisons.

Count the number of inversions in an array of distinct positive integers.

• Use merge sort algorithm to count inversions efficiently.

• Divide the array into two halves and recursively count inversions in each half.

• Merge the two sorted halves while counting split inversions.

• Time complexity can be optimized to O(n log n) using merge sort.

• Example: For input A = [2, 4, 1, 3, 5], the output should be 3.

Find the K-th smallest element in an array of distinct integers.

• Sort the array and return the element at index K-1.

• Use a min-heap to find the K-th smallest element efficiently.

• Implement quickselect algorithm for optimal performance.

Given a graph with vertices and edges, determine if it can be colored using two colors without adjacent vertices sharing the same color.

• Check if the graph is bipartite using graph coloring algorithm like BFS or DFS.

• If the graph is bipartite, return 'Possible' with a valid coloring assignment.

• If the graph is not bipartite, return 'Impossible'.

Write a program to compress a string by replacing consecutive duplicate characters with the character followed by the number of repetitions.

• Iterate through the string and count consecutive occurrences of each character

• Append the character and its count to a new string

• Return the compressed string if it is shorter than the original, else return the original string

• Handle edge cases like single characters or when compressed string is longer than original

Given a non-negative integer as a string and an integer k, find the smallest possible integer after removing k digits.

• Use a stack to keep track of the digits in non-decreasing order from left to right.

• Pop elements from the stack if the current digit is smaller than the top of the stack and k is greater than 0.

• Handle edge cases like leading zeros and ensuring the final result is not an empty string.

• Example: For num = "1432219" and k = 3, the smallest possible integer after rem...read more

Calculate and print the median after each new integer is added to the stream.

• Use two heaps - a max heap to store the smaller half of the numbers and a min heap to store the larger half.

• Keep the sizes of the two heaps balanced to efficiently calculate the median.

• If the total number of elements is odd, the median will be the top element of the max heap.

• If the total number of elements is even, the median will be the average of the top elements of the max and min heaps.

Code a run length encoding algorithm to compress a text string in place.

• Use a loop to iterate through the string and count consecutive characters

• Create a new string to store the compressed version of the original string

• Add the character and its count to the new string

• Compare the length of the new string to the original string to determine if compression was successful

The function ring() calculates the number of blocks of both types based on sensor state changes.

• Create a variable to keep track of the number of 49 cm blocks

• Create another variable to keep track of the number of 50 cm blocks

• Initialize both variables to 0

• Whenever the sensor changes state, increment the corresponding block variable

• Return the count of both block types as an array of strings

Compress a string by replacing consecutive characters with their count.

• Iterate through the string and count consecutive characters.

• Append the character and its count to a new string.

• Handle edge cases like single characters.

The question asks to add two numbers represented as linked lists and return the sum as a linked list.

• Traverse both linked lists simultaneously, adding the corresponding digits and carrying over the carry.

• Create a new linked list to store the sum digits.

• Handle cases where one linked list is longer than the other.

• Consider cases where the sum has an additional carry digit at the end.

The code inserts a given string at the specified position in a compact data structure that stores strings sequentially.

• To insert the string at the ith place, we need to shift all the strings after the ith position by the length of the new string.

• We can use a loop to iterate through the data structure and find the ith position.

• After finding the ith position, we can calculate the new length of the data structure and allocate memory accordingly.

• We then shift all the strings afte...read more

Merge 'n' identical linked lists from 'n' salespersons to handle insertions, deletions, and updates.

• Iterate through each linked list and merge them into a single linked list

• Handle insertions, deletions, and updates by traversing the merged list and making necessary changes

• Repeat the process for the next day by resetting the merged list

ACID properties in DBMS ensure data integrity and consistency.

• Atomicity: All transactions are either fully completed or fully aborted. For example, transferring money from one account to another should be completed in its entirety.

• Consistency: The database remains in a consistent state before and after the transaction. For example, if a constraint is violated during a transaction, the transaction will be rolled back.

• Isolation: Transactions are isolated from each other until t...read more

There can be multiple such elements in the matrix.

• Multiple elements can be max in their row and min in their col

• The function should return all such elements

• The elements can be in different rows and columns

Memory management in operating systems involves allocation, deallocation, and optimization of memory usage.

• Memory allocation: OS allocates memory to processes based on their requirements.

• Memory deallocation: OS frees up memory when it is no longer needed by a process.

• Memory optimization: OS optimizes memory usage through techniques like paging, segmentation, and virtual memory.

• Examples: Paging in which memory is divided into fixed-size blocks and virtual memory which allows p...read more

Demonstrate communication between two processes using inter-process communication (IPC) methods.

• Use sockets for communication between two processes running on the same or different machines.

• Implement message passing using shared memory or message queues.

• Utilize pipes for communication between parent and child processes.

Constructing parse tree for ((a+b)*c)/d using data structures.

• Use stack data structure to keep track of operators and operands.

• Start with the innermost parentheses and work outwards.

• Create a node for each operator and operand and link them together.

• The root node will be the final result of the expression.

• Example: ((a+b)*c)/d can be represented as / -> * -> + -> a, b, c, d.

The given linked list needs to be inverted in pairs of two nodes.

• Iterate through the linked list, swapping every two adjacent nodes.

• Keep track of the previous node to update the next pointers correctly.

• Handle the edge cases of odd number of nodes or empty list.

Prove that given 5 points in a plane, there will be at least two points such that their midpoint is an integer.

• Consider the x and y coordinates of the 5 points.

• If any two points have the same x and y coordinates, their midpoint will be an integer.

• If not, consider the differences between the x and y coordinates of each pair of points.

• If any two pairs have differences that are both even or both odd, their midpoints will be integers.

• By the Pigeonhole Principle, there must be at ...read more

Insert an element into a sorted circular linked list.

• Find the correct position to insert the element based on its value

• Update the pointers of the previous and next nodes to include the new node

• Handle special cases such as inserting at the beginning or end of the list

• Example: Inserting 5 into a list with values 1, 3, 4, 6, 7 would result in 1, 3, 4, 5, 6, 7

Find the leftmost node in the same level as a given node in a binary tree.

• Traverse the tree level by level using BFS

• For each level, keep track of the leftmost node encountered

• Return the leftmost node at the same level as the given node

Count total palindromic substrings in a given string.

• Iterate through each character in the string and consider it as the center of a palindrome. Expand outwards to find all palindromic substrings.

• Use dynamic programming to efficiently check if a substring is a palindrome.

• Consider both odd-length and even-length palindromes.

• Example: Input 'ababa', output 7 (a, b, a, b, a, aba, aba)

Use exponentiation by squaring algorithm to find nth power of a number in shortest computational time.

• Use recursion to divide the power by 2 and multiply the base accordingly

• If power is odd, multiply the base with the result of recursive call

• If power is negative, take reciprocal of base and make power positive

• Handle edge cases like power=0 and base=0 or 1

• Time complexity is O(log n)

Count the number of times a substring appears in a string.

• Use a loop to iterate through the string and check for the substring at each index.

• Use the count() method to count the number of occurrences of the substring.

• Consider using regular expressions to find all occurrences of the substring.

• Handle edge cases such as empty strings or substrings.

Print the leftmost node at the same level as a given node in a binary search tree.

• Traverse the tree level by level using BFS

• Keep track of the leftmost node at each level

• Return the leftmost node at the level of the given node

• If the given node is not found, return null

Search for an element in a rotated sorted array in sublinear time.

• Use binary search to find the pivot point where the array is rotated.

• Determine which half of the array the target element is in.

• Perform binary search on the appropriate half of the array to find the target element.

• Time complexity is O(log n).

Find the leftmost node in the same level as a given node in a binary tree.

• Traverse the tree level by level using BFS

• For each level, keep track of the leftmost node encountered

• Return the leftmost node in the level of the given node

Find the nth largest number in a binary tree

• Traverse the tree in-order and store the values in an array

• Return the (n-1)th index of the sorted array in descending order

• Use a max heap to keep track of the largest n elements