Microsoft Corporation Interview Questions, Process, and Tips

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.

Determining the result of string reversal and rotation operations using a reverse function.

• The first operation reverses the first half and second operation reverses the second half of the string, resulting in a rotation of the string left k positions.

• The third operation reverses the entire string, resulting in a reversal of the string.

• Therefore, the correct answer is (b) Rotates the String left k positions.

• Example: s =...read more

Relation between num and len in a given code snippet

• The code recursively calls the function abc() twice for each character in the string

• The printf() statement prints each character once

• The number of '>' characters printed on the screen is equal to num

• The length of the string is equal to len

• The relation between num and len is num = 2^len - 1

Identifying which numbers cannot be accurately represented in binary.

• Binary cannot accurately represent decimal fractions that do not have a power of 2 as their denominator.

• Option a (0.1) and option e (0.590625) cannot be accurately represented in binary.

• Option b (6.5) and option d (1.32) can be accurately represented in binary.

• Option c (1/16) can be accurately represented in binary as 0.0001.

Additional processors required to execute a process in 150s with 40% sequential execution.

• Process takes 300s on a single processor

• 40% of the process is sequential and doesn't require additional processors

• Calculate the time taken by the remaining 60% of the process

• Determine the speedup required to execute the remaining 60% in 150s

• Calculate the number of additional processors required based on the speedup

Determining worst case time complexity of a code snippet with given time complexity of a function and array

• The time complexity of the given code snippet is O(n)

• The function f(m) is called only when a 0 is encountered in the array

• The worst case time complexity is O(n)

• The code snippet iterates through the entire array once

Increasing RAM improves CPU efficiency due to virtual memory and reduced page faults.

• Increasing RAM allows for more data to be stored in memory, reducing the need for frequent access to slower storage devices.

• Virtual memory allows the operating system to use hard disk space as if it were RAM, increasing the effective amount of memory available to the CPU.

• Reducing page faults, which occur when the CPU needs to access da...read more

To find n-k th element from last in a string of unknown length

• Traverse the string to find its length

• Calculate the position of n-k th element from last

• Traverse the string again to find the element at calculated position

Count the number of unique occurrences in an array of strings.

• Create a hash table to store the count of each string occurrence.

• Iterate through the array and update the count in the hash table.

• Count the number of unique occurrences by counting the number of keys in the hash table.