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] ;)
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] ;)
In first google telephonic. How n=0 and minimum(h) will be the first person?
ReplyDelete9,2,6,8,4 |->
here in this case for "2" n=0 and for "4" n=0 then according to your solution "2" will be selected...
Am I missing something?