Microsoft Corporation Interview Questions, Process, and Tips

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.

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.

The task is to compress a given string by replacing consecutive repeated characters with the character followed by the count of repetitions.

• Iterate through the string and keep track of the current character and its count.

• If the next character is the same as the current character, increment the count.

• If the next character is different, append the current character and its count to the result string.

• Return the compressed

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

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

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

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

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.

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

Function to check if min^2 < max condition is satisfied in an array of strings

• Convert array elements to integers

• Find the minimum and maximum values in the array

• Check if min^2 < max, return 1 if true, 0 if false

The number of delfirst() operations needed to satisfy a condition in an array.

• The number of delfirst() operations needed is equal to the index of the first element that satisfies the condition.

• For example, if the array is ['apple', 'banana', 'cherry'] and the condition is to have the first element start with 'b', then 1 delfirst() operation is needed to get ['banana', 'cherry'].

To satisfy the condition 1, only one operation is needed - either delfirst() or dellast().

• To satisfy the condition 1, you can either use delfirst() or dellast() operation once.

• For example, if the array is ['a', 'b', 'c', 'd'], you can use delfirst() operation to get ['b', 'c', 'd'] or dellast() operation to get ['a', 'b', 'c'].

Sort a large int array in the range 1-10.

• Use counting sort algorithm for efficient sorting.

• Create a count array to store the frequency of each number.

• Iterate through the count array to reconstruct the sorted array.

Given multiple rectangles on a screen, find the smallest rectangle enclosing a user-clicked point.

• Iterate through each rectangle and check if the clicked point lies within its boundaries

• Keep track of the smallest enclosing rectangle found so far

• Return the smallest enclosing rectangle

The poke feature in Facebook allows users to send a quick and playful gesture to get someone's attention.

• Users can poke their friends to say hello or get their attention.

• Poking someone sends them a notification.

• Pokes can be sent back and forth between friends.

• Pokes can be used as a fun way to interact with friends without sending a message.

Merge N large files containing operations sorted by name for an address book

• Read each file and merge the operations based on name

• Use a sorting algorithm to maintain the order while merging

• Handle duplicate operations for the same name

• Consider memory constraints while merging large files

Common in 2 threads: share same memory space, variables, code, and resources. Difference: have separate execution paths and stack.

• Common: share same memory space, variables, code, and resources

• Difference: have separate execution paths and stack

• Example: Two threads in a process sharing access to a global variable

Communication between 2 processes can be achieved through inter-process communication mechanisms.

• Use pipes to establish a unidirectional communication channel between processes

• Use sockets for bidirectional communication over a network

• Shared memory can be used to exchange data between processes

• Message queues provide a way to send and receive messages between processes

• Signals can be used to notify and communicate between

Check if 4 selected boxes in a 2-D array of chars are continuous in the 3x3 sub array surrounding each box.

• Iterate through the selected boxes and check if they are within the 3x3 sub array of each box.

• Consider edge cases where the selected boxes are at the boundaries of the array.

• Example: If the selected boxes are (1,1), (1,2), (2,1), (2,2), they form a continuous 2x2 sub array.