26 posts

## Interview questions

Back to Forum: Coffeehouse
• I thought it might be interesting to see what sort of interview questions people ask / are asked these days. I've been in ms for a while now so it's been a long time since i've experienced dev interviews anywhere else.

Here it's many many one hour sessions with different devs / dev leads etc, and the interviews are almost entirely technical -  whiteboarding algorithms / designs etc...

As this is a dev forum, i thought i'd post a couple of the questions i ask when interviewing ( or rather asked up until now  ) - so please post yours - these things are always fun to try without the interview pressure i think

----
( pretty much all ms interviews are stated in c, but an answer in any language would be ok in an interview... )

Given an array of ints 'a' that's sorted, write a function with the following prototype:

Node * CreateTree( int * a, int start, int end );

which takes the array and inserts it into a binary search tree so that the tree ends up balanced.

For example given a = 1, 3, 5, 6, 7, 9

you would call CreateTree( a, 0, 5 ); and expect to get something equivalent to ...

5
3   7
1    6  9

Node is just a basic tree node, and the function returns a pointer to the root node of the created tree.

----
( i sometimes ask a puzzle / non-cs question..this is my favourite one, but is getting old now.. .)

I have two bomb fuzes that burn for 60 minutes each...
60
----------------------------------

60
---------------------------------- (b)

( this is supposed to show the fuzes, with the time they would burn if you lit one end of them - it's easier on a whiteboard... )

the rate of burning of the fuzes isn't constant - so might burn 90% of its length in 10 minutes, and the other 10% in the remaining 50 minutes.

The rate of burning isn't the same for each fuze.

Use these fuzes to time me 45 minutes exactly.

• spod wrote:

I thought it might be interesting to see what sort of interview questions people ask / are asked these days. I've been in ms for a while now so it's been a long time since i've experienced dev interviews anywhere else.

Here it's many many one hour sessions with different devs / dev leads etc, and the interviews are almost entirely technical -  whiteboarding algorithms / designs etc...

As this is a dev forum, i thought i'd post a couple of the questions i ask when interviewing ( or rather asked up until now  ) - so please post yours - these things are always fun to try without the interview pressure i think

apologies for the length...these are normally face-to-face things so take a bit of explaining...( hopefully i've done ok? let me know if not )

----
( pretty much all ms interviews are stated in c, but an answer in any language would be ok in an interview... )

Given an array of ints 'a' that's sorted, write a function with the following prototype:

Node * CreateTree( int * a, int start, int end );

which takes the array and inserts it into a binary search tree so that the tree ends up balanced.

For example given a = 1, 3, 5, 6, 7, 9

you would call CreateTree( a, 0, 5 ); and expect to get something equivalent to ...

5
3   7
1    6  9

Node is just a basic tree node, and the function returns a pointer to the root node of the created tree.

----
( i sometimes ask a puzzle / non-cs question..this is my favourite one, but is getting old now.. .)

I have two bomb fuzes that burn for 60 minutes each...
60
----------------------------------

60
---------------------------------- (b)

( this is supposed to show the fuzes, with the time they would burn if you lit one end of them - it's easier on a whiteboard... )

the rate of burning of the fuzes isn't constant - so might burn 90% of its length in 10 minutes, and the other 10% in the remaining 50 minutes.

The rate of burning isn't the same for each fuze.

Use these fuzes to time me 45 minutes exactly.

I think the best question I got asked in a Microsoft interview that wasn't technical was the famous "how would you count the number of gas stations in the world?"

Questions that let the interviewers see how you go about solving a non-obvious problem are priceless.

• I've got a page on my web site that covers my 'standard' interview for a VB position. It's a little dated now for interviews that include .NET or Web development so I'll add a few in as needed.

http://www15.brinkster.com/vbnotebook/VBInterview.asp

I don't care for 'math teaser'questions in interviews, either giving them or getting them, probably because I'm not that good at them. I prefer tough, open ended, questions on related technical subjects that give some a feel for how much you know about a particular topic or are you just a good BS'er. Ones like this that I asked recently in interviews at work (that aren't on my web page) included:

1. In SQL Server T-SQL how would you build a stored procedure that had to have optional parameters for the SELECT, WHERE, and ORDER BY clauses?

2. In VB6, you have common code that has to be implemented in every text box. How would you implement this?

• I'm probably unusual in that I love the 'impossible questions'. I really enjoy logic questions as well, but impossible questions (how many gas station in the world, how many piano tuners in the world, how many marbles to fill a 747) really get my brain going. I get far too animated for my own good

• Here are a few questions I was asked a few months ago, not for my current position however:

1. What is the difference between Authentication and Authorization in Asp.Net.

2. What is the difference between Polymorphism and Inheritance.

3. Explain what connection pooling is in SQL.

4. What is the difference between a Union and Join in SQL.

5. Explain a scenario where you would use ByRef instead of ByVal.

6. What is the difference between .Net Remoting and Web Services, and when would you use one over the other.

7. What would you use in place of a public variable in Asp.Net and explain why.

Those are a few that came to mind. I will edit the post as I think of more.

~ Knute

• spod wrote:

I have two bomb fuzes that burn for 60 minutes each...
60
----------------------------------

60
---------------------------------- (b)

the rate of burning of the fuzes isn't constant - so might burn 90% of its length in 10 minutes, and the other 10% in the remaining 50 minutes.

The rate of burning isn't the same for each fuze.

Use these fuzes to time me 45 minutes exactly.

I might be making a fool of myself but is that even possible to work out? If both fuses don't burn at a constant speed it is impossible to determine 45min's. If you measured the rate of B using the fact that A burns 90% in 10min's that still doesn't work because B could change rates and therefore would throw off your measurements. You could wait till A has burned 98% but then it is less than accurate... Is this to test someone's thinking? (Clearly I would not do well at Microsoft

• Knute wrote:
Here are a few questions I was asked a few months ago, not for my current position however:

1. What is the difference between Authentication and Authorization in Asp.Net.

2. What is the difference between Polymorphism and Inheritance.

3. Explain what connection pooling is in SQL.

4. What is the difference between a Union and Join in SQL.

5. Explain a scenario where you would use ByRef instead of ByVal.

6. What is the difference between .Net Remoting and Web Services, and when would you use one over the other.

7. What would you use in place of a public variable in Asp.Net and explain why.

Those are a few that came to mind. I will edit the post as I think of more.

~ Knute

These are okay screening questions testing to see if a candidate has a minimum level of knowledge to do the job. I try to question at a higher level: do you have the skills and disposition to be effective in the role I want you for.

Some examples:

We have an RS/6000 running DB/2. We need to combine that data with data residing on our SQL Servers. The data is used in a reporting application build on Access 2003. How would you design a system that allowed this to work with minimum execution time?

I'm really looking for two things: what questions do you ask and what does your design look like.

Another one: We need to develop an application that will accept electronic payments from our clients and will post these payments to both our accounting and project management system. You have 30-days and \$200,000 to get the system in place. What do you do?

Here I'm more interested in the questions you ask than what you design.

A final one: You have a bug an application you are writing. You've checked the on-line documentation but the suggested fix doesn't help. Your team mates need you to complete this bit of the program within the next 24 hours or the project is in real trouble. What do you do?

If the applicant say "go have a beer and start surfing the help wanted ads" (yes, I did have somebody jokingly answer that), I'm very tempted to tell them right then and there that that's exactly what they should go do. Immediately.

• The rope burning one's a great one. It's one that isn't commonly used in interviews because it's overly difficult.

A better one is:

You have 2 buckets, one of 5 litres (I'm Canadian, if you're American use Imperial instead), one of 3 litres. You must measure out exactly 7 litres.

It's (personally) one of my favourites because it illustrates the core of logic puzzles (though the pirates and gold one is good too).

The problem to the fuses is interesting. You need to gather data which is "impossible" to get by normal means.

Some of the options you might generate in the interview would be to bend it in half and light in the middle (which doesn't actually mean anything), to create an X (which would help if they were all of the same burn rate) and to 'get creative'.

One 'get creative' way is to light both ends of one fuse at once. The result, of course, will be that it burns up in 30 minutes (they'll each traverse 30 minutes worth of fuse).

That solves half our puzzle, now we just need to figure out how to get the remaining 15 minutes. To be honest that part stumped me, so I ended up buying "How to Move Mount Fuji" just to get the answer (I highly recommend this book if you plan on working for Microsoft, not just because of puzzle answers but, more importantly, because it gives you a lot of the psychology behind hiring... If you can't afford it, at least read this link by ex-MS'er Joel Spolsky: http://www.joelonsoftware.com/printerFriendly/articles/fog0000000073.html).

...

Sorry, lost my train of thought. Oh yeah, the last bit was so simple I smacked myself.

Light 3 ends of the fuses. The first two will meet at exactly 30 minutes. When they meet light the remaining end. Because Fuse B has already travelled 30 minutes, the next 2 will meet halfway: 15 minutes, fora  total of 45 minutes.

Most of these puzzles (the time / weight ones) are focussed on figuring out how to get the difference between 2 sums. Once you do that you're set. You'll often need to abandon assumptions and generate a lot of options in order to figure this out. That's what Microsoft interviewers want. They want ot hear you think, even if you don't get the answer or don't get the right one.

• I was asked this question once at an interview...

You are in a small rowing boat which is floating in a pond. You pick up a brick which is also in the boat, and throw it over the side, into the water.  Question:  What happens to the level of the water in the pond, and why?

It wasn't for an IT job, but is still kinda fun!

• Yeah, that's one that's fairly heavily debated as well. The core is water displacement. The object type is also important. If the object sinks (a brick), then the water level falls because it isn't displacing water in an amount equal to it's weight, it's displacing it in an amount equal to it's size (much smaller).

If it was something else like a ... dunno, trunk or something, then it would displace the same amount of water as it did in the boat, so the water level would be identical.

I like those questions too

My next favourite are the impossible math ones:

There are 5 jars full of beans. Each bean weighs 10 grams, except for the poison beans (all in one jar), which weigh 9 grams.

Weighing only once, and only using the scale how do you determine which jar has poisonous beans?

• The bridge one's one of my favourites as well. You're right about it's applications to CS.

17 minutes:

1 & 2 cross: 2 minutes
2 returns: 4 minutes
5 & 10 cross: 14 minutes
1 returns: 15 minutes
1 & 2 cross: 17 minutes

The cars one I haven't heard before and I'll need to think about (both becasue I'm not pressed for time like in an interview and because I'm about to turn a DVD on with the family).

As far as interviews, I see 2 decent reasons for candidates to at leat get one or two such questions:

1. It really does show the way someone thinks. Obviously if someone slouches over or can't generate ideas it's a good indication of a No Hire.
2. Corporate Culture.
It's a really great 'bonding' and relational thing. Everyone's been through it, so I'm sure there's a bit of "so, what questoin did you get?" type thing that happens. Plus, if you get a really good one you can share it with some of the puzzlers that work at Microsoft who enjoy really good puzzles

That's my take on it. That said, when I get my interview you guys are free to NOT give me any. I'm sure I'll fit in just fine in spite of that

• spod wrote:
two cars drop from an plane with parachutes attached. The cars drop on to a railway track like this ( side view ), with the parachutes dropping behind them

------PA---------PB----------

where - represents the track
P represents a parachute
A, B represent the cars ( facing to the right )

the track is assumed to go on infinitely in both directions.

You have a computer with the following instructions:

number: defines a label which can prefix any command
Goto label - jumps to a label. label: can be any characters
IF ON PARACHUTE - checks if the car is currently on a parachute - and executes the single following instruction if so.
MOVE LEFT - moves the car one foot to the left
MOVE RIGHT - moves the car one foot to the right.
STOP stops the car.

So an example of a valid program would be

1: MOVE RIGHT
IF ON PARACHUTE
STOP
MOVE RIGHT
GOTO 1

Both cars must execute the same program, and must start executing the program at the same time. each instruction takes 1 unit of time to execute ( so the programs are clock-synchronised)

Write a program that makes the cars collide.

EDIT: u don't know how far the cars are apart when they land...

Are the parachutes attached or dettached after landing?

• Yeah - i like these types off question too. i wouldn't have a clue on the boat one though...

In general i think the puzzle type questions are a bit too arbitrary for an interview, so i've kinda stopped using them - except when i run out of other things to ask

The reason i like the fuse one is that it's somewhat cs related. its a bit of a stretch - but what u r doing is recursive decomposition: when you've solved the 30 minutes problem, you've got another problem exactly the same to solve to get the remaining 15 minutes.

Here's a couple of others that are old but kinda cs related,a nd are fun if u've never seen them ( most have though i imagine? )...

----
4 people have to cross a bridge. One takes 10 minutes to cross, one 5 minutes , one 2 minutes and the last person 1 minute. Only two people can be on the bridge at one time. It is dark and there is one torch. It is impossible to cross the bridge without the torch. What's the shortest time it takes the four people to get from one side to the other.

For example, call the people 10, 5, 2 and 1 then one way is:

1 and 2 cross ( 2 minutes )
1 comes back with the torch( 3 minutes )
1 and 10 cross ( 13 minutes )
1 comes back with the torch( 14 minutes )
1 and 5 cross ( 19 minutes )

can you do better than 19 minutes?

----
two cars drop from an plane with parachutes attached. The cars drop on to a railway track like this ( side view ), with the parachutes dropping behind them

------PA---------PB----------

where - represents the track
P represents a parachute
A, B represent the cars ( facing to the right )

the track is assumed to go on infinitely in both directions.

You have a computer with the following instructions:

number: defines a label which can prefix any command
Goto label - jumps to a label. label: can be any characters
IF ON PARACHUTE - checks if the car is currently on a parachute - and executes the single following instruction if so.
MOVE LEFT - moves the car one foot to the left
MOVE RIGHT - moves the car one foot to the right.
STOP stops the car.

So an example of a valid program would be

1: MOVE RIGHT
IF ON PARACHUTE
STOP
MOVE RIGHT
GOTO 1

Both cars must execute the same program, and must start executing the program at the same time. each instruction takes 1 unit of time to execute ( so the programs are clock-synchronised)

Write a program that makes the cars collide.

EDIT: u don't know how far the cars are apart when they land...

EDIT again ( thanks manip ). The parachutes detach from the cars on landing and don't move from then on.

• spod wrote:
Both cars must execute the same program, and must start executing the program at the same time. each instruction takes 1 unit of time to execute ( so the programs are clock-synchronised)

Write a program that makes the cars collide.

1: MOVE RIGHT
IF ON PARACHUTE
GOTO 2
MOVE RIGHT
IF ON PARACHUTE
GOTO 2
MOVE LEFT
GOTO 1

2: MOVE RIGHT
GOTO 2

John.

• Or with a slight optimisation..

1: MOVE RIGHT
IF ON PARACHUTE
GOTO 3

2: MOVE RIGHT
IF ON PARACHUTE
GOTO 3
MOVE RIGHT
MOVE LEFT
GOTO 2

3: MOVE RIGHT
GOTO 3

John.

• Bah! This one is better..

1: MOVE RIGHT
IF ON PARACHUTE
GOTO 2
MOVE RIGHT
MOVE LEFT
GOTO 1

2: MOVE RIGHT
GOTO 2

John.

• You'd think I'd have something better to do on Sunday evening.. anyway, there's something about moving to a space to the right and not testing it that bothers me. I prefer this algorithm:

1: MOVE RIGHT
IF ON PARACHUTE
GOTO 2
MOVE LEFT
MOVE RIGHT
GOTO 1

2: MOVE RIGHT
GOTO 2

The cars are likely to collide sooner with this algorithm anyway. I'm leaving it alone now. I promise..

John.

• OK, I tried to leave this alone, but I'm forced out of frustration to break my promise. It's a disease.

Firstly, it's not explicit in the instructions that STOP will terminate the program, although based on the example I assume this was implied. This is likely omitted since the STOP instruction seems to be nothing more than a red-herring. But I assume it will terminate the program rather than pause the car for one unit of time. It would be nice if STOP could be used to vary the rate of movement of the car and there was some method for determining efficiency (i.e. optimise for fast code, optimise for small code, optimise for car conservation of energy, etc.). Having stats of typical distances that cars might be separated when they land could help you come up with algorithms that were likely to be more efficient in the greatest proportion of likely cases.

Secondly, the language specification in the question states that each instruction takes one unit of time to execute. It states that the "number:" syntax is an instruction, so it will take one unit of time to evaluate a labelled statement prior to executing the statement it labels. This is bogus, so I ignored it when coming up with my last solution assuming it was a mistake in the specification. I also ignored the rule that states the "IF ON PARACHUTE" 'instruction' takes one unit of time to execute. Mostly I ignored this because it's not likely to be relevant in any real application (unless 'searching' to determine 'on parachute' required slow machinery perhaps). Anyway, I pretty much only considered that 'moving' would take time, however with respect to the rules as stated, this program will also work (and is more 'efficient', although no parameters for determining efficiency have been given it is typically safe to assume that acceleration has a cost. It is however less intuitive code):

1: MOVE RIGHT
IF ON PARACHUTE
GOTO 2
GOTO 1

2: MOVE RIGHT
GOTO 2

Thirdly, I have also assumed that the parachute will only cover 'one foot' of ground evenly aligned with the 'points' on the track that the car can move to, such that a distance of one foot could be considered as a point on a line, and that if only one parachute existed on the line and 'on parachute' was true at point x then 'on parachute' was not true at point x-1 or x+1 and that each car was separated by a number of feet that was an integer. I also assume that IF ON PARACHUTE will return true regardless of 'whose' parachute is being tested, and that the parachute will be left at the same point that the car lands, such that 'on parachute' would be true from the first instruction. So like this if the cars land at P(3) and P(8) for example:

-|--|--|--|--|--|--|-
-3--4--5--6--7--8--9-
-P--------------P----

If the parachute might cover more distance on the track than one point, perhaps like this:

-|--|--|--|--|--|--|-
-3--4--5--6--7--8--9-
-[ PA ]-----[  PB  ]-

Then as long as there is guaranteed to be at least one point at which a car will test for 'on parachute' where the result will be false between parachutes and the cars are 'on parachute' when the program commences, then you'd need a program like this:

1: MOVE RIGHT
IF ON PARACHUTE
GOTO 1

2: MOVE RIGHT
IF ON PARACHUTE
GOTO 3
GOTO 2

3: MOVE RIGHT
GOTO 3

If it is possible that the cars land next to each other such that their parachutes overlap then they will move in the same direction at the same rate infinitely looking for the beginning of the next parachute. If however the absolute possible distance that a parachute might cover is known then a program can be written to accommodate the possibility of overlapping parachutes. If not, then I don't know how to solve the problem.

Assuming the known maximum distance that a parachute could cover was X feet (points on the line), then the maximum distance a car could travel from its landing position in any direction before 'on parachute' was false at least once would be 2X feet. I guess implicitly we are relying on 'Newtonian' concepts of time and motion, which are crude but likely to work well enough for our example (if not I don't want to play anymore!). The corresponding maximum amount of 'instruction' time until a car was definitely not on a parachute would be 4X-1, and the minimum time is 3 (based on the first part of the algorithm that moves the car right until it is not on a parachute using the timings as originally specified). In which case the following program will work for x=3, assuming cars at the same point at the same time constitutes collision (hey, it's worth stating, a collision might require an overlap, of might happen earlier (i.e. if the cars have width), but since we consider cars as at a point, even thought they are likely to have something greater than infinitely small width, 'at the same point' seems fair enough):

1: MOVE RIGHT
IF ON PARACHUTE
GOTO 1

MOVE LEFT
MOVE RIGHT
MOVE LEFT
MOVE RIGHT
MOVE LEFT
MOVE RIGHT
MOVE LEFT
MOVE RIGHT
MOVE LEFT
MOVE RIGHT
MOVE LEFT
MOVE RIGHT

2: MOVE RIGHT
IF ON PARACHUTE
GOTO 3
GOTO 2

3: MOVE RIGHT
GOTO 3

If 'on parachute' is not true when the program begins executing then the direction in which this can be assumed to be true will need to be specified or else the distance in which it is possible for it to be true will need to be known in addition to this distance being less than any possible distance that the cars could be apart from each other when they land.

If 'on parachute' is only true for the parachute dropped by the car doing the testing (i.e. the parachute that 'belongs' to that car) then I don't know how to solve the problem. If 'on parachute' is true for any parachute then you would have a problem if there was a parachute on the track that was not dropped by either of the two cars.

If it was exceedingly unlikely, but still possible that 'on parachute' was false at the start of the program and the direction of the parachute was unknown then the following program would still be effective in the face of a failure by exactly one car (assuming parachutes are at a point):

IF ON PARACHUTE
GOTO 1
STOP

1: MOVE RIGHT
IF ON PARACHUTE
GOTO 2
GOTO 1

2: MOVE RIGHT
GOTO 2

Or in the same situation this program would cause the cars to collide after less time:

IF ON PARACHUTE
GOTO 1
GOTO 3

1: MOVE RIGHT
IF ON PARACHUTE
GOTO 2
GOTO 1

2: MOVE RIGHT
GOTO 2

3: MOVE LEFT
GOTO 3

That was fun. I'm sure it was worthwhile..

John.