Interviews with Microsoft Bing and Google.

There and back again!

Here are my recent interview experiences with Microsoft and Google.

Microsoft, India Development Center
Interviewed for: Software Development Engineer

I was referred to Microsoft by one of my friends who is working there and I was interviewed for two teams separately in parallel, one for the Bing team and other for the Office team.

Here are my experiences with both the teams:

Bing Team:

Round 1:

Q1. Given a binary tree, return true if it is a BST. Do it in a non-recursive way.

The first part of the question was a little bit of a cliche, even the second part was nothing but a straight application of Morris Inorder traversal.

Q2. There is a 2D matrix of size 10 X 10, where you have to begin from the location (0,0) and move to the location (9,9). You can either move right on down. Find out the number of distinct paths in which you can reach (9,9) from (0,0).

Hint: Dynamic Programming

Round 2:

Only one question was asked in this round and it lasted only for about 25 min.


Q1. Given a linked list with random pointers, clone the linked list. That is every node in the linked list will have a 'next' pointer and a 'random' pointer, where the random pointer can point to any node in the linked list (including itself and null).

Create and insert new nodes in the given linked list so that the initial list 1->2->3->4 would look like 1->1*->2->2*->3->3*->4->4*, where all the *'ed nodes are newly created ones. To fill in the random pointers of the *'ed nodes, do the following: Take two pointers p1 and p2, p1 pointing to '1' and p2 pointing to '1*'. Point the random pointer of p2 to the 'next' node of the node pointed by the 'random' pointer of p1. That is, p2->random = (p1->random)->next. Then split the linked list 1->1*->2->2*->3->3*->4->4* into two lists of the form - 1->2->3->4 and 1*->2*->3*->4* and the latter is the cloned version of the given LL.


Round 3:

Q1. Given an array with a special property, find the smallest number in it. The special property is that the elements in the array are monotonically decreasing and then increasing.

Trivial ;) A Slight modification of the binary search would solve the problem.

Q2. Write code for the above problem.

This kinda went into an open discussion about code re-usability andpolymorphism. Wrote stud level code in Java ;)

Round 4:

This was the final interview with the hiring manager of the Bing team.

Q1. Design a system (data structure and the algorithm) in Bing that predicts what word would the user be typing in from the semi-typed word. That is if the user has typed "micro", the system should give suggestions like "microsoft", "microscope" etc. Also the system should take care of any spelling mistakes that the user has entered.

I proposed two systems, one for predicting the probable word that the user is searching for, looking at the partially entered text and other for finding if there are any spelling mistakes in the text entered by the user so far (assuming that the user has entered the complete text in this case). The latter system can implement the Edit Distance algorithm to solve its problem. Coming to the former system, a simple trie based dictionary would solve it.

Q2. Then he asked questions about a project that I had worked on before and asked me draw the whole design of it.

In the last minutes of this interview, he asked me that they have liked my candidature and I would get an offer :)

Office Team:

These interviews were very boring as compared to the other team's.

I was interviewed for both Software Development Engineer (SDE) and Software Development Engineer in Test (SDET) roles and was told that they would offer me the role that they think would suit me.

Here are a few questions that I remember and rest of them were related to testing, so I am not going to talk about them much.

Q1. Given a circularly sorted array, find the smallest number in it.

Straight forward.

Q2. Write a c function that tells if a given string is a valid IP address or not. Write test cases for it.

Articulated the idea of a state machine.

I hardly remember others.

Google, Mountainview, California
Interviewed for: Software Engineer

This is one of the best interviews I ever had. I was jubilated at the end of the interviews with the standard of the questions that they asked me and the way I nailed them ;)

Telephonic Interview:

Q1. There are m persons in a queue. Every person knows his height and also the number of persons who are shorter than him(her) and are infront of him(her) in the queue. During the lunch time, the queue got dispersed and given this information, you have to re-generate the queue.

Took some time for me to think about this and here is what I came up with. Say, for a person, 'n' be the number of persons shorter than him and who are infront of him in the queue and 'h' be his height. Now, for every person we know the pair (n,h). Claim: The person whose n=0 and h is the smallest would be the first person in the queue (prove the claim, using proof by contradiction). Now that you found the first person, update the n's of all the other remaining persons (ie., subtract 1 from the n's of all the persons whose 'h' is greater than the first person's h). Now the problem got reduced to size (m-1). Repeat the same process until all the positions are found.

Q2. Given an unknown language (say arabic) and a dictionary of that language, find the ordering of the alphabets in the language using the dictionary. (Remember that the dictionary maintains the ordering between alphabets).

The problem can be seen as a graph problem, where each alphabet is a node and the directed edge gives the ordering between the two alphabets represented as the nodes. Go through the whole dictionary, learn the edges between the nodes from the dictionary and perform topological sort to finally get the ordering of all the alphabets.
Improved this with a much efficient algorithm - Start with the first word, compare it with the next word, draw an edge between the two characters at which first point of conflict arises between those two words. [Ex: "abcd" and "abce", then draw an edge d->e]

Round 1:

Q1. There is a city which can be treated as a 2D matrix. There is a group of people living at different locations in the city (given by the co-ordinates of the matrix) and they all would like to meet for dinner. Suggest a place in the city (co-ordinates) so that the complete distance traveled by all of them is minimum. Distance between two points (a,b) and (c,d) is given by |a-c|+|b-d|.

Hint: Look at medians of the x and y co-ordinates of all the people.

Q2. Design Google Search.

As evident from the question, this is very open-ended. Gave the idea about clustering the documents per topic and searching in these topics.

Round 2:

Q1. Given an array of numbers, print the smallest numbers in a sliding window of size k. [Ex: 5,2,4,3,1 is the array and if k=3, the output should be 2, 3, 1].

Hint: Using heap - takes O(n lg k). Using a modified queue structure, it takes O(n) :)

Q2. Given a linked list and a number k, reverse every k nodes in the list. That is, say the linked list is 1->2->3->4->5 and k = 3, then the returned list should be of the form: 3->2->1->4->5 and if k=2, then result would be: 2->1->4->3->5. Write code for this.

Round 3:

Q1. Given a "k-specially sorted" array, sort it completely. A k-specially sorted array is an array which is initially sorted and then the numbers in the array are scrambled such that an element belonging to the index 'i' in the sorted array would be moved to any index in the range [i-k, i+k].

Take the first 2k elements, sort them and the first k elements are now in their sorted places. Repeat the process until the complete array is covered. Complexity - O(n lgk)

Q2. Given a set of words, store them in such a way that given a new word, you should return all the words that are the permutations of the given word.

Similar to one of the questions in my previous post. Use a trie data structure. Running time complexity of the query - O(n), where n is the length of the word.

Round 4:

He is the most arrogant person I have ever seen. Asked me to code in Java on white board and was cribbing for the syntax errors all the time. Very unfriendly.

Q1. Given a huge file of integers, so huge that you cant fit all of them in memory, sort them.

It took sometime for me to come up with the solution for this. The interviewer hinted about map reduce, which I wasn't aware of then. Here is the solution that I gave which is similar to the idea of map-reduce :). Break the file into so many files such that each file is small enough that it can fit into memory. Now, sort numbers in each file and use a heap-based merging technique.

Round 5:

Q1. There is a game of 2 players and 50 coins, positioned in sequence. Each coin has a value and the ordering of coins is random. Each player gets a turn and during his turn, he has to pick a coin either from the first position or the last position. Let us say that you are the player to make the first move, come up with a strategy so that your win is guaranteed. Note that the other person is as clever as you.

Hint: This game is flawed and with a strategy, the first player can always win.

Solution: Sum all the coins in even positions and all the coins in the odd positions. Always pick from odd position if the sum of coins in odd positions is greater or pick from even position, otherwise.


Q2. The most challenging question ;) Given a dictionary and a string made of alphabets, check if a sentence can be formed by adding appropriate spaces into that string or not. You should also enumerate all the possible sentences that can be made out of the string. For example, if the string is "googleisgreat", you should output - "google is great" and "go ogle is great". Here, a sentence doesn't mean it has to satisfy grammatical rules, but anything that is formed using valid English words.

This took a huge amount of time for me to finally arrive at the answer. So, I am not going to present it to you, yet ;) Hint: Dynamic Programming, tussi great ho [DP is the key here] ;)

A few more interview questions from my friends' experiences

Q1. [Microsoft Interview] There is a binary tree, with each node storing its parent pointer as well. Given a pointer to a node in such a tree, you should return the leftmost node in the same level as the given node. Write code and provide test cases to test the same.

A. Pretty much straight forward. Idea: Just move up till you reach the root, and from there drop down to the left most node which would fall into the same level, as the given node. Time Complexity: O(h), where h is the depth of the given node.

Q2. [Microsoft Interview] There is a binary tree, where each node has an extra pointer called 'next' which will be pointing to NULL. Given the root of such a binary tree, fill in the 'next' pointer of all the nodes in the tree in such a way that, the next pointer of a node should point to its in-order successor.

A. Finding the inorder successor for a given node takes O(lg n) time (explained in one of my previous posts). Using that, you can fill in the 'next' pointers in O(nlgn). However, there is a much better way of doing it using slight modification of Morris Inorder traversal.

Q3. [Again, Microsoft Interview] Given an array of integers A, return another array B, whose element 'i' defines the product of all the elements in A except A[i]. That is B[i] should contain the product of all elements in A, except A[i].

A. Yes, multiply all the numbers (say 'product') and store it in a temp variable. And fill in the array B as B[i] = product/A[i]. However, this method will not work if there are more than one zeroes in the array A. An alternative method is take two temp arrays X and Y and fill them as: X[i] = A[0]*A[i]*....A[i-1] and Y[i] as A[i+1] * A[i+2] * .... A[n-1]. Use this to fill in the array B.

Q4. [Google Interview] There are N persons standing in a queue at a store, where each person knows his height and the number of persons who are taller than him. Now, because of the lunch break the queue had dispersed. You job is to reconstruct the queue with the same configuration like it was before dispersion, given that you only know, for each person, his height and number of persons who are taller than him and are infront of him in the queue.

A. Hint: Use recursion:- at each step find the person who should be standing first in the queue.

Q5. {Google Interview] Given a sorted dictionary of the Chinese language and the list of alphabets of the language, find the precedence of the alphabets using the dictionary.

A. Hint: Construct a directed graph with alphabets as nodes and perform the topological sort.

Interview with Directi

I faced this company during campus placements.

There was a preliminary test(usually online) followed by another online coding round and then followed by two personal interviews.


I hardly rememeber any questions from the first two rounds. Following are some of the questions that I remember from the two personal interviews:


Q1. You are given 'n' nuts and 'n' bolts. Each nut will fit to exactly one bolt and viceversa. For a given nut and a bolt, you can check if the nut is large for the bolt or the nut is small for the bolt or they form a perfect fit. There is no way you can compare two nuts or two bolts. Given this scenario, design an algorithm to identify the perfect fit pairs.


A. The idea is something similar to quicksort. Randomly pick a bolt and compare it with every other nut. Place all the nuts which are larger for the bolt in one set and all the nuts which are smaller in other set. Now, pick the nut which is a perfect fit for the bolt and make the split over the other bolts is the same way as described above. Repeat the operation on thw two sets recursively(Divide and conquer).


Q2. What are heaps? Where are they used and what are the running times for each of the operations performed on a heap.


Please note that the running time complexity of Build-Heap operation is O(n) and make sure that you know the proof for it.

Q3. How are the databases implemented? What data structure is used?

A. B-Trees. Important to know about B-Trees.

These are the questions that I remember.

Interviews with other companies!

Following are the questions that I and some of my friends had faced in different interviews, some time back.

Q1. Given a sorted array, how do you find the index of the first occurrence of a given number, x? For example, consider the sorted array, 1 2 3 3 4 5 and the index of the first occurrence of the number 3 (=x) is 2 (assuming that the array begins with 0 index).


This can be solved by slightly modifying the binary search algorithm. Perform binary search for number x in the array and if you find a match, recursively perform binary search on the left sub-array for the number x, to check whether the match found is the first occurrence or not. Running time complexity is O(lg n).


Q2. Given two arrays A and B of same size 'n', find if there exists a set of pairs (a_i, b_i), such that a_i belongs to A and b_i belongs to B and a_i+b_i = S, for all 1 < i < n. Note that, an element a_i (or b_i) can only appear in exactly one pair, in the entire set.


Sort the two arrays, one in non-increasing order and the other in non-decreasing order. If there exists such a set, then the set will be formed only with the pairs obtained by combining the first elements of the two sorted arrays. For example, let a₁....a_n be one sorted array (in non-increasing order) and b₁....b_n be the other sorted array (in non-decresing order). Then the required set, if at all exists, is (a₁, b₁), ...... (a_n, b_n) (Think why??).


Q3. (Interviewed for: Software Development Engineer)Given an array of 'n' numbers and a number 'k' (< n), compute the numbers which are obtained by computing the smallest number in the window of size 'k' with starting index i (varying from 0 to n-k).


Hint: Use heap :)


Q4. Write a code to perform breadth first search in a binary tree.


This is nothing but level-order traversal.

Q5. Write a code to convert a decimal number to a binary number.


Following are a set of simple puzzles.


Puzzle-1: There are three baskets with one having apples in it, the other having oranges in it and the third basket having both oranges and apples. Each of the basket have labels on them, saying what is contained in each of the basket. However, all the three baskets have been labeled WRONGLY. That is, not even one basket bears the correct label on it. A trial is defined as choosing a basket and drawing a fruit from it, observing it and replacing it in the basket. How many minimum trials are needed to label each basket correctly.


Answer to this puzzle is 1 (Find out how??).


Puzzle-2: There are 25 horses with a race track, in which only 5 horses can run at a time. How many races need to be conducted to identify the top 5 fastest running horses.


Answer is 7 (how??).

Puzzle-3: The classic puzzle of 2 eggs and 100 floors problem (google for the exact question).

A New Experience with a Networking Start-up!

Please note that I am a fresher from one of the IITs. So, the interviews for the same companies might be different for non-freshers.

Brief Intro about the company: Arista Networks is the name of the company, that I got interviewed for. It is a networking start-up company.


The interviews I had for this company are very different from the ones that I had before. They gave me a laptop to work on and the interviewer was sitting right infront of me on another laptop, looking at what I was doing, by 'ssh'ing in to my laptop. They weren't keen on asking questions related to a specific topic. Rather, they were just looking at how sharp the candidate is. There were just two rounds of interviews, pretty big ones though with each one lasting about 2-3 hrs.

Round-1 Interview:

The interviewer asked me questions to test my familiarity with Linux. He was not just asking about basic linux stuff, he asked me to find out the memory layout for a process. He asked me questions about /proc filesystem. How would I go about using the /proc filesystem to extract the information corresponding to each running process. He was completely obsessed with acronyms. He says "copy-on-write" is called "COW". I have NEVER heard of such an acronym. Huffff!!! It was a very tiresome job and I was absolutely lost!!!

Then the second part of the interview starts, which is about the Algorithms and Data structures (my favourite!). Here are the questions:

Q1. Given a pointer to a node in Binary Search Tree, return the next inorder successor of that node.

Straight forward code. Kids stuff! :P

Q2. Given a binary tree, write a function which would return true if the tree is a valid binary search tree or false if the tree is not a valid binary search tree.

Straight forward again! He was a bit impressed that I solved them without taking any hints.

Q3. Given a linked list and a number, remove all the nodes in the linked list whose 'key' value is equal to the given number. For example, given the linked list 5->6->1->3->5->5->7->8 and number 5 as input to the function, the function should modify the linked list as 6->1->3->7->8.

This again, pretty straight forward kids stuff! :P :P

Then he tells me that he was absolutely worried about the first part of my interview. I realized that he wasn't impressed with the first part, at all. But, he was happy with my second part. However, I still don't know whether he would select me or not.


Round-2 Interview:

This guy is an absolute genius. He seems to have quite some experience with the networking and stuff. He asked what would be my favourite area. I said operating systems. And then he started.

Q1. How would two processors inter-communicate with each other?

I told him things about Advanced Programmable Interrupt Controller(APIC). And then I realized that I got the question incorrectly. The questions was:

Q1. How would two "processes" inter-communicate with each other?

I told him that this can be done using shared memory, signals, memory queues, etc. He asked me to explain the signals a bit more. I told him about how the signals are generated and how they are handled in uniprocessor and multi-processor systems. I knew what I said was correct.

Q2. This is a very hypothetical question that he had asked me. There are two processes running and you want to send a text string from one process to another process. And the only way these processes can communicate with each other is by using signals. He asked me not use shared memory/message queues etc. Like as I said, the only way of communication between these two processes would be through signals.

I gave a very wacky solution. Convert the string into a binary string. And assign two signals (let us call them SIGX and SIGY), one to the binary '1' and the other to the binary '0'. For the bit '1'(/bit '0'), process-1 sends the signal SIGX(/SIGY) to process-2 and in the signal handler of SIGX in process-2, it sends a signal(let us call this as SIGZ) to process-1 as an ack for the signal received. After receiving ack from process-2, process-1 transmits the next bit in the same way and so on. (You would understand why I am doing this if you know how signals are handled in the linux kernel). He seemed to be satisfied with the solution.

Q3. He asked me questions about the memory management in linux. How is virtual memory handled and how is that converted into physical address and so on.

Q4. He asked me the difference between Arrays and Linked lists. Pros and cons for both of them. I even told him about dynamic arrays and how are they implemented. Asked me to analyze each of them interms of the resources available in the system(memory and cpu time). Took me to the systems level.

I think I have done a good job in answering this question.

Q5. There is memory(RAM) of size 32GB and you want to count the number of times the word 'a' occurs in the entire memory. How would you go about solving this problem on a (i) uni-processor machine and (ii) a multi-processor machine.

I told him that parallelization can be done on a multi-processor system where as, single thread would be more efficient on a uni-processor system. Reason: On uni-processor multi-threading leads to unnecessary overhead because of context switches.


That's all folks! I haven't been told the result yet and I think they might not select me.

My Interview Experiences with CS Companies

This blog is about my personal interviews experiences with various companies. I will talk about the questions that I've been asked and hints to their answers.

Microsoft, India Development Center
Interviewed for: Internship

The first phase of the selection process was a written exam. I found it pretty straight forward. Then there were 4 rounds of technical interviews.

Round-1 Interview(Technical):

Q1. How do you divide two numbers with out using division operator?

Unfortunately, the interviewer wasn't friendly, in the way that she wasn't giving any hints. I gave a solution by using continuous subtraction. I had this feeling that there should be a much better way of solving this problem. However, the I couldn't get the idea then. Later, I found that this problem can be solved using an idea similar to binary search.

Q2. Design a single remote that can be used to control TV, Music Player and DVD player.

I talked about a system similar to the 'Project Natalie' of the XBox systems of Microsoft. She was happy with the design that I gave.

Round-2 Interview(Technical):

Q1. Design a cache system. What data structure would you use?

I gave the solution, using a dynamic hash table.

Q2. Given a pointer to a node in a binary tree, return the pointer to the successor node. Every binary node has a parent pointer stored in it, as well. (Note that the pointer to the root is not given - not needed anyway :) )

This was a pretty straight forward. Wrote the code easily without any problem.

Round-3 Interview(Technical):

Q1. There are k systems given and each system has n numbers in the sorted order. You are given a new system which has a space of O(k). Your system can contact with any other system and fetch a number from it. Your task is to write all these n*k numbers into a file in the sorted order using the system that was given to you.

This was a straight forward implementation of the generalized merge-sort(merging k arrays). (Hint: Get the smallest number from each system and build a min-heap with them and take it from there.)

Q2. How are parameters passed to a function, at the machine level?

Parameters are pushed onto the stack(this is the most common and popular way of doing it).

Q3. How is inheritance implemented in C++ and Java? What are the differences?

C++ involves building Virtual tables at compile time and Java involves resolving at run-time.

Round-4 Interview(Technical):

Q1. What are your areas of interest?

I told that operating systems are my favorite.

Q2. Implement semaphor and spinlock using test&set instruction.

Q3. Solve the readers-writers problem. How do you ensure fairness(the bounded waiting) for both readers and writers?

These are the classical synchronization problems.

Finally, got selected for the internship program.

Amazon Development Center, India

Interviewed for: Position of Software Development Engineer(SDE)

Telephonic Interview(Technical):

Q1. Given a linked list of the form, 1->2->3->4->5->6, convert it into the form 2->1->4->3->6->5. Note that the nodes need to be altered and not the data contained in them.

Q2. Write the code for finding the least common ancestor in a Binary Search Tree.

Q3. The classical puzzle of 25 horses with a race track for 5.

5 rounds of on-site technical interviews!(sigh!)

Round-1 Interview(Technical):

This round is what they call 'Data structures and Algorithms round'.

Q0. Intro about me and about the projects that I've done.

Q1. Given a set of words, divide them into groups such that, each group contains words which are anagrams to each other.

Idea that I used to solve: If I alphabetically sort each word belonging to a group, the resulting sorted words would be the same for all the words in the same group.

Ex: bca, cab, cba are all anagrams to each other. Sorting each of them alphabetically gives the same word, abc.

Take every word, sort it alphabetically and insert this sorted word into a patricia trie, with each node containing a linked list of all the words which have the same sorted word. Every node in the resulting trie would correspond to a group.

Q2. You will be given a dictionary containing all possible English words and your job is to store the dictionary in such a way that, you should be able to solve any given cross-word puzzle, as soon as possible.

The data structure that I suggested is very complex to be explained here. However, the idea is to store all the words according to their word lengths and build a structure to choose the words to fill a slot in the cross-word puzzle. You would also need to do the back-tracking to solve this.

Q3. Implement a stack using queues.

This is pretty straight forward.


Round-2 Interview(Technical):

This round is the 'Coding and Problem Solving' round.

Q0. Intro about myself and my final year project.

Q1. Write a program to return the word count, character count and line count for a given input file.

Straight forward.

Q2. Write a code to return the first non-repeating character of a very long string.

I gave the working code with one pass of the string and with an extra space of 26 character array.

Q3. Given a word, print all the possible anagrams of that word. Also, take care of repeating characters.

Gave a recursive solution involving a static variable.

Round-3 Interview(Non-Technical):

This round was with my hiring manager. Absolutely, HR stuff and HR questions like "When was the last time you felt that you lost in something?", "When was the last time your team mate complained about you?", etc. I guess the key to this round was to be absolutely patient.

Round-4 Interview(Technical):
This round is the 'CS Basics' one.

Q1. Questions about the necessity of cloud computing. Design a simple cloud of servers to serve the queries for amazon.com(considering the scale of number of queries/sec).

As, Networks was not my area of interest, I had to logically think and solve each of the issues he posed on me. Luckily, my solutions turned out to be the ones which are currently being used in the industry.

Q2. A code to test my understanding of memory management for processes in the system.

Basics of architecture and OS.

Q3. Semaphors vs Spinlocks. Advantages of one over the other and justification for the necessity of having both, rather than, having just one of them.

OS fundamental stuff.

Q4. There were other questions on CS fundamentals, which I couldn't recollect.

Round-5 Interview(Technical & Non-Technical):

This interview was with another manager of another team.

Q1. Explained in detail about my final year project and summarization of the results.

Q2. Some HR questions.

Q3. Write a code to find contiguous sub-array, whose sum is maximum, in an array containing both positive and negative numbers.

Straight forward code with O(n) running time and O(1) space complexity.