Microsoft Corporation Interview Questions, Process, and Tips

Remove duplicates in an array of strings

• Create a new empty array

• Loop through the original array and check if the current element exists in the new array

• If it doesn't exist, add it to the new array

• Return the new array

Removing characters in Fibonacci position in a string and compacting it

• Iterate through the string and remove characters at Fibonacci positions

• Compact the string by removing the spaces or special characters

• Return the final compacted string as the result

Finding the closest parent in a binary tree

• Traverse the tree from root to the given node and store the path in an array

• Traverse the tree again from root to the other given node and check if any node in the path array is common

• The last common node in the path array is the closest parent

• If one of the given nodes is the parent of the other, return the parent node

Placing Rooks on a chessboard without attacking each other.

• A rook can move horizontally or vertically any number of squares.

• Place one rook in each row and column to avoid attacking each other.

• The maximum number of rooks that can be placed on an n x n chessboard is n.

• The problem can be solved using backtracking algorithm.

malloc and free are functions used for dynamic memory allocation in C. The operating system manages memory allocation and deallocation.

• malloc is used to allocate memory dynamically, while free is used to deallocate memory.

• malloc allocates a block of memory of the specified size and returns a pointer to the beginning of the block.

• free releases the previously allocated memory block, making it available for reuse.

• The oper...read more

When a high-level language program is compiled and run, it goes through lexical analysis, syntactic analysis, intermediate code generation, code optimization, code generation, paging, caching, pipelining, interrupts, polling, instruction sets, and ALU operations.

• Lexical analysis: Converts source code into tokens.

• Syntactic analysis: Checks the grammar and structure of the program.

• Intermediate code generation: Translates...read more

Print all downward paths from any node in a binary tree with sum of elements equal to N.

• Traverse the binary tree and keep track of the sum of elements in the path from root to current node.

• If the sum equals N, print the path from root to current node.

• Recursively traverse the left and right subtrees with updated sum.

• Use a stack to keep track of the current path being traversed.

• Example: Binary tree with root 1, left chil...read more

Yes, it is possible to get the accurate result from the given data.

• The coordinates (i,j,k) where metallic balls are present can be determined by finding the set elements in both matrix1 and matrix2.

• Additional data is not required as the given data is sufficient to determine the coordinates.

• The coordinates can be obtained by iterating through the elements of matrix1 and matrix2 and checking for set elements.

A function to merge two sorted linked lists and determine its time complexity.

• Create a new linked list to store the merged result

• Compare the values of the nodes from both lists and add the smaller value to the new list

• Move the pointer of the list with the smaller value to the next node

• Repeat the comparison and addition until one of the lists is fully traversed

• If any list still has remaining nodes, append them to the ne...read more

To build a valid binary search tree from a preorder traversal

• Iterate through the preorder traversal array

• Use a stack to keep track of nodes

• Compare each element with the top of the stack to determine its position in the BST

Merge two sorted arrays efficiently into a bigger array.

• Use a two-pointer approach to compare and merge elements from both arrays.

• Start from the end of the bigger array and move backwards to avoid overwriting elements.

• Continue merging until all elements from both arrays are placed in the bigger array.

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.