The Old Joel on Software Forum: Part 4 (of 5)

I got the MS internship :)

Hey guys - I posted a couple of weeks ago for tips about interviewing for Microsoft, and just wanted you all to know I got the job :)

Details: I was applying for a Software Development Engineer position. They asked the following questions:

1: Given 2 sorted linked lists, merge them

2: Determine whether or not a linked list has a loop

3: You are on the 100th floor of a building with a cart of computer equipment that you need to get to the 1st floor. You call an elevator and get in, but no matter what button you push, the elevator just opens on the 100th floor again. How do you get to the 1st? (This one was open ended, I was allowed to ask a lot of clarifying questions).

4: Design a TV Guide sort of thing - it should hold information about channel, time, show, and episode, and be able to search amongst the records by any one of those features

5: Design a generic tree structure

6: Given a square board X spaces across, determine if it is a winning board (under tic-tac-toe rules - get X in a row to win) and return the winner.

7: Perform a depth first walk of a tree (using the design from 5)

8: Perform a breadth first walk

9: Draw a checkerboard Px pixels wide and Py pixels tall with Cx columns and Cy rows

10: implement a stack

11: now implement a queue... in 10 seconds.

All in all it was 5 interviews and took about 8 hours. The recruiter said I did "extraordinarily well" and that I could take my pick of the two projects I interviewed with - e-home (XP media center edition) and the avalon team (client interface for longhorn). I picked avalon! Very exciting :)

I'd be glad to answer any questions or anything other candidates have ~ thanks again for your tips everyone, they were very helpful :)

Riley Lark
Tuesday, March 2, 2004

"The Dark Side, tempting it is. Quick, easy at first, but a trap is the Dark Side. Corrupting, evil. Once you start down the Dark path, forever will it dominate your destiny."

Yoda
Tuesday, March 2, 2004

Congratulations, and much envy! ^_^

Mediocre ASP Monkey
Tuesday, March 2, 2004

Riley - Congrats on your achievement and thanks for sharing. I'm sure to learn something working on those questions.

Yoda - don't look now but you'e a caricature of yourself

seth
Tuesday, March 2, 2004

holy crap. an *8* hour interview? Congrats, but I hope they pay well. Your definatly seem skilled enough to be making some good money, so I cringed when I saw the "internship" word. Good luck.

vince
Tuesday, March 2, 2004

They asked me not to say how much I get paid, but I can say, "it's a lot." It really is a lot.

Like, I'd be happy to make this much as an entry-level FULL time programmer.

Really happy.

:)

Riley Lark
Tuesday, March 2, 2004

Oh, and yeah, the interview was really rather grueling. It was fun, though. They tell you at the start that "you'll get 3 interviews, and then one to two more if we need more information," which I took to mean "you'll get at least 3, but if you're doing well we'll try to break you down more." So it was satisfying to keep hearing I had "another interview scheduled" even though I was pretty exhausted. My throat hurt like crap afterwards - I was basically talking nonstop all day.

Riley Lark
Tuesday, March 2, 2004

Did you apply for a summer 2004 internship? When did you apply?

I applied about 3 weeks ago, and on their website was written that they would gather resumes for summer 2004 internships at the end of february. They now changed the website ( http://www.microsoft.com/college/intern/ ) and don't seem to be taking interns for summer 2004 anymore.

I didn't hear about them, and your comment makes me wonder if I should conclude that they are not interested.

Simon Perreault
Tuesday, March 2, 2004

I applied for a summer 2004 internship, but I first gave them my resume in October of 2003. Then, I had a 30-minute interview with them here at my college in Maryland in December, and they invited me to this big day-long interview in February. When they offered me a choice of day-long interview dates, the latest one was March 7th... I don't know if that means they aren't doing any interviews after March 7th or if it was just a distributing mechanism or what.

So, sorry, I don't really know what it means that they haven't contacted you ~ I did read somewhere that they get 12,000 resumes a month, though.

Riley Lark
Wednesday, March 3, 2004

Congrats, Gosh, I don't think I could answer half those question.

Though I did like the elevator question, it was a real-life puzzle. frustratingly fun.

Aussie Chick
Wednesday, March 3, 2004

"3: You are on the 100th floor of a building with a cart of computer equipment that you need to get to the 1st floor. You call an elevator and get in, but no matter what button you push, the elevator just opens on the 100th floor again. How do you get to the 1st? (This one was open ended, I was allowed to ask a lot of clarifying questions)."

If it was asked exactly like that, was "take the stairs" an option?

Philo

Philo
Wednesday, March 3, 2004

Congratulations, Riley. And this one goes into my favourites too.

Sathyaish Chakravarthy
Wednesday, March 3, 2004

> 3: You are on the 100th floor of a building with a cart of computer...

I came up with "Use another elevator". (A 100 floor building cannot have a single elevator only!)

I guess this is one of those questions impossible questions that Joel had written about:

http://www.joelonsoftware.com/global/English/Articles/Interviewing.html

Pupose of the question being only to test the analytical and out-of-the-box thinking ability of a person.

T-90
Wednesday, March 3, 2004

I think the stairs would be a viable option, if you had a lot of interns under your control ;_) Then again, perhaps the "computer parts" are only a keyboard and mouse.

You could open the elevator, keep the door open with the cart, pull the fire alarm, then enter the elevator. Assuming it's one of those automated systems that brings all the elevators to the bottom.

Or you could leave the cart in the elevator, call the person you need to deliver it to, who's on the first floor, to press the button for the elevator and get it themselves.

Knowing me, if I was in the actual interview myself, I would keep muttering, "Uhhhh. Ummmm." with a deer-caught-in-headlights look :_(

VP
Wednesday, March 3, 2004

*sigh*

I'm dying of envy.

Simon Perreault
Wednesday, March 3, 2004

ROFL - I'd think if you were stuck with a cart of computer parts (not another intern to be found) and 100 flights of stairs it would be:
SHOVE - on the first set, and
BOOT - for every-one following.

Perpetual Newbie II
Wednesday, March 3, 2004

Regarding the elevator question I'm afraid I would have to ask wtf they are doing sending highly paid software engineers to move computer equipment around. Don't they have people employed to do that kind of thing?

What was your answer, Riley, out of interest? Of the elevators that I have known personally there is a room at the top of the building where one can manually lower the elevator (what do you think happens if it gets stuck between floors with people in it, they just get left there to rot away?). VP's answer is a good one, very good in fact.

Wednesday, March 3, 2004

For the elevator question: just ring someone on the 1st floor from your cell phone to call the elevator when you are inside ;-)

R Chevallier
Wednesday, March 3, 2004

The elevator question isn't about answering or solving it, but it is used to see how well one can gather requirements. There are certain parameters you must know before you can solve it, and this question is used to see if you can think of enough things before you attempt the solution. If you just try to solve it without finding out what possibilities you have, how much time, how many parts, do you have a phone available etc. etc. then it would basically mean that you didn't ace that question.

That's how I've used similar questions when I interview people, though I've always had a question more close to programming. Like (this is a free translation - I'm not a native English speaker) "a customer is asking you to build a report that would list all their maintenance duties that are late, so that they can dispatch an extra maintenance guy to help out on the field. How would you start doing it?".

Now, the answer that I like is of course that whoever I'm interviewing starts asking me all sorts of questions about what sort of maintenance does the customer have, and how is it determined that something is late and so on, and the "wrong" answer is to start explaining the solution right away (unless of course the solution is so good that it will work no matter what, but I haven't heard that one yet ;-)

Antti Kurenniemi
Wednesday, March 3, 2004

The damn elevator was on service.

Just hold the "door close" button until the door closes. While keeping "door close" held, push the first floor button. You can let go of "door close" once the elevator starts moving.

David Jones
Wednesday, March 3, 2004

Does such a thing as a 100 floor elevator exist?

Pietro
Wednesday, March 3, 2004

There's a building called "Taipei 101" with 101 floors.

Christopher Wells
Wednesday, March 3, 2004

The elevator problem took me about 6 or 7 minutes of saying things like, "let's see, my assumptions are that 1: I cannot get another elevator no matter what because this elevator is fooling the system into thinking I already have one, and 2: my only interface is the buttons inside the elevator and the call buttons on the outside. Those assumptions lead me to conclude the problem is impossible - how can I challenge them? Hm. I can walk to another floor without my computer stuff and call a different elevator." At which point the interviewer said "the same elevator comes down to whatever floor you were on, and has the same problem." So I said, "oh! Call someone on the first floor and have them press the call button." And he said "when the person on the first floor calls, a DIFFERENT elevator comes to them." And I looked at him and said "..." and started to get nervous ;)

If you guys want the answer you can check out my crosspost at gamedev.net: http://www.gamedev.net/community/forums/topic.asp?topic_id=210882

Riley Lark
Wednesday, March 3, 2004

Very interesting questions. Does anybody know if Microsoft asks the same questions for people that have been working for a while?

When I graduated from university I could have probably answered many of the more theory-focused questions... but after a few years on the job it becomes a little more difficult. :) However, I can see that these are great questions for someone fresh out of school.

(It certainly wouldn't be difficult to review some school notes and very quickly gain back the knowledge, however.)

2_legit
Wednesday, March 3, 2004

Given that it was MS, the elevator not moving was a feature, not a bug, and the user will just have to wait six months for a patch. The issuing of a patch does not mean that liability is accepted for any losses which may have occured because of the users' misuse of a perfectly good elevator.

Do I get the job?
Wednesday, March 3, 2004

Is there any clever answer to the #6 tic-tac-toe problem? And how detailed did the solution have to be?

My first thought is the bruteforce solution where a winning position is one where it's your turn and either:
- a move immediately wins the game
- a move exists such that the game doesn't end immediately and every response by the opponent will result in a winning position

That shouldn't be hard to implement if I get to choose the language, and optimizations like caching are possible. However there might be a more clever solution I'm totally missing, like all boards with size > 4 are non-winners. (I guess the fact that the # moves goes up as the square of sides has something to do with it?)

Tayssir John Gabbour
Wednesday, March 3, 2004

Make sure you wear a linux T-shirt to your first day on the job.

hoser
Wednesday, March 3, 2004

If there is only one elevator, put the stuff in the elevator, take the stairs down to the first floor and push the button.

pdq
Wednesday, March 3, 2004

Not being able to take an elevator from a 100th floor is potentially dangerous; you're supposed to be able to evacuate these tall building. Call the building's superintendent or your floor's emergency coordinator.

Christopher Wells
Wednesday, March 3, 2004

All of you who walked to the first floor are going to have to turn around and climb back up 100 flights of stairs. There's a mechanical problem with the elevator. Likely a stuffed penguin got squished on floor 99.

Wednesday, March 3, 2004

Tayassir,

Yes, there is a simple, elegant way to determine if there is a winner in a tic-tac-toe game. I was given this problem in college.

dmooney
Wednesday, March 3, 2004

Good point about the squished penguin. So the elevator is stuck on the 100th. Everytime you push the button, the system thinks the stuck elevator is the best elevator to use, because it's already there.

You need the person on the 1st floor to send his elevator up to the 100th. Then you can take that one back down to the 1st.

VP
Wednesday, March 3, 2004

" Yes, there is a simple, elegant way to determine if there is a winner in a tic-tac-toe game. I was given this problem in college. "

What is it? I just checked all the rows, then all the columns, then the diagonals.

Riley Lark
Wednesday, March 3, 2004

Aah Riley, as I understand you now, it's just about whether a person can win immediately with one move. I thought the questiron was about finding "perfect moves" if they exist. So that if you play perfectly and the opponent doesn't shoot you, you will eventually win.

Still, one day I should figure out an elegant solution to tic-tac-toe.

Tayssir John Gabbour
Thursday, March 4, 2004

------"You call an elevator and get in, but no matter what button you push, the elevator just opens on the 100th floor again. How do you get to the 1st? "------

Do a clean format and reinstall; the elevator system clearly runs on Windows.

Stephen Jones
Thursday, March 4, 2004

With regard to the "perfect" Tic-tac-toe Occam's razor suggests that if brute force proves four is a tie, the answer is no for any number of rows and columns greater than two.

Stephen Jones
Thursday, March 4, 2004

In response to the elevator question:

On the other board you posted two pieces of information that trivialize the entire problem.

-you mean down to the 1st floor, 100 flights? Too many steps! Also, you can't be guaranteed the same elevator will come.
- when you call an elevator on the 99th floor, the same broken one comes, and the problem continues.

Here you said that on the 99th floor the same elevator comes down, but on the first floor, it's quite possible that a different elevator will arrive.

a) If at any time a different elevator does arrive, problem solved, take it to the 100th floor, load up your goods, go back down to the 1st floor.

b) At some point in time, there is going to be a cross over between the same broken elevator arriving and a working elevator arriving. Let's say this is the 50th floor for example. If at any time a working elevator arrives, revert to point a, otherwise, if the limit approaches and reaches the first floor, then you just put in the computer equipment and floor 100, and call the broken elevator.

Either way, the two givens contradict each other. You can't guarantee that either a different elevator will show up or the same elevator will show up, and this trivializes the problem.

In response to it being a lower floor that the boundary exists at, I figure if in a large rush I can decline 10 flights of steps in 1 minute, so 10 minutes to the bottom. In the time you spent figuring out the problem, and testing hypothesis on different floors, I've moved the equipment to the ground floor.

Besides, using the computer equipment to keep the door open? With this type of broken elevator, who's to say it won't start moving down when you call it from a lower level, and crush everything in between with the force of the several thousand pound counterwieght? Seems like an awful large risk to take. It may be faster (if you thought of this instantly) but it won't seem so damn smart if/when you deliver a pile of silicon remenants to the ground floor.

Elephant
Thursday, March 4, 2004

Jump in the lift (assuming it is moving in between opening the doors on the 100th).

Use a couple of floors to test. Does it take twice as long between opening doors when I hit 98th floor as it does when I hit 99th??

Extrapolate to ground floor. When you get to estimated time, hit the emergency stop, and force the doors open.

Tapiwa
Thursday, March 4, 2004

" a) If at any time a different elevator does arrive, problem solved, take it to the 100th floor, load up your goods, go back down to the 1st floor.

b) At some point in time, there is going to be a cross over between the same broken elevator arriving and a working elevator arriving. Let's say this is the 50th floor for example. If at any time a working elevator arrives, revert to point a, otherwise, if the limit approaches and reaches the first floor, then you just put in the computer equipment and floor 100, and call the broken elevator. "

I don't really understand your method.. are you saying you just keep going down a couple flights at a time via stairs until you get a working elevator, and then you either have a working elevator or you eventually get to the first floor? What about the scenario in which, right as you get on a working elevator, someone else on a different floor in the building calls for an elevator and your computer equipment gets launched to some random floor? You'll never be sure you can catch up to it, even if the elevator has some sort of indicator. My solution is guaranteed to work, barring criminal activity. Maybe I should leave a note on the cart blocking the door that it shouldn't be moved..

Riley Lark
Thursday, March 4, 2004

Good point. I never gave consideration to others asking for elevators at the same time. If that was not a consideration, then you could either go down a few flights of stairs at a time to minimize flights traversed, or do the stairs logrithmically to minimize the number of lift requests that need to be made.

With the fact that multiple people are requesting elevators, then your solution is the most elegant and is guranteed to work. I stand corrected.

Regarding criminal activity, you may want to consider locking the equipment in your office, and fliping the stop switch to lock the elevator on the floor.

Elephant
Thursday, March 4, 2004