Microsoft Corporation Software Developer Interview Questions, Process, and Tips

Add two numbers stored in linked lists and return the sum in a linked list.

• Traverse both linked lists and add the digits at each node while keeping track of carry.

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

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

• Handle cases where the sum of the last digits results in a carry.

• Return the new linked list with the sum digits.

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.

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.

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

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

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 the same differences, their midpoints will be integers.

• Otherwise,...read more

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)

Function to calculate number of 49cm and 50cm wood blocks using two sensors 50cm apart.

• Create a variable to store the count of 49cm blocks and another for 50cm blocks

• Use a loop to continuously check the state of the sensors and increment the respective block count

• Call the ring() function whenever the state of the sensors change

• Return the count of both types of blocks

Invert every two nodes in a linked list.

• Create a temporary node to store the next node

• Swap the positions of the current and next nodes

• Set the current node's next to the temporary node

• Move to the next pair of nodes and repeat until end of list

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 allo...read more

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.

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