The 5 questions asked in every Microsoft interview & how to answer them

Reading Time: 6 minutes

If you believe you’ve got ideas running in you head and are creative, Microsoft is the place you should be.

With extensive arms with its research, business and tech Microsoft continues to offer some of the best job roles for freshers with an enviable workplace to go with.

With the variety of fields that they are involved in, your career growth and skill set will see no signs of stopping.

With most of the interview rounds being technical in nature, it’s important to understand the complete recruitment process; the topics that the questions will be asked from, the skills that are given importance etc.

Here we have the top most asked questions from Microsoft for their Software Engineer position.


Interview style of every company is different. There are some companies who don’t provide clarifications or encourage questions. But that’s not the case with Microsoft…

They encourage asking questions. Trying to clarify interview questions or asking insightful doubts will fetch you brownie points.

The Microsoft interviews are mostly technical in nature. They don’t hold any HR interviews.

Here are some of the commonly asked questions and methods you can answer them:

1. How do you check if a Binary Tree is BST or not?

A binary search tree (BST) is a node based binary tree data structure which has the following properties.

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

From the above properties it naturally follows that:

  • Each node (item in the tree) has a distinct key.

A: A better solution looks at each node only once. The trick is to write a utility helper function isBSTUtil(struct node* node, int min, int max) that traverses down the tree keeping track of the narrowing min and max allowed values as it goes, looking at each node only once. The initial values for min and max should be INT_MIN and INT_MAX — they narrow from there.

/* Returns true if the given tree is a binary search tree 
 (efficient version). */ 
int isBST(struct node* node) 
{ 
  return(isBSTUtil(node, INT_MIN, INT_MAX)); 
} 

/* Returns true if the given tree is a BST and its 
 values are >= min and <= max. */ 
int isBSTUtil(struct node* node, int min, int max)

2. Search an element in a sorted and rotated array

An element in a sorted array can be found in O(log n) time via binary search. But suppose we rotate an ascending order sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2 .

Devise a way to find an element in the rotated array in O(log n) time.

Input  : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};
key = 3
Output : Found at index 8
Input  : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};
key = 30
Output : Not found
Input : arr[] = {30, 40, 50, 10, 20}
key = 10
Output : Found at index 3

A: The idea is to find the pivot point, divide the array into two sub-arrays and call binary search.
The main idea for finding pivot is — for a sorted (in increasing order) and pivoted array, pivot element is the only element for which next element to it is smaller than it.
Using above criteria and binary search methodology we can get pivot element in O(logn) time

Input arr[] = {3, 4, 5, 1, 2}
Element to Search = 1
1) Find out pivot point and divide the array in two
sub-arrays. (pivot = 2) /*Index of 5*/
2) Now call binary search for one of the two sub-arrays.
(a) If element is greater than 0th element then search in left array
(b) Else Search in right array
(1 will go in else as 1 < 0th element(3))
3) If element is found in selected sub-array then return index
Else return -1.

3. Find the repeating and the missing

Given an unsorted array of size n. Array elements are in the range from 1 to n. One number from set {1, 2, …n} is missing and one number occurs twice in the array. Find these two numbers.

Examples:

arr[] = {3, 1, 3}
Output: 2, 3   // 2 is missing and 3 occurs twice
arr[] = {4, 3, 6, 2, 1, 1}
Output: 1, 5 // 5 is missing and 1 occurs twice

A: Method 1 (Use Sorting)

1) Sort the input array.
2) Traverse the array and check for missing and repeating.

Time Complexity: O(nLogn)

Thanks to LoneShadow for suggesting this method.

Method 2 (Use count array)

1) Create a temp array temp[] of size n with all initial values as 0.
2) Traverse the input array arr[], and do following for each arr[i]
……a) if(temp[arr[i]] == 0) temp[arr[i]] = 1;
……b) if(temp[arr[i]] == 1) output “arr[i]” //repeating
3) Traverse temp[] and output the array element having value as 0 (This is the missing element)

Time Complexity: O(n)
Auxiliary Space: O(n)

Method 3 (Use elements as Index and mark the visited places)

Traverse the array. While traversing, use the absolute value of every element as an index and make the value at this index as negative to mark it visited. If something is already marked negative then this is the repeating element. To find missing, traverse the array again and look for a positive value.

Time Complexity: O(n)

Method 4 (Make two equations)

Let x be the missing and y be the repeating element.

1) Get sum of all numbers.
Sum of array computed S = n(n+1)/2 — x + y
2) Get product of all numbers.
Product of array computed P = 1*2*3*…*n * y / x
3) The above two steps give us two equations, we can solve the equations and get the values of x and y.

Time Complexity: O(n)

This method can cause arithmetic overflow as we calculate product and sum of all array elements.

Method 5 (Use XOR)

Let x and y be the desired output elements.
Calculate XOR of all the array elements.

xor1 = arr[0]^arr[1]^arr[2].....arr[n-1]

XOR the result with all numbers from 1 to n

xor1 = xor1^1^2^.....^n

In the result xor1, all elements would nullify each other except x and y. All the bits that are set in xor1will be set in either x or y. So if we take any set bit (We have chosen the rightmost set bit in code) of xor1 and divide the elements of the array in two sets — one set of elements with same bit set and other set with same bit not set. By doing so, we will get x in one set and y in another set. Now if we do XOR of all the elements in first set, we will get x, and by doing same in other set we will get y.

Time Complexity: O(n)

This method doesn’t cause overflow, but it doesn’t tell which one occurs twice and which one is missing. We can add one more step that checks which one is missing and which one is repeating. This can be easily done in O(n) time.

4. What is the difference between process and thread?

A: In programming, there are two basic units of execution: processes and threads. They both execute a series of instructions. Both are initiated by a program or the operating system.

A process is an instance of a program that is being executed. It contains the program code and its current activity. Depending on the operating system, a process may be made up of multiple threads of execution that execute instructions concurrently. A program is a collection of instructions; a process is the actual execution of those instructions.

The main difference between the two terms is that the threads are a part of a process, i.e. a process may contain one or more threads, but a thread cannot contain a process.

The major difference between threads and processes is:

  • Threads share the address space of the process that created it; processes have their own address.
  • Threads have direct access to the data segment of its process; processes have their own copy of the data segment of the parent process.
  • Threads can directly communicate with other threads of its process; processes must use interprocess communication to communicate with sibling processes.
  • Threads have almost no overhead; processes have considerable overhead.
  • New threads are easily created; new processes require duplication of the parent process.
  • Threads can exercise considerable control over threads of the same process; processes can only exercise control over child processes.
  • Changes to the main thread (cancellation, priority change, etc.) may affect the behaviour of the other threads of the process; changes to the parent process does not affect child processes. (Source: Process vs Thread)

5. Remove all duplicates from a given string

A: Method 1 (use sorting)-

Algorithm:

1) Sort the elements.
2) Now in a loop, remove duplicates by comparing the
current character with previous character.
3)  Remove extra characters at the end of the resultant string.

Time Complexity: O(nlogn) If we use some nlogn sorting algorithm instead of quicksort.

Method 2 (use hashing )-

Algorithm:

1: Initialize:
str  =  "test string" /* input string */
ip_ind =  0          /* index to  keep track of location of next
character in input string */
res_ind  =  0         /* index to  keep track of location of
next character in the resultant string */
bin_hash[0..255] = {0,0, ….} /* Binary hash to see if character is
already processed or not */
2: Do following for each character *(str + ip_ind) in input string:
(a) if bin_hash is not set for *(str + ip_ind) then
// if program sees the character *(str + ip_ind) first time
(i)  Set bin_hash for *(str + ip_ind)
(ii)  Move *(str  + ip_ind) to the resultant string.
This is done in-place.
(iii) res_ind++
(b) ip_ind++
/* String obtained after this step is "te sringng" */
3: Remove extra characters at the end of the resultant string.
/* String obtained after this step is “te sring” *

If you found this article useful, please do recommend and tag your friends in the comments below. Help them ace the Microsoft interviews.

If you still have doubts about the recruitment process, fill out this Google form with some basic information and we will get in touch within 48 hrs to help you out.

Leave a Reply

Your email address will not be published. Required fields are marked *