
Yesterday morning, I had my first-round interview with Microsoft. My interviewer was a woman named Shauna. Shauna has been with Microsoft for two years and works doing testing for a Windows Communication group. My overall impression of the interview was favorable, but with an interview system set up to err on the side of false negatives (meaning: they don’t care if they miss out on good people so long as they don’t hire bad ones) you never know.
After an introduction, and a pitch of Microsoft - she asked me the standard “Why work for Microsoft question.” After that question, she went on to ask me an interesting open-ended question.
Design a media center
The gist of the question was that I was to design a media center. She mentioned it could be living-room based, portable, or however I wanted to make it. That was the original specification. I asked her clarifying questions such as: Is there a target audience? (No) Is there a budget? (No, the sky is the limit) Is there any specific other requirements I should be aware of? (Nope.) So at that point, I had to come up with something- anything - that would play video, music, pictures… etc. I decided to go for something rather interesting (to me) and designed a $2.5 million media center.
Young Electric Sign Company - in Las Vegas - has an awesome semi-truck design that they build for use at big events like concerts and the like. The truck uses a standard wide-load trailer and stores a LCD screen on the back of it. The screen is split into two pieces so that the truck can drive under bridges and such - and once it is as the location it will assemble itself into a gigantic screen and then use a hydralic lift to put the screen in the air 30 feet. The result is a 16 foot by 24 foot monster of an LCD screen that you can rotate around for different viewing angles. This was the screen on my “media center.”
I specified that this media center would be used at concerts and large gatherings of people - and built all of my features around that goal. It would be controlled by a technician working inside the truck. I went on to describe the intricate details of the interface for the person controlling it… etc. She asked me a few questions along the way about different aspects of it, and I would go on to describe them to her. I think I framed my answers very well and did a good job explaining my reasoning behind my decisions. At no point along the way did I stumble and say “Hmm… well - you could to it this way or this way, I don’t know.” I had clear and concise reasons, and by the end of the thing I really wanted to buy one of those trucks. If only I had $2.5 million.
That question went on for a long time. I had a lot of details. I think that my presentation of my ideas was well thought out - and she seemed to be enjoying hearing my ideas. It’s probably completely different from what she was expecting. I wasn’t really trying to show off any kind of “out of the box” thinking - that was honestly the first idea that came to my mind when she removed any limitation of budget, size, or specific target-audience. I’m sure she’s heard a million people describe a standard media center a lot.
Programming question
The next question was a programming one. I was asked to take an array of integers and return an array that had even integers from the original array, followed by the odd integers. I came up with a few methods to do it. I picked Java - (I should have picked “C” - it would have made coming up with different methods much easier). She kept asking me “Can you think of a better way?” My first method was order “n” (meaning it takes the same number of calculations as there are integers in the original array to compute the result.) When we got done I asked her what the fastest way, and she mentioned a method that was a little better - it would only use on average “n/2″ calculations. It was s simple method that I should have thought of in the first place. It’s been a long time since my programming problems have involved sorting - but I think that they view it as some kind of “if you don’t know how to do this, you wont know how to do much else.”
The interview environment
I didnât wear a suit to the interview - because between the lines in most of the Microsoft recruiting blogs they said not to. Iâm glad I didnât - my interviewer was dressed somewhere between casual and business casual - and didnât really seem to care about what I wore. I think that if you wear a suit to a Microsoft interview that you are starting off down a point or two in the mind of the interviewer - who is trying to evaluate both your competance and your âfitâ within their organization. One thing that was also interesting about this interview was that she had a laptop open and was taking notes on it the entire time. I was a big dell laptop. It didnât bother me, but it was an interesting departure from the open space that most interviewers like to keep between them and the interviewee.
Overall Impressions
I’m not very worried about not scoring so high on the programming part. Either she really liked my over-the-top media center response or she hated it - and that question was more related to the skills needed for the job I was most interested in - the Program Manager
In any case I expect to hear back from them within two weeks (hopefully sooner) about a possible second-round interview.
For those of you who are in the job-hunt, let me recommend to you Career Builder.com:
November 12th, 2005 at 8:40 pm
Good luck Ryan! is this this one in mn? =)
November 12th, 2005 at 9:32 pm
No. Microsoft is in Washington state.
November 16th, 2005 at 10:47 pm
Microsoft is in many places — there are a couple offices in the SF Bay Area. The mothership is in Redmond.
November 17th, 2005 at 12:28 pm
I’d be interested to see how the problem could be solved in O(n/2).. i shtis assuming a random array as input?
Good luck with the interview process!
November 17th, 2005 at 12:41 pm
It wasn’t a pure O(n/2) algorithm. I believe it would technically be O(n) in the worst case, but it should be faster than that in most cases.
The algorithm is simple: Make an index to the last item. Start at the first item, if it is even, move to next item. If it is odd, swap with the index to the last item, decrement the last index. Check to see if the new one is even or odd… etc.
My method was go through the array. Build a new array of the same size - keep an index to first and last item. For each integer, if it is even put it towards the front - if it is odd, put it towards the back. (So evens build front to back, odds builds back to front) When you get done, you are done. It’s always straight-up O(n).
I have been thinking in the back of my mind about ways to do it differently. I’ve been tooling around with how you might be able to use bitwise operations to rig up something, but I’ve not really tried very hard to get anything to gel. (Simple idea, one bit will tell you even or odd… build something out of that and play around)
November 17th, 2005 at 4:33 pm
The O(n/2) algorithm would be:
void evOd(int a[], int size)
{
int temp;
int i=size-1;
int j=0;
while(i>j)
{
if(a[i]%2==0 && a[j]%2==1)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
i–;
j++;
}
else if(a[i]%2!=0) i–;
else if(a[j]%2!=0) j++;
}
}
November 17th, 2005 at 6:29 pm
Jackline’s alg to test on the following goes forever
{ 2, 3, 5, 8, 9 }
November 17th, 2005 at 6:36 pm
else if(a[j]%2!=0) j++; ===> else if(a[j]%2==0) j++;
November 18th, 2005 at 10:52 am
or
else if(a[j]%2!=1) j++;
Sorry, for the typo!
November 18th, 2005 at 12:58 pm
That’s what I thought, your interviewer was wrong - this is O(n) which ever way you look at it. For an array of n integers you make n checks. All this moving around to the end of the array doesn’t get around the fact that one way or another you have tested each value so it’s O(n).
I think your way was clearer and much more obvious, and still O(n) so you get full marks from me.
There’s no other way of doing it unless you have some prior knowledge about the array, and even then it’s unlikely to get you better than O(n).
I have to say that’s a pretty disappointing interview question… unless she was expecting you to correct her of course. In that case it’s a sneaky question:-)
I’m not going to bother fixing Jacklines code, but believe me it actually makes *more* than n comparisons, no way is it better than O(n). In the case of the sample data from CTan it makes 7 comparisons - don’t be fooled by the fact that sometimes it does 2 on one line, it still does 2 comparisons on that line (and yes, I know it short circuits under some conditions) and often it checks the same value twice. Sorry.
Anyway, did you get the job?
November 18th, 2005 at 1:03 pm
It was just a screening interview. She never really said it was O(n/2) - and she only told me that method when we were done the coding part and she asked me “Do you have any more questions?” and I asked: “What is the best way?”
I’m still waiting to hear back from them if they are going to interview me in Seattle. I’ll keep you all posted when I get done.
November 18th, 2005 at 2:11 pm
I still prefer your way, much easier to follow!
If I was interviewing you I’d have said you did OK with the simple answer you gave, I like simple answers. Then again I’d have asked you a harder question to begin with:-)