dmorin's Journal: Microsoft Interview Questions

Finally got to interview at a place with an ex-Microsoft guy. Here are the the questions I got:

• You have one room with 3 incandescent lights, all off. You have another room with three light switches. Starting in the room with the switches, how many times do you have to go in the room with the lights in order to determine which switch controls which light? (Assume all the obvious stuff like you can't see the light through the door, and so on). There is an easy answer, which I got, and a harder one, which I got with a hint.
• You have a block of cheese. You wish to cut a smaller cube of cheese from the middle. How many cuts does it take. I got this one.
• Write "string reverse" on a char array, in place (i.e. without cloning the array). I wasn't happy with my answer to this one, I overthought it.
• Insert into a binary tree. (Not sure why he put this one in there, it seemed kinda easy. Maybe it was to see if I knew how to answer a recursion question.)
• Reverse a singly-linked list. Annoying pointer math.
• Count the set bits in an unsigned int. I gave him an answer he called "a good, brute force answer." This bugged me so much that the next day I emailed him a better answer. I even wrote "You probably don't care but my head will explode if I don't write this down."
• You have randomly distributed numbers from 1-n in an array of size n-1. In other words, one of the numbers in the range 1-n is missing. Determine which one. When I gave him a standard answer (since I knew this one) of "While iterating through the array once, make separate sums of i and a[i]. The difference at the end is your answer" he said "That's a good, optimal answer. Now give me a different one." That really threw me. Even when he showed me the answer he was thinking of I tried to optimize it for him (and couldn't).

MS quiz

[lucasw]

There was an article in the July Wired called 'The Microsoft IQ Test' about a book about Microsoft quiz questions: "How Would You Move Mount Fuji: Microsoft's Cult of the Puzzle".

I liked this one - you have 8 billiards balls, one of which weighs different than the rest, find it using a balance with two weighings.

The worst questions are the ones that are the most overused- and it shows the exact lack of creativity and smarts of the interviewer that they were trying to gauge in the interviewee.

Re:MS quiz

[dmorin]

I think that one is used alot. I've certainly heard it in a zillion logic puzzle discussions. What I wonder with those is, if you've heard it and know the answer do you come clean, or do you try to fake it and pretend like you're thinking it over? I don't think I could do the latter. The first one the guy gave me (find a missing random integer in the array) I said "I know this one." I'm happy to say, though, I that I knew it because I had come up with an answer, not because somebody told me an answer.

Re:MS quiz

[dmorin]

Well, I think I can do it in 3. We're assuming that the 3v3 is lopsided, therefore the bad ball is in there somewhere. Take two balls from pan A and set them aside. Move 2 balls from B to A. And put the 2 extra balls we had (which we proved are not the bad one) into B.

If the scale balances, then one of the two balls you dumped is the bad one. Hold onto this information for a second.

If the scale changes, then that means you moved a bad one from B to A, so it's one of the two that you moved. Hold tha

Re:MS quiz

[lucasw]

I really do want to know if it can be done in 2, though.

I guess I made it a little harder in my transcription- you actually know that one weighs heavier or lighter, so you do the 3 vs. 3 and take the heavier or lighter (accordingly) set and weigh two of them. One of the questions in the article was actually slightly impossible and the 'right' answer was to recognize that and come up with the closest thing as possible.

A slightly different version of the summation one could be to use the equations to sum

Re:MS quiz

[dmorin]

What was the interviewer's other way?

He said, "Create another array of size n bits. Iterate through the list and for every number you find, set the appropriate bit in the array. Then iterate through again and find the unset one." I mean, hey, it works. It's not anything special, but I think that was his point.

Re:MS quiz

[dmorin]

Ummm.... did you forget to give a piece of information? http://rec-puzzles.org/sol.pl/logic/weighing/bala n ce seems to say that the way you describe the problem, it is impossible. I looked it up cuz I was wasting too much time on it :). Part of a good answer is knowing when to set priorities and move on. :) :) If you have a number of balls that is divisible by 3 and know whether the odd one is heavy or light, it is a much easier puzzle.

String reversal

[tcdk]

I was wondering what you did with this one (that was to complicated).

My first thought goes something like

for i=0 to strlen/2
b = str[i];
str[i]=str[strlen-i];
str[strlen-i] = b;

Re:String reversal

[dmorin]

Yeah, for some reason I Was thinking that there might be an edge case when the length was odd vs even. So at the end I had sometihng like "if len%2==0 then swap one more time". Which was technically right cuz I was looking at that remaining digit, there was just no reason to swap it with itself :). Hence, redundant rather than wrong.