TranceAddict Forums (www.tranceaddict.com/forums)
- Chill Out Room
-- Microsoft interview Question...
Pages (2): « 1 [2]

^^^simple, they all got drunk the third night, forgot that they werent allowed to communicate and just rolled up all the green hairs in a rug and threw them off a cliff....

quote:

Originally posted by Durafei I'll repost the question, make it more clear: There is a village.. People can see each other, but they cannot communicate and there are no mirrors in the village. One night everybody has the same dream: At least one person in the village(could be anyone including you) got his hair painted green, and as soon as that person finds out that his hair is green he MUST leave the village. 1st morning: Everyone gathers, looks at each other, and everyone goes home. 2nd morning: Everyone gathers, looks at each other, and everyone goes home. 3rd morning: Everyone gathers, looks at each other, and everyone who has hair painted leaves the village, others go home. what happened ?

I know the answer! I'll answer it after class though, no time to type it all out right now.

quote:

Originally posted by DigiNut I know the answer! I'll answer it after class though, no time to type it all out right now.

OK, how about the light-bulb question the

quote:

Originally posted by Durafei OK, how about the light-bulb question the

we already answered this a few weeks ago (and by we, i mean digi) but its like 14 or something, i cant remember, but ill leave solution so others can try it

uh, since they aren't allowed to communicate (verbally, facial expressions, gestures, body postures), i'm assuming there is no practical way for the painted hair people to ever know if their hair became green. stupid question. :\ (unless, like before, there is a bog)

quote:

Originally posted by Durafei OK. Here is a cool question from Microsoft Interview. There is a village.. People can see each other, but they cannot communicate and there are no mirrors in the village. One night everybody has the same dream: At least one person in the village(could be anyone including you) got his hair painted green, and as soon as that person finds out that his hair is green he MUST leave the village. 1st morning: nothing happens. 2nd morning: nothing happens 3rd morning: everyone whos hair was painted leaves the village. what happened ? Here is one more: You have two light bulbs and 100 storey building. You must determine the minimal floor such that if you drop the light bulb from that floor it breaks. Once you break a bulb, it can't be reused. Question: What's the smallest number of drops required in the WORST case to determine the minimal floor.

Well, you'd start on the first floor, and keep on dropping the bulb till it finally breaks, and that floor will be # of times you needed to drop?

i already answered this. Id go to the owner of the building and tell him Ill give him 2 lightbulbs if he tells me how tall his building is.

quote:

Originally posted by smoorhs uh, since they aren't allowed to communicate (verbally, facial expressions, gestures, body postures), i'm assuming there is no practical way for the painted hair people to ever know if their hair became green. stupid question. :\ (unless, like before, there is a bog)

Nope. Here's the answer.

You know that at least 1 person has green hair. If you're gathered together, and you see nobody else with green hair, you know that person is you. Also, if you see just 1 other person with green hair and he doesn't leave, you know that you're the other person (otherwise he would have left because he saw no other green-hairs).

So on the first day, nobody leaves. When everyone goes home, they know that there has to be at least 2 people with green hair.

On the second day, everybody knows that there are at least 2 people with green hair. So if you had green hair, and you saw 2 other people with green hair not saying anything, you'd know that there have to be at least 3 people.

3rd day comes. There are 3 people with green hair. Everybody who has green hair knows that at least 3 people have green hair, they see only 2 other people with green hair, so they know that they are the other one. They all leave.

Here is two more problems, both a bit complicated.

A philosopher wakes up one morning and decides to climb a mountain. He starts climbing at 8AM. He climbs at a variable speed. When he reaches the top, he rests there for a few days and finally a few days later starts descent at 8AM. He goes down the exact same path he went up. He travels at variable speed, generally faster than his "up" speed.

Prove that there is a point on his path, which he passed through at the same time of day during his trip up and down.

The rigorous proof is probably very complicated, but there is a very simple and intuitive proof to this.

Another problem. There are 5 pirates and 100 golden coins. The senior pirate proposes division of money. If at least half the pirates(including senior) agree, the money is divided and pirates go home. Otherwise the senior pirate is killed and the next most senior pirate proposes division. Process is repeated until one plan is accepted.

You are the MOST senior pirate and propose division first. What do you propose?

quote:

Originally posted by Mr Game+Watch Well, you'd start on the first floor, and keep on dropping the bulb till it finally breaks, and that floor will be # of times you needed to drop?

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

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).

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?

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.

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

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.

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).

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

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?

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?

Powered by: vBulletin
Copyright © 2000-2021, Jelsoft Enterprises Ltd.