Microsoft Corporation Interview Questions, Process, and Tips

Connect nodes to their right in a binary tree using an extra pointer.

• Traverse the tree using level order traversal

• For each node, connect its right child to the next node in the level

• If there is no next node, set the right child to null

Design considerations for an elevator system with 5 elevators and 50 floors.

• Traffic patterns and peak hours should be analyzed to determine the optimal number of elevators to be in operation at any given time.

• Elevators should be programmed to prioritize stops based on the direction of travel and the proximity of the requested floor to the elevator's current location.

• The system should be designed to minimize wait times ...read more

Given two linked lists, check if they have a common node.

• Traverse both lists and compare each node's memory address

• Use a hash table to store memory addresses of nodes in one list and check for matches in the other list

• If one list is shorter, traverse it first and then start traversing the longer list from the difference in length

Find if an array has a majority element in O(n)

• Iterate through the array and keep track of the count of each element

• If the count of any element is greater than half the length of the array, return true

• Otherwise, return false

Find element in 2D array which is max in column and min in row with minimum comparisons

• Iterate over rows and columns to find max and min elements respectively

• Compare the max element of a column with the min element of its row

• Return the element if it satisfies the condition

• Consider edge cases like multiple elements satisfying the condition

Return an array with only unique elements

• Use a Set to store unique elements

• Loop through the array and add each element to the Set

• Convert the Set back to an array and return it

Merging two sorted linked lists and writing test cases.

• Create a new linked list to store the merged list

• Compare the first nodes of both lists and add the smaller one to the new list

• Repeat until one of the lists is empty, then add the remaining nodes to the new list

• Write test cases to cover all possible scenarios, including empty lists and lists of different lengths

WAP to check if binary tree is height-balanced and write testcases

• A binary tree is height-balanced if the difference between the heights of its left and right subtrees is not more than 1

• Use recursion to check if each subtree is height-balanced

• Write testcases to cover all possible scenarios, including empty tree, single node tree, and unbalanced trees

Find the intersection point of two linked lists.

• Traverse both lists and find their lengths.

• Move the head of the longer list to make both lists equal in length.

• Traverse both lists in parallel until the intersection point is found.

C code to print last n lines of a file given file pointer and integer n.

• Use fseek() to move the file pointer to the end of the file

• Count the number of newline characters encountered from the end of the file until n lines are found

• Use fgets() to read and print the last n lines

Deadlock is a situation where two or more processes are unable to proceed due to a circular dependency on resources.

• Deadlock occurs when two or more processes are waiting for resources held by each other.

• Conditions for deadlock are mutual exclusion, hold and wait, no preemption, and circular wait.

• Methods to prevent deadlock include resource allocation graph, banker's algorithm, and deadlock avoidance.

• To prevent deadloc...read more

Use synchronization techniques like locks, semaphores, or mutexes to prevent multiple processes from accessing shared memory simultaneously.

• Implementing a locking mechanism to ensure only one process can access the shared memory at a time.

• Using semaphores to control access to the shared memory.

• Using mutexes to ensure mutual exclusion and prevent race conditions.

• Using atomic operations to ensure that memory operations a...read more

IPC stands for Inter-Process Communication. It is a mechanism that allows processes to communicate with each other.

• Types of IPC include shared memory, message passing, and pipes.

• Shared memory allows processes to share a portion of memory.

• Message passing involves sending messages between processes.

• Pipes are a unidirectional form of communication.

• Shared memory is faster than message passing, but message passing is more r...read more

Designing an offline browser poses challenges such as data storage, synchronization, and user experience.

• Ensuring efficient data storage and retrieval

• Implementing synchronization with online content

• Providing a seamless user experience with limited connectivity

• Handling updates and changes to online content

• Managing cache and memory usage

• Dealing with security concerns

• Handling different file types and formats

Data structure and code for BFS of N-ary tree

• N-ary tree can be represented using a node class with a list of child nodes

• BFS can be implemented using a queue data structure

• Iterate through the queue and add child nodes to the queue

• Pop the node from the queue and process it

• Repeat until the queue is empty

Find node with maximum weight in a binary tree based on data and level of node

• Calculate weight of each node based on data and level

• Traverse the binary tree and keep track of node with maximum weight

• Return the node with maximum weight

Program to check if a given number is a lucky number or not.

• Create a function that takes an integer n as input

• Initialize a variable count to 2

• Loop through the sequence and delete every count-th element

• Repeat the above step until the end of the sequence

• If n is present in the final sequence, return true, else return false

Code to find inorder successor of given node in binary tree

• Check if the given node has a right subtree, if yes then find the leftmost node in the right subtree

• If the given node does not have a right subtree, then traverse up the tree until we reach a node which is the left child of its parent

• If we reach the root and the given node is the rightmost node, then there is no inorder successor

Given an integer array, find all (a,b,c) such that a^2 + b^2 = c^2. Solution is O(n^2). Write code and testcases.

• Use nested loops to iterate through all possible pairs of integers in the array

• Check if the sum of squares of the two integers is a perfect square

• If yes, add the triplet to the result list

• Return the result list

Find height of binary tree without recursion

• Use a stack to keep track of nodes

• Iteratively traverse the tree and update height

• Testcases: empty tree, single node tree, balanced tree, unbalanced tree

Count the number of occurrences of a given bit pattern in an integer.

• Extract the n trailing bits from the pattern and create a mask with all other bits set to zero.

• Use a sliding window approach to compare the extracted pattern with all possible n-bit sequences in the input integer.

• Increment a counter every time the extracted pattern matches with a sequence in the input integer.

Given a binary tree, check if left and right subtrees are mirror images of each other.

• Traverse the tree and compare left and right subtrees recursively.

• Use a stack or queue to traverse the tree iteratively.

• Check if the left subtree is a mirror image of the right subtree by comparing their values and structures.

• Consider an empty tree as a mirror image of itself.

Find the longest repeating substring in a given string.

• Create an array of all possible substrings of the given string.

• Sort the array in lexicographic order.

• Find the longest common prefix between adjacent strings.

• Return the longest common prefix found.

• If no repeating substring is found, return an empty string.

Pick a fruit from the basket containing both fruits and label the baskets accordingly.

• Pick a fruit from the basket labelled 'apples and oranges'

• If you pick an apple, label the basket containing only apples

• If you pick an orange, label the basket containing only oranges

• Label the remaining basket as containing both fruits

Escape from an intelligent lion at the circumference of a circular pond with given speeds.

• Swim towards the circumference of the pond to make the lion run a longer distance.

• Once the lion is at a considerable distance, get out of the pond and run in the opposite direction.

• Use obstacles like trees or rocks to slow down the lion.

• Try to confuse the lion by changing directions frequently.

Use a min-heap data structure for efficient operations on an array.

• Min-heap allows for constant time retrieval of the minimum element in the array.

• Insertion and deletion of elements in a min-heap can be done in logarithmic time complexity.

• Example: arr = [5, 2, 8, 1, 3], min-heap representation: [1, 2, 8, 5, 3]

Inorder traversal can be implemented using recursion or stack data structure.

• For recursive implementation, traverse left subtree, visit root node, traverse right subtree

• For iterative implementation, use stack to traverse left subtree, visit node, then traverse right subtree

• Inorder traversal is used to print nodes in ascending order in a binary search tree

Stack is a data structure that follows LIFO (Last In First Out) principle.

• Stack holds a collection of elements.

• It has two main operations: push (adds element to top) and pop (removes element from top).

• It also has peek operation (returns top element without removing it).

• Stack can be implemented using arrays or linked lists.

• Examples of stack usage: undo/redo functionality, back/forward buttons in web browsers.