Friday, March 19, 2010

Passing the Microsoft Interview

As you know, I work for Microsoft - specifically on the bing.com team, more specifically on the core core relevance team (yes, that's two cores...don't ask). Even more specifically on the anchor team in the core core relevance team of bing.com in Microsoft. Wow, that's a mouthful.

Anyway, bing is hiring and that means I'm interviewing a lot these days. I'm doing at least one interview every other week, sometimes more. In addition, not many people are passing. So, to help everyone out, I thought I would put together a list of tips to help you pass the Microsoft Interview.

Tip #1: Know your stuff


Yeah, easier said than done. However, there are a number of resources out there that can help you. I've listed them in a previous blog post, so study up and have a good understanding of data structures, algorithms, and Big O notation before getting here.

Tip #2: Understand the problem


A lot of people encourage you to ask lots of clarifying questions. I think that is good practice and would also encourage you to do it. In addition, I think you should also spend quite a bit of time at the beginning to list out examples, both positive and negative.
Let's use a concrete example. One question that I see posted all over the web is to write a function to take a string as input and reverse the order of the words in the string. So, for example, "Hello World" would get reversed to "World Hello".
The first thing you should do is ask clarifying questions. Here are some examples:
1) Should I reverse the string in place, or create a new string?
2) What is the return value for the empty string?
3) How should a null pointer be handled?
4) What constitutes a word separator?
5) ASCII or Unicode?
6) How should punctuation at the end of the string be handled?
7) What about capitalization?
8) Is it a c style string or are embedded nulls allowed?

Now that you have fleshed out the problem, the next thing to do is think of some example inputs and see what the outputs would be. I would think of this in a tabular format with input on the left and output on the right







inputoutput
nullassertion failure
""""
"Hello""Hello"
"Hello world""world Hello"
"Hello from Microsoft""Microsoft from Hello"


There may be more examples depending on the answer to the clarifying questions, but these would be the minimum examples necessary. Go through each example with your interviewer and make sure he or she agrees with your mapping function.

Tip #3: Describe the algorithm


After you have created your examples, but before you start to code, describe, in English, the algorithm you have devised. First, this helps you to think about the algorithm before you code it and second it gives your interviewer a chance to hint at the right solution if you missed it. If, instead, you immediately start coding a poorly performing algorithm, you give your interviewer no choice but to sit idly by while you waste his time coding something he knows won't work. If you, instead, discuss the algorithm with the interviewer, it gives him or her the chance to point you in the right direction and lets you write code that the interviewer wants to see.

In our word reversal example, you might start by describing an algorithm whereby you find the first space and the last space and then swap the words and repeat until the spaces are the same. The interviewer might ask you about the complexity of this approach and then ask if there is a less expensive algorithm. Doing things in this order makes sure that you are coding the algorithm the interviewer wants to see.

Tip #4: Don't mention a naive algorithm to fill time


The interviewer has asked you a difficult question. You're not sure of the correct way to solve it. Don't just mention the first, most naive, solution that pops into your head. If you think your first solution is a good one, then by all means mention it, but if you know it sucks and is O(n!) or some such nonsense, then stop, think, and come up with something better. By giving a poor solution to begin with you are just giving the interviewer a reason to reject you. You don't have to get the right solution to begin with, just make sure it's not horrible.

Tip #5: When coding, make sure you check your boundary conditions


Nothing sets me off more than when someone forgets a null check or a boundary condition check. This is just Engineering 101 and is critical for a system such as bing. If you can't be bothered to check for null in all the right situations, then don't even apply. Sure, everyone makes mistakes, but in the interview keep null checks on the top of your mind.

Tip #6: After coding, run through your examples and make sure your code works


I've seen too many people write code on the whiteboard, spend 5 seconds looking at it, and then say "Yes, that looks good." There is NO way you have tested it in your head after 5 seconds. Even if it is correct, how do you know? The best thing to do is to use your examples that you generated to walk through your code. You might discover, for instance, that you assumed there would always be a space, when there might not. This gives you a chance to correct your own mistakes without forcing the interviewer to intervene.

Tip #7: Ask questions about the interviewer


This is just good psychology. Make the interviewer feel important by spending a few minutes at the end asking about the interviewer's team and work. The benefit to you is that you get to hear about the day to day activities and make sure they sound interesting. The benefit to the interviewer is that he or she gets to talk about his or her exciting projects. This leaves the interviewer with a good feeling leaving the interview, which is always a good thing. So, the next time you are stuck without a question, ask the interviewer to tell you about a recent project - and hopefully it excites you both!

There you have it, 7 tips on getting through a Microsoft interview. Of course, I honed in on coding, but many of the same ideas apply to the design based interview questions, as well. Regardless, be prepared, be confident, and most of all, have fun!

24 comments:

Consultuning Services said...

I can see a lot of problems with your way of selecting candidates.

The first is that the problem is stated in an ambiguous form. "Reversing a String" is not concise enough. The following examples could be all valid:

"Hello World" -> "World Hello"
"Hello World" -> "dlroW olleH"

And yet only one is allowed.

The second, having a "bad" solution is much better than having none at all. If the Bing team is judging people, and implementing its system always counting on people delivering the best solution as their first one, then Bing is headed to failure.

The third is that you're committing the same mistake that Google is making. Assuming that people can keep in its head every detail of complex algorithms is asking for waling enciclopedias, not creative workers. If you want a good example of why this is counter to make progress, check the story about the cat map in "Surely you're joking Mr Feynman".

All those together don't make me exactly crazy for landing a job at Bing.

albert said...

Such simple test which everyone should pass after taking part on a computer science course in school for one year is the skills you are asking for new employees? That is not much more than an advaced Hello World! Even more sad that people fail that test...

Anonymous said...

Slightly OT, but does core core relevance team mean you are responsible for the returning relevant results for broad searches rather than deep ones?

I ask because it appears that, in the US at least, Bing has surpassed Google in returning good results for popular terms, but is still woefully behind in terms of long tail and deep searches.

Tim said...

Tip #4 precisely contradicts one other "principle" that is bandied about on the intertubes in programming blogs: Do The Simplest Things That Could Possibly Work.

I'm not an agilist, I just making an observation.

Anonymous said...

On similar lines as tip#5, how serious will you consider it if a candidate forgets about checking for 'new' operator returning NULL? I recently did this in my phone screen and wondering.

Tanton said...

Hi Consultuning Services,
First, the problem I mentioned is not used by us in hiring. I just found it on the web and thought it would be a good problem to use for examples. It was simple and straightforward.

As for being ambiguous, most of the time real world problems are ambiguous, how you manage that ambiguity is important.

Second, this has been the most contentious tip on the blog. I do agree that mentioning the naive solution is ok if you immediately springboard to a better solution. However, if you stop at the bad solution, that's not good. Notice I never said you had to come up with the best solution as your first one. I'm not sure why people read it that way. In fact, I tried to go out of my way to mention you didn't have to find the best solution. Instead, find a good solution (where good is O(n^2) or O(n^3)) and move on from there.

Is this how things happen in real life? No, definitely not. You find the first thing that works and you optimize when necessary. However, in real life you typically don't have to reverse words in a string. In addition, if you do have to do some complex algorithm magic, we need to be sure that you are capable of that.

We definitely don't want you to keep everything in your head. Talk about it, use the white board, explain your ideas. My tip was merely to say if given the problem: "you have a sorted 10 million element list, how do you find a given number" the answer is never "linear search". I'm not even sure saying linear search adds anything to the discussion, so if you need to talk about something, talk about edge cases, examples, etc... to get your creative juices flowing, then bring up the better solutions (not necessarily the best).

Tanton said...

Hi Albert,

No, we don't ask this question. As I mentioned in the blog, I found it on the internet.

Thanks for reading!

Tanton said...

Hi Anonymous,

No, core core relevance doesn't mean that. The team I am on is responsible for both broad and deep searches.

Tanton said...

Hi Tim,

An interview setting and a real world setting are often different :-) I do agree with the "simplest thing" principle; however the types of problems for which that principle is designed are not typically the types of problems you get in interviews. In addition, in an interview the interviewer wants to see that you can handle the complexity and can "go deep" on the problem.

Tip #4 was never supposed to read "don't speak until you have the perfect solution". Instead it was intended to read "don't mention stupid stuff." Use your time and the interviewers time to delve deeper into the question so you can at least give a "medium good" solution. Giving a bad solution, to me, just means you couldn't be bothered to think of anything better. I know a lot of people disagree with this sentiment, and that's fine, but it's my opinion and I'm sticking to it :) Unfortunately, I don't think people have understood what my opinion is...

Tanton said...

Hi Anonymous@10:51,

operator new in C++ hasn't returned null in a long time. Now, it throws an exception if it doesn't work. And, in most cases, it wouldn't do any good to catch the exception, so I wouldn't count off at all.

Gayle Laakmann said...

Interesting - I (founder of CareerCup.com) encourage people I coach on technical interviewing to mention the dumb, brute force solution. I do this for three reasons:

1) The brute force solution might be a pretty good one.
2) Even if it's not, it may be a good starting point to optimize from.
3) It can't hurt you to say "here's a brute force approach, but it's bad for these reasons." That shows how you're approaching the problem, while showing that you can analyze problems in a solution.

I strongly recommend this approach. (And I've interviewed 120+ people for Google, and run CareerCup.com dedicated to coaching technical interviewing.)

So, candidates: please mention the brute force solution, or at least realize there are differing view points on this.

Tanton said...

Hi Gayle,

Thanks for the comment! Yes, people should always realize there are differing points of view. And, if all you can think of is a brute force solution then by all means you should give that and let the interviewer drop some hints. Don't sit there in stunned silence hoping the answer will come to you.

My advice was intended to say: when answering a question, start by examining the problem not the solution. If you start by describing a brute force solution before you have thought about the problem you are doing yourself a disservice.

In the end, if you do mention a brute force algorithm, try to describe when it might be useful. A simple linear search is quicker than binary search if the number of elements in the array is trivially small, for instance. Then, move on to when it isn't useful and start talking about how to craft an algorithm that best handles those scenarios.

Please, don't sit in silence leaving your interviewer wondering what you are thinking. That is just nonsense and I never meant to imply that you should do that.

PuTTYshell said...

Hi, Gayle,

I am a developer of a middle sized company.

I agree with Tanton about starting the conversation by clarifying the problem rather than diving into the solution.

There are a few drawbacks about the brute force method:

1) More often than not, the brute force method is not the answer the interviewer is looking for. Sometimes, it wastes time.

2) The brain tends to stop work once you have a solution. Starting the conversation with a brute force method is especially bad because the interviewer is convincing himself that this method works and can be optimised.

3) It is more natural to repeat the problem and give more test cases right after the question asked than 'solve' the problem according to his own understanding.

IMHO, it is important to use a few minutes to clarity the scope of problem to solve as Tanton said.

Umesh said...

Well, I applied the technique in my coding interview at Bing and regret it totally now. I performed at my worst on the day of interview.
I focused more on the boundary conditions and make silly mistakes about main logic. To be fair, I would say, practice this technique well and enough number of times before you apply it in interview directly.
My coding style always has been to write the main logic 1st with only most obvious boundary conditions and handle non obvious ones later.
Another tip : Don't get conscious and bogged down. I will say following CareerCups book is far better.

Tanton said...

Hi Umesh,

I'm sorry it didn't work out well for you. One should always practice and interview at a few secondary places first to get warmed up. Additionally, I would say that you should do what works for you. If you've had success at interviews before, then by all means stick with that approach. Don't change just because I or anyone else recommends it.

Hem said...

Hi Tanton,

You said that you don't ask this kind of question in interview but I was asked same kind of question in interview and I suggested efficient solution to the problem. And coded it well. Later they provided me feedback that they didn't like my coding style :-o. Do you select people based on their coding style ? If you select people based on their coding style then why bing don't provide it's coding style document to be followed during interviews ?

Tanton said...

Assuming your algorithm was correct, I would not judge your coding style. Seems a bit silly to me. Where you put curly braces on a white board should never affect the outcome. I'm sorry your experience wasn't good and I wish you luck going forward.

The Sapient Mind said...

Not to play the "Thread Necro" card here, but I recently went through this process, and it was exactly as you described. The position I was after was not a dev role primarily, more engineering/dev hybrid, which threw me for a loop when asked dev-focused questions in two out of four interview sections. I think recruiting could do a better job of clarifying the expectations for the interview, so I don't waste everyone's time (and my own) meeting for a position that is not what I expected at all.

The first code-focused interview was centered on log-parsing, conversion, sorting, and reporting (after a 10 minute introduction, leaving approx 45 min for pseudo-code and discussion/clarification).

The second was nearly the same, but with a focus on doing the above in a multi-target environment, with database goodness lumped in.

Neither of these were at all very difficult, but for someone like me who writes slow and takes time to think things through, I felt the time-pressure.

Also, to anyone reading this -- be forewarned that English may well be the second or third language spoken by your interviewer. If you speak one of their native languages, lucky you! If not, prepare to waste extra time clarifying things due to communication barriers and or difficulty hearing accents. All this counts against you, if it pushes you past the allotted time.

Despite all this, I did a passable job, but "lack the experience they needed for a senior service engineering role", getting a "hire for Microsoft, no hire for the role" result, which I guess is better than the "no hire/no hire" result for sure. I wonder how it would have gone if they hadn't switched my interviewers literally at the last minute to two dev leads instead of two service engineers.

I suppose I should have suspected that outcome when the last "As Needed" interviewer of the day was "unavailable"; at the time I shrugged it off, because he is the director of the particular org, and very likely to be booked weeks in advance.

Sorry Mario, but your princess is in another castle.

Anonymous said...

Recently, a Microsoft interviewer asked me exactly this question. I did not know about this post beforehand, and I never heard the question before nor had practiced in any way for it.

Nevertheless, I did exactly what you suggested, asking exactly the same questions you suggested (amazingly!), and came up with a linear time solution with little help.

I was told I bombed the interview.

Mind you, I also found that the intelligence/skills/knowledge of this group to be questionable. I had a question posed that betrayed the fact that they knew only their little universe and nothing else. I found all technical interviews to be unchallenging.

I was disappointed by what I saw at Microsoft. Doesn't matter, as they were apparently disappointed with me.

Tanton said...

@Anon, I'm sorry your experience wasn't very good. Microsoft is a great company, but it has over 90,000 employees, so there is a high variance in the quality of the different teams. You should definitely try again with a new team. In addition, I would strongly recommend buying "Cracking the Coding Interview" by Gayle (who commented above). That book is freaking amazing and is really the only study guide you need.

Praveen Kumar said...

I hate when interviewers judge candidate on petty things like null checks. I am surprised it is emphasized so much in your blog post. The basic idea in the interview should be to get the main algorithm right. This is not an actual work day and the expectation from the candidate to pay attention to every stupid null check is not right.

sonia said...

hi congrats ,
i want to ask u a question ..i m appearing for microsoft interviews next week ..but i m already having an offer from oracle for oracle cloud services ..so should i tell microsoft about this offer or not ??because microsoft is my dream company and if selected i ll definitely join ms ..but i jst had this confusion whether i shud inform them or not ??pls suggest something ..

Tanton said...

Hi Sonia,

Yes, in my opinion, you should tell your recruiter. The recruiter can do things like speed up your interview process so that you are sure to have both offers in hand before you make a decision. In no way will it hurt you and it will often help you, so go for it and good luck!

Anonymous said...

Hi, I got through first 3 levels successfully. After every interview I knew that I did well. But the 4th level interviewer was all dull and gloomy. I felt his wife fought with him for going to work on Sunday. He dint ask good questions neither he heard my answers. He was totally in a different world. He rejected me saying i was 'over confident'. I felt really bad. My dream of joining Microsoft cant be ruined because of a persons mood. I wrote my experience in 4th level as a reply to the 'Regret mail'. I got a reply that they will nullify my 4th level and consider 3 levels results and conduct 4th again in June. Microsoft is super. Now i am waiting for further intimation. :)