First interview starts at 8am. Last interview (6th) ended at 5pm. For those of you keeping track, that is 9 hours of straight interviews. Even at lunch.
By the way, lunch was at the MSFT cafeteria. The burger was pretty good, the fries were not.
So, what should you expect when interviewing with Microsoft? Data structures. Then more data structures. Then, after that, a few more data structures.
Every one of my interviews went about the same. Meet the interviewer, get a problem description from them, and then do some coding. After you solve the technical problem, come up with a bunch of test cases to test this algorithm.
Here are the specific algorithms and questions, as I can remember them:
Some suggestions:
I'm supposed to find out tomorrow if they are interested in offering me a position. The 5 hiring managers are apparently going to sit down in a room together, and come up with a decision about which team(s) will offer me a position.
Oh yeah, and I found out something else. It's taboo at MSFT to bypass the system, which I sorta did. There were raised eyebrows when my recruiter learned that an SDET took me around Seattle on his own time, without being asked.
There are two teams on the Office Live group, Core Services and User Experience. So, those are the two teams that will have the option to present me an offer.
More updates to follow.
By the way, lunch was at the MSFT cafeteria. The burger was pretty good, the fries were not.
So, what should you expect when interviewing with Microsoft? Data structures. Then more data structures. Then, after that, a few more data structures.
Every one of my interviews went about the same. Meet the interviewer, get a problem description from them, and then do some coding. After you solve the technical problem, come up with a bunch of test cases to test this algorithm.
Here are the specific algorithms and questions, as I can remember them:
- Given a binary tree, and a number, find the item in the tree that has the next highest value.
- Given a binary tree, create singly-linked lists that connect all of the nodes at each level. So, all of the sibling nodes in the tree should be connected to each other, in a list that goes from lowest to highest values.
- You have a 100 element array of integers. The values 1-100 are in the array, but in random locations. I will take away one of the values, and replace it with a zero. Find out which value was removed. The best solution I could come up with worked in a constant O(n) time. My first solution was found in O(n2) time.
- Given two arrays, A and B, of unknown length, determine if the array B is contained inside array A. So, B contains a list of integers. We need to know if that same list of integers exists anywhere in A.
- Implement the String.Split function. Except, instead of passing in a character as the delimiter, we will provide a string delimiter. Memory utilization is important for this one. Try to implement the algorithm without any memory overhead beyond the strings passed in to the function.
- Given the 'Save As' dialog from notepad, come up with test cases for the file name textbox. I came up with about 30 test cases, which would have resulted in thousands of permutations.
Some suggestions:
- Get extra sleep. 8 am comes early, and I did the worst on my first technical interview. The 3 hour time difference messed us up here.
- Study up on data structures. You need to know about every data structure from your class, to include linked lists, queues, stacks, hash tables, and particularly binary search trees.
I'm supposed to find out tomorrow if they are interested in offering me a position. The 5 hiring managers are apparently going to sit down in a room together, and come up with a decision about which team(s) will offer me a position.
Oh yeah, and I found out something else. It's taboo at MSFT to bypass the system, which I sorta did. There were raised eyebrows when my recruiter learned that an SDET took me around Seattle on his own time, without being asked.
There are two teams on the Office Live group, Core Services and User Experience. So, those are the two teams that will have the option to present me an offer.
More updates to follow.
7 comments:
About the first question, what is meant by the "next highest" number in a BST?
Isn't the right child the smallest number greater than the given number?
Did you mean the second largest number in the tree?
yes, you're right. The catch in this problem is that the number you are given may or may not be in the tree. For instance, if I have a BST that has these elements inserted, in this order: 5, 2, 20, 100, 4, -10, 89.
If I give you the input of 7, and tell you to find the next highest number, how are you going to do it?
Thanks for the reply on the previoius post. On the question about split, I cannot see how extra memory than the given ones cannot be used?
The split function would return an array or list of tokens parsed from the string. So you do need to create memory for these. Shouldn't the parsing algo be the major concern instead?
in order for the split to work with no additional overhead, you have to use a language that doesn't do memory management for you. For my interview, we talked about that particular algo in C++.
Does that help? Note that you don't have to return an array of elements as a seperate piece of memory. Plus, in C, what is the difference between char * and char * [] ?
thanks again. One could as well return an array of pointers, each element pointing to the beginning of the various tokenized strings.
For this question if someone chose C# or Java to implement would it be a cause for rejection?
Choice of programming language should never be a cause for rejection in a Microsoft interview.
The times I've encountered this question, and dealt with the zero extra memory solution, it was after the candidate had already 'passed' the question with a workable, performant solution. This part of the question is more an exercise in theory, and gives a bit more insight into the mind of the candidate, and how they approach problems.
I found the 100 element problem particularly interesting, because I thought up (what I thought was) a neat solution for sorting positive consecutive integers beginning with 0:
// int arr[100];
int newArr[101];
for(int i = 0; i < 101; i++)
newArr[arr[i]] = i;
printf("%d", newArr[0]);
Anyway, it's good to hear you got an offer from Microsoft! It sounds pretty exciting :)
Post a Comment