|
Microsoft interview Question... (pg. 3)
|
View this Thread in Original format
| 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 ? |
|
|
| Resnick |
| ^^^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.... |
|
|
| DigiNut |
| 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. :p |
|
|
| Durafei |
| 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. :p |
OK, how about the light-bulb question the :p |
|
|
| Resnick |
| quote: | Originally posted by Durafei
OK, how about the light-bulb question the :p |
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 |
|
|
| 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) |
|
|
| Mr Game+Watch |
| 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? |
|
|
| Orbax |
| 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. |
|
|
| DigiNut |
| 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. |
|
|
| Durafei |
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? |
|
|
| Dr. Cfire |
| 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 |
|
|
| 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). |
|
|
|
|
