quote:

Originally posted by Dr. Cfire Another problem from a microsoft test: two handcars are droped randomly on a linear track. the handcars do not know their location or the location of the other handcar is. The handcars can tell how far they have moved by counting rail ties. Find a solution for the handcars to findeach other in the minimum number of steps.(they can be on either side of each other).

1) What is a "step" ?
2) Can one of the handcars just stand on one point?
3) Is the track infinite in both directions?

___________________

My Blog: durafei.blogspot.com - Last Update March 23, 2006

quote:

Originally posted by Dr. Cfire No that would not be the minimum # of drops. you would get the answer though Answer (minimum): 1) Start at the middle floor of building. (10 floors start a floor 5)-drop the bulb. Point A Now we have 2 cases: If the bulb does not break Take the # floors above you go half way up the leftover floors drop the first bulb again.-Start over at point A. If the Bulb breaks start a floor 1 and move up until the bulb breaks. This will find the answer in the minimum # of drops. It uses the divide and conquor algroithm

Actually that algorithm works, but it doesn't find the minimum number of drops. Using a slightly move clever algorithm you can get the minimum to be 19. Using a more complicated, even better algorithm produces a minimum of 14.

___________________

My Blog: durafei.blogspot.com - Last Update March 23, 2006

quote:

Originally posted by Dr. Cfire This will find the answer in the minimum # of drops. It uses the divide and conquor algroithm

i thought that too at first, but you are wrong

___________________

get font

I see your 4 Crushs and raise you 3 As The Rush Comes. - Yan from PvD's first summerstage event in '03

For the mountain climber, the intuitive proof is this:

Imagine two people making the trip, one forward and one back, both starting at 8 am on the same day. At some point, they would obviously have to meet each other. It follows that they'd still reach this same point at the same time of day if one of the trips happened a day later.

The egg drop has already been answered - you drop at floors 14, 27, 39, 50, 60, 69, 77, 85, 92, 96. As soon as one breaks, you drop from the previous floor +1 until the floor it broke -1. If you reach 96, you just go from 97 to 99, if it doesn't break at 99 you know it's 100.

That question's been posted and answered already btw.

I'll think about the pirates one on my way home. Don't quite understand the railroad one.

___________________
My party schedule:
2009-02-21 - DJ Attention @ I'm So Popular
2009-06-18 - DJ Annoying @ People Need To Know Where I'll Be
2012-11-32 - DJ Insufferable ɸ Or At Least the Stalkers I Complain About
2048-06-66 - Spastic & Whocares ¶ Although I'm Actually Flattered
9999-45-81 - Tweaker Gimp ☼ I Probably Won't Even Go To This But I Have To Make Sure I Fill Up All The Available Space Here

For the pirates one...

I suppose we're assuming that all 5 pirates are in it for themselves, and also intelligent and will make whatever decision they know will get them the most coins.

So work backwards - if we start with only pirates #4 and #5, then #4 can take all of the money since he is technically "half".

#5 doesn't want to get into this position, so if there are 3 pirates left, he should tend to agree with whatever #3 says in this case, as long as he's getting at least 1 coin.

#4, therefore, does not want to get into the above scenario since he could end up with nothing, therefore, when there are 4 people, he will tend to agree with what #2 says, as long as he's getting at least 1 coin. If you were #2 in this position, you'd offer 2 coins to #5 to make sure he agrees (because if he disagrees, he might end up with only 1 or less). And you could offer nothing to the other two pirates, because you already have half the votes.

So, #4 and #3 are definitely going to want to avoid this situation, because they get nothing, but #2 and #5 will want to be in it, so they are guaranteed to vote against you no matter what you say. All you need to do is take the votes of #3 and #4.

If there are 5 pirates, offer pirates #3 and #4 one coin each. They know they could end up with nothing if they let you get killed. Take the other 98 for yourself.

I think that's the answer, but I might be making the wrong assumptions. I haven't really been taking into account "pacts" or any such things... just assuming it's every man for himself and that they all know what's best for them (they are pirates, after all).

___________________
My party schedule:
2009-02-21 - DJ Attention @ I'm So Popular
2009-06-18 - DJ Annoying @ People Need To Know Where I'll Be
2012-11-32 - DJ Insufferable ɸ Or At Least the Stalkers I Complain About
2048-06-66 - Spastic & Whocares ¶ Although I'm Actually Flattered
9999-45-81 - Tweaker Gimp ☼ I Probably Won't Even Go To This But I Have To Make Sure I Fill Up All The Available Space Here

quote:

Originally posted by DigiNut For the pirates one... I suppose we're assuming that all 5 pirates are in it for themselves, and also intelligent and will make whatever decision they know will get them the most coins. So work backwards - if we start with only pirates #4 and #5, then #4 can take all of the money since he is technically "half". #5 doesn't want to get into this position, so if there are 3 pirates left, he should tend to agree with whatever #3 says in this case, as long as he's getting at least 1 coin. #4, therefore, does not want to get into the above scenario since he could end up with nothing, therefore, when there are 4 people, he will tend to agree with what #2 says, as long as he's getting at least 1 coin. If you were #2 in this position, you'd offer 2 coins to #5 to make sure he agrees (because if he disagrees, he might end up with only 1 or less). And you could offer nothing to the other two pirates, because you already have half the votes. So, #4 and #3 are definitely going to want to avoid this situation, because they get nothing, but #2 and #5 will want to be in it, so they are guaranteed to vote against you no matter what you say. All you need to do is take the votes of #3 and #4. If there are 5 pirates, offer pirates #3 and #4 one coin each. They know they could end up with nothing if they let you get killed. Take the other 98 for yourself. I think that's the answer, but I might be making the wrong assumptions. I haven't really been taking into account "pacts" or any such things... just assuming it's every man for himself and that they all know what's best for them (they are pirates, after all).

Correct reasoning.. but somewhere along the lines of the proof you made a mistake

___________________

My Blog: durafei.blogspot.com - Last Update March 23, 2006

quote:

Originally posted by Durafei Correct reasoning.. but somewhere along the lines of the proof you made a mistake

Really? I can't see that... it's understood that #1 is you (most senior) and #5 is least, right?

Where's the error?

___________________
My party schedule:
2009-02-21 - DJ Attention @ I'm So Popular
2009-06-18 - DJ Annoying @ People Need To Know Where I'll Be
2012-11-32 - DJ Insufferable ɸ Or At Least the Stalkers I Complain About
2048-06-66 - Spastic & Whocares ¶ Although I'm Actually Flattered
9999-45-81 - Tweaker Gimp ☼ I Probably Won't Even Go To This But I Have To Make Sure I Fill Up All The Available Space Here

quote:

Originally posted by Durafei 1) What is a "step" ? 2) Can one of the handcars just stand on one point? 3) Is the track infinite in both directions?

1) a step is considered a movement of one or both cars in a single direction one square.

Square is considered a set distance defined by the distance between the rail road ties.

-------------------------------
|<-square->| | | | |
-------------------------------

2) Yes one of the handcars can not move. You can control the two handcars seprartly.

3)
The tack is of infinate length

and what exactly is a Microsoft Interview?

___________________
sempre contra a corrente do jogo