Microsoft interview questions

[z-component]

These three riddles appeared during a certain Microsoft job interview.
The interviewer would watch how the interviewee responds to these riddles. Even if they didn't get the answer, the interviewer wants to see how they think as they explain the steps they're making to TRY to solve it. Some might be too easy to solve directly! See if you can solve these.

Riddle #1:

1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
3 1 2 2 1 1

What's the pattern?


Riddle #2:

You have four people at a bridge... one HAS to carry a flashlight as they cross, but only two can cross at a time. And nobody can go alone.

It only takes one 1 minute to cross. Another takes 2 minutes. Another, 5. And the last, 10.

If the person who takes 1 minute goes with the person who takes 10... it automatically takes 10 minutes.

How many minutes will it take them all to cross.. at the quickest?

Riddle #3:

You have two fuses... they burn at different rates and not at steady rates. BUT! They only burn for one hour. One could burn the entire way except one inch within one minute, then spend the last 59 on that last inch, for example.

You also have to use this to somehow time 45 minutes exactly. How would you do it?

 

[Icebreaker]

1

1 3 1 1 2 2 2 1

2

18

3

Ignite string A on both ends, string b on one end. When string A burns out, ignite string B on both ends.

 

[TenaliRaman]

2.
17

-- AI

 

[xJuggleboy]

Where are you getting your answer of 17 or 18 for question 2??

This is my answer and reason...

19 Min

1&10 cross 1 comes back 11min, 5&1 cross 1 comes back 6 min, 2&1 2 min = 19 min

How can it be done faster?

 

[neurocomp2003]

how does one get the pattern for 1?

 

[20questions]

Riddle #2:

You have four people at a bridge... one HAS to carry a flashlight as they cross, but only two can cross at a time. And nobody can go alone.

It only takes one 1 minute to cross. Another takes 2 minutes. Another, 5. And the last, 10.

If the person who takes 1 minute goes with the person who takes 10... it automatically takes 10 minutes.

How many minutes will it take them all to cross.. at the quickest?

12 minutes. 10 & 5 cross, =10 minutes then 2 & 1 cross =2 minutes

 

[TenaliRaman]

<snip>answer</snip>

Oh ofcourse, they throw the flashlight from one end to the other, how in the world i didnt think of this

How can it be done faster?

max(1,2)+min(1,2)+max(5,10)+min(2,5,10)+max(1,2)=17
Sorry if i am cryptic, but this was supposed to be a brain teaser

-- AI

 

[20questions]

Oh ofcourse, they throw the flashlight from one end to the other, how in the world i didnt think of this


max(1,2)+min(1,2)+max(5,10)+min(2,5,10)+max(1,2)=17
Sorry if i am cryptic, but this was supposed to be a brain teaser

-- AI

Why would you assume there is only one flashlight? Post said A flashlight not THE flashlight. If not two would have to cross and then two cross back (if one can't cross alone one shouldn't be able to cross back alone) and all 4 would never all get across

 

[TenaliRaman]

Why would you assume there is only one flashlight? Post said A flashlight not THE flashlight.

Point taken and understood. But then it wouldn't be much of a brain teaser would it be?

If not two would have to cross and then two cross back (if one can't cross alone one shouldn't be able to cross back alone) and all 4 would never all get across

quoting the question,
Only two can cross at a time
I believe this means, "at the max only two people can cross at one time" and not "exactly two people should cross the bridge at any instant".

-- AI

 

[neurocomp2003]

very clever tenai...but then by your logic..it would only take 10 mins.

i guess it all depends on your take of "noone can go alone"

oh and could you please tell me or hint to solve 1...

 

[TenaliRaman]

very clever tenai...but then by your logic..it would only take 10 mins.

Really

oh and could you please tell me or hint to solve 1...

Google for Conway sequence, its one of the well known sequence and according to one paper (which is not freely available unfortunately) this sequence has many interesting properties.

-- AI

 

[mattmns]

Tenali, are you saying this?

The 1 minute person has the flashlight. 1 min + 10 min cross, then 1 min + 5 min cross, then 1 min + 2min cross. = 17 mins. Now when I say 1 min + 5 min cross, I mean that 1 min is coming back to the start while 5 min is going to the end.

Probably easier to see in this image: http://img11.imageshack.us/img11/28/msquestion3oa.gif

 

[nnnnnnnn]

There is no trick to breaking the rules- two people max, both same way, one flashlight. The trick is to illiminate the bad affects of the 10 and 5 person- think of the farmer, the fox, the chicken, and the egg riddle if you know it...

3) light one rope at both ends

 

[TenaliRaman]

Tenali, are you saying this?
<snip>
Probably easier to see in this image: http://img11.imageshack.us/img11/28/msquestion3oa.gif

Err nope,
(warning : spoiler)

Assume a,b,c,d are on the left side.
Objective -> a,b,c,d to go to right side in minimum time
Constraints -> Just one flashligh, flashlight necessary to cross and bridge can balance at the max 2 people
a(1 min,flashlight),b(2 min) go right --> 2 mins
a(1 min,flashlight) goes left --> 1 mins
c(5 min,flashlight),d(10 min) go right -> 10 mins
b(2 min,flashlight) goes left --> 2 mins
a(1 min,flashlight),b(2 min) go right --> 2 mins
Total -> 2+1+10+2+2 = 17 mins


-- AI

 

[neurocomp2003]

this was my solution..i'm not going to white it because its a matter of the way you interpret the question. 10min carries flashlight.5+2+1+1+1=8 = 10.

 

[20questions]

Point taken and understood. But then it wouldn't be much of a brain teaser would it be?


quoting the question,
Only two can cross at a time
I believe this means, "at the max only two people can cross at one time" and not "exactly two people should cross the bridge at any instant".

-- AI

(Agreed, but it was the 'nobody one can go alone' line that, for me, ruled out someone crossing either way alone. Hmm, perhaps 'go' may be just mean 'go' and not 'come back'. Two people on the bridge at the same time, even if one's crossing leftward and one's crossing rightward may be legal to the rules as I saw them though.
The 3rd line implied to me that the faster person must walk slow to actually stay with the slower person, i.e. hand in hand.

Knowing other puzzles on this board maybe one of the crossers is named Nobody! )

 

[TenaliRaman]

(Agreed, but it was the 'nobody one can go alone' line that, for ... <snip> Knowing other puzzles on this board maybe one of the crossers is named Nobody!)

Oh well, poorly defined question, yeah probably. I guess, your solution stands good given that the concerns you have raised seem appropriate

-- AI

 

[nnnnnnnn]

I didnt notice the nobody can go alone line but if that were true the question would be impossible.

 

[mattmns]

^ Yes exactly! That is why I think one comes back, with the flashlight, while another crosses at the same time. They are not together, but they are crossing the bridge at the same time.

 

[BobG]

quoting the question,
Only two can cross at a time
I believe this means, "at the max only two people can cross at one time" and not "exactly two people should cross the bridge at any instant".

-- AI

Tenali, you solved the problem as it should have been written. You didn't read the way it was actually written closely enough.

"You have four people at a bridge... one HAS to carry a flashlight as they cross, but only two can cross at a time. And nobody can go alone."

As written, it pretty much makes the problem unsolvable unless you either have two flashlights or get to throw the only flashlight.

 

[TenaliRaman]

As written, it pretty much makes the problem unsolvable unless you either have two flashlights or get to throw the only flashlight.

Oh well, poorly defined question, yeah probably. I guess, your solution stands good given that the concerns you have raised seem appropriate

I did accept it didnt I? Though i do believe your comment came just after read the first page and prolly didnt realize there was a second page. (I have made this mistake one time too many).

-- AI

 

[neurocomp2003]

tenali you solution doesn't have two people crossing between steps 4,5

 

[TenaliRaman]

tenali you solution doesn't have two people crossing between steps 4,5

Assume a,b,c,d are on the left side.
Objective -> a,b,c,d to go to right side in minimum time
Constraints -> Just one flashligh, flashlight necessary to cross and bridge can balance at the max 2 people
<snip>

Tenali, you solved the problem as it should have been written. You didn't read the way it was actually written closely enough.

"You have four people at a bridge... one HAS to carry a flashlight as they cross, but only two can cross at a time. And nobody can go alone."

As written, it pretty much makes the problem unsolvable unless you either have two flashlights or get to throw the only flashlight.

I did accept it didnt I?

These are all quotes from previous posts.

Maybe it was not understood as to what i meant by "i did accept it" ??
I accepted that 20questions' concerns were correct and so was his answer, in which case my solution becomes null and void. Should i detail out how i am wrong and when i would have been right?

To make it clear as to what happened so far,
1. I proposed a solution
2. 20questions proposed a solution
3. 20questions convinced me how he was right, given the way the question was framed
4. I accepted his answer completely, (which means i accepted that my answer won't work the way the question was framed (maybe i should bold this statement hmm?) )
5. However, in my answer, i distinctly cleared what objectives and constraints of the problems i have taken into considerations, which shows when my solution would have worked.

-- AI
P.S -> Also in my solution, there is just one man crossing even in step 2 and not just in step 4.

P.S2 -> I WAS WRONG! (This is for those who are expecting it!)

 

[chronon]

Other versions of this puzzle (e.g. here - there is nothing new under the sun), don't have the "no one can go alone" restriction, and without that TenaliRaman is correct. With it I would say that the problem is impossible. Maybe Microsoft decided that that was what they wanted, like the interviewee being asked into the room and told to sit down, but finding that there isn't a chair (anywhere). I can well believe that Microsoft might stress out their candidates in that way

 

[AKG]

These three riddles appeared during a certain Microsoft job interview.
The interviewer would watch how the interviewee responds to these riddles. Even if they didn't get the answer, the interviewer wants to see how they think as they explain the steps they're making to TRY to solve it. Some might be too easy to solve directly! See if you can solve these.

Riddle #1:

1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
3 1 2 2 1 1

What's the pattern?

This one's been on here a bunch of times. Actually, the last time I saw Microsoft riddles, they were a lot harder than these. Are you sure these are Microsoft riddles? Anyways:

1 3 1 1 2 2 2 1

Riddle #2:

You have four people at a bridge... one HAS to carry a flashlight as they cross, but only two can cross at a time. And nobody can go alone.

It only takes one 1 minute to cross. Another takes 2 minutes. Another, 5. And the last, 10.

If the person who takes 1 minute goes with the person who takes 10... it automatically takes 10 minutes.

How many minutes will it take them all to cross.. at the quickest?

First 1 and 2 go across, then 1 comes back. Then 10 and 5 go across and then 2 comes back. Then 1 and 2 go across. Total time: 2 + 1 + 10 + 2 + 2 = 17.

I have a strong feeling these aren't even Microsoft riddles. I've seen these before, some of them quite a while ago, and never thought they were from Microsoft.

Riddle #3:

You have two fuses... they burn at different rates and not at steady rates. BUT! They only burn for one hour. One could burn the entire way except one inch within one minute, then spend the last 59 on that last inch, for example.

You also have to use this to somehow time 45 minutes exactly. How would you do it?

Take fuse A and light both ends. At the same time, light only one end of fuse B. Fuse A will extinguish after precisely half an hour. At the exact time that it extinguishes, ignite the other end of fuse B. When fuse B has extinguished, exactly 45 minutes will have elapsed.

 

[AKG]

Maybe by "no one can go alone" he means "no one can go without the flashlight (or without a partner who has it)."

 

[CaptainQuaser]

It says one has to carry a flashlight, it doesn't say that everytime someone crosses they have to carry a flashlight, send 1 and 2 with the light, then followed after by 5 and 10, not carrying a flashlight.

 

[ArielGenesis]

there are 4 flash light and each one has a flash light

10 and 1 go
by the time 1 reach the end, 2 go instantly. So 10 is togather with the 2
by the time 2 reach the end, 5 go instantly. So 10 is togahter with the 5
then 5 walk slowly so that they reach the end togahter with the 10
so 10 minutes right?

 

[z-component]

The correct answer to the second riddle is found using AKG's method.

 

[Rahmuss]

Why would you assume there is only one flashlight? Post said A flashlight not THE flashlight. If not two would have to cross and then two cross back (if one can't cross alone one shouldn't be able to cross back alone) and all 4 would never all get across

1. You're right that it can't be done if they can't throw the flashlight across unless they meant just that at least two people needed to cross. If that's the case, then you wouldn't need to throw the flashlight, and it would take you 17 minutes.

2. I figure that since it doesn't specify, have person A carry person D across since person A can cross in one minute you have only taken one minute. Then throw the flashlight across to person B who takes two minutes to carry person C across. You have a total of 3 minutes to cross. Because person A doesn't "[go] with" person D, they CARRY person D, and person B CARRIES person C. I'm sure this isn't what they were referring to; but hey, I think it works.

 

[Rahmuss]

Err nope,
(warning : spoiler)

Assume a,b,c,d are on the left side.
Objective -> a,b,c,d to go to right side in minimum time
Constraints -> Just one flashligh, flashlight necessary to cross and bridge can balance at the max 2 people
a(1 min,flashlight),b(2 min) go right --> 2 mins
a(1 min,flashlight) goes left --> 1 mins
c(5 min,flashlight),d(10 min) go right -> 10 mins
b(2 min,flashlight) goes left --> 2 mins
a(1 min,flashlight),b(2 min) go right --> 2 mins
Total -> 2+1+10+2+2 = 17 mins


-- AI

The problem is that "nobody can go alone".

 

[Rahmuss]

this was my solution..i'm not going to white it because its a matter of the way you interpret the question. 10min carries flashlight.5+2+1+1+1=8 = 10.

This is a good thought. When it says that they can't go alone does that mean that they have to be on the bridge the same time as someone else? If that's the case then I think that works out well.

 

[Rahmuss]

Really


Google for Conway sequence, its one of the well known sequence and according to one paper (which is not freely available unfortunately) this sequence has many interesting properties.

-- AI

Problem #1 is actually pretty simple. Below is a clue:

How many '1's are in line #1?

 

[Rahmuss]

Tenali, you solved the problem as it should have been written. You didn't read the way it was actually written closely enough.

"You have four people at a bridge... one HAS to carry a flashlight as they cross, but only two can cross at a time. And nobody can go alone."

As written, it pretty much makes the problem unsolvable unless you either have two flashlights or get to throw the only flashlight.

Actually, with this pointed out it seems that only one person has to carry the flashlight as they (singular person) cross. So you really only need one person to carry the flashlight as they cross. The others are free to go as they please. So let 10 and 5 start out, then after 5 minutes, let 2 go, then after 2 minutes let 1 go and finish walking with 10 (unless the name of 10 is "nobody"). Total time of 10 minutes.

 

[ArielGenesis]

1 3 1 1 2 2 2 1First 1 and 2 go across, then 1 comes back. Then 10 and 5 go across and then 2 comes back. Then 1 and 2 go across. Total time: 2 + 1 + 10 + 2 + 2 = 17.
]

"And nobody can go alone."
isn't 1 and 2 go alone when they say 'comes back'. Somehing like go back and threfore, go back alone.