The Microsoft Interview Revealed
This Monday I had an interview with Microsoft for a summer internship position. I decided I would go for the Software Design Engineer in Test. It’s a job that involves writing code to break code, writing secure code, profiling, and a lot of debugging–all things I enjoy. For my classes, I’ve written software compilers that don’t crash on mp3s, games that persist even if the AI or the server dies, and databases that even silly users can’t ruin. It’s interesting how much testing goes into good software. I’ve written code to write testcases for other code, and turned in 40 pages of SML test code for one CS312 assignment. You can see how much I enjoy it!
After we discussed the position, I was asked to write a piece of code to take a 7 digit phone number, and generate all possible combinations of the letters in their 7 places. Imagine a slots machine with 7 spinners. The problem is to write out all the possible slots combinations you could arrive at by pulling the level and spinning each digit. (Aside: I was tempted to write this as a random problem, and draw a random set of digits until I had exhausted the set space. I resisted.)
Here’s simple code to solve this Microsoft problem:
public void myCutiePie(char[] in, int level){
if(level == in.length){
System.out.println(in);
return;
}
for(int j = 0; j < 3; j++){
char temp = in[level];
in[level] = getNextLetter(temp, j);
myCutiePie(in, level+1);
in[level] = temp;
}
}
The getNextLetter() function just takes a digit and returns the appropriate letter. It’s just a little bit of character arithmetic that I didn’t want to write in an interview without an ASCII reference. Of course, the interviewer didn’t mind, since that wasn’t the point. When I was done, after a false start where I wanted to generate all the combinations of all the letters, he asked me:
How would you test this code?
Well, if I had a better method of generating these permutations, I could test this new one against the verified output of the old one. I would test cornercases–sorted , unsorted, and alternating arrays of digits. I’d test invalid inputs, like an array of size 0, or in a loosely typed language, another datatype. I’d also test some random, easy to check cases, as well. After he looked at my code, he said:
That’s an interesting way to write it.
Apparently he was expecting me to nest 7 for-loops… which is not my idea of good code. And, it would have filled up the whole page. Icky. The next brain teaser was
How do you cut a cake in half where some rectangle has already been cut out?
You have to bisect both rectangles and cut along the line formed by the points of bisection–but he had to walk me through that. Geometry and cakes is not my strong point. After that, we talked more about the position and my qualifications.
All in all, the interview went well, and the famous Microsoft brainteaser coding question didn’t seem as hard as last year’s, where I was expected to reverse a string in place, by word.
Update: I should have mentioned that duplicates were considered OK.
Update 2: My outer loop was duplicating the results from the recursion. No point in doing that!
| This entry was posted on Wednesday, November 3rd, 2004 at 8:28 pm and is tagged with software design engineer, summer internship position, digit phone number, ascii reference, microsoft problem, slots machine, software compilers, writing secure code, random problem, good software, test code, println, public void, interviewer, arithmetic, level 1, digits, combinations, little bit, lt. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback. |
24 Responses to “The Microsoft Interview Revealed”
Leave a Reply
I’ve gotten the “reverse a string in place, by letter” question, which is no walk in the park!
It seems like you did a pretty good job on your interview. What groups were you interviewing with?
I’ve been an MS intern twice, and it’s an experience that’s worth every minute. Not to mention they pay well.
Well, I selected Server, OS, and I think one more of the hardcore groups to interview for. We’ll see how they like me or not!
Hey, did you ever hear back from your interviews?
I’ve been following your site pretty closely–I have to admit it was more than a little inspiration for the new version of my site. I started with Kubrick and then modified it in all different directions.
I like how you’re starting a blogging network–are you pulling your fellow students to be members of your editorial staff?
Yeah, my Microsoft interview went ok, but I need to work on being more vibrant. Interviews make me quite nervous!
some how I don’t feel you code is right. Is in[] the original ph number. If it is, then your code is wrong. You are changing in[] in the recursion process. In that case how can you read the digits of ph.No to temp variable? Since in[] is input , it’s length will be 7. That means for each recursion you r looping it 7 times. This is not correct. Did you get the correct output for this code??
Oops… now I got it… you are again assigning the temp to in[]. Still that doen’t explain you looping it 7 times in each recursion. On total the function is called 7^7 times in your code.
I guess you can safely remove the first for loop
Nope. The first for loop is needed–and it works, I promise, except for maybe a typo or something.
For each digit in the phone number
For each letter corresponding to that digit
recursively invoke
End
End
You need to swap in three different letter choices for each digit (there are 7, usually) in the input. If you pay attention to the bounds, you’ll notice that only about 7! calls are made, too, because the number of calls decreases by 1 everytime.
[...] st three matches are Ludacris lyrics, ethical blogging, and finally something useful–Microsoft interview tales. Now, take a look at what I get back w [...]
Microsoft Interview
About the cake… if the cut out portion lies within one half of the cake, then you can simply cut out it’s mirror image on the other side of the cake. Then cut both the “new” piece and the remnant of the original directly across the middle. A piece of the new rectangle and a piece of the original cake will add up to half.
A few points I would make regarding all of this.
First, kudos on using a recursive call - I’m sure if you did try to nest seven for loops they’d ask you to extend your code to a 100-digit number. I haven’t compiled and run your code, but on inspection I see one enhancement and one bug/issue/problem. The enhancement is a performance one, which the compiler may do for you, but to make it explicit you only need the middle two of the four lines to be in the inner for ‘j’ loop.
The bug/issue/problem isn’t in the code but in phone numbers. I’m looking at my phone now and the ‘7′ and ‘9′ have four letters tied to them. Your for ‘j’ loop is hardcoded for only ‘3′ letters. Not a big deal. Just some extra code for the special cases I guess. The important part is your code is recursive.
Second point is in testing the code. Two special numbers I’d be keen on testing are ‘0′ and ‘1′ since they don’t have three or four letters associated with them. In fact, that’s a good question to ask on how to handle them before you even coded the algorithm. Understandable how you’d miss that since you deferred coding getNextLetter(). Beware of abstracting code thought to be no-brainer busywork.
My final point is also in verifying the code. You can run this code on a 7-digit number and come up with a list of 7-letter strings. I’d take some assurance in knowing the number of unique strings produced agreed with, and here’s where I admit I’m weak on counting theory, the combinations or permutations or whatever of 7-digits crossed with three or four letters per digit. I guess order matters so it’d be permutations? Anyway, I’d first inspect that the algorithm produced a few correct answers, then I’d look that the number of answers agrees with the predicted counting amount.
For my background… I’m a six year veteran of hardware design verification for a major networking company, and I’m in the interview process with Google. That’s what’s brought me to this site; research for my onsite interviews. I’ve also had interviews with major Wall Street banks so I’ve seen the whole brainteaser side of the equation, too.
In my first Google phone interview I was asked how I’d verify that a random number generator was truly random and to compare and contrast C++ vs. Java. I hope that helps some SDE/SDET candidates out there.
I don’t know why I can’t get this out of my head. I still haven’t gone as far as compiling and running your code, but I think there are more problems with it.
Shouldn’t your for ‘i’ loop go from level up to in.length() instead of starting at 0? Every new call of myCutiePie() will be starting over at the beginning, only the new beginning on in[] will be a letter instead of a number. That’ll give getNextLetter() some trouble.
And when you recursively call myCutiePie() I think you need the 2nd param to be (level + 1) instead of level++, for a couple of reasons. You shouldn’t be able to or allowed to modify level since it’s a pass-by-value param (although I’m a C++ coder and maybe it’s a Java reference var and is ok?). Regardless of it being legal, it’s still not giving the incremented version of level to the next call of myCutiePie(). Either do ++level or (level + 1).
It seems like there is always a right way, a wrong way, and a Microsoft way to do things. I’ve interviewed with them as well and they had me write a similar function. I think that asking a programmer to write code during an interview is silly. The environment that you work in when you write code is vastly different. I bet they’ve passed up tons of talented programmers because they weren’t good at jotting down code with paper and pencil while the interviewer watches. Kudos on the recursive approach… Having 7 for loops is a silly way to solve the problem.
There is another bug in the code!
I think this code is wrong. from a mathmatical sense.
# of permutation of 7 is 7!..
but the program generates 7*3 calls first, then each call generates 7*3, then … which and goes 7 rounds( if u start level at 0) …
the result is way more than expected and loaded with repeats.
rite code would be something like:
for each digit behind and includes currentDigit
swap with currentDigit
recursive call (move the currentDigit to the next)
end
* currentDigit start from 0, end at length-1.
the point is, 1 loop, not 2.
An important thing that you seem to be missing is that the numbers of the phone number don’t move around. You take:
6072290623
and make
m paaw mad
m pabw mbd
m pacw mcd
So, there’s no need to do any swapping in the main loop. This is not a permutations problem.
http://www.emicrosoftinterview.com is good guide for microsoft interview questions
How different are SDE interviews from SDET interviews.I have a SDET interview with MS in 2 weeks..how should i prepare.
I run across http://www.technical-interview.com which provides questions and answers from G and MS interviews
typically how many interviews are conducted with MS?i recently interviewed in-person with microsoft for SDET position. i had 4 rounds. i did well with all of them. but i did not have a 5th interview. is it always madatory!!! i am still awaiting results..!
I ran into http://www.emicrosoftinterview.com which provides all Microsoft Interview Questions
I’m not sure if anyone reads this page anymore…. but I would like to point out that the code for generating all possible letter combinations is indeed minorly flawed.
As Bob pointed out, ‘i’ should start from level, not 0. In fact, ‘i’ should only be equal to level - it should not increment until length. Consequently, Rakesh is also correct: the first ‘for’ loop is in fact, redundant. The code may be corrected completely by eliminating the ‘i’ for loop, and subsequently replacing ‘i’ by ‘level’ in the following 4 lines of code inside the ‘j’ for loop.
[...] An interesting account — with code samples! [...]